容器之路 HashMap、HashSet解析(一)
2019-11-22

1.1 HashMap概述

相信大家在大学的时候都学习过散列表。

使用散列表的查找算法主要分为两步,第一步是利用散列函数将被查找的键转化为一个索引,理想情况下,所有不同的key都会被散列为不同的索引值,但是由于散列函数无法达到完美的散列,所以,我们通常还需要处理碰撞的情况。

处理碰撞的方法主要有两种,一种是拉链法,另一种是线性探测法。

HashMap中,使用的是拉链法,也就是一个桶,由数组构成,数组的索引代表了散列值,每个数组后接了一个链表。当出现冲突碰撞的情况时,我们将判断这个key是否已经存在,如果存在,那么,替换value值,如果不存在,那么,将这个Entry链接到链表上。

//HashMap中的桶transient Node<K,V>[] table;

那么,当我们查找时,先找到对应的索引值,然后,遍历链表,找到所需的内容。

这里,我们需要注意,如果大量数据的散列值相同,就会导致链表很长,查找效率也就变低了。因此,在JDK1.8中,当链表的长度超出阈值,我们会将链表进行树化,形成红黑树,让查找效率提高。

还有就是,关于MapresizeMap中有一个参数叫做负载因子loadFactor,当桶中的数据量达到桶的长度乘上负载因子时,就会进行扩容。扩容过程中,会把桶的大小变为原来的2倍,并且,将原来Map中的内容进行重新散列,这部分内容也是HashMap中的一个难点,而且,这个算法十分巧妙。

下面是HashMap中节点的数据结构,是单链表结点

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}

1.2 插入数据

通常情况下,如果我们使用我们自己创建的类来作为HashMap中的key,那么,我们需要提供一个比较好的hashCode ,如果这个方法有问题,将会影响散列函数的效率。所以,通常情况下,推荐使用不可变类来作为key,例如String

根据注释可以初步了解插入数据的流程

public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //新建后第一次插入数据会调用resize方法 n = (tab = resize()).length; //如果找到的索引位置没有插入数据,那么直接新建节点,插入即可 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { /** * 如果该索引出已经有数据,可能是两种情况 * 一种是,当前插入节点的key值已经存在,那么需要替换value值 * 另外一种是,出现冲突,需要将结点增加到链表中 */ Node<K,V> e; K k; //第一种情况 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) { //遍历过程中没有找到相同的key,确定新增 p.next = newNode(hash, key, value, null); //新增结点后,如果链表长度超过阈值即>=7,链表转化为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //找到了相同的key跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果是已经存在的结点,替换value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //HashMap中此方法为空,LinkedHashMap实现了这个方法 afterNodeAccess(e); return oldValue; } } ++modCount; //达到阈值,扩容 if (++size > threshold) resize(); //HashMap中此方法为空,LinkedHashMap实现了这个方法 afterNodeInsertion(evict); return null;}

1.2.1 确定索引位置

当我们已经有了keyhash值,确定索引位置,也就是散列值的方法如下。

这里n是桶的长度

(n - 1) & hash

这种方式实际上是除留取余法,这种方法方便计算,使用运算符&mod效率更高一点。

如果n=2^m,那么这样的方式我们就取得了hash值的低m位。

1.2.2 构造函数与tableSizeFor

这里首先介绍一下HashMap的构造函数,主要有以下两个。

public HashMap() { //没有给出初始值,那么负载因子默认为0.75 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //初始值超出最大值,那么就去最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //这里通过tableSizeFor方法获取到离给定值最近的2的幂 this.threshold = tableSizeFor(initialCapacity);}

我们需要注意,在HashMap中,桶的大小,也就table的大小必须是2的幂,这样后面计算索引的时候更加方便,因此,我们需要一个算法来获取这个值。

tableSizeFor这里的算法十分巧妙,我也是参考了博客HashMap源码注解 之 静态工具方法hash()、tableSizeFor()(四) - 程序员 - CSDN博客,这里把精华部分摘录一下,再增加一点自己的理解,大家可以到上面的连接中查看详悉解析。

/** * Returns a power of two size for the given target capacity. */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;}

首先,我们考虑如何取一个大于给定数字的并且离给定数字最近的2的幂。

关于这里为什么减1,后面又加一,实际上,如果给定数字已经是2的幂,这里给出的算法获得的将是其倍数,而不是本身。

下面来看一下JDK中的实现。

在这里,我们发现,初始化时,并没有给桶的大小赋初值,这个操作延迟到了放入数据的resize函数中,接下来,我们来看一下resize函数。

1.2.3 resize扩容

扩容主要分为两步,第一步是确定扩容后的桶的大小和再次扩容的阈值threshold,第二步是将原来HashMap中的数据移动到新的Map中。

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //由于初始化时没有给table赋初值,所以这里指的时map已经有数据的情况 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 } //初始化时,赋了初值,在此处将这个值赋newCap else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { //之前调用了没有参数的构造函数,这里使用默认值,阈值是DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY 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"}) 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) { //释放原有的空间,以便GC 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 { // preserve order //如果后面有链表,那么我们需要特殊处理 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;}

这段代码中,最为巧妙的地方就是如何找到已有结点在新map中的位置。

前面已经说过,一个entry的索引位置实际是hash值的低m位,那么扩容后,这个取值就会变为低m+1位。这样,如果hash值的第m+1位是0,那么这个数据还在原来的位置;如果这位为1,那么这个数据就会在原来位置加上oldCap的位置处。

理解了这部分内容,我们就可以了解上面的算法为什么将原来的一条链表分为两条了。

那么我们的重点就是获得这个m+1为的值,方法如下

e.hash & oldCap

至此,我们对扩容已经有了一个深入的了解。关于HashMap的树化,已经树化后扩容的移动问题,我们将在下一篇中介绍。

, 1, 0, 9);