HashMap原理：HashMap 是基 于 Map 接口实现的一种键-值对<key,value>的存储结构，允许 null 值，同时非 有序，非同步(即线程不安全)。HashMap 的底层实现是数组 + 链表 + 红黑树 （JDK1.8 增加了红黑树部分）。它存储和查找数据时，是根据键 key 的 hashCode 的值计算出具体的存储位置。HashMap 最多只允许一条记录的键 key 为 null， HashMap 增删改查等常规操作都有不错的执行效率，是 ArrayList 和 LinkedList 等数据结构的一种折中实现。
HashMap源码解析：
table 哈希表
size 实际存储键值对的个数
threshold 下一次扩容时的阈值
loadFactor 哈希表的负载因子
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
·····
/* ---------------- Fields -------------- */
/**
* 哈希表，在第一次使用到时进行初始化，重置大小是必要的操作，
* 当分配容量时，长度总是 2 的 N 次幂。 */
transient Node<K,V>[] table;
/*** 实际存储的 key - value 键值对 个数 */
transient int size;
/*** 下一次扩容时的阈值 * (阈值 threshold = 容器容量 capacity * 负载因子 load factor).
* @serial */
int threshold;
/*** 哈希表的负载因子
** @serial */
final float loadFactor;
·····
}
final int hash;//元素的哈希值 由 final 修饰可知，当 hash 的值确定 后，就不能再修改
final K key;// 键，由 final 修饰可知，当 key 的值确定后，就不能再 修改
V value; // 值
Node<K,V> next; // 记录下一个元素结点(单链表结构，用于解决 hash 冲突)
/*** 定义 HashMap 存储元素结点的底层实现 */
public static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//元素的哈希值 由 final 修饰可知，当 hash 的值确定 后，就不能再修改
final K key;// 键，由 final 修饰可知，当 key 的值确定后，就不能再 修改
V value; // 值
Node<K,V> next; // 记录下一个元素结点(单链表结构，用于解决 hash 冲突)
/*** Node 结点构造方法 */
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;//元素的哈希值
this.key = key;// 键
this.value = value; // 值
this.next = next;
// 记录下一个元素结点
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
/*** 为 Node 重写 hashCode 方法，值为：key 的 hashCode 异或 value 的 hashCode* 运算作用就是将 2 个 hashCode 的二进制中，同一位置相同的值为 0， 不同的为 1。*/
public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
/*** 修改某一元素的值 */
public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; }
/*** 为 Node 重写 equals 方法 */
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;
}
}
HashMap put原理
HashMap hash计算原理
jdk1.7中档数组扩容后需要重新计算hash再将旧数组的节点放入新数组
jdk1.8中hash计算和扩容方法进行优化，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。
/*** JDK 8 的 hash 方法 */
public static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
