共计 5287 个字符，预计需要花费 14 分钟才能阅读完成。
关于 hashCode
hashCode 的存在主要是用于查找的快捷性，如 Hashtable，HashMap 等，hashCode 是用来在散列存储结构中确定对象的存储地址的.
1.hashcode 是用来查找的，如果你学过数据结构就应该知道，在查找和排序这一章有例如内存中有这样的位置 0 1 2 3 4 5 6 7 而我有个类，这个类有个字段叫 ID, 我要把这个类存放在以上 8 个位置之一，如果不用 hashcode 而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。但如果用 hashcode 那就会使效率提高很多。我们这个类中有个字段叫 ID, 那么我们就定义我们的 hashcode 为 ID%8，然后把我们的类存放在取得得余数那个位置。比如我们的 ID 为 9，9 除 8 的余数为 1，那么我们就把该类存在 1 这个位置，如果 ID 是 13，求得的余数是 5，那么我们就把该类放在 5 这个位置。这样，以后在查找该类时就可以通过 ID 除 8 求余数直接找到存放的位置了。2. 但是如果两个类有相同的 hashcode 怎么办那（我们假设上面的类的 ID 不是唯一的），例如 9 除以 8 和 17 除以 8 的余数都是 1，那么这是不是合法的，回答是：可以这样。那么如何判断呢？在这个时候就需要定义 equals 了。也就是说，我们先通过 hashcode 来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要再通过 equals 来在这个桶里找到我们要的类。那么。重写了 equals()，为什么还要重写 hashCode()呢？想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写 hashcode()来找到桶，光重写 equals()有什么用啊
理解了 hashCode 我们来理解 HashMap
HashMap 概述
HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。在 java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap 也不例外。HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
内部存储
HashMap 的内部存储是一个数组（bucket），数组的元素 Node 实现了是 Map.Entry 接口(hash, key, value, next)，next 非空时指向定位相同的另一个 Entry，如图：
关于 hashCode
hashCode 的存在主要是用于查找的快捷性，如 Hashtable，HashMap 等，hashCode 是用来在散列存储结构中确定对象的存储地址的.
1.hashcode 是用来查找的，如果你学过数据结构就应该知道，在查找和排序这一章有例如内存中有这样的位置 0 1 2 3 4 5 6 7 而我有个类，这个类有个字段叫 ID, 我要把这个类存放在以上 8 个位置之一，如果不用 hashcode 而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。但如果用 hashcode 那就会使效率提高很多。我们这个类中有个字段叫 ID, 那么我们就定义我们的 hashcode 为 ID%8，然后把我们的类存放在取得得余数那个位置。比如我们的 ID 为 9，9 除 8 的余数为 1，那么我们就把该类存在 1 这个位置，如果 ID 是 13，求得的余数是 5，那么我们就把该类放在 5 这个位置。这样，以后在查找该类时就可以通过 ID 除 8 求余数直接找到存放的位置了。2. 但是如果两个类有相同的 hashcode 怎么办那（我们假设上面的类的 ID 不是唯一的），例如 9 除以 8 和 17 除以 8 的余数都是 1，那么这是不是合法的，回答是：可以这样。那么如何判断呢？在这个时候就需要定义 equals 了。也就是说，我们先通过 hashcode 来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要再通过 equals 来在这个桶里找到我们要的类。那么。重写了 equals()，为什么还要重写 hashCode()呢？想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写 hashcode()来找到桶，光重写 equals()有什么用啊
理解了 hashCode 我们来理解 HashMap
HashMap 概述
HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。在 java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap 也不例外。HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
内部存储
HashMap 的内部存储是一个数组（bucket），数组的元素 Node 实现了是 Map.Entry 接口(hash, key, value, next)，next 非空时指向定位相同的另一个 Entry，如图：
HashMap 实现存储和读取
存储
public V put(K key, V value) {
// HashMap 允许存放 null 键和 null 值。
// 当 key 为 null 时，调用 putForNullKey 方法，将 value 放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据 key 的 keyCode 重新计算 hash 值。
int hash = hash(key.hashCode());
// 搜索指定 hash 值在对应 table 中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
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;
}
}
// 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry。
modCount++;
// 将 key、value 添加到 i 索引处。
addEntry(hash, key, value, i);
return null;
}
根据 hash 值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。hash(int h)方法根据 key 的 hashCode 重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的 hash 冲突。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
HashMap 中要找到某个元素，需要根据 key 的 hash 值来求得对应数组中的位置。如何计算这个位置就是 hash 算法。前面说过 HashMap 的数据结构是数组和链表的结合，所以我们当然希望这个 HashMap 里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。
根据上面 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() 方法的说明。
具体如何根据 hash 计算下标呢，参见
JDK 源码中 HashMap 的 hash 方法原理是什么？
获取
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;
}
从 HashMap 中 get 元素时，首先计算 key 的 hashCode，找到数组中对应位置的某一元素，然后通过 key 的 equals 方法在对应位置的链表中找到需要的元素。
HashMap 的 resize
当 hashmap 中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对 hashmap 的数组进行扩容，数组扩容这个操作也会出现在 ArrayList 中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在 hashmap 数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是 resize。那么 hashmap 什么时候进行扩容呢？当 hashmap 中的元素个数超过数组大小 loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75，也就是说，默认情况下，数组大小为 16，那么当 hashmap 中元素个数超过 160.75=12 的时候，就把数组的大小扩展为 216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 hashmap 中元素的个数，那么预设元素的个数能够有效的提高 hashmap 的性能。比如说，我们有 1000 个元素 new HashMap(1000), 但是理论上来讲 new HashMap(1024)更合适，不过上面 annegu 已经说过，即使是 1000，hashmap 也自动会将其设置为 1024。但是 new HashMap(1024)还不是更合适的，因为 0.751000 < 1000, 也就是说为了让 0.75 * size > 1000, 我们必须这样 new HashMap(2048)才最合适，既考虑了 & 的问题，也避免了 resize 的问题。
1.8 的优化
Java8 做的改变:1.HashMap 是数组 + 链表 + 红黑树 (JDK1.8 增加了红黑树部分), 当链表长度 >= 8 时转化为红黑树在 JDK1.8 版本中, 对数据结构做了进一步的优化, 引入了红黑树。而当链表长度太长(默认超过 8) 时，链表就转换为红黑树，利用红黑树快速增刪改查的特点提高 HashMap 的性能，其中会用到红黑树的插入、刪除、查找等算法。
java8 中对 hashmap 护容不是重新计算所有元素在数组的位置，而是我们使用的是 2 次幂的扩展(指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置在扩充 HashMap 的时候，不需要像 JDK1.7 的实现那样重新计算 hash, 只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”。
面试中通常被问到的。
HashMap 高并发情况下会出现什么问题?
扩容问题 HashMap 的存放自定义类时，需要实现自定义类的什么方法?
hashCode 和 equals. 通过 hash(hashCode)然后模运算 (其实是与的位操作) 定位在 Entry 数组中的下标，然后遍历这之后的链表，通过 equals 比较有没有相同的 key, 如果有直接覆盖 value, 如果没有就重新创建一一个 Entry。
hashmap 为什么可以插入空值?
HashMap 中添加 key == null 的 Entry 时会调用 putForNullKey 方法直接去遍历 table[0]Entry 链表，寻找 e.key == null 的 Entry 或者没有找到遍历结束如果找到了 e.key==null, 就保存 null 值对应的原值 oldValue, 然后覆盖原值，并返回 oldValue 如果在 table[O]Entrty 链表中没有找到就调用 addEntry 方法添加一个 key 为 null 的 Entry
Hashmap 为什么线程不安全(hash 碰撞和扩容导致)
HashMap 扩容的的时候可能会形成环形链表，造成死循环。
