前言

Java现在的市场占用率有目共睹，为(ying)了(fu)学(mian)好(shi)Java，Java的一些底层知识不得不了解，与其需要的时候东一锤，西一刀到处找，这里总结一下，以备不时之需。相关图片和详细资料都可以在参考文章下的源文章中找到。

HashMap

HashMap.png

HashMap是数组和链表的组合。HashMap的高性能依赖数组，链表是为了处理哈希冲突。HashMap通过对Key的hashCode()进行哈希扰乱(hash())，进一步与数组lenght-1进行&运算，最终通过indexFor()决定具体的地址。

常规状态下，HashMap的寻址时间复杂度为O(1)。可是哈希函数不能保证计算出来的地址是唯一的，也就是说，会存在多个不同的Key，指向同一个地址，这被成为哈希冲突(碰撞)。这时通过链表将指向同位置的数据链接，对于这个位置的数据，通过Key的equals()进行匹配，寻址时间复杂度可以认为为O(n)，n为该位置链表长度。所以，HashMap中链表越少越短，其性能越高。

HashMap存在容量(Capacity，默认16)与负载因子(loadFactor，默认0.75)，容量指数组的长度，也是HashMap中允许存放的数据量，负载因子指数据占比。负载因子的存在是为了减少哈希冲突，我们可以理解为，数据量越接近最大负载，越容易发生哈希碰撞。当数据占位比达到负载上限，需要进行扩容。每次扩容即将当前容量翻倍，这样可以保证数据在搬运到数组中时，hash与length-1进行与运算出来的下标保持不变。所以，HashMap的容量永远是2的指数幂。

线程不安全，在JDK1.7中，多线程同时扩容时，执行到resize中的transfer方法重新散列table，散列元素为从头插入(头插法)，最终形成环形链表，下一次调用get方法或put方法遍历这个Hash数组的位置的链表，如果元素key不存在，就在这个循环链表中无限循环遍历了，因为不存在尾结点的指针域为null停止循环遍历了。在JDK1.8中，通过尾插法，在resize时保持原来链表元素的顺序，避免循环链表的bug。HashMap线程不安全的问题还有很多，比如多线程resize时，put会出现原来数据节点的丢失；一个线程通过迭代器遍历或删除时，另一个线程修改了HashMap，则modCount++，造成迭代器中的expectedModCount与HashMap中的modCount不一样，抛出ConcurrentModificationException异常等等原因。所以，HashMap就是设计给单线程作业的，多线程要么二次通过并发封装，要么使用HashTable或ConCurrentHashMap等线程安全的集合。

JDK1.8优化HashMap，转链表为红黑树。无论什么样的哈希函数，都无法避免哈希碰撞的问题，为此JDK1.8在JDK1.7的基础上对原来的链表结构进行了优化。当链表长度超过8时，将链表转化为红黑树，红黑树的时间复杂度为O(lgn)，可以有效提升HashMap的查找性能。

HashMap put方法逻辑图(JDK1.8).png

HashMap知识点：

• 数组链表组合；
• 容量总是2的指数幂；
• 红黑树优化；
• 非线程安全；
• 无序

note*:哈希冲突解决方案，开放定址法(发生冲突，继续寻找下一块未被占用的存储地址)、再散列函数法、链地址法(数组+链表)等。

TreeMap

TreeMap基于红黑树实现，所以其增查改删的复杂度也是O(lgn)。虽然比起HashMap来说，其性能有所缺憾，但是，在类结构上，TreeMap实现了SortedMap接口，允许通过默认或者自定义的Comparator进行排序，实现有序的Map。默认的顺序与常规的List不同，不是添加顺序，而是通过Key的排列顺序排序的。TreeMap中也没有对线程安全做相关的处理，也会出现数据丢失、数据同步异常等问题，所以TreeMap也是线程不安全的。

TreeMap知识点：

• 红黑树；
• 非线程安全；
• 有序

HashTable

HashTable是比较老的Hash集合，现在基本不用了。基本实现与HashMap相同，由于保障线程安全的原因，为一些特别的方法加上了synchronized(函数级synchronized)，在多进程的情况下，同时只允许一个进程访问该方法，所以性能上稍差。由于synchronized的原因，HashTable的操作在多线程下会变成串行，数量多了就会造成阻塞，因此，由于其是直接在方法上加入synchronized控制并发，所以阻塞的概率还是比较大的。但是，因为这种大段串行竞争锁的机制，每次都是锁住整个表，HashMap能反映最近的数据更新，更保险。当前，一般是通过HashMap并发包装，或者ConcurrentHashMap在多线程下保证线程安全。
HashTable知识点：

• 线程安全；
• 串行；
• 阻塞；

ConcurrentHashMap

ConcurrentHashMap是为了兼顾性能和线程安全而存在的。ConcurrentHashMap也有HashMap，因为在数据处理上使用了相同的方法，数组-链表-[红黑树]，所以保证了效率。但是它又是线程安全的，因为它在处理的通过synchronized来保障数据同步。但是它的效率又高于HashTable，因为使用了分段锁技术，对HashMap的数据单元Node的数据结构进行了调整，并将锁细粒度化，从而实线分段锁，提升了线程安全下的性能。

JDK1.7中，通过Segment实现分段锁。ConcurrentHashMap由多个Segment组成，每个Segment下维护一个HashEntry数组，这个数组的结构就和HashMap一样了，每次操作时，锁住数据对应的Segment，实现数据安全，比起HashTable锁住整个表，效率提升了很多。

JDK1.8中，通过CAS+Synchronized来保证并发更新的安全。CAS是乐观锁的一种实现，读取无所谓，在数据更新时，通过compareAndSwap，保障数据安全。1.8中舍弃了Segment，数据结构与1.8的HashMap差不多，将锁的粒度从之前的Segment，细粒度到Node。如果当前操作的Node为NULL，CAS保证原子性，非空，synchronized上锁当前位置链表头或红黑树根节点，这样的结合方式可以有效提升并发操作效率。

ConcurrentHashMap的数据的弱一致。ConcurrentHashMap通过volatile保证Node数组对多线程的可见性，这样get时，就总能得到真实的数据。当迭代器iterator创建后，数据再发生改变，不会将操作直接作用到原始数据上，而是new新的数据，当iterator完成后再将修改作用到原始数据上，所以CocurrentHashMap不能及时的反应数据的更新。这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键，是一致性与效率之间的一种权衡。

ConcurrentHashMap知识点：

• 线程安全；
• 分段锁；
• CAS+Synchronized

参考文章

深入浅出学Java——HashMap
java遍历TreeMap元素顺序不是添加的顺序问题
JAVA学习-红黑树详解
JDK1.8 HashMap和TreeMap区别,读懂这一篇就够了
红黑树时间复杂度证明(O(lgn))
Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例
HashMap 和 HashTable 区别
Java基础之ConcurrentHashMap
JAVA7与JAVA8中的HASHMAP和CONCURRENTHASHMAP知识点总结