HashMap实现原理
HashMap也是我们使用非常多的Collection,它是基于哈希表的 Map 接口的实现,以key-value的形式存在。在HashMap中,key-value总是会当做一个整体来处理,系统会根据hash算法来来计算key-value的存储位置,我们总是可以通过key快速地存、取value。下面就来分析HashMap的存取。
定义 HashMap实现了Map接口,继承AbstractMap。其中Map接口定义了键映射到值的规则,而AbstractMap类提供 Map 接口的骨干实现,以最大限度地减少实现此接口所需的工作,其实AbstractMap类已经实现了Map。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public class HashMap <K,V> extends AbstractMap <K,V> implements Map <K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L ; static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ; static final int MAXIMUM_CAPACITY = 1 << 30 ; static final float DEFAULT_LOAD_FACTOR = 0.75f ; static final int TREEIFY_THRESHOLD = 8 ; static final int UNTREEIFY_THRESHOLD = 6 ; static final int MIN_TREEIFY_CAPACITY = 64 ; transient Node<K,V>[] table; transient Set<Map.Entry<K,V>> entrySet; transient int size; transient int modCount; int threshold; final float loadFactor; }
这里讲讲为什么默认容量大小为16,负载因子为0.75,主要原因是这两个常量的值都是经过大量的计算和统计得出来的最优解,仅仅是这样而已。
构造函数 HashMap提供了三个构造函数:
HashMap():构造一个具有默认初始容量 (16) 和默认负载因子 (0.75) 的空 HashMap。
1 2 3 4 public HashMap () { this .loadFactor = DEFAULT_LOAD_FACTOR; }
HashMap(int initialCapacity):构造一个带指定初始容量和默负载因子 (0.75) 的空 HashMap。
1 2 3 public HashMap (int initialCapacity) { this (initialCapacity, DEFAULT_LOAD_FACTOR); }
HashMap(int initialCapacity, float loadFactor):构造一个带指定初始容量和负载因子的空 HashMap。
初始化
调用构造方法进行初始化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 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); }
在这里提到了两个参数:初始容量,负载因子。这两个参数是影响HashMap性能的重要参数,其中容量表示哈希表中桶的数量,初始容量是创建哈希表时的容量,负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。系统默认负载因子为0.75,一般情况下我们是无需修改的。
tableSizeFor
根据参数返回最近的2的n次幂的大小
1 2 3 4 5 6 7 8 9 10 11 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 ; }
这种方法的效率非常高,可见Java8对容器优化了很多
内部数据结构 Node
Node是 HashMap的静态内部,HashMap主干是一个Node数组,Node是HashMap的最基本组成单位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 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 ; } }
在jdk8之前HashMap是数组加链表的形式实现,但是在1.8之后为提高哈希冲突后链表的查询速度,当桶内链表长度超过树化阀值 且总长度超过最小树化容量 后会将链表转换为红黑树。
速度 查询与修改 先用散列函数对键进行散列,没有冲突的情况下查询是下标查询,时间复杂度是 O(1),速度很快。
存在哈希冲突的情况,需要对链表/红黑树进行遍历,equals比对查询。
性能上,考虑是链表/红黑树上的元素越是越好,越均匀越好;此外HashMap主干未必越长越好,会有用不到的桶浪费空间。
增加与删除 由于查询速度快,而桶里用链表/红黑树实现,所以添加和删除效率也很高。HashMap会在size超过阀值后进行调整大下(resize),所以根据具体情况提前给HashMap一个合适的初始长度是个不错的习惯。
put方法
put方法是一个重点方法,这里有 HashMap初始化,数据在 HashMap中是如何储存的,什么情况下链表会转换为红黑树等内容,需要仔细研究。
1 2 3 4 5 6 7 8 9 10 11 public V put (K key, V value) { return putVal(hash(key), key, value, false , true ); }
putVal 方法
putVal是final修饰的方法,子类 LinkedHashMap也是用的这各方法,evict(看下面的的第5个参数)就是给 LinkedHashMap使用的,HashMap中并没有什么用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 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 ) { n = (tab = resize()).length; } if ((p = tab[i = (n - 1 ) & hash]) == null ) { tab[i] = newNode(hash, key, value, null ); } else { 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 ) { 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 ) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null ) { e.value = value; } afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) { resize(); } afterNodeInsertion(evict); return null ; }
hash 方法 1 2 3 4 5 6 7 8 9 10 11 12 13 static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
为什么要使用异或运算
这是因为找key的位置时,(n - 1) & hash
是table的索引,n的长度不够大时,只和hashCode()的低16位有关,这样发生冲突的概率就变高。
为减少这种影响,设计者权衡了speed, utility, and quality,将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了,而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下,既减少了系统的开销,也不会造成的因为高16位没有参与下标的计算(table长度比较小时)而引起的碰撞。
resize方法
这也是一个很重要的方法,主要包括两部分,第一部分是根据size是否超过阀值判断是否需要进行扩容,第二部分是扩容后将原Node[]中数据复制到扩容后的Node[]中
扩容的三种情况
使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table,并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold,接着threshold = 当前的容量(threshold) * DEFAULT_LOAD_FACTOR。
HashMap不是第一次扩容。如果HashMap已经扩容过的话,那么每次table的容量以及threshold量为原有的两倍
这边也可以引申到一个问题就是HashMap是先插入数据再进行扩容的,但是如果是刚刚初始化容器的时候是先扩容再插入数据。
扩容部分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 final Node<K, V>[] resize() { 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 ; } } else if (oldThr > 0 ) { newCap = oldThr; }else { 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;
复制数据部分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 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;
复制过程,a过去,假设计算后位置不边,进到i,此时i为null,a进去后即是head,又是tail
然后循环,到b,假设计算后还是i,i中已经有a,所以b直接丢到a后面,a任是head,单tail已经变成了b
以此类推,a,b,c,d都会放在i,j中
其实是先拼完链表才装进桶里的,这里只是方便描述,说成是一个一个过去
至此,put方法已经说完了,重点是putVal,hash和resize三个方法。
get方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public V get (Object key) { Node<K, V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
其最终是调用了 getNode
函数。 其逻辑如下
getNode方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 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 && ((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 ; }
remove 方法
remove就是先找到节点位置,然后移除,核心方法是removeNode()
1 2 3 4 5 6 7 8 9 10 public V remove (Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null , false , true )) == null ? null : e.value; }
removeNode 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 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; 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 ); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) { ((TreeNode<K, V>) node).removeTreeNode(this , tab, movable); } else if (node == p) tab[index] = node.next; else { p.next = node.next; } ++modCount; --size; afterNodeRemoval(node); return node; } } return null ; }
总结 我们现在可以回答开始的几个问题,加深对HashMap的理解:
1.什么时候会使用HashMap?他有什么特点?
是基于Map接口的实现,存储键值对时,它可以接收null的键值,是非同步的,HashMap存储着Entry(hash, key, value, next)对象。
2.你知道HashMap的工作原理吗?
通过hash的方法,通过put和get存储和获取对象。存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。
3.你知道get和put的原理吗?equals()和hashCode()的都有什么作用?
通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点
4.你知道hash的实现吗?为什么要这样实现?
在Java 1.8的实现中,是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。
5.如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
如果超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法。 关于Java集合的小抄中是这样描述的: 以Entry[]数组实现的哈希桶数组,用Key的哈希值取模桶数组的大小可得到数组下标。 插入元素时,如果两条Key落在同一个桶(比如哈希值1和17取模16后都属于第一个哈希桶),Entry用一个next属性实现多个Entry以单向链表存放,后入桶的Entry将next指向桶当前的Entry。 查找哈希值为17的key时,先定位到第一个哈希桶,然后以链表遍历桶里所有元素,逐个比较其key值。 当Entry数量达到桶数量的75%时(很多文章说使用的桶数量达到了75%,但看代码不是),会成倍扩容桶数组,并重新分配所有原来的Entry,所以这里也最好有个预估值。 取模用位运算(hash & (arrayLength-1))会比较快,所以数组的大小永远是2的N次方, 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。 iterator()时顺着哈希桶数组来遍历,看起来是个乱序。
6.当两个对象的hashcode相同会发生什么?
因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。
7.如果两个键的hashcode相同,你如何获取值对象?
找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。因此,设计HashMap的key类型时,如果使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择
8.如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置
9.你了解重新调整HashMap大小存在什么问题吗?
当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。因此在并发环境下,我们使用CurrentHashMap来替代HashMap
10.为什么String, Interger这样的wrapper类适合作为键?
因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能