关于android:HashMap源码详细解析

29次阅读

共计 7236 个字符，预计需要花费 19 分钟才能阅读完成。

前言

HashMap 是 Java 程序员应用最多的数据结构之一，同时也是 面试必问的知识点，随着 JDK 的进化与倒退，JDK 1.8 也对底层实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文将联合 JDK 1.7 和 1.8 的源码，深入探讨 HashMap 的构造实现和性能原理，篇幅有些长请急躁看完。

简介

HashMap 和 ArrayList 一样也是 继承一个实现一个，继承关系简直统一，只是把 List 换成了 Map。

Java 为数据结构中的映射定义了一个接口 java.util.Map，此接口次要有四个罕用的实现类，别离是 HashMap、HashTable、LinkedHashMap 和 TreeMap，HashMap 类继承关系如下图所示：

基本原理

根本数据结构

HashMap 的根本数据结构是数组 + 链表 / 红黑树，小规模状况下以数组 + 链表（相似于桶存储）为主，大量数据的时候会转换为红黑树，这里须要提的是 何时会转换为红黑树，这是一个咱们必须要关注的问题，会在前面讲到。

put 原理

在进行 put 源码剖析之前咱们须要先理解一个叫 扰动函数 的货色，用于计算存储的 hash 值。

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

从上述函数咱们能够看出几个比拟要害的信息：

  • HashMap 反对 key 为 null 存储，为 null 的时候返回为 0。
  • 如果间接拿散列值作为下标拜访 HashMap 主数组的话，思考到 2 进制 32 位带符号的 int 表值范畴从 -2147483648 到 2147483648，很难呈现碰撞，不过这个 hash 值不能间接拿来用，因为 hashmap 的初始值才 16。
  • 如何解决 hash 值：在这之前会有一个函数叫做 indexFor 去解决，次要是联合长度进行模运算。在 JDK8 中这一操作被放到了 putVal 中间接解决。
    • *

说完了扰动函数咱们正式进入 put 原理的剖析。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

上述源码 put 函数最外层的办法，putVal 为 HashMap 理论应用的办法，其实 HashMap 的源码很简单，其它的每一个局部都能写一篇文章，用来阐明如此精妙的数据结构是如何设计进去的。

putVal 源码正文解析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果 table 为空或者 0 则执行 resize，并将长度赋值给 n，做必要的初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null) // 此处 & 代替了 %（除法散列法进行散列）// 如果 hash 进去的值为空，则新建一个结点并插入到指定地位（意思就是 tab[i]的地位此时还没有数据插入）tab[i] = newNode(hash, key, value, null);
      // 这里的 p 结点是依据 hash 值算进去对应在数组中的元素，如果为空就代表还未插入。else {
        Node<K,V> e; K k;
                // 如果插入的 key 雷同，进行笼罩操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            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;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                                // 及时更新 p
                p = e;
            }
        }
                // 如果 e 存在，就进行笼罩
        if (e != null) {// existing mapping for key
V oldValue = e.value;
                        // 判断是否容许笼罩，并且 oldValue 此时的状态
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 回调以容许 LinkedHashMap 后置操作
            return oldValue;
        }
    }
    ++modCount;   // 更改操作次数
        // 如果容量超标，则执行 resize 进行扩容
    if (++size > threshold)
        resize();
        // 完结 Node 插入之后的操作
    afterNodeInsertion(evict);
        // 回调以容许 LinkedHashMap 后置操作
    return null;
}

对于 HashMap putVal 操作次要分为如下几个步骤：

1）初始化并筹备好结点。

2）判断须要进行的操作，进行创立赋值（雷同 key，红黑树结点，链表操作）。

3）将创立玩的结点利用到 Map 中去。

4）容量检测。

这里咱们有几个关注点：

1）在数组中如何存储对应的结点数据：通过(n – 1) & hash 计算出地位再放入的。

2）链表在什么时候会转换为红黑树：binCount 大于 7 的时候就会转换为红黑树，当其小于 6 的时候就会变会链表。

get 原理

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

利用 key 以及 put 时候的同款 hash 计算方法找到对应的值。

getNode 返回一个数的数据结点，如果为空则返回 null；

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash &&// always check first node
((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                        // 链表的迭代
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

1）通过 hash & (table.length – 1)获取该 key 对应的数据节点的 hash 槽。

2）判断首个结点是否为空，如果为空就间接返回 null。

3）判断首个结点的 hash 是否与待查找的 hash 值雷同，如果雷同间接返回取出。

4）进入链表迭代的循环，流程图如下所示。

当 Node 为红黑树的状况下 getNode 返回的是 key 对应的红黑树节点。

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc =comparableClassFor(k)) != null) &&
                 (dir =compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

Hash 碰撞

顾名思义就是多个值的 hashCode 计算雷同，都处于同以空间的时候，put 的时候发生冲突。

在 Java HashMap 中采纳“拉链法”解决 HashCode 的碰撞问题，具体图片如下所示。

HashMap 应用链表来解决碰撞问题，当碰撞产生了，对象将会存储在链表的下一个节点中。hashMap 在每个链表节点存储键值对对象。当两个不同的键却有雷同的 hashCode 时，他们会存储在同一个 bucket 地位的链表中

红黑树

R-B Tree，全称是 Red-Black Tree，又称为“红黑树”，它一种非凡的二叉查找树。红黑树的每个节点上都有存储位示意节点的色彩，能够是红 (Red) 或黑(Black)。

红黑树特色：

（1）每个节点或者是彩色，或者是红色。

（2）根节点是彩色。

（3）每个叶子节点（NIL）是彩色。[留神：这里叶子结点，是只为空的叶子结点！]

（4）如果一个节点是红色的，则它的子节点必须是彩色的。

（5）从一个节点到该节点的子孙节点的所有门路上蕴含雷同数目的黑结点。

下图就是一个简略的红黑树。

链表到红黑树的转换

// 链表转双向链表操作
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
        // 如果元素总个数小于 64，则持续进行扩容，结点指向调节
    if (tab == null || (n = tab.length) <MIN_TREEIFY_CAPACITY)
        resize();
     // 先找到那个链表的头
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null; // hd：树头部
        do {
                        // 创立红黑树根结点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
           // 此处才是真正的转为红黑树（树化其实就是红黑树的创立，这里就不过多剖析了）hd.treeify(tab);
    }
}

上述是一个红黑树入口办法，当 HashMap 须要转换为红黑树的时候，此时便会进入这个办法。

1）当结点数量为空，或少于 64 个的时候会主动触发 resize()。

2）递归构建 TreeNode，构建实现调用 treeify 实现树化。

扩容机制

理解一个数据结构，咱们必须要晓得的就是其扩容算法，在 HashMap 之中通过 resize 实现扩容，接下来将解析 resize 的扩容机制。

final Node<K,V>[] resize() {
        // 取得旧元素数组的各种信息
    Node<K,V>[] oldTab = table;
   // 获取旧容量长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
   // 扩容的临界点
    int oldThr = threshold;
     // 定义新数组的长度，以及扩容的临界值
    int newCap, newThr = 0;
   // 如果旧的容量 > 0 也就是原有 table 不为空。if (oldCap > 0) {
        // 如果数组长度达到最大值，则批改临界值为 Integer.MAX_VALUE
        if (oldCap >=MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 上面就是扩容操作（2 倍）else if ((newCap = oldCap << 1) <MAXIMUM_CAPACITY&&
                 oldCap >=DEFAULT_INITIAL_CAPACITY)
            // 阈值也变为二倍
            newThr = oldThr << 1;
}
    else if (oldThr > 0)// 旧阈值倍设置为新容量
newCap = oldThr;
    else { // 如果是新的初始化，则 cap 设置为默认容量
newCap =DEFAULT_INITIAL_CAPACITY;
                // 如果阈值设置为默认阈值
        newThr = (int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) { // 如果临界值为 0，则设置临界值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap <MAXIMUM_CAPACITY&& ft < (float)MAXIMUM_CAPACITY?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 更新填充因子
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
        // 上面就是扩容之后，要针对性调整红黑树或链表的指向。if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) // 红黑树调整
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
// 链表调整
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 {if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab; // 最初返回新的 table data；}

下面就是一份残缺的扩容的源代码，总体分为两个局部：扩容新空间，调整原有数据的地位。我曾经在必要的中央进行了些许正文阐明，其实光看代码，有些问题咱们并不能晓得，接下来为将针对性的解决几个问题。

什么时候会触发 resize 呢？

影响 HashMap 触发 resize 的起因如下：

Capacity：以后 HashMap 的长度

LoadFactor：负载因子，默认值为 0.75f。

当 capacity > currentCapacity * LoadFactor 的时候，就回去触发 resize 进行扩容。

如何扩容？

分为两步：

  • 扩容新建一个新的数组，长度为原来的两倍（这一点在源码正文上有提到）。
  • 把原数组，从新 Hash 过后放入新的数组中去。

为何是 reHash 之后寄存而不是间接寄存？

这一点须要联合咱们新增时候的 hash 扰动函数来说，(n – 1) & hash 咱们在计算出地位的时候是通过 n 和 hash 之间的模运算得出的，如果此时咱们的 n 产生了变动还沿用以前的地位就会呈现找不到地位的状况，具体示意图如下所示。

扩容前的地位：

未扩容前，有一个容量为 3 的 HashMap 存储桶，此时其中的数据如下所示，此时须要对 HashMap 进行扩容。

如果扩容后间接复制过来：

如果未进行 rehash，那么此时的地位如上图所示，而此时因为是曾经扩容实现的，那么 getNode 那边在获取到对应 HashMap 的 size 将是 6，而不是原来的 3，那么试想一下(6 – 1) & hash 等于 (3 – 1) & hash 么？答案不言而喻是不等的，那么 resize 过后如果不从新 resize，所有的以前的 Node 都拿不到了。

从新 rehash 之后的后果：

如果此时从新 rehash 了，就不会存在此类问题，能够间接获取到对应的值。

总结

HashMap 这样的知识点还有很多，一篇文章是说不完的，所以我并没有介绍一些 HashMap 的基本知识，将更多的篇幅放在了一些比拟要害局部的介绍，至于更多的玄机须要咱们一起去摸索。

相干视频举荐：
【Android 面试必问的 HashMap 源码解析】03-HashMap 的表构造原理
【Android 面试题精选】资深架构师带你逐题详解 Android 大厂精选高频面试题
)

本文转自 https://juejin.cn/post/6967650737429938183，如有侵权，请分割删除。

正文完
android
发表至： android
2021-11-26
 0
关于android:Unity平台-快速集成华为性能管理服务
关于android:有声小说源码付费小说网站源码带支付系统开源小说站源码全自动采集
关于android:二维码污损反光距离远还能扫出来吗统一扫码服务告诉你能
关于android:ShareSDK-Android端权限说明