HashMap

HashMap

1. Key/Value 结构
2. 线程不安全

3. 一般Key用String类型

   String类为final，hashcode()计算是根据字符数组的每个元素，能保证同一个String会得到同一个hashcode。

4. 数据结构

   1.7之前，数组（Entry）+ 链表

   Entry，数组，地址连续，大小固定，查询快。包含key、value、hash、next等数据。
   链表，为了节省空间，链表在内存中存储地址不连续，可以更好的利用内存空间。
   

   1.8,数组（Entry）+ 链表 + 红黑树

   当链表长度 > 8 , 链表转为红黑树 ,加快检索速度。
   

5. 扩容机制

   负载因子（loadFactor）默认 0.75
   负载临界值（threshold）= loadFactor * loadFactor。
   capacity 容量大小 ， 2的n次方 ，左移运算。
   put元素是，size >= threshold ，调用resize()方法，扩容，2倍。

6. ConcurrentHashMap

   解决HashTable 和 Collections.synchronizedMap() 效率低下的问题

   1.7之前，使用分段锁，加锁基于segment（段）粒度

   static class Segment<K,V> extends ReentrantLock implements Serializable 
   

   

   1.8，底层使用了Node数组+链表+红黑树数据结构，用synchronized的关键字