我的所有原创Android常识体系,已打包整顿到GitHub.致力打造一系列适宜初中高级工程师可能看得懂的优质文章,欢送star~
1. 存储构造
1.1 JDK 1.7
外部是以数组的模式存储了Entry对象,而每个Entry对象外面有key和value用来存值.它外面蕴含了key、value、next、hash四个字段,其中next字段是用来援用下一个Entry的(雷同的hash值会被放入同一个链表中).数组中的每个地位都是一条单链表(也能够称之为桶),数组中的元素的表头.解决抵触的形式是拉链法,同一条单链表中的Entry的hash值是雷同的.
transient Entry<K,V>[] table;static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash;}1.2 JDK 1.8
存储构造也是数组,只不过将Entry换了个名字叫Node.1.7中hash值雷同的是放单链表中,1.8也是,当这个单链表的长度超过8时,会转换成红黑树,减少查找效率.
2. 基本概念
2.1 负载因子和阈值
/** * The default initial capacity - MUST be a power of two. */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** * The load factor used when none specified in constructor. */static final float DEFAULT_LOAD_FACTOR = 0.75f;HashMap的默认大小是16,默认负载因子是0.75,意思是当存的元素个数超过16*0.75时就要对数组扩容,这里的阈值就是16*0.75=12.负载因子就是用来管制什么时候进行扩容的.
阈值 = 以后数组长度*负载因子
每次扩容之后都得从新计算阈值.默认的数组长度是16,默认的负载因子是0.75这些都是有考究的.在元素个数达到数组的75%时进行扩容是一个比拟折中的临界点,如果定高了的话hash抵触就很重大,桶就会很深,查找起来比较慢,定低了又节约空间.个别状况下,还是不会去定制这个负载因子.
ps: 到底是阀值还是阈值,傻傻分不清,,,,知乎上有个对于这个问题的探讨 - 「阀值」是否为「阈值」的误笔？
2.2 拉链法工作原理
每次新存入一个新的键值对时,首先计算Entry的hashCode,用hashCode%数组长度失去所在桶下标,而后在桶内顺次查找是否已存在该元素,存在则更新,不存在则插入到桶的头部.
3. 源码剖析
3.1 JDK 1.7
有了下面的根底概念,上面开始看源码学习
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{ //默认初始容量,必须是2的幂 这里的值是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //默认的负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的空数组 static final Entry<?,?>[] EMPTY_TABLE = {}; //用来盛放实在数据的数组 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //以后HashMap的实在键值对数量 transient int size; //阈值 = 数组长度*负载因子 int threshold; //负载因子 final float loadFactor; //标识对该HashMap进行构造批改的次数,构造批改是指增删改或其余批改其内部结构(例如rehash)的次数. //用于迭代器疾速失败. transient int modCount; public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //能够同时制订数组大小和负载因子 public HashMap(int initialCapacity, float loadFactor) { ...//省略局部逻辑判断 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; ... this.loadFactor = loadFactor; threshold = initialCapacity; ... } static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; } }3.1.1 put
下面是HashMap的一些根本属性,都是绝对比拟重要的.接着咱们来看一下增加元素put办法的实现,以下是JDK 1.7的put代码
public V put(K key, V value) { //1. 数组为空 -> 初始化(创立)数组 if (table == EMPTY_TABLE) { inflateTable(threshold); } //2. key为null,独自解决 if (key == null) return putForNullKey(value); //3. 计算hash值 int hash = hash(key); //4. 计算该hash值该寄存在数组的哪个索引处 int i = indexFor(hash, table.length); //5. 遍历链表(数组的每个元素都是单链表的表头) 查找链表中是否已存在雷同的key 如果有,则替换掉 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //6. 增加元素到数组中 addEntry(hash, key, value, i); return null;}3.1.1.1 inflateTable 数组初始化
简简单单几句代码波及的货色缺特地多,咱们一一来解读一下.首先是初始化数组inflateTable办法,传入的是阈值.
private void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity);}private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}//Integer.highestOneBitpublic static int highestOneBit(int var0) { //求掩码 var0 |= var0 >> 1; var0 |= var0 >> 2; var0 |= var0 >> 4; var0 |= var0 >> 8; var0 |= var0 >> 16; //>>>：无符号右移。无论是负数还是正数，高位统统补0. 这里减了之后只剩下最高位为1 return var0 - (var0 >>> 1);}roundUpToPowerOf2办法是为了求一个比number大一点的2的幂次方的数,这里的代码看起来有点迷.它最初会求出数组应该初始化的长度,它能够主动将传入的容量转换为2的n次方.
Integer.highestOneBit是取传入的这个数的二进制模式最右边的最高一位且高位前面全副补零,最初返回int类型的后果.比方传入的是7(0111),则最初失去的是4(0100).它这里先将number-1,而后再左移一位,比方number是9,则number-1等于8(1000),左移一位等于10000就是16.这样最初它就将传入的容量转换为了2的n次方.
计算好了容量之后,计算阈值,而后初始化数组.
3.1.1.2 putForNullKey 增加null key
用了一个专门的办法用来操作key为null的状况
/** * Offloaded version of put for null keys */private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null;}将元素寄存到了数组的第一个地位.第一个地位也是一个桶,这桶外面只有一个元素的key能够是null,其余元素都是被hash算法调配到这里来的.
3.1.1.3 计算hash值
/** * Retrieve object hash code and applies a supplemental hash function to the * result hash, which defends against poor quality hash functions. This is * critical because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}获取到了key的hashCode之后,又进行了一些骚操作,这里的hash算法设计得很神,这里的hash算法设计得好的话,则会大大减少hash抵触.
3.1.1.4 indexFor 计算元素在数组中的索引
/** * Returns index for hash code h. */static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1);}用hash值按位与数组长度-1,相当于 h % length.&运算比%效率高,所以这里是&运算来进行.为什么h & (length-1) = h % length ? 这其实与length无关,length下面说过,必须是2的幂.咱们简略举个例子,h=2,length=8.
h & (length-1)= 00000010 & 00000111= 00000010下面的最初后果是2 , 2 % 8 的确是等于2,验证结束.
3.1.1.5 addEntry 增加元素到数组中
增加元素的时候可能之前这个地位是空桶,也可能之前这里的桶曾经有元素存在了(hash抵触了).
/** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */void addEntry(int hash, K key, V value, int bucketIndex) { //1. 键值对数量超过阈值 && 该索引处数组不为空(阐明这里之前曾经存在元素) if ((size >= threshold) && (null != table[bucketIndex])) { //扩容->原来的2倍 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } //2. 创立Entry节点 createEntry(hash, key, value, bucketIndex);}//创立新的节点 void createEntry(int hash, K key, V value, int bucketIndex) { //table[bucketIndex] 是放到新插入节点的前面,,所以这里是头插法 Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++;}键值对超过阈值就会扩容
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //依据新的容量创立数组 Entry[] newTable = new Entry[newCapacity]; //转移数据到新数组 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; //更新阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}//转移数据到新数组void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { //元素非空 则转移 while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } //依据该节点hash值计算一下该节点该放到新数组的哪个索引处 int i = indexFor(e.hash, newCapacity); //将桶内元素一一转移到新的数组的新的索引处 //留神: 这里桶内程序会倒过去. //比方桶内是1->2->3 转移数据之后就是3->2->1 e.next = newTable[i]; newTable[i] = e; e = next; } }}扩容之后就波及到数据的迁徙,迁徙的时候须要从新计算节点在新数组中的地位,迁徙实现还得更新一下阈值.
JDK 1.7中的put操作就是这些啦,货色还挺多的. 最外围的也就是put局部的代码,get的话比较简单这里就不做剖析了.
3.2 JDK 1.8
基本上思路是差不多的,也是用数组+链表(or 红黑树)来装数据.
transient Node<K,V>[] table;//链表长度超过8且数组长度大于64,则将链表转换成红黑树static final int TREEIFY_THRESHOLD = 8;//在1.8中节点改名字了.. 改成了Nodestatic class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;}来看看它的put办法是怎么实现的
3.2.1 put
1.8的put办法略微比1.7的看起来简单些,然而不必怕,咱们一句一句的剖析
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}/** * Implements Map.put and related methods. * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //1. table为空表时,创立数组 初始化. resize既是初始化也是扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //2. 依据hash和数组长度求出元素应该在数组中的索引地位,如果此处为空则将节点放到这里 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //3. 该索引处曾经有节点存在且hash值和key都相等(须要替换value),则记录下该索引处的节点援用 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //4. 如果该索引处是红黑树,则将节点插入到树中 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //5. 该索引处是链表 else { //5.1 顺次遍历链表 for (int binCount = 0; ; ++binCount) { //5.2 找到链表尾部,将节点插入到尾部 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果链表长度超过8,则转换成红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //5.3 找到key相等的了,则完结for循环,已在链表中找到须要替换value的节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //6. 替换原来的值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //7. 超过阈值,则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;}正文写得比拟具体,这里与1.7的区别还是挺大的.
- Java7中将节点插入链表是头插法,而Java8是尾插法
- Java8中链表超过8且数组长度大于64则会将链表树化
- Java7将key为null的独自解决,Java8没有独自解决(尽管它们的hash都是0,都是放数组第0处)
3.2.1.1 resize 扩容
首先来关注外围代码,扩容.
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */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) { //老数组长度大于MAXIMUM_CAPACITY,则将阈值设置成Integer.MAX_VALUE 不扩容了.. //个别状况下,不会走到这个逻辑分支外面去 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //1. 扩容: 将数组长度*2 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //阈值也是*2 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults //2. 初始化数组 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) { //3. 遍历旧数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //3.1 该索引处 桶内只有一个元素,依据该节点的hash和新数组长度求出该节点在新数组中的地位,而后搁置到新数组中 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //3.2 该索引处为红黑树 独自解决 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //3.3 该索引处为单链表(链表长度小于8) else { // preserve order //不必移动地位的链表,hash值&老数组长度为0,loHead为头部,loTail为尾部 Node<K,V> loHead = null, loTail = null; //须要移动地位的链表,hash值&老数组长度为1,hiHead为头部,hiTail为尾部 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //hash值&老数组长度 // 其实就是求最高位是0还是1,是0则放弃原地位不动;是1则须要挪动到 j + oldCap 处 //每条链表都被扩散成2条,更扩散 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; } //这些元素挪动到了 老索引地位+oldCap 处 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}resize的货色比拟杂,即蕴含了初始化数组,也蕴含了扩容的逻辑.初始化数组比较简单,咱间接看一下扩容局部逻辑.首先是遍历原数组,此时原数组的每个索引处可能存在3种状况
- 该索引处桶内只有一个元素->依据该节点的hash和新数组长度求出该节点在新数组中的地位,而后搁置到新数组中
- 该索引处为红黑树->独自解决
- 该索引处链表长度大于1,小于8
第3种状况比较复杂,这里独自剖析一下.
剖析前咱们来看个货色,假如数组长度n=16,那么依据put局部的代码,存入数组时索引是(16 - 1) & hash,这里有2个元素key1和key2,它们的hash值别离为5和21.上面是它们的计算过程
key1:00001111 & 00000101 = 5key2:00001111 & 00010101 = 5当数组扩容,n=32
key1:00011111 & 00000101 = 00101 = 5key2:00011111 & 00010101 = 10101 = 5 + 16 = 21扩容后n-1比以前多了1个1,这样会导致按位与的时候key2的地位变成了原地位+16的地位.因为咱们应用的是2次幂的扩大,所以元素的地位要么在原地位,要么在原地位+2次幂的地位.
有了下面的剖析之后,再回到咱们3.3处的逻辑
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;}e.hash & oldCap: 用元素hash值与上老数组长度,假如之前数组长度是16,那么这里就是按位与10000,而平时put的时候算索引是按位与(n-1)也就是1111.扩容之后,在put的时候就得按位与11111.因而它这里只是想看看hash值新增的那个bit是1还是0.如果是0则保留老地位,是1的话则在老地位的根底上加老数组长度才是新的地位.
为什么要这么干? 次要是计算简略,不须要像JDK 1.7那样还须要从新计算hash.还有就是让元素更扩散.原本原来是一条链上的,当初在2条链上(不同的数组索引处)了,查找更快了.
须要留神的一个小点就是,这里是尾插法且还是原来的程序,而JDK 1.7是头插法且程序与想来相同.
扩容的内容大略就是这些,略微有点多.
4. 相干知识点
4.1 HashMap 1.7和1.8区别
- JDK1.7用的是头插法,JDK1.8及置换是尾插法. 且1.7插入时候程序是与原来相同的,而1.8则还是原来的程序
- JDK1.7是数组+链表,JDK1.8是数组+链表+红黑树
- JDK1.7在插入数据之前进行扩容,JDK1.8是插入数据之后才扩容
- JDK1.7是Entry来示意节点,而JDK1.8是Node
- JDK1.7扩容和后存储地位是用
hash & (length-1)计算来的,而JDK1.8只须要判断hash值新增参加运算的位是0还是1就能疾速计算出扩容后该放在原地位,还是须要放在 原地位+扩容的大小值 . - 计算hash值的时候,JDK1.7用了9次扰动解决,而JDK1.8是2次
ps: 红黑树查找元素,须要O（logn）的开销
4.2 Hashtable与HashMap的区别
- Hashtable不反对null键和值
- Hashtable应用synchronized来进行同步(有性能开销)
- Hashtable的迭代器是fail-fast迭代器
- Hashtable默认容量为11且不要求底层数组的容量肯定要是2的整数次幂,而HashMap则是16,必须是2的整数次幂.
HashMap是绝大部分利用键值对存取场景的首选.多线程环境下,举荐应用ConcurrentHashMap.
参考
- 图解HashMap(一)
- 图解HashMap(二)
- Java 容器
- openjdk汇合源码