HashMap是Map中最为常用的一种,面试中也经常会被问到相关的问题。由于HashMap数据结构较为复杂,回答相关问题的时候往往不尽人意,尤其是在JDK1.8之后,又引入了红黑树结构,其数据结构变的更加复杂,本文就JDK1.8源码为例,对HashMap进行分析;
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; this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } 复制代码
构造方法一共重载了四个,主要初始化了三个参数:
我们最常使用的是无参构造,在这个构造方法里面仅仅设置了加载因子为默认值,其他两个参数会在resize方法里面进行初始化,在这里知道这个结论就可以了,下面会在源码里面进行分析; 另外一个带有两个参数的构造方法,里面对初始容量和阈值进行了初始化,对阈值的初始化方法为 tableSizeFor(int cap),看一下源码:
/** * 找到大于或等于 cap 的最小2的幂 */ 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; } 复制代码
第一次看大这个方法的时候,我当时的心情是:
接下来分析一下这个方法,对于无符号右移运算符不了解的,可以看一下这篇文章了解一下,下面偷一张图(真的是借别人的图,google搜索的,不知道是谁的,如果大佬觉得太可耻,私信我我删了他)以10为例进行分析:
另外,需要注意一下的是,第一步 int n = cap - 1; 这个操作,执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下,经过运算后得到的结果是cap的二倍的结果,例如如果n为l6,经过一系列运算之后,得到的结果是0001 1111,此时最后一步n+1 执行之后,就会返回32,有兴趣的可以自己进行尝试;
在hashMap源码中,put方法逻辑是最为复杂的,接下来先看一下源码:
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) //如果table尚未初始化,则此处进行初始化数组,并赋值初始容量,重新计算阈值 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) //通过hash找到下标,如果hash值指定的位置数据为空,则直接将数据存放进去 tab[i] = newNode(hash, key, value, null); else { //如果通过hash找到的位置有数据,发生碰撞 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果需要插入的key和当前hash值指定下标的key一样,先将e数组中已有的数据 e = p; else if (p instanceof TreeNode) //如果此时桶中数据类型为 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; } //如果链表中有新插入的节点位置数据不为空,则此时e 赋值为节点的值,跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //经过上面的循环后,如果e不为空,则说明上面插入的值已经存在于当前的hashMap中,那么更新指定位置的键值对 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //如果此时hashMap size大于阈值,则进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 复制代码
从代码看,put方法分为三种情况:
table尚未初始化,对数据进行初始化
table已经初始化,且通过hash算法找到下标所在的位置数据为空,直接将数据存放到指定位置
table已经初始化,且通过hash算法找到下标所在的位置数据不为空,发生hash冲突(碰撞),发生碰撞后,会执行以下操作:
首先分析table尚未初始化的情况:
n = (tab = resize()).length; 复制代码
从代码可以看出,table尚未初始化的时候,会调用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; //1、table已经初始化,且容量 > 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 } //2、阈值大于0 threshold 使用 threshold 变量暂时保存 initialCapacity 参数的值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //3 threshold 和 table 皆未初始化情况,此处即为首次进行初始化 //也就在此处解释了构造方法中没有对threshold 和 初始容量进行赋值的问题 else { // zero initial threshold signifies using defaults //如果阈值为零,表示使用默认的初始化值 //这种情况在调用无参构造的时候会出现,此时使用默认的容量和阈值 newCap = DEFAULT_INITIAL_CAPACITY; //此处阈值即为 threshold=initialCapacity*loadFactor newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // newThr 为 0 时,按阈值计算公式进行计算,容量*负载因子 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; //如果之前的数组桶里面已经存在数据,由于table容量发生变化,hash值也会发生变化,需要重新计算下标 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //如果指定下标下有数据 if ((e = oldTab[j]) != null) { //1、将指定下标数据置空 oldTab[j] = null; //2、指定下标只有一个数据 if (e.next == null) //直接将数据存放到新计算的hash值下标下 newTab[e.hash & (newCap - 1)] = e; //3、如果是TreeNode数据结构 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //4、对于链表,数据结构 else { // preserve order //如果是链表,重新计算hash值,根据新的下标重新分组 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; } 复制代码
resize方法逻辑比较复杂,需要静下心来一步步的分析,但是总的下来,分为以下几步:
put方法分析完成之后,剩下的就很简单了,先看一下源码:
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } 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) { //1、根据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) { //如果该节点为红黑树,则通过树进行查找 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; } 复制代码
get方法相对于put来说,逻辑实在是简单太多了
在这个方法里面,需要注意的有两个地方:hash(key)和hash的取模运算 (n - 1) & hash
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 复制代码
这段代码叫做扰动函数,也是hashMap中的hash运算,主要分为下面几步:
在hashMap的代码中,在很多地方都会看到类似的代码:
first = tab[(n - 1) & hash]) 复制代码
hash算法中,为了使元素分布的更加均匀,很多都会使用取模运算,在hashMap中并没有使用(n)%hash这样进行取模运算,而是使用(n - 1) & hash进行代替,原因是在计算机中,&的效率要远高于%;需要注意的是,只有容量为2的n次幂的时候,(n - 1) & hash 才能等效(n)%hash,这也是hashMap 初始化初始容量时,无论传入任何值,都会通过tableSizeFor(int cap) 方法转化成2的n次幂的原因,这种巧妙的设计真的很令人惊叹; 至于为什么只有2的n次幂才能这样进行取模运算,这里就不再详细叙述了,有兴趣的可以看一下一位大佬写的文章: 由HashMap哈希算法引出的求余%和与运算&转换问题
了解完get方法之后,我们再最后了解一下remove方法:
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; //根据key和key的hash值,查找到对应的元素 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } //如果查找的了元素node,移除即可 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { //如果是TreeNode,通过树进行移除 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //如果是第一个节点,移除第一个节点,将index下标的位置指向第二个节点 else if (node == p) tab[index] = node.next; else //如果不是链表的第一个节点,则移除该节点 p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; } 复制代码
从源码可以看出来,通过key找到需要移除的元素操作过程和get方法几乎一致,最后在查找到key对应的节点之后,根据节点的位置和类型,进行相应的移除操作就完成了,过程非常简单
到这里,hashMap的源码基本就解析完成了,其余的方法和源码逻辑相对非常简单,大部分还是使用上述代码来实现的,例如containsKey(jey),就是使用get方法中的getNode()来判断的,由于篇幅原因就不一一介绍。
另外,中间有很部分不影响逻辑理解的代码被一笔带过,比如 红黑树的转化,查找,删除等操作,有兴趣的可以自己进行学习,不过还有一些其他的特性需要提醒一下
最后总结一下: