Java-基础-HashMap Java-基础-HashMap

1. 简介 Java8 HashMap结构（数组 + 列表 + 红黑树）如图：

文章图片

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
2. 定义 2.1 主要属性

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { //序列号，序列化的时候使用。 private static final long serialVersionUID = 362498820763181265L; /**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量，2的30次方。 static final int MAXIMUM_CAPACITY = 1 << 30; //负载因子，用于扩容使用。 static final float DEFAULT_LOAD_FACTOR = 0.75f; //当某个桶节点数量大于8时，会转换为红黑树。 static final int TREEIFY_THRESHOLD = 8; //当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。 static final int UNTREEIFY_THRESHOLD = 6; //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。 static final int MIN_TREEIFY_CAPACITY = 64; //存储元素的数组，transient关键字表示该属性不能被序列化 transient Node[] table; //将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。 transient Set> entrySet; //元素数量 transient int size; //统计该map修改的次数 transient int modCount; //临界值，也就是元素数量达到临界值时，会进行扩容。 int threshold; //也是负载因子，只不过这个是变量。 final float loadFactor; }

2.2 构造方法
HashMap共有三个构造函数：

初始化一个默认容量=16，负载因子=0.75 的hashmap对象。

public HashMap() { // DEFAULT_LOAD_FACTOR = 0.75f this.loadFactor = DEFAULT_LOAD_FACTOR; }

初始化一个指定初始容量和负载因子-0.75 的hashmap对象。

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }

初始化一个指定初始容量和负载因子的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); }

2.3 node

Node是HashMap的静态内部类，HashMap主干是一个Node数组，Node是HashMap的最基本组成单位。

/** * HashMap 的Node 节点元素 * @param 元素的key * @param 元素的Value */ static class Node implements Map.Entry { // 这个节点所在位置的hash值 final int hash; //这个节点的Key final K key; //这个节点的value V value; //后继节点 Node next; //构造方法 Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = https://www.it610.com/article/value; this.next = next; }public final K getKey(){ return key; } public final V getValue(){ return value; } public final String toString() { return key +"=" + value; }/** * 获取HashCode * key和value 的hash做异或运算防止hash冲突 * @return */ public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }/** * 设置value * @param newValue * @return */ public final V setValue(V newValue) { V oldValue = https://www.it610.com/article/value; //替换当前node的value value = newValue; //返回旧的value return oldValue; }/** * equals 比较 * 如果 key和value都一致判断equals相等 * @param o * @return */ 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; } }

3. 初始容量负载因子上文中反复提到了两个参数：初始容量，负载因子。这两个参数是影响HashMap性能的重要参数。
容量：

transient Node[] table;

即 table的长度，初始容量是创建哈希表时的容量

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

即初始容量为 16。
负载因子：

 final float loadFactor;

容器进行初始化的时候会将值设置为0.75 ( 也就是初始可用的容量为：16 * 0.75 = 12，当容量达到12的时候就会进行扩容操作)，负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间使用程度，负载因子越大表示散列表的装填程度越高，反之越小。
为什么说容量和负载因子会影响 HashMap的性能？
我们在考虑HashMap的时候，首先要想到HashMap只是一个数据结构，既然是数据结构最主要的就是节省时间和空间。负载因子的作用肯定是节省时间和空间。为什么节省呢？

假设负载因子 = 1.0
HashMap是将key进行hash运算得到桶的位置（table的索引）的。既然是hash运算，那么Hash冲突是避免不了的。当负载因子是1.0的时候，意味着会出现大量的Hash冲突（因为要将整个table填满，并且为了将数均匀填充，jdk还使用了扰动函数，增加随机性），底层的红黑树会变的异常复杂。对查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。
假设负载因子 = 0.5
负载因子是0.5的时候，也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素好了，Hash冲突也会减少，那么底层的链表或者红黑树的高度就会降低。查询效率就会增加。但是，这时候空间利用率就会大大降低，显然也不太好。

总结：
? 默认容量 = 16，负载因子 = 0.75，这两个常量的值都是经过大量的计算和统计得出来的最优解。

当然如果知道自己的hashmap容量大小，尽量在初始化的时候就指定一下，可以避免扩容带来的性能损耗。但负载因子就别随意改了，毕竟是最优解。

4. 添加元素

put方法是一个重点方法，这里有hashmap的初始化，数据的在hashmap中是如何存储的，什么情况下会转换成红黑树等。

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }/** * putVal 方法真正进行插入操作的方法， * * @param hash传入key的哈希值 * @param key * @param value * @param onlyIfAbsent 如果该值是true,如果存在值就不会进行修改操作 * @param evictLinekdHashMap尾操作使用，这里暂无用途 * @return */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; /**********初始化********/// 如果table长度是0或table是null会调整一次大小 // 这时tab会指向调整大下后的Node[](主干数组) // n被赋值为新数组长度// 如果没有调整大小，tab指向table if ((tab = table) == null || (n = tab.length) == 0) { n = (tab = resize()).length; } /********开始查找键的位置，并存储value*******/ // i = (n - 1) & hash这个是获取key应该在哪个桶里,下面详说 // 这里将p指向当前key所需要的那个桶 if ((p = tab[i = (n - 1) & hash]) == null) { // 如果空桶，也就是无哈希冲突的情况，直接丢个Node进去。 // 此时的tab就是table tab[i] = newNode(hash, key, value, null); //存在冲突，开始寻找我们要找的节点 } else { Node e; K k; // 判断第一个节点是不是我们找的 // 此时k储存了 p.key if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { // hash值相等，key值相等，定位完成,是修改操作 // e来储存p这个节点，一会修改 e = p; // 判断是否是红黑树节点 } else if (p instanceof TreeNode) { // 是红黑树节点，存在就返回那个节点，不存在就返回null e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value); // 最终，是链表了，开始对链表遍历查找 } else { for (int binCount = 0; ; ++binCount) { // 上面知道第一个接点不是我们要的，直接获取下一个，并储存给e // 下一个是空，直接丢个Node在这里，然后p.next指向这里 // 这里下一个节点地址给了e if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // ！大于树化阀值，开始树化 // 注意-1是因为binCount是索引而不是长度 // 其实此时链表长度已经是7+1（索引） + 1（新进来的Node） // 已经大于树化阀值8，也就是说链表长度为8时是不会树化的 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //树化 treeifyBin(tab, hash); //加进去就跳出循环了 break; } // 下个节点有值，且是我们找的节点，跳出去 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { break; } //下一个节点不是我们找的节点继续编历 p = e; } } // 上面说了，这有修改操作e才能不是null if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; // 给e新值 if (!onlyIfAbsent || oldValue == null) { e.value = value; } // 这个是LinkedHashMap用的，HashMap里是个空实现 afterNodeAccess(e); // 修改就会把旧值返回去 return oldValue; } } /*********修改完成的后续操作**********/ // 修改次数加1 ++modCount; // 如果size大于阀值，会执行resize()方法调整大小 if (++size> threshold) { resize(); } // 这个是给LinkedHashMap用的，HashMap里也是个空实现 afterNodeInsertion(evict); // 添加成功返回null return null; }

hash方法扰动函数

/** * hash 运算 * @param key * @return */ static final int hash(Object key) { int h; /** *key是null就返回0，key不是null就先取hashCode（） *然后与这个hashCode（）无符号右移进行亦或运算 */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

看到了熟悉的hashCode，这就解释了为什么重写equals方法的时候，一定要重写hashCode方法，因为key是基于hashCode来处理的。

为什么获取了key的hashcode() 返回的int型的散列值还要异或（^）h >>> 16 呢？有什么用？
实质上是把一个数的低16位与它的高16位做异或运算，混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
**那为什么要增加低16位的随机性呢？ **
根本目的是为了增加散列表的装填程度，为了使数据分布的更均匀。
因为在找key的位置tab[i = (n - 1) & hash])，是通过(n - 1) & hash 计算索引位置的，而当n的长度不够大时，只和hashCode()的低16位有关。
这样做有几个好处：

&运算速度快，至少比%取模运算快
能保证索引值肯定在 capacity 中，不会超出数组长度
( n -1) & hash，当n为2次幂时，会满足一个公式：(n -1) & hash = hash % n

文章图片

5. 扩容方法扩容的三种情况：

使用默认构造方法初始化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量为原有的两倍

【Java-基础-HashMap】这边也可以引申到一个问题就是HashMap是先插入数据再进行扩容的，但是如果是刚刚初始化容器的时候是先扩容再插入数据。

5.1 扩容部分

/** * 扩容方法 * * @return */ final Node[] resize() { Node[] oldTab = table; // 原容量，table为null返回0，否则返回table长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //原始阈值 int oldThr = threshold; //新容量，新阈值 int newCap, newThr = 0; // table已经初始化，旧容量>0 if (oldCap > 0) { // 容量已经超过最大容量，直接返回去 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; // 2倍扩容后小于最大容量，并且原容量大于默认初始化容量(我还没想清楚为什么要大于默认初始容量) } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) { // 阀值加倍 newThr = oldThr << 1; // double threshold } // 原数组容量为0，未初始化，但阀值不为0 // 也就是构造方法里threshold = tableSizeFor(initialCapacity）这个步骤 } else if (oldThr > 0) { // initial capacity was placed in threshold newCap = oldThr; // 啥都没有，默认构造 }else {// zero initial threshold signifies using defaults 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;

5.2 复制数据部分

// 创建新的数组 Node[] newTab = (Node[]) new Node[newCap]; table = newTab; //开始复制数据 if (oldTab != null) { //开始遍历 for (int j = 0; j < oldCap; ++j) { Node 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) e).split(this, newTab, j, oldCap); //链表操作在下面 } else { // preserve order // 不是直接进行计算元素在新数组中的位置，而是原位置加原数组长度 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { // 把链表下一个节点放在 next里 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;