关于hashmap:HashMap-是如何工作的图文详解一起来看看

48次阅读

共计 12935 个字符,预计需要花费 33 分钟才能阅读完成。

1 HashMap 在 JAVA 中的怎么工作的?

基于 Hash 的原理。

2 什么是哈希?

最简略模式的 hash,是一种在对任何变量 / 对象的属性利用任何公式 / 算法后,为其调配惟一代码的办法。

一个真正的 hash 办法必须遵循上面的准则:

哈希函数每次在雷同或相等的对象上利用哈希函数时, 应每次返回雷同的哈希码。换句话说, 两个相等的对象必须统一地生成雷同的哈希码。

Java 中所有的对象都有 Hash 办法,Java 中的所有对象都继承 Object 类中定义的 hashCode() 函数的默认实现。此函数通常通过将对象的外部地址转换为整数来生成哈希码,从而为所有不同的对象生成不同的哈希码。

3 HashMap 中的 Node 类

Map 的定义是:将键映射到值的对象。

因而,HashMap 中必须有一些机制来存储这个键值对。答案是必定的。HashMap 有一个外部类 Node,如下所示:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 记录 hash 值,以便重 hash 时不须要再从新计算
    final K key; 
    V value;
    Node<K,V> next;
    
    ...// 其余的代码
}

当然,Node 类具备存储为属性的键和值的映射。

key 已被标记为 final,另外还有两个字段:next 和 hash。

在上面中,咱们将会了解这些属性的必须性。

4 键值对在 HashMap 中是如何存储的

键值对在 HashMap 中是以 Node 外部类的数组寄存的,如下所示:

transient Node<K,V>[] table;

哈希码计算出来之后,会转换成该数组的下标,在该下标中存储对应哈希码的键值对,在此先不具体解说 hash 碰撞的状况。

该数组的长度始终是 2 的次幂,通过以下的函数实现该过程

static final int tableSizeFor(int cap) {
    int n = cap - 1;// 如果不做该操作,则如传入的 cap 是 2 的整数幂,则返回值是料想的 2 倍
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

其原理是将传入参数 (cap) 的低二进制全副变为 1,最初加 1 即可取得对应的大于 cap 的 2 的次幂作为数组长度。

为什么要应用 2 的次幂作为数组的容量呢?

在此有波及到 HashMap 的 hash 函数及数组下标的计算,键 (key) 所计算出来的哈希码有可能是大于数组的容量的,那怎么办?

能够通过简略的求余运算来取得,但此办法效率太低。HashMap 中通过以下的办法保障 hash 的值计算后都小于数组的容量。

(n - 1) & hash

这也正好解释了为什么须要 2 的次幂作为数组的容量。因为 n 是 2 的次幂,因而,n – 1 相似于一个低位掩码。

通过与操作,高位的 hash 值全副归零,保障低位才无效,从而保障取得的值都小于 n。同时,在下一次 resize() 操作时,从新计算每个 Node 的数组下标将会因而变得很简略,具体的后文解说。

以默认的初始值 16 为例:

    01010011 00100101 01010100 00100101
&   00000000 00000000 00000000 00001111
----------------------------------
    00000000 00000000 00000000 00000101    // 高位全副归零,只保留末四位
    // 保障了计算出的值小于数组的长度 n

然而,应用了该性能之后,因为只取了低位,因而 hash 碰撞会也会相应的变得很重大。这时候就须要应用「扰动函数」

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

该函数通过将哈希码的高 16 位的右移后与原哈希码进行异或而失去,以以上的例子为例

异或

此办法保障了高 16 位不变,低 16 位依据异或后的后果扭转。计算后的数组下标将会从原先的 5 变为 0。

应用了「扰动函数」之后,hash 碰撞的概率将会降落。有人专门做过相似的测试,尽管应用该「扰动函数」并没有取得最大概率的防止 hash 碰撞,但思考其计算性能和碰撞的概率,JDK 中应用了该办法,且只 hash 一次。

5 哈希碰撞及其解决

在现实的状况下,哈希函数将每一个 key 都映射到一个惟一的 bucket,然而,这是不可能的。哪怕是设计在良好的哈希函数,也会产生哈希抵触。

前人钻研了很多哈希抵触的解决办法,在维基百科中,总结出了四大类

哈希碰撞解决办法

在 Java 的 HashMap 中,采纳了第一种 Separate chaining 办法 (大多数翻译为拉链法)+ 链表和红黑树来解决抵触。

JDK8 中 HashMap 后果

HashMap 中,哈希碰撞之后会通过 Node 类外部的成员变量 Node<K,V> next; 来造成一个链表 (节点小于 8) 或红黑树(节点大于 8,在小于 6 时会从新转换为链表),从而达到解决抵触的目标。

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

6 HashMap 的初始化

public HashMap();
public HashMap(int initialCapacity);
public HashMap(Map<? extends K, ? extends V> m);
public HashMap(int initialCapacity, float loadFactor); 

HashMap 中有四个构造函数,大多是初始化容量和负载因子的操作。以 public HashMap(int initialCapacity, float loadFactor) 为例

public HashMap(int initialCapacity, float loadFactor) {
    // 初始化的容量不能小于 0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity:" +
                                           initialCapacity);
    // 初始化容量不大于最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 负载因子不能小于 0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor:" +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

通过该函数进行了容量和负载因子的初始化,如果是调用的其余的构造函数,则相应的负载因子和容量会应用默认值(默认负载因子 = 0.75,默认容量 = 16)。

在此时,还没有进行存储容器 table 的初始化,该初始化要提早到第一次应用时进行。HashMap 面试 21 问!面试的举荐你看下。关注公众号 Java 技术栈回复面试获取更多面试材料。

7 HashMap 中哈希表的初始化或动静扩容

所谓的哈希表,指的就是上面这个类型为外部类 Node 的 table 变量。

transient Node<K,V>[] table;

作为数组,其在初始化时就须要指定长度。在理论应用过程中,咱们存储的数量可能会大于该长度,因而 HashMap 中定义了一个阈值参数 (threshold),在存储的容量达到指定的阈值时,须要进行扩容。

我集体认为初始化也是动静扩容的一种,只不过其扩容是容量从 0 扩大到构造函数中的数值(默认 16)。而且不须要进行元素的重 hash.

7.1 扩容产生的条件

初始化的话只有数值为空或者数组长度为 0 就会进行。而扩容是在元素的数量大于阈值(threshold)时就会触发。

threshold = loadFactor * capacity

比方 HashMap 中默认的 loadFactor=0.75, capacity=16, 则

threshold = loadFactor * capacity = 0.75 * 16 = 12

那么在元素数量大于 12 时,就会进行扩容。扩容后的 capacity 和 threshold 也会随之而扭转。

负载因子影响触发的阈值,因而,它的值较小的时候,HashMap 中的 hash 碰撞就很少,此时存取的性能都很高,对应的毛病是须要较多的内存;而它的值较大时,HashMap 中的 hash 碰撞就很多,此时存取的性能绝对较低,对应长处是须要较少的内存;不倡议更改该默认值,如果要更改,倡议进行相应的测试之后确定。

7.2 再谈容量为 2 的整数次幂和数组索引计算

后面说过了数组的容量为 2 的整次幂,同时,数组的下标通过上面的代码进行计算

index = (table.length - 1) & hash

该办法除了能够很快的计算出数组的索引之外,在扩容之后,进行重 hash 时也会很奇妙的就能够算出新的 hash 值。因为数组扩容之后,容量是当初的 2 倍,扩容之后 n-1 的无效位会比原来多一位,而多的这一位与原容量二进制在同一个地位。示例

扩容前后

这样就能够很快的计算出新的索引啦

7.3 步骤

  1. 先判断是初始化还是扩容,两者在计算 newCap 和 newThr 时会不一样
  2. 计算扩容后的容量,临界值。
  3. 将 hashMap 的临界值批改为扩容后的临界值
  4. 依据扩容后的容量新建数组,而后将 hashMap 的 table 的援用指向新数组。
  5. 将旧数组的元素复制到 table 中。在该过程中,波及到几种状况,须要离开进行解决(只存有一个元素,个别链表,红黑树)

具体的看代码吧

final Node<K, V>[] resize() {
        // 新建 oldTab 数组保留扩容前的数组 table
        Node<K, V>[] oldTab = table;
        // 获取原来数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 原来数组扩容的临界值
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 如果扩容前的容量 > 0
        if (oldCap > 0) {// 如果原来的数组长度大于最大值(2^30)
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 扩容临界值进步到正无穷
                threshold = Integer.MAX_VALUE;
                // 无奈进行扩容,返回原来的数组
                return oldTab;
                // 如果当初容量的两倍小于 MAXIMUM_CAPACITY 且当初的容量大于 DEFAULT_INITIAL_CAPACITY
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 临界值变为原来的 2 倍
                newThr = oldThr << 1;
        } else if (oldThr > 0) // 如果旧容量 <= 0,而且旧临界值 > 0
            // 数组的新容量设置为老数组扩容的临界值
            newCap = oldThr;
        else { // 如果旧容量 <= 0,且旧临界值 <= 0,新容量裁减为默认初始化容量,新临界值为 DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
            newCap = DEFAULT_INITIAL_CAPACITY;// 新数组初始容量设置为默认值
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 计算默认容量下的阈值
        }
        // 计算新的 resize 下限
        if (newThr == 0) {// 在当下面的条件判断中,只有是初始化时 (oldCap=0, oldThr > 0) 时,newThr == 0
            //ft 为长期临界值,上面会确定这个临界值是否非法,如果非法,那就是真正的临界值
            float ft = (float) newCap * loadFactor;
            // 当新容量 < MAXIMUM_CAPACITY 且 ft < (float)MAXIMUM_CAPACITY,新的临界值为 ft,否则为 Integer.MAX_VALUE
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        // 将扩容后 hashMap 的临界值设置为 newThr
        threshold = newThr;
        // 创立新的 table,初始化容量为 newCap
        @SuppressWarnings({"rawtypes", "unchecked"})
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
        // 批改 hashMap 的 table 为新建的 newTab
        table = newTab;
        // 如果旧 table 不为空,将旧 table 中的元素复制到新的 table 中
        if (oldTab != null) {
            // 遍历旧哈希表的每个桶,将旧哈希表中的桶复制到新的哈希表中
            for (int j = 0; j < oldCap; ++j) {
                Node<K, V> e;
                // 如果旧桶不为 null,应用 e 记录旧桶
                if ((e = oldTab[j]) != null) {
                    // 将旧桶置为 null
                    oldTab[j] = null;
                    // 如果旧桶中只有一个 node
                    if (e.next == null)
                        // 将 e 也就是 oldTab[j]放入 newTab 中 e.hash & (newCap - 1)的地位
                        newTab[e.hash & (newCap - 1)] = e;
                        // 如果旧桶中的构造为红黑树
                    else if (e instanceof TreeNode)
                        // 将树中的 node 拆散
                        ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    else {  // 如果旧桶中的构造为链表, 链表重排,jdk1.8 做的一系列优化
                        Node<K, V> loHead = null, loTail = null;
                        Node<K, V> hiHead = null, hiTail = null;
                        Node<K, V> next;
                        // 遍历整个链表中的节点
                        do {
                            next = e.next;
                            // 原索引
                            if ((e.hash & oldCap) == 0) {if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {// 原索引 +oldCap
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到 bucket 里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引 +oldCap 放到 bucket 里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
}

7.4 注意事项

尽管 HashMap 设计的十分优良,然而应该尽可能少的防止 resize(), 该过程会很消耗工夫。

同时,因为 hashmap 不能主动的放大容量。因而,如果你的 hashmap 容量很大,但执行了很多 remove 操作时,容量并不会缩小。如果你感觉须要缩小容量,请从新创立一个 hashmap。

8 HashMap.put() 函数外部是如何工作的?

在应用屡次 HashMap 之后,大体也能说出其增加元素的原理:计算每一个 key 的哈希值,通过肯定的计算之后算出其在哈希表中的地位,将键值对放入该地位,如果有哈希碰撞则进行哈希碰撞解决。

而其工作时的原理如下(图是我很早之前保留的,忘了出处了)

源码如下:

/* @param hash         指定参数 key 的哈希值
 * @param key          指定参数 key
 * @param value        指定参数 value
 * @param onlyIfAbsent 如果为 true,即便指定参数 key 在 map 中曾经存在,也不会替换 value
 * @param evict        如果为 false,数组 table 在创立模式中
 * @return 如果 value 被替换,则返回旧的 value,否则返回 null。当然,可能 key 对应的 value 就是 null。*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {Node<K, V>[] tab;
    Node<K, V> p;
    int n, i;
    // 如果哈希表为空,调用 resize()创立一个哈希表,并用变量 n 记录哈希表长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /**
     * 如果指定参数 hash 在表中没有对应的桶,即为没有碰撞
     * Hash 函数,(n - 1) & hash 计算 key 将被搁置的槽位
     * (n - 1) & hash 实质上是 hash % n,位运算更快
     */
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 间接将键值对插入到 map 中即可
        tab[i] = newNode(hash, key, value, null);
    else {// 桶中曾经存在元素
        Node<K, V> e;
        K k;
        // 比拟桶中第一个元素 (数组中的结点) 的 hash 值相等,key 相等
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            // 将第一个元素赋值给 e,用 e 来记录
            e = p;
            // 以后桶中无该键值对,且桶是红黑树结构,依照红黑树结构插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            // 以后桶中无该键值对,且桶是链表构造,依照链表构造插入到尾部
        else {for (int binCount = 0; ; ++binCount) {
                // 遍历到链表尾部
                if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                    // 查看链表长度是否达到阈值,达到将该槽位节点组织模式转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 链表节点的 <key, value> 与 put 操作 <key, value> 雷同时,不做反复操作,跳出循环
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到或新建一个 key 和 hashCode 与插入元素相等的键值对,进行 put 操作
        if (e != null) { // existing mapping for key
            // 记录 e 的 value
            V oldValue = e.value;
            /**
             * onlyIfAbsent 为 false 或旧值为 null 时,容许替换旧值
             * 否则无需替换
             */
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 拜访后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 更新结构化批改信息
    ++modCount;
    // 键值对数目超过阈值时,进行 rehash
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

在此过程中,会波及到哈希碰撞的解决。

9 HashMap.get() 办法外部是如何工作的?

/**
 * 返回指定的 key 映射的 value,如果 value 为 null,则返回 null
 * get 能够分为三个步骤:* 1. 通过 hash(Object key)办法计算 key 的哈希值 hash。* 2. 通过 getNode(int hash, Object key)办法获取 node。* 3. 如果 node 为 null,返回 null,否则返回 node.value。*
 * @see #put(Object, Object)
 */
public V get(Object key) {
    Node<K, V> e;
    // 依据 key 及其 hash 值查问 node 节点,如果存在,则返回该节点的 value 值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

其最终是调用了 getNode 函数。其逻辑如下

getNode 工作逻辑

源码如下:

 /**
 * @param hash 指定参数 key 的哈希值
 * @param key  指定参数 key
 * @return 返回 node,如果没有则返回 null
 */
final Node<K, V> getNode(int hash, Object key) {Node<K, V>[] tab;
    Node<K, V> first, e;
    int n;
    K k;
    // 如果哈希表不为空,而且 key 对应的桶上不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        // 如果桶中的第一个节点就和指定参数 hash 和 key 匹配上了
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
            // 返回桶中的第一个节点
            return first;
        // 如果桶中的第一个节点没有匹配上,而且有后续节点
        if ((e = first.next) != null) {
            // 如果以后的桶采纳红黑树,则调用红黑树的 get 办法去获取节点
            if (first instanceof TreeNode)
                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
            // 如果以后的桶不采纳红黑树,即桶中节点构造为链式构造
            do {
                // 遍历链表,直到 key 匹配
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 如果哈希表为空,或者没有找到节点,返回 null
    return null;
}

作者:阿进的写字台

出处:https://www.cnblogs.com/homejim/

正文完
 0