Android--HashMap原理

threshold 阈值，没有阀值的说法（各行各业都没有阀值，只有阈值）。当 HashMap 存储的数据量超过 threshold 时，就会触发扩容。

关于扩容：
面试官：”准备用HashMap存1w条数据，构造时传10000会触发扩容吗？“

关于Hashtable和ConcurrentHashMap：
面试中的HashMap、ConcurrentHashMap和Hashtable，你知道多少？

关于红黑树：
什么是红黑树？

HashMap的长度为什么设置为2的n次方

为什么HashMap 初始化时，指定集合初始值大小?
说明：HashMap 使用 HashMap(int initialCapacity) 初始化，如果暂时无法确定集合大小，那么指定默 认值（16）即可。

正例：initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子（即 loader factor）默认 为 0.75，如果暂时无法确定初始值大小，请设置为 16（即默认值）。

反例： HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素增加而被迫不断扩容， resize()方法总共会调用 8 次，反复重建哈希表和数据迁移。当放置的集合元素个数达千万级时会影响程序 性能。

一、HashMap数据结构

Hash表融合了二者的优点，如下：

二、源码分析

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);}

构造方法一共重载了四个，主要初始化了三个参数：

1、initialCapacity 初始容量（默认16）：hashMap底层由数组实现+链表（或红黑树）实现，但是还是从数组开始，所以当储存的数据越来越多的时候，就必须进行扩容操作，如果在知道需要储存数据大小的情况下，指定合适的初始容量，可以避免不必要的扩容操作，提升效率。

2、threshold 阈值：hashMap所能容纳的最大价值对数量，如果超过则需要扩容，计算方式：threshold=initialCapacity*loadFactor（构造方法中直接通过tableSizeFor(initialCapacity)方法进行了赋值，主要原因是在构造方法中，数组table并没有初始化，put方法中进行初始化，同时put方法中也会对threshold进行重新赋值，这个会在后面的源码中进行分析）

3、loadFactor 加载因子（默认0.75）：当负载因子较大时，去给table数组扩容的可能性就会少，所以相对占用内存较少（空间上较少），但是每条entry链上的元素会相对较多，查询的时间也会增长（时间上较多）。反之就是，负载因子较少的时候，给table数组扩容的可能性就高，那么内存空间占用就多，但是entry链上的元素就会相对较少，查出的时间也会减少。所以才有了负载因子是时间和空间上的一种折中的说法。所以设置负载因子的时候要考虑自己追求的是时间还是空间上的少。（一般情况下不需要设置，系统给的默认值已经比较适合了）

我们最常使用的是无参构造，在这个构造方法里面仅仅设置了加载因子为默认值，其他两个参数会在resize方法里面进行初始化，在这里知道这个结论就可以了，下面会在源码里面进行分析；另外一个带有两个参数的构造方法，里面对初始容量和阈值进行了初始化，对阈值的初始化方法为 tableSizeFor(int cap),看一下源码：

public HashMap(int initialCapacity, float loadFactor) {/*** 找到大于或等于 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;}

接下来分析一下这个方法，对于无符号右移运算符不了解的，可以看一下这篇文章了解一下（https://www.jianshu.com/p/927009730809），以10为例进行分析：

另外，需要注意一下的是，第一步 int n = cap - 1; 这个操作，执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下，经过运算后得到的结果是cap的二倍的结果，例如如果n为l6，经过一系列运算之后，得到的结果是0001 1111，此时最后一步n+1 执行之后，就会返回32，有兴趣的可以自己进行尝试；

put方法
在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 1sttreeifyBin(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 keyV 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方法分为三种情况：
1、table尚未初始化，对数据进行初始化
2、table已经初始化，且通过hash算法找到下标所在的位置数据为空,直接将数据存放到指定位置
3、table已经初始化，且通过hash算法找到下标所在的位置数据不为空，发生hash冲突（碰撞），发生碰撞后，会执行以下操作：
（1）判断插入的key如果等于当前位置的key的话，将 e 指向该键值对
（2）如果此时桶中数据类型为 treeNode，使用红黑树进行插入
（3）如果是链表，则进行循环判断， 如果链表中包含该节点，跳出循环，如果链表中不包含该节点，则把该节点插入到链表末尾，同时，如果链表长度超过树化阈值（TREEIFY_THRESHOLD）且table容量超过最小树化容量（MIN_TREEIFY_CAPACITY），则进行链表转红黑树（由于table容量越小，越容易发生hash冲突，因此在table容量TREEIFY_THRESHOLD,会优先选择扩容，否则会进行链表转红黑树操作）

首先分析table尚未初始化的情况：

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已经初始化，且容量 > 0if (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 thresholdnewCap = oldThr;//3 threshold 和 table 皆未初始化情况，此处即为首次进行初始化//也就在此处解释了构造方法中没有对threshold 和 初始容量进行赋值的问题else {               // zero initial threshold signifies using defaults//如果阈值为零，表示使用默认的初始化值//这种情况在调用无参构造的时候会出现，此时使用默认的容量和阈值newCap = DEFAULT_INITIAL_CAPACITY;//此处阈值即为 threshold=initialCapacity*loadFactornewThr = (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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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方法逻辑比较复杂，需要静下心来一步步的分析，但是总的下来，分为以下几步：

1、首先先判断当前table是否进行过初始化，如果没有进行过初始化，此处就解决了调用无参构造方法时候，threshold和initialCapacity 未初始化的问题，如果已经初始化过了，则进行扩容，容量为原来的二倍

2、扩容后创建新的table，并对所有的数据进行遍历
（1）如果新计算的位置数据为空，则直接插入
（2）如果新计算的位置为链表，则通过hash算法重新计算下标，对链表进行分组
（3）如果是红黑树，则需要进行拆分操作

get方法，查找

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来说，逻辑实在是简单太多了

1、根据hash值查找到指定位置的数据2、校验指定位置第一个节点的数据是key是否为传入的key，如果是直接返回第一个节点，否则继续查找第二个节点3、如果数据是TreeNode（红黑树结构），直接通过红黑树查找节点数据并返回4、如果是链表结构，循环查找所有节点，返回数据5、如果没有找到符合要求的节点，返回null

在这个方法里面，需要注意的有两个地方：hash（key）和hash的取模运算 (n - 1) & hash

hash（key）的源码

 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

这段代码叫做扰动函数，也是hashMap中的hash运算，主要分为下面几步：
1、 key.hashCode()，获取key的hashCode值，如果不进行重写的话返回的是根据内存地址得到的一个int值

2、key.hashCode() 获取到的hashcode无符号右移16位并和元hashCode进行^ ，这样做的目的是为了让高位与低进行混合，让两者都参与运算，以便让hash值分布更加均匀

取模运算 (n - 1) & 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哈希算法引出的求余%和与运算&转换问题

https://www.cnblogs.com/ysocean/p/9054804.html

remove方法，删除

了解完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（）来判断的，由于篇幅原因就不一一介绍。

另外，中间有很部分不影响逻辑理解的代码被一笔带过，比如 红黑树的转化，查找，删除等操作，有兴趣的可以自己进行学习，不过还有一些其他的特性需要提醒一下

最后总结一下：

1、HashMap 底层数据结构在JDK1.7之前是由数组+链表组成的，1.8之后又加入了红黑树；链表长度小于8的时候，发生Hash冲突后会增加链表的长度，当链表长度大于8的时候，会先判读数组的容量，如果容量小于64会先扩容（原因是数组容量越小，越容易发生碰撞，因此当容量过小的时候，首先要考虑的是扩容），如果容量大于64，则会将链表转化成红黑树以提升效率

2、hashMap 的容量是2的n次幂，无论在初始化的时候传入的初始容量是多少，最终都会转化成2的n次幂，这样做的原因是为了在取模运算的时候可以使用&运算符，而不是%取余，可以极大的提上效率，同时也降低hash冲突

3、HashMap是非线程安全的，在多线程的操作下会存在异常情况（如形成闭环（1.7），1.8已修复闭环问题，但仍不安全），可以使用HashTable或者ConcurrentHashMap进行代替

参考文章：

https://juejin.im/post/6844903799748821000

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！