HashMap
1. 哈希表的存储过程
- 根据key计算出哈希值h.
- 假设箱子个数为n,那么键值对应该放在第h%n个箱子中
- 如果箱子中有了键值对，应该解决冲突
2. 解决hash冲突
在使用链表解决冲突时，属于同一个箱子的所有键值对都会排列在链表中。
哈希表还有一个重要的属性: 负载因子(load factor)，它用来衡量哈希表的 空/满 程度，一定程度上也可以体现查询的效率，计算公式为:负载因子 = 总键值对数 / 箱子个数
负载因子越大，越容易导致冲突，性能也就越低。当负载因子大于某个常数（1，0.75）时，哈希表将自动扩容。理想状态下哈希表的每个箱子中，元素的数量遵循泊松分布：
当负载因子为 0.75 时，上述公式中 λ 约等于 0.5，因此箱子中元素个数和概率的关系如下: | 数量 | 概率 |
|---|---|
| 0 | 0.60653066 |
| 1 | 0.30326533 |
| 2 | 0.07581633 |
| 3 | 0.01263606 |
| 4 | 0.00157952 |
| 5 | 0.00015795 |
| 6 | 0.00001316 |
| 7 | 0.00000094 |
| 8 | 0.00000006 |
所以，java8中，在一个箱子的数量大于8时，将链表转成红黑树，小于6时红黑树转成链表。一定程度上解决hash有问题导致一个箱子数量过大导致的而性能问题。
3. 扩容
HashMap，在元素个数大于 容量* 负载因子时，会进行扩容，默认情况下为16*0.75=12
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ....... // 这时候开始扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;} 默认2倍扩容，并做rehash，就算hashcode 不做任何改变，rehash之后对应的箱子也是有可能不同的。对n取模后的值有变化。