HashMap的数据结构
HashMap的数据结构=数组+链表+红黑树，允许key为null,value为null。遍历时无序。
HashMap实现了Cloneable接口，可进行拷贝，浅层次的拷贝（即对拷贝对象的改变会影响拷贝的对象）
它是线程不安全的，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap,
Map map=Collections.synchronizedMap(new HashMap())
存储流程
image
HashMap中的重要参数（变量）
/**
* 主要参数 同 JDK 1.7
* 即：容量、加载因子、扩容阈值（要求、范围均相同）
*/
// 1. 容量（capacity）： 必须是2的幂 & <最大容量（2的30次方）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
// 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
final float loadFactor; // 实际加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子 = 0.75
// 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）
// a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
// b. 扩容阈值 = 容量 x 加载因子
int threshold;
// 4. 其他
transient Node<K,V>[] table; // 存储数据的Node类型 数组，长度 = 2的幂；数组的每个元素 = 1个单链表
transient int size;// HashMap的大小，即 HashMap中存储的键值对的数量
/**
* 与红黑树相关的参数
*/
// 1. 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 3. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
image
hash（key）
// JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
// 1. 取hashCode值： h = key.hashCode()
// 2. 高位参与低位的运算：h ^ (h >>> 16)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
// a. 当key = null时，hash值 = 0，所以HashMap的key 可为null
// 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
// b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
}
image
image
所有处理的根本目的，都是为了提高 存储key-value的数组下标位置 的随机性 & 分布均匀性，尽量避免出现hash值冲突。即：对于不同key，存储的数组下标位置要尽可能不一样
https://www.jianshu.com/p/8324a34577a0
https://blog.csdn.net/wufaliang003/article/details/79997585
https://blog.csdn.net/mbshqqb/article/details/79799009
https://www.jianshu.com/p/22ae6596b004
网友评论