1.Map类图结构
2.HashMap
2.1.哈希表，线程不安全，且可以接受null的键值
2.2.初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
2.3. 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
2.4.插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
哈希冲突：若干Key的哈希值按数组大小取模后，如果落在同一个数组下标上，将组成一条Entry链，对Key的查找需要遍历Entry链上的每个元素执行equals()比较。
加载因子：为了降低哈希冲突的概率，默认当HashMap中的键值对达到数组大小的75%时，即会触发扩容。因此，如果预估容量（capacity）是100，即需要设定100/0.75＝134的初始化容量。capacity/load factor = initial capacity。
容量（capacity）：hash表中桶的数量。
负载因子（load factor）：当负载因子（size/capacity）达到默认值（HashMap和Hashtable默认的“负载极限”为0.75）时，触发rehashing。
put():当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来存储值对象。
get():当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。
HashMap使用链表来解决碰撞问题，当发生碰撞时，对象将会储存在链表的下一个节点中。HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时，它们会储存在同一个bucket位置的链表中，可通过键对象的equals()方法来找到键值对。如果链表大小超过阈值（TREEIFY_THRESHOLD=8），链表就会被改造为树形结构（红黑树）。
3.HashTable
3.1.哈希表，线程安全，不可以接受null的键值。
3.2.初始size为11，扩容：newsize = oldsize*2+1。
4.HashTable和HashMap区别
5.HashTable和ConcurrentHashMap同样是线程安全，区别是什么？
5.1.ConcurrentHashMap底层采用分段的数组+链表实现，线程安全。
5.2.通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。
5.3.Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。
5.4.有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。
5.5.段内扩容。
锁分离技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。 ConcurrentHashMap中则是一次锁住一个桶。ConcurrentHashMap默认将hash表分为16个桶，诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。
6.ConcurrentHashMap在JDK1.7和1.8中的实现不同
JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap.
6.1.1.7是ReentrantLock+Segment+HashEntry，1.8改为synchronized+CAS+HashEntry+红黑树。1.8取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
6.2.JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
6.3.原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
6.4.从原来的遍历链表O(n)，变成遍历红黑树O(logN)。
6.5.定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
CAS：CAS是compare and swap的缩写，即我们所说的比较交换。CAS是一种基于锁的操作，而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。
CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。CAS是通过无限循环来获取数据的，若果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。
7.TreeMap
7.1.初始化容量为0，内部是红黑树结构，不存在hash冲突的情况，不存在扩容的操作,key-value不可以为NULL值
7.2.可以实现元素的自动排序，默认情况下通过Key值的自然顺序进行排序。
8.HashSet
（哈希集合，无序存储对象，底层依然是map存储，以空间消耗换取时间）
兼具set的性质：互异性，无序性
网友评论