共计 12133 个字符，预计需要花费 31 分钟才能阅读完成。
咱们最先苍老的不是模样，而是不顾一切的闯劲。有时候，要敢于背上超出本人意料的包袱，真的致力后，你会发现自己要比设想的优良很多。
HashMap 抵触的解决办法比拟考验一个开发者解决问题的能力。
下文给出 HashMap 抵触的解决办法以及原理剖析，无论是在面试问答或者理论应用中，应该都会有所帮忙
在 Java 编程语言中，最根本的构造就是两种，一种是数组，一种是模仿指针(援用)，所有的数据结构都能够用这两个根本构造结构，HashMap 也一样。
当程序试图 将多个 key-value 放入 HashMap 中时，以如下代码片段为例：
HashMap<String,Object> m=new HashMap<String,Object>();
m.put("a", "rrr1");
m.put("b", "tt9");
m.put("c", "tt8");
m.put("d", "g7");
m.put("e", "d6");
m.put("f", "d4");
m.put("g", "d4");
m.put("h", "d3");
m.put("i", "d2");
m.put("j", "d1");
m.put("k", "1");
m.put("o", "2");
m.put("p", "3");
m.put("q", "4");
m.put("r", "5");
m.put("s", "6");
m.put("t", "7");
m.put("u", "8");
m.put("v", "9");HashMap 采纳一种所谓的“Hash 算法”来决定每个元素的存储地位。当程序执行 map.put(String,Obect)办法 时，零碎将调用 String 的 hashCode() 办法失去其 hashCode 值——每个 Java 对象都有 hashCode() 办法，都可通过该办法取得它的 hashCode 值。失去这个对象的 hashCode 值之后，零碎会依据该 hashCode 值来决定该元素的存储地位。
源码如下:
public V put(K key, V value) {if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
// 判断以后确定的索引地位是否存在雷同 hashcode 和雷同 key 的元素，如果存在雷同的 hashcode 和雷同的 key 的元素，那么新值笼罩原来的旧值，并返回旧值。// 如果存在雷同的 hashcode，那么他们确定的索引地位就雷同，这时判断他们的 key 是否雷同，如果不雷同，这时就是产生了 hash 抵触。//Hash 抵触后，那么 HashMap 的单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链。// 零碎只能必须按程序遍历每个 Entry，直到找到想搜寻的 Entry 为止——如果恰好要搜寻的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），// 那零碎必须循环到最初能力找到该元素。if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
} 下面程序中用到了一个重要的外部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从下面程序中能够看出：当零碎决定存储 HashMap 中的 key-value 对时，齐全没有思考 Entry 中的 value，仅仅只是依据 key 来计算并决定每个 Entry 的存储地位。
这也阐明了后面的论断：咱们齐全能够 把 Map 汇合中的 value 当成 key 的从属，当零碎决定了 key 的存储地位之后，value 随之保留在那里即可。HashMap 程序通过我革新，我成心的结构出了 hash 抵触景象，因为 HashMap 的初始大小 16，然而我在 hashmap 外面放了超过 16 个元素，并且我屏蔽了它的 resize()办法。不让它去扩容。
这时 HashMap 的底层数组 Entry[] table 构造如下:
Hashmap 外面的 bucket 呈现了单链表的模式，散列表要解决的一个问题就是散列值的抵触问题，通常是两种办法：链表法和凋谢地址法。
- 链表法就是将雷同 hash 值的对象组织成一个链表放在 hash 值对应的槽位；
- 凋谢地址法是通过一个探测算法，当某个槽位曾经被占据的状况下持续查找下一个能够应用的槽位。
java.util.HashMap 采纳的链表法的形式，链表是单向链表。造成单链表的外围代码如下：
void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
} 下面办法的代码很简略，但其中蕴含了一个设计：零碎总是将新增加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处曾经有了一个 Entry 对象，那新增加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象，也就是下面程序代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。
HashMap 外面没有呈现 hash 抵触时，没有造成单链表时，hashmap 查找元素很快,get()办法可能间接定位到元素，然而呈现单链表后，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，零碎只能必须按程序遍历每个 Entry，直到找到想搜寻的 Entry 为止——如果恰好要搜寻的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那零碎必须循环到最初能力找到该元素。
当创立 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是工夫和空间老本上一种折衷：增大负载因子能够缩小 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会减少查问数据的工夫开销，而查问是最频繁的的操作（HashMap 的 get() 与 put() 办法都要用到查问）；减小负载因子会进步数据查问的性能，但会减少 Hash 表所占用的内存空间。
一、HashMap 概述
HashMap 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并容许应用 null 值和 null 键。（除了不同步和容许应用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保障映射的程序，特地是它不保障该程序恒久不变。
值得注意的是 HashMap 不是线程平安的，如果想要线程平安的 HashMap，能够通过 Collections 类的静态方法 synchronizedMap 取得线程平安的 HashMap。
Map map = Collections.synchronizedMap(new HashMap());二、HashMap 的数据结构
HashMap 的底层次要是基于数组和链表来实现的，它之所以有相当快的查问速度次要是因为它是通过计算散列码来决定存储的地位。HashMap 中次要是通过 key 的 hashCode 来计算 hash 值的，只有 hashCode 雷同，计算出来的 hash 值就一样。如果存储的对象对多了，就有可能不同的对象所算进去的 hash 值是雷同的，这就呈现了所谓的 hash 抵触。学过数据结构的同学都晓得，解决 hash 抵触的办法有很多，HashMap 底层是 通过链表来解决 hash 抵触 的。
图中，紫色局部即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决抵触的，如果不同的 key 映射到了数组的同一地位处，就将其放入单链表中。
咱们看看 HashMap 中 Entry 类的代码：
/** Entry 是单向链表。* 它是“HashMap 链式存储法”对应的链表。* 它实现了 Map.Entry 接口，即实现 getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
**/
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
// 指向下一个节点
Entry<K, V> next;
final int hash;
// 构造函数。// 输出参数包含 "哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {return key;}
public final V getValue() {return value;}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判断两个 Entry 是否相等
// 若两个 Entry 的“key”和“value”都相等，则返回 true。// 否则，返回 false
public final boolean equals(Object o) {if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
// 实现 hashCode()
public final int hashCode() {return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
public final String toString() {return getKey() + "=" + getValue();}
// 当向 HashMap 中增加元素时，绘调用 recordAccess()。// 这里不做任何解决
void recordAccess(HashMap<K, V> m) { }
// 当从 HashMap 中删除元素时，绘调用 recordRemoval()。// 这里不做任何解决
void recordRemoval(HashMap<K, V> m) {}}HashMap 其实就是一个 Entry 数组，Entry 对象中蕴含了键和值，其中 next 也是一个 Entry 对象，它就是用来解决 hash 抵触的，造成一个链表。
三、HashMap 源码剖析
1、要害属性
先看看 HashMap 类中的一些要害属性：
transient Entry[] table;// 存储元素的实体数组
transient int size;// 寄存元素的个数
int threshold; // 临界值 当理论大小超过临界值时，会进行扩容 threshold = 加载因子 * 容量
final float loadFactor; // 加载因子
transient int modCount;// 被批改的次数其中 loadFactor 加载因子是示意 Hsah 表中元素的填满的水平.
若: 加载因子越大, 填满的元素越多, 益处是, 空间利用率高了, 但: 抵触的机会加大了. 链表长度会越来越长, 查找效率升高。反之, 加载因子越小, 填满的元素越少, 益处是: 抵触的机会减小了, 但: 空间节约多了. 表中的数据将过于稠密（很多空间还没用，就开始扩容了）
抵触的机会越大, 则查找的老本越高.
因而,必须在 “ 抵触的机会 ” 与 ” 空间利用率 ” 之间寻找一种均衡与折衷. 这种均衡与折衷实质上是数据结构中有名的 ” 时 - 空 ” 矛盾的均衡与折衷.
如果机器内存足够，并且想要进步查问速度的话能够将加载因子设置小一点；相同如果机器内存缓和，并且对查问速度没有什么要求的话能够将加载因子设置大一点。不过个别咱们都不必去设置它，让它取默认值 0.75 就好了。
2、构造方法
上面看看 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);
// Find a power of 2 >= initialCapacity
int capacity = 1; // 初始容量
while (capacity < initialCapacity) // 确保容量为 2 的 n 次幂，使 capacity 为大于 initialCapacity 的最小的 2 的 n 次幂
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int) (capacity * loadFactor);
table = new Entry[capacity];
init();}
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();}咱们能够看到在结构 HashMap 的时候如果咱们指定了加载因子和初始容量的话就调用第一个构造方法，否则的话就是用默认的。默认初始容量为 16，默认加载因子为 0.75。咱们能够看到下面代码中 13-15 行，这段代码的作用是确保容量为 2 的 n 次幂，使 capacity 为大于 initialCapacity 的最小的 2 的 n 次幂，至于为什么要把容量设置为 2 的 n 次幂，咱们等下再看。
重点剖析下 HashMap 中用的最多的两个办法 put 和 get
3、存储数据
上面看看 HashMap 存储数据的过程是怎么的，首先看看 HashMap 的 put 办法：
public V put(K key, V value) {// 若“key 为 null”，则将该键值对增加到 table[0]中。if (key == null)
return putForNullKey(value);
// 若“key 不为 null”，则计算该 key 的哈希值，而后将其增加到该哈希值对应的链表中。int hash = hash(key.hashCode());
// 搜寻指定 hash 值在对应 table 中的索引
int i = indexFor(hash, table.length);
// 循环遍历 Entry 数组, 若“该 key”对应的键值对曾经存在，则用新的 value 取代旧的 value。而后退出！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))) { // 如果 key 雷同则笼罩并返回旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 批改次数 +1
modCount++;
// 将 key-value 增加到 table[i]处
addEntry(hash, key, value, i);
return null;
}下面程序中用到了一个重要的外部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从下面程序中能够看出：当零碎决定存储 HashMap 中的 key-value 对时，齐全没有思考 Entry 中的 value，仅仅只是依据 key 来计算并决定每个 Entry 的存储地位。
这也阐明了后面的论断：咱们齐全能够把 Map 汇合中的 value 当成 key 的从属，当零碎决定了 key 的存储地位之后，value 随之保留在那里即可。
咱们缓缓的来剖析这个函数，第 2 和 3 行的作用就是解决 key 值为 null 的状况，咱们看看 putForNullKey(value)办法：
private V putForNullKey(V value) {for (Entry<K, V> e = table[0]; e != null; e = e.next) {if (e.key == null) { // 如果有 key 为 null 的对象存在，则笼罩掉
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0); // 如果键为 null 的话，则 hash 值为 0
return null;
}留神：如果 key 为 null 的话，hash 值为 0，对象存储在数组中索引为 0 的地位。即 table[0]
咱们再回去看看 put 办法中第 4 行，它是通过 key 的 hashCode 值计算 hash 码，上面是计算 hash 码的函数：
// 计算 hash 值的办法 通过键的 hashCode 来计算
static int hash(int h) {
// 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);
}失去 hash 码之后就会通过 hash 码去计算出应该存储在数组中的索引，计算索引的函数如下：
static int indexFor(int h, int length) { // 依据 hash 值和数组长度算出索引值
return h & (length - 1); // 这里不能轻易算取，用 hash&(length-1)是有起因的，这样能够确保算进去的索引是在数组大小范畴内，不会超出
}这个咱们要重点说下，咱们个别对哈希表的散列很天然地会想到用 hash 值对 length 取模（即除法散列法），Hashtable 中也是这样实现的，这种办法根本能保障元素在哈希表中散列的比拟平均，但取模会用到除法运算，效率很低，HashMap 中则通过 h &(length-1)的办法来代替取模，同样实现了平均的散列，但效率要高很多，这也是 HashMap 对 Hashtable 的一个改良。
接下来，咱们剖析下为什么哈希表的容量肯定要是 2 的整数次幂。首先，length 为 2 的整数次幂的话，h&(length-1)就相当于对 length 取模，这样便保障了散列的平均，同时也晋升了效率；其次，length 为 2 的整数次幂的话，为偶数，这样 length- 1 为奇数，奇数的最初一位是 1，这样便保障了 h &(length-1)的最初一位可能为 0，也可能为 1（这取决于 h 的值），即与后的后果可能为偶数，也可能为奇数，这样便能够保障散列的平均性，而如果 length 为奇数的话，很显著 length- 1 为偶数，它的最初一位是 0，这样 h &(length-1)的最初一位必定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标地位上，这便节约了近一半的空间，因而，length 取 2 的整数次幂，是为了使不同 hash 值产生碰撞的概率较小，这样就能使元素在哈希表中平均地散列。
这看上去很简略，其实比拟有玄机的，咱们举个例子来阐明：
假如数组长度别离为 15 和 16，优化后的 hash 码别离为 8 和 9，那么 & 运算后的后果如下：
h & (table.length-1) hash table.length-1
8 & (15-1)：0100 & 1110 = 0100
9 & (15-1)：0101 & 1110 = 0100
-----------------------------------------------------------------------------------------------------------------------
8 & (16-1)：0100 & 1111 = 0100
9 & (16-1)：0101 & 1111 = 0101从下面的例子中能够看出：当它们和 15-1（1110）“与”的时候，产生了雷同的后果，也就是说它们会定位到数组中的同一个地位下来，这就产生了碰撞，8 和 9 会被放到数组中的同一个地位上造成链表，那么查问的时候就须要遍历这个链 表，失去 8 或者 9，这样就升高了查问的效率。同时，咱们也能够发现，当数组长度为 15 的时候，hash 值会与 15-1（1110）进行“与”，那么 最初一位永远是 0，而 0001，0011，0101，1001，1011，0111，1101 这几个地位永远都不能寄存元素了，空间节约相当大，更糟的是这种状况中，数组能够应用的地位比数组长度小了很多，这意味着进一步减少了碰撞的几率，减慢了查问的效率！而当数组长度为 16 时，即为 2 的 n 次方时，2n- 1 失去的二进制数的每个位上的值都为 1，这使得在低位上 & 时，失去的和原 hash 的低位雷同，加之 hash(int h)办法对 key 的 hashCode 的进一步优化，退出了高位计算，就使得只有雷同的 hash 值的两个值才会被放到数组中的同一个地位上造成链表。
所以说，当数组长度为 2 的 n 次幂的时候，不同的 key 算得得 index 雷同的几率较小，那么数据在数组上散布就比拟平均，也就是说碰撞的几率小，绝对的，查问的时候就不必遍历某个地位上的链表，这样查问效率也就较高了。
依据下面 put 办法的源代码能够看出，当程序试图将一个 key-value 对放入 HashMap 中时，程序首先依据该 key 的 hashCode() 返回值决定该 Entry 的存储地位：如果两个 Entry 的 key 的 hashCode() 返回值雷同，那它们的存储地位雷同。如果这两个 Entry 的 key 通过 equals 比拟返回 true，新增加 Entry 的 value 将笼罩汇合中原有 Entry 的 value，但 key 不会笼罩。如果这两个 Entry 的 key 通过 equals 比拟返回 false，新增加的 Entry 将与汇合中原有 Entry 造成 Entry 链，而且新增加的 Entry 位于 Entry 链的头部——具体阐明持续看 addEntry() 办法的阐明。
void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K, V> e = table[bucketIndex]; // 如果要退出的地位有值，将该地位原先的值设置为新 entry 的 next, 也就是新 entry 链表的下一个节点
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold) // 如果大于临界值就扩容
resize(2 * table.length); // 以 2 的倍数扩容
}参数 bucketIndex 就是 indexFor 函数计算出来的索引值，第 2 行代码是获得数组中索引为 bucketIndex 的 Entry 对象，第 3 行就是用 hash、key、value 构建一个新的 Entry 对象放到索引为 bucketIndex 的地位，并且将该地位原先的对象设置为新对象的 next 形成链表。
第 4 行和第 5 行就是判断 put 后 size 是否达到了临界值 threshold，如果达到了临界值就要进行扩容，HashMap 扩容是扩为原来的两倍。
4、调整大小
resize()办法如下：
从新调整 HashMap 的大小，newCapacity 是调整后的单位
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);// 用来将原先 table 的元素全副移到 newTable 外面
table = newTable; // 再将 newTable 赋值给 table
threshold = (int) (newCapacity * loadFactor);// 从新计算临界值
}新建了一个 HashMap 的底层数组，下面代码中第 10 行为调用 transfer 办法，将 HashMap 的全副元素增加到新的 HashMap 中, 并从新计算元素在新的数组中的索引地位
当 HashMap 中的元素越来越多的时候，hash 抵触的几率也就越来越高，因为数组的长度是固定的。所以为了进步查问的效率，就要对 HashMap 的数组进行扩容，数组扩容这个操作也会呈现在 ArrayList 中，这是一个罕用的操作，而在 HashMap 数组扩容之后，最耗费性能的点就呈现了：原数组中的数据必须从新计算其在新数组中的地位，并放进去，这就是 resize。
那么 HashMap 什么时候进行扩容呢？当 HashMap 中的元素个数超过数组大小_loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75，这是一个折中的取值。__也就是说，默认状况下，数组大小为 16，那么当 HashMap 中元素个数超过 16_0.75=12 的时候，就把数组的大小扩大为 2*16=32，即扩充一倍，而后从新计算每个元素在数组中的地位，扩容是须要进行数组复制的，复制数组是十分耗费性能的操作，所以如果咱们曾经预知 HashMap 中元素的个数，那么预设元素的个数可能无效的进步 HashMap 的性能。
5、数据读取
public V get(Object key) {if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K, V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}有了下面存储时的 hash 算法作为根底，了解起来这段代码就很容易了。从下面的源代码中能够看出：从 HashMap 中 get 元素时，首先计算 key 的 hashCode，找到数组中对应地位的某一元素，而后通过 key 的 equals 办法在对应地位的链表中找到须要的元素。
6、HashMap 的性能参数：
HashMap 蕴含如下几个结构器：
- HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创立一个 HashMap。
HashMap 的根底结构器 HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量 initialCapacity 和加载因子 loadFactor。 - initialCapacity：HashMap 的最大容量，即为底层数组的长度。
- loadFactor：负载因子 loadFactor 定义为：散列表的理论元素数目(n) 散列表的容量(m)。
负载因子掂量的是一个散列表的空间的应用水平，负载因子越大示意散列表的装填水平越高，反之愈小。对于应用链表法的散列表来说，查找一个元素的均匀工夫是 O(1+a)，因而如果负载因子越大，对空间的利用更充沛，然而结果是查找效率的升高；如果负载因子太小，那么散列表的数据将过于稠密，对空间造成重大节约。
HashMap 的实现中，通过 threshold 字段来判断 HashMap 的最大容量：
threshold = (int)(capacity * loadFactor); 联合负载因子的定义公式可知，threshold 就是在此 loadFactor 和 capacity 对应下容许的最大元素数目，超过这个数目就从新 resize，以升高理论的负载因子。默认的的负载因子 0.75 是对空间和工夫效率的一个均衡抉择。当容量超出此最大容量时，resize 后的 HashMap 容量是容量的两倍。
