一、HashMap的介绍
1、hashMap的两个重要参数，capacity和load_factor。这两个参数，capacity表示hashMap的bucket的大小，默认值为16，load_factor是负载因子，表示hashMap中bucket的使用率，达到0.75的时候就需要扩容了。
capacity的值均为2的倍数，比如设置15，那么会自动帮你改成16，设置27会改为32，这样子做有利于做hash运算的时候找到index位置。hashMap扩容会变为原来的2倍，并且将之前的数据在进行一次hash放在新的数组中
2、hashMap中有个modCount值，是用来快速验证失败的（fast-fail）。比如在并发中，一个线程在迭代遍历hashMap，另一个线程改变了hashMap中的内容，可以立马感知出来，而不是等到迭代遍历完成了才知道。
3、hashMap的底层实现图
hashMap底层数据结构图
4、hashMap的put，①计算key的hashcode②hashcode取模运算，计算出来在table中的index③在index对应的Entry和当前的entry对比，如果entry为空，说明没有冲突直接赋值，如果有冲突，则依次遍历链表，对比key的值，如果有相同的则覆盖value，否则插入在链表最后一个
5、hashMap的get方法，①计算key的hashcode②hashcode取模运算，计算出来在table中的index③遍历table中index位置的链表，找到与key相关的那个entry取出来即可。
6、hashMap中的key很重要，一般这个key所对应的对象，需要重新其Hashcode和equals方法，hashcode是计算出该对象的hash值，减少冲突的概率，equals是计算对比当有hash冲突的时候，比如两个key的对象是否相等。
7、hashMap的key的对象，一般推荐使用String这种不变对象，为了防止在put之后，key对象没变，但是key的值改变引起hashcode改变找不到对应的value。
8、hashMap是非线程安全的，需要同步的话使用Colections.synchronizedMap(new HashMap)实现。
9、hashMap不是线程安全的，而之前的HashTable是线程安全的，但是HashTable使用了synchronized来进行同步，效率很低，目前已经不推荐使用，如果实在单线程模型下，推荐使用HashMap，如果是多线程模型下，推荐使用ConcurrentHashMap。
二、ConcurrentHashMap
HashMap不是线程安全的，HashTable使用synchronized来进行同步，当有很多线程同时读写的时候，效率非常低，因此ConcurrentHashMap就出现了，Concurrent底层使用Segment 数组（大小默认为16），然后使用reentranLock来锁定某个segment。Segment包含了一个Hashentry 数组（可以认为是一个hashMap）。底层的实现结构图如下：
concurrentHashMap底层数据结构
1、put方法加锁加在segment上，而不是ConcurrentHashMap上。
2、put会先算一个hashcode然后计算使用segment数组中的哪个segment，这时候才对segment加锁（理论上，如果hashcode分布均匀的话，可以同时多个segment读写，提高并发效率）
3、在分段找到对应的segment后，在里面再进行一次hash，然后找到对应的hashBucket，然后放进去值
ConcurrentHashMap总结：
- 1、用分离锁的设计模式来实现更深层次的并发（多个segment可以同步读写）
- 2、hashMap多数情况是读数据操作，通过volatile来协调多个线程的内存可见性，读数据基本上不需要加上，进一步提高了并发性能。
3、使用hashEntry的不变性，来降低读操作的线程，对遍历链表的加锁要求，提高并发性能。
三、LinkedHashMap
1、LinkedHashMap 实现了维护插入顺序或者访问顺序，可以通过accessOrder决定是哪种顺序。
2、LinkedHashMap的底层和HashMap一样，只不过同时维护了一个双向链表，来保证插入和遍历的顺序性
3、LinkedHashMap使用LRU的方式，即最近最少使用，来维护这个双向链表。
LinkedHashMap之所以能实现顺序操作，是因为其保存了一个header变量，来维护一个双向链表。
LinkedHashMap的put和get方法都和HashMap一样，只是重写了addEntry、createEntry、addBefore、recordAccess等方法，这几个方法的作用，就是在put和get、remove等方法调用的时候，维护双向链表的映射，以保证顺序。
LinkedHashMap 示意图.png
参考资料：
Java集合框架：HashMap
HashMap 的实现原理
LinkedHashMap 的实现原理
Java集合-LinkedHashMap工作原理
网友评论