首页 > 资讯 > 后端开发 > Python >Java 源码重读系列之 HashMap

494

分享到

Java 源码重读系列之 HashMap

Java HashMap源码重读 Java HashMap 2023-05-15 14:05:32 494人浏览独家记忆

Python 官方文档：入门教程 => 点击学习

摘要

目录0. 成员变量1. hash()2. comparableClassFor()3. tableSizeFor()4. table、threshold、loadFactor5. p

0. 成员变量

首先我们先看一下 HashMap 有哪些成员变量

    
    static final int DEFAULT_INITIAL_CAPACITY = 1 &lt;&lt; 4; // aka 16

    
    static final int MAXIMUM_CAPACITY = 1 &lt;&lt; 30;
    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //下面还有三个树化的参数
    //如果哈希值相同的元素超过 8 个，则树化
    static final int TREEIFY_THRESHOLD = 8;
    //树的节点小于 6 个，则转成链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //如果 map 的元素小于 64，即便是 哈希值相同的元素超过 8 个了，也不树化，会扩容
    static final int MIN_TREEIFY_CAPACITY = 64;

下面还有一个 Node 类，这个类就是 HashMap 存储元素的容器，其实很简单

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        //... ... 

}

没有多少复杂的内容，类似于链表的Node节点，key、value、next，因为大量的地方都需要用到对象的 hash 值，所以又记录了下 key 的 hash 值。

1. hash()

继续往下看

	//求 key 的哈希值
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

也没什么好说的，就是通过对象的 hashCode 计算出一个 int 值。

2. comparableClassFor()

下面有个 comparableClassFor 方法，这个方法的主要是判断入参 x 是否实现了 Comparable 接口。不过写的格式有点紧凑，我们需要展开以下。

	static Class<?> myComparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c = x.getClass();
            // 获取 x 实现的所有接口
            Type[] ts = c.getGenericInterfaces();
            Type[] as;
            Type t;
            ParameterizedType p;
            //如果 x  是 String 类型 直接返回
            if (c == String.class) {
                return c;
            }
            if (ts != null) {
                // 遍历实现的所有接口
                for (int i = 0; i < ts.length; ++i) {
                    t = ts[i];
                    // 如果接口有泛型
                    if (t instanceof ParameterizedType) {
                        p = (ParameterizedType) t;
                        // 如果泛型对象是 Comparable
                        if (p.getRawType() == Comparable.class) {
                            as = p.getActualTypeArguments();
                            // 只有一个泛型参数，且参数类型是 x.class
                            if (as != null && as.length == 1 && as[0] == c) {
                                return c;
                            }
                        }
                    }
                }
            }
        }
        return null;
    }

举个例子:

class MyTest implements Comparable<MyTest> {}

会返回 MyTest.class

class MyTest implements Comparable<Integer> {}

会返回 null

这个方法就结束了，如果还是不能理解，可以将代码复制出来，打个断点跑一下。继续往下看。


    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

这个方法有意思，注释是说，如果 x 是 kc 的类型，返回 k.compareTo(x) （k 是筛选过的比较类）。如果你查找下这个方法的使用地方就会发现，kc 这个参数就是上面 comparableClassFor 返回的类型。

这么一看是不是就清晰了？ comparableClassFor(x) 拿到类型，然后传入 compareComparables(kc,k,x) 去比较。

3. tableSizeFor()

下面又是一个方法：

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        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 的 2 的幂值。还是那句话， main 方法试试就知道了。不多说。

4. table、threshold、loadFactor

再往下就是一些变量了。其中最核心的变量就是 table

    transient Node<K,V>[] table;

通过注释我们就可以知道这个是存储 HashMap 元素的数组，在第一次使用时被初始化，并且根据需要调整大小，长度适中是 2 的幂。

table 数组就是存储 HashMap 元素的底层结构，具体怎么存储我们后面再看。不过需要注意的是这个变量使用了一个 transient 修饰符，这在我们平常的编码中是很少见到的。这个修饰符的作用是在序列化时跳过该属性。是跟 Serializable 相对应的。其实就是当一个 HashMap 对象被序列化到文件中时，其中的元素是没有写到文件里的。所以通过反序列化也是拿不到元素的。

我们知道了它的功能，但是 HashMap 为什么要这么做呢？其实这个是跟 HashMap 的 put 方法有关系，我们稍后再说。继续往下看。

下面还有一些其他的属性，其中有两个比较重要。

    int threshold;

    final float loadFactor;

threshold 是下次扩容时 HashMap 的容量。 loadFactor 是加载因子，当 HashMap 的容量达到总容量的一定比例就会触发扩容。这两个字段都跟扩容有关，等看到扩容时再说。

再往下就是几个构造方法了，前面三个构造方法都只是在确定 threshold、loadFactor 这两个属性的默认值。没有什么好说的

threshold 如果初始化时没有传值就是 0 ，loadFactor 默认值是 DEFAULT_LOAD_FACTOR = 0.75f。也就是说，如果 HashMap 的当前容量达到总容量的 75% 就会触发扩容。

5. putMapEntries()

后面还有一个构造方法是传入了一个 Map 集合，它会把入参中集合里的元素 put 到当前的 HashMap 集合中。

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

这个构造方法首先初始化了 loadFactor 属性，然后调了putMapEntries 方法，这个方法就在下面。同样格式有点乱，没关系，我们先调整下格式。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s <= 0){
            return;
        }
        if (table == null) {
            float ft = ((float)s / loadFactor) + 1.0F;
            int t;
            if (ft < (float)MAXIMUM_CAPACITY){
                t = (int)ft;
            }else {
                t = MAXIMUM_CAPACITY
            }
            if (t > threshold){
                threshold = tableSizeFor(t);
            }

        }
        else if (s > threshold){
            resize();
        }


        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.geTKEy();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }

如果 map 里没有元素，直接结束。因为我们是构造方法进入到这个方法里的，所以 table 一定为 null，然后计算了一下 ft ，表示放入 m 个元素后，HashMap 的最大容量，（如果 s = 75,那 ft = 101）。

然后计算了一下 t 就是 map 需要的最大容量。并且判断一下是否超限。然后判断了一下是否要更新 threshold ，因为我们是构造方法进来的，所以一定是需要更新的。更新结束后就是 for 循环依次调用 putVal 将元素放入到当前的 HashMap 里。

6. putVal()

然后我们跳到 putVal 方法。这个方法的格式依然不太好阅读，我们需要修改下。

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> p;
        int n, i;

        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            HashMap.Node<K, V> e;
            K k;
            if (p.hash == hash) {
                k = p.key;
                if (k == key || key != null && key.equals(k)) {
                    e = p;
                }
            } else {
                if (p instanceof HashMap.TreeNode) {
                    e = ((HashMap.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) {
                                treeifyBin(tab, hash);
                            }
                            break;
                        }
                        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                            break;

                        p = e;
                    }
                }
            }

            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

首先判断了 table 是否进行了初始化，没有的话进行 resize，这个方法我们一会再看。它的作用就是返回一个 Node 数组，数组的长度就是 threshold。初始化好之后就是判断下这个数组的(n - 1) & hash 位置是否有值，没有值的话直接创建一个 Node 存到数组里就结束了。其实 (n - 1) & hash 相当于 hash % (n-1) 的作用，但是与操作的效率比取模的效率高。二者达到的效果是一样的。

如果有值，并且 key 相等，说明是同一个元素，这个时候 e 就是 HashMap 里的元素，后面对 e 的判断就会直接返回 e 对应的 value。

如果 key 不相等，说明发生了 hash 冲突。两个 hash 值不一样的元素应该存储到数组的同一个位置。这个时候判断了一下 Node 的类型。如果是 TreeNode 那么调用 putTreeVal 方法。

如果不是，则依次遍历当前位置节点的 next 指针，直到为空，插入新节点。其实就是讲新节点挂到了已当前节点为表头的链表尾部。插入成功之后判断了一下链表的长度，如果需要则进行树化。将当前链表转成一个红黑树。这个主要是解决链表太长，查询效率低的问题。而且在遍历链表期间依然判断了 key 是否相等，相等则直接返回旧元素的 value。

好像也不是很难，这个就是 HashMap 最核心的方法之一了。从这个方法中也可以知道，HashMap 的底层存储结构是一个数组。如果发生 hash 冲突后，会采用链表的方式存储，当链表长度过长时，会将链表转成红黑树结构，提高查询效率。

7. resize()

下面我们看一下resize() 方法

final HashMap.Node<K, V>[] resize() {
    HashMap.Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes", "unchecked"})
    HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            HashMap.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 HashMap.TreeNode)
                    ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                else { // preserve order
                    HashMap.Node<K, V> loHead = null, loTail = null;
                    HashMap.Node<K, V> hiHead = null, hiTail = null;
                    HashMap.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;
}

resize() 方法的主要作用就是当 table 数组中的元素超过一定的数量后，对 table 数组进行扩容，以便减少 hash 碰撞发生的概率。最前面一大串的 if 、else 判断主要是为了确定两个变量的值 newCap 和 newThr 。newCap 是指扩容后新的 table 数组的长度。newThr 是指新数组的元素超过多少时需要扩容。

计算的方式分几种场景。第一种 oldCap > 0: 这种是正常扩容，oldTable 已经有元素了，而且元素的数量也达到了扩容的数量。这时 newCap 和 newThr 是原来数值的 2 倍（<< 是右移操作）而且判断了下是否超过了最大值。如果 oldCap 已经大于等于最大值了，那直接把下次扩容的阈值调整到最大就结束了，因为 table 数组已经无法扩容了。

(newCap = oldCap << 1) < MAXIMUM_CAPACITY 这一行代码很有意思它的执行逻辑是，先将 oldCap 右移一位后的数值赋值给 newCap，然后判断 newCap 是否超过了 MAXIMUM_CAPACITY 。有意思的点在于，它没有关注 newCap 的溢出情况！！这个其实也是 HashMap 的的容量永远都是 2 的整数次幂的原因。因为，把一个2 的整数次幂的数值右移一位后，依然是一个2 的整数次幂，而 MAXIMUM_CAPACITY 就是允许的最大的 2的整数次幂。因为之前已经判断过是否等于 MAXIMUM_CAPACITY 了。所以，oldCap 右移后，最大只能是等于 MAXIMUM_CAPACITY ，不会溢出。而且，当 newCap 等于 MAXIMUM_CAPACITY 是没有对 newThr 赋值的，对 newThr 赋值的逻辑是在下面的 if (newThr == 0) 的地方。

第二个场景 else if (oldThr > 0) 执行到这个 if 里的情况是，初始化的时候传了 initialCapacity 这个参数。还记得之前初始化时 threshold 的赋值逻辑么？

this.threshold = tableSizeFor(initialCapacity)

当初始时传了 initialCapacity 参数，在第一次 put 操作时，就会触发首次扩容（或者说初始化 table 数组）。

这里有个小知识点：我们在平时写代码使用到 HashMap 时，为了提高效率，不让 HashMap 触发扩容，都会指定 HashMap 的容量，比如：

Map<String, String> map = new HashMap<>(40);

这个时候我们往 Map 里放 5 个元素，应该是只扩容一次即初始化 table 那次。好像没有什么问题。这时因为在第一次初始化时 tableSizeFor 这个参数返回的是大于等于 initialCapacity 的最小的 2 的整数幂的值。比如你传 50，初始化的结果是 64 。而默认的 loadFactor 是 0.75，也就是在元素达到 48 时才会触发扩容。

但是，如果你给的值是 48 以上的呢? 或者说恰好是 64 的时候。这个时候就会在插入第 49 个元素时再次触发一次扩容。所以，如果你明确的知道元素的容量的话，可以初始化 2 倍元素容量的 HashMap ，这样就不会触发两次扩容了。

继续往下说，计算好 newCap 和 newThr 的值后，就创建了一个 newTab，然后就是遍历 oldTab 不断的将元素转移到 newTab 里去。

首先将 oldTab 的引用置为 null，避免内存泄露。然后当前元素会有三种情况：第一种 e.next == null 就是当前位置只有这一个元素，没有发生 hash 冲突。这种最简单，直接放到 newTab 里就可以了。第二种 e instanceof TreeNode，就是发生了 hash 冲突，且已经把链表转成了红黑树的结构了（还记的 putVal 方法么？）。这种就需要按照红黑树的操作，把 e 这个节点从 oldTab 上摘下来，挂到 newTab 上去（有点复杂，已经超过了本文的内容。需要了解的可以搜一下红黑树）。第三种，就是发生了 hash 冲突，但是存储结构还是链表的情况。这种情况如果按照正常的思路的话，无非就是遍历链表，依次将链表的元素放入到 newTab 就好了。但是这样就会有一个问题，就是链表上的元素依然有可能出现 hash 冲突，如果在遍历链表期间多个元素发生了 hash 冲突怎么办呢？

很显然，从代码上来看，并没有按照我们的思路来。代码逻辑是根据元素的 hash 值将一个链表分成了两个链表。loHead 和 hiHead。等拆分完成后，直接将链表的表头保存到了 newTab 的两个元素里。是不是很神奇？？就好像是在说，扩容前发生了 hash 冲突的元素，那么扩容后也有可能发生 hash 冲突，并且这些元素一定应该放到 newTab[j] 或者是 newTab[j+oldCap] 这两个位置。事实就是这样！！

其实，你可以写代验证下，扩容前发生 hash 冲突的元素，如果 (e.hash & oldCap) == 0 那么它一定会落在 newTab[j]上，否则一定落在 newTab[j+oldCap] 上。数学就是这么完美~~

好了，resize()方法到这里就结束了。我们回到 putMapEntries() 方法这里继续往下看。

再往下，szie() 和 isEmpty() 都没有什么好说的，下面是 get(Object key) 方法，这个是 HashMap 最常用的方法之一。

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

好像也没有特别复杂，计算 key 的 hash 值，然后通过 getNode 方法获取 node 对象，找不到就返回 null，找到了就返回对应的 value。getNode()方法就在下面。

8. getNode()

如果你对 putVal() 方法已经非常熟悉了，其实 getNode() 就非常清晰了。首先判断了 table 是否为空，不为空的话就通过 hash 找对应位置的元，如果对应的位置有值，就判断 key 是否相等。相等直接返回。

如果不相等，则判断当前位置是否有其他元素，如果是 TreeNode 则从红黑树里找，如果是链表则遍历链表找。

这里需要注意下，还记得之前我们说过 table 这个变量加了 transient 修饰符么，就是为了不让 table 元素进行序列化。其实是跟hash(key) 这个方法有关系。你可以翻看下hash() 这个方法，里面有这样一段 h = key.hashCode()。这里的 hashCode() 你找到它的定义会发现是下面这样的,

 public native int hashCode();

这是一个本地方法。这个方法在不同的 JVM 上可能会有不同的实现，所以，就有可能出现，序列化前和序列化后的对象 hashCode() 方法返回的值不同。但是在序列化后，HashMap 保存在 table 中的位置没有变，就会出现找不到的情况，这就是 HashMap 中的一些元素不能序列化的原因。

继续往下就没有什么好说的了，剩下的除了像 clear()、remove() 这种比较简单的方法外，就剩一个最复杂的treeify和untreeify。这个是 HashMap 里最复杂的部分，都是 TreeNode 里的方法，已经超出了本文的内容。

以上就是Java 源码重读系列之 HashMap的详细内容，更多关于Java HashMap源码重读的资料请关注编程网其它相关文章！

您可能感兴趣的文档:

--结束END--

本文标题: Java 源码重读系列之 HashMap

本文链接: https://lsjlt.com/news/209113.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341