Map 框架
Map 框架集成于 Map 接口，除了早期的 Map 类，其他类集成于 AbstractMap 抽象类，这个类实现了 Map 接口的通用功能。
HashTable 是早期 Java 提供的线程安全哈希映射表，对应于 Vector 类。
LinkedHashMap 采用双向链表 + 哈希映射实现的，兼具两者的优点，可以在常数级时间实现插入、删除、查找等操作，重写 removeEldestEntry 方法可以根据自定义规则清理最不常被访问的对象，简单的 LRU 算法实现可以直接套用这个类。
TreeMap 底层是红黑树和链表。实现了 NavigableMap，有序且实现类似双向队列的 Map 版功能。
LinkedHashMap 和 TreeMap 的顺序
这两个类都能维持一定的顺序，但是这个“顺序却大不相同”。
LinkedHashMap 维持的是访问的顺序， put、get、compute 等操作都算是访问。
TreeMap 维持是整体的顺序，是根据键的顺序关系决定的。这个顺序可以通过 Comparator 或者 Comparable 定制。
hashCode() 和 equals() 及 compareTo()
这三个方法其实是有约定的，写程序时应注意维持一种关系：hashCode 相等的对象，equals() 方法 和 compareTo() 方法返回值应该是 true 和 0。
在 map 里就利用这个前提做了一些事，hashMap 的性能依赖于 hashCode 和 equals 的有效性，在树化后也是用 hashCode 决定记录应该放在树节点的左边还是右边。如果这个前提不成立，map 中的记录就可能分布得不均衡，性能恶化。TreeMap 中要求 compareTo 的返回值的关系需要和 equals 一致，不然就会出现模棱两可的情况。
hashMap 源码简析
内部实现
hashMap 内部可以看作是数组 (Node<K,V>[] table) 和链表的组合成的复合结构，数组被分为一个个桶 (bucket) ，通过哈希值决定了键值在这个数组的寻址；哈希值相同的键值对，则以链表形式存储。在链表长度大小超过阈值 (TREEIFY_THRESHOLD, 8) , 时相应的链表会被改装成红黑树结构。
lazy-load
hashMap 是按照 lazy-load 设计的，她的初始化方法仅仅是设置了一些初始值而已
public HashMap(int initialCapacity, float loadFactor){
// ...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
初始化和动态扩容都是集中在 resize() 函数中。比如在插入记录时，若是没初始化，会执行 resize() 方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbent,
boolean evit) {
Node<K,V>[] tab; Node<K,V> p; int , i;
if ((tab = table) == null || (n = tab.length) = 0)
n = (tab = resize()).legth;
……
}
以及在元素达到扩容的条件时开始动态扩容
if (++size > threshold)
resize();
定位记录
具体键值对在哈希表中的位置（数组 index）取决于下面的运算
i = (n - 1) & hash
而这里的 hash 值是 hashMap 二次运算得到的值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到这里做了一次处理，将 key 本身的 hashCode 中的高位数据移到低位进行异或运算。
分析 hashMap 的定位数据设计，可以发现：
-
n 是 table 的长度，是 2 的幂次方，n-1 得到一个二进制低位全是 1 的掩码，与二次哈希后的哈希值进行与操作，即 hashmap 是用二次哈希值得低位作为键值对在数组中的位置。
-
因为有些数据计算得出的哈希值差异主要在高位，而在上一点中说了哈希寻址是根据地位来运算的，所以进行了一次高位与低位的运算，避免了类似情况下的哈希碰撞。
-
hashMap 将性能优化到极致，table 尺寸是 2 的幂次方，使得可以通过位运算进行二次哈希及定位，位运算高速，二次哈希提高性能。
resize() 方法的细节
final Node<K,V>[] resize() {
// ...
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPAITY)
newThr = oldThr << 1; // double there
// ...
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaultsfults
newCap = DEFAULT_INITIAL_CAPAITY;
newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY；
}
if (newThr ==0) {
float ft = (float)newCap * loadFator;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
}
threshold = neThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newap];
table = n；
// 移动到新的数组结构 e 数组结构
}
依据 resize 源码，可以发现：
- 理论最大容量是 10 亿多个键值对，由 MAXIMUM_CAPACITY 指定，数值是 1<<30，即 2 的 30 次方。
- 门限值等于（负载因子）x（容量），如果我们构建 HashMap 时没有指定它们，那就是依据相应的常量值 16。
- 门限值是以倍数进行调整（ newThr = oldThr << 1）。配合上一点，可以知道初始不指定初始值的 hashMap，在键值对达到 16 * 0.75 = 12 个时，就会达到门限值，触发 resize() 方法，门限值扩容到 24 。
- 扩容后需要将老的数组中的元素重新放置到新的数组，这是扩容的主要开销。同时这个扩容是非线程安全的，再此时若是有并发添加记录的操作，可能会触发死循环。
容量、负载因子
容量和负载因子决定了可用的桶的数量，空桶太多会浪费空间，如果使用太满则会严重影响操作的性能。极端情况下，假设只有一个桶，那 hashMap 就退化成一个链表，完全不能提供常数时间的操作性能。
对于容量，如果预先知道要存取的键值对数量，或者数量级别，可以考虑预先设置合适的容量大小。具体数值可以根据扩容发生的条件来做简单的预估，容量的计算条件为：
负载因子 * 容量 > 元素数量
即预先设置的容量需要满足，大于“预估元素数量 / 负载因子”，同时是 2 的幂数。
对于负载因子：
- 如果没有特别的要求，不要轻易进行更改，因为 JDK 默认的负载因子是非常符合通用场景的需求的。
- 如果需要调整，建议不要设置超过 0.75 的数值，因为会显著增加冲突，降低 HashMap 的性能。
- 如果使用太小的负载因子，按照上面的扩容条件公式，预设的容量值也应该进行调整，否则可能导致更加频繁的扩容，增加无谓的性能开销，本身访问的性能也会受限。
树化
当某个桶中键值对的数量达到树化的门限值，就会触发扩容或者树化，树化的逻辑主要在 putVal 和 treeifBin 中。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 树化改造逻辑
}
}
根据 treeifBin 中的逻辑，可以理解为当桶中的键值对的数量大于 TREEIFY_THRESHOLD 时：
- 如果容量小于 TREEIFY_THRESHOLD ，即桶的数量少于 64 个，则会进行简单的扩容。
- 如果容量大于 TREEIFY_THRESHOLD，则会触发树化改造。
树化的原因很多，提高性能和维护安全是主要的目的。如果在元素放置的过程中，大量的对象哈希冲突，被放到同一个桶里，则会形成一个很长的链表，而链表的查找时间是线性的，会严重影响性能。在现实世界中这种构造哈希冲突导致服务器 CPU 大量占用的攻击，叫做哈希碰撞拒绝服务攻击。
网友评论