非线程安全 Map 简谈

2018-11-08  本文已影响17人  wean_a23e

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 的定位数据设计，可以发现：

  1. n 是 table 的长度，是 2 的幂次方，n-1 得到一个二进制低位全是 1 的掩码，与二次哈希后的哈希值进行与操作，即 hashmap 是用二次哈希值得低位作为键值对在数组中的位置。

  2. 因为有些数据计算得出的哈希值差异主要在高位，而在上一点中说了哈希寻址是根据地位来运算的，所以进行了一次高位与低位的运算，避免了类似情况下的哈希碰撞。

  3. 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 源码，可以发现：

容量、负载因子

容量和负载因子决定了可用的桶的数量，空桶太多会浪费空间，如果使用太满则会严重影响操作的性能。极端情况下，假设只有一个桶，那 hashMap 就退化成一个链表，完全不能提供常数时间的操作性能。

对于容量，如果预先知道要存取的键值对数量，或者数量级别，可以考虑预先设置合适的容量大小。具体数值可以根据扩容发生的条件来做简单的预估，容量的计算条件为：

负载因子 * 容量 > 元素数量

即预先设置的容量需要满足，大于“预估元素数量 / 负载因子”，同时是 2 的幂数。

对于负载因子：

树化

当某个桶中键值对的数量达到树化的门限值，就会触发扩容或者树化，树化的逻辑主要在 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 时：

树化的原因很多，提高性能和维护安全是主要的目的。如果在元素放置的过程中，大量的对象哈希冲突，被放到同一个桶里，则会形成一个很长的链表，而链表的查找时间是线性的，会严重影响性能。在现实世界中这种构造哈希冲突导致服务器 CPU 大量占用的攻击，叫做哈希碰撞拒绝服务攻击。

上一篇下一篇

猜你喜欢

热点阅读