HashMap
![]()
HashMap底层数据结构.png
HashMap底层数据结构.png
影响HashMap性能的2个因素
- 初始容量，默认为16，表示哈希表中桶的数量；
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 加载因子，默认值为0.75，表示哈希表的容量在自动增加之前可以达到多满的尺度，当哈希表中的条目数=哈希表的容量*加载因子，将触发扩容操作resize()；
static final float DEFAULT_LOAD_FACTOR = 0.75f;
注：初始容量和加载因子2个值在哈希表初始化的时候可以设定；
HashMap的寻址方式
- 对于新插入的数据和要读取的数据，HashMap会将其key按照一定计算规则计算出哈希值，并对数组长度进行取模，结果作为其插入数组的index；
- 取模的代价远高于位运算的代价，所以HashMap中数组的长度要求必须是2^n， 具体为，将取模操作换成对2^n-1的与运算；
- HashMap初始化的时候传入的容量可以不是2^n， HashMap会根据传入的值得到一个相应的2^n的值；
- HashMap是线程不安全的，主要体现在resize的时候可能出现死循环，以及在使用迭代器的时候会出现ParsedFailed；
- 扩容的具体做法：创建一个新的，长度为原来容量2倍的数组，保证新的容量仍为2^n，并将原来的数组重新插入新数组，这个过程称为再哈希，这个方法不是线程安全的；
单线程下的resize图示
HashMap在单线程下的ReHash.png
多线程resize时候出现死循环图示
-
线程1处理5到一半，5和9还没有完全断开，切到线程2，线程2已经把整个ReHash动作做完；
多线程下的ReHash_1.png -
切回线程1，把5挂在索引为1的元素后面；
多线程下的ReHash_2.png -
由于在线程1中，5和9没断开，线程1会把9再放到5前面，这是在新数组中完成的；
多线程下的ReHash_3.png -
处理完9后，线程1看到9后面还有5，这是因为线程2已经完成了ReHash动作，然后又将5排在9前面，9在5前面，5在9前面，这就死循环了；
多线程下的ReHash_4.png
ParsedFailed分析
- 在遍历HashMap的时候，如果HashMap中的元素有变更，ConcurrentModifacationException，这就是所说的ParseFailed；
解决方案
- Collections.synchronizedMap()构造出一个同步的Map；
- 或者直接使用ConcurrentHashMap()；
ConcurrentHashMap
ConcurrentHashMap结构.png
- 与HashMap不同的是，ConcurrentHashMap外面不是一个大数组，而是多个小数组，每个小数组是一个Segment；
- 在读写某个key时，先计算出该key的哈希值，并将哈希值的高sshift位对Segment个数取模，从而得到该key属于哪个Segment；
- 接着就像操作HashMap一样操作Segment；
- Segment继承自J.U.C的ReentrantLock，所以可以很方便的对每个Segment上锁，就是所谓分段锁；
HashMap与ConcurrentHashMap的区别
- ConcurrentHashMap是线程安全的，HashMap不是线程安全的；
- HashMap允许key和value为空，ConcurrentHashMap不允许；
- HashMap在用iterator遍历的同时，不允许修改HashMap；ConcurrentHashMap允许该行为，并且更新对后续的遍历是可见的；
Java8对ConcurrentMap的改进
- Java7中的ConcurrentHashMap理论上最大并发数和Segment个数相等；
-
Java8废弃了分段锁的方案，直接使用一个大数组，并对哈希碰撞下的寻址做了优化，当链表的长度超过一定值（默认8），列表将转换成红黑树，寻址的时间复杂度从O(n)降为O(logn)；
Java8中的ConcurrentHashMap的进步.png
