哈希表的物理结构
HashMap底层都是哈希表（也称散列表），线程不安全，其中维护了一个长度为2的幂次方的Entry类型的数组table，数组的每一个索引位置被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到某个table[index]桶中。使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]。
JDK8中HashMap结构如图：
JDK7 HashMap分析
以JDK1.7.0_07为例，其结构如图所示：
1. Entry
key-value被封装为HashMap.Entry类型，而这个类型实现了Map.Entry接口。
public class HashMap<K,V>{
transient Entry<K,V>[] table;
// 内部类
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next; // 指向下一个Entry
int hash; // 根据key计算出的哈希值2，存储用以之后的添加等操作
// 构造器
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
//略
}
}
2. 属性
//table数组的默认初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 16;
//哈希表
transient Entry<K,V>[] table;
//哈希表中key-value键值对的个数
transient int size;
//临界值、阈值
int threshold;
//加载因子
final float loadFactor;
//默认加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 键值对数量上限2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
3. 构造器
无参构造器
public HashMap() {
//DEFAULT_INITIAL_CAPACITY：默认初始容量16
//DEFAULT_LOAD_FACTOR：默认加载因子0.75
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
含参构造器
// 构造器
public HashMap(int initialCapacity, float loadFactor) {
//校验initialCapacity合法性,[0,size)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//校验initialCapacity合法性
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//校验loadFactor合法性
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//计算得到table数组的长度（保证capacity是2的整次幂）
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1; // <<乘2
//加载因子，初始化为0.75
this.loadFactor = loadFactor;
// threshold 初始为初始容量initialCapacity*加载因子d
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化table数组
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init(); // 该方法方法体为{}
}
4. put
put方法基本步骤如下：
put方法将(key1,value1)添加到当前hashmap的对象中，首先会调用key1所在类的hashCode()方法，计算key1的哈希值1，此哈希值1再经过某种运算，得到哈希值2。此哈希值2再经过某种运算(indexFor())，才能确定在底层table数组中的索引位置i。
（1）如果数组索引为i上的数据为空，则(key1,value1)直接添加成功 ------位置1
（2）如果数组索引为i上的数据不为空，有(key2,value2)，则需要进一步判断：-----哈希冲突
此时需要进一步判断key1的哈希值2与key2的哈希值是否相同：
（3） 如果哈希值不同，则(key1,value1)直接添加成功 ------位置2
如果哈希值相同，则需要继续调用key1所在类的equals()方法，将key2放入equals()形参进行判断
（4） equals方法返回false : 则(key1,value1)直接添加成功 ------位置3
equals方法返回true : 默认情况下，value1会覆盖value2。
各位置说明：
位置1：直接将(key1,value1)以Entry对象的方式存放到table数组索引i的位置。
位置2和位置3：(key1,value1) 与现有的元素以链表的方式存储在table数组索引i的位置，新添加的元素指向旧添加的元素（头插法）。
…
在不断的添加的情况下，满足如下条件的情况下，会进行扩容:
if ((size >= threshold) && (null != table[bucketIndex])) :
threshold：临界值->数组长度*加载因子，数组长度默认值为16，加载因子默认值为0.75
bucketIndex：新添加的元素在table数组中的索引位置，table[bucketIndex]在jdk7的条件下会新增链表
默认情况下，当要添加的元素个数超过12(即：数组的长度 * loadFactor得到的结果)时，就要考虑扩容。
默认扩容长度为原数组长度的两倍
public V put(K key, V value) {
// HashMap运行key和value为null
//如果key是null，单独处理，存储到table[0]中，如果有另一个key为null，value覆盖
if (key == null)
return putForNullKey(value);
/*
hashCode值 xxxxxxxxxx
table.length-1 000001111
hashCode值 xxxxxxxxxx 无符号右移几位和原来的hashCode值做^运算，使得hashCode高位二进制值参与计算，
也发挥作用，降低index冲突的概率。
*/
// 将key传入hash(),内部使用了key的哈希值1（hashcode），此方法执行结束后，返回哈希值2
int hash = hash(key);
// 计算新的映射关系应该存到table[i]位置，
// i = hash & table.length-1，可以保证i在[0,table.length-1]范围内
int i = indexFor(hash, table.length);
/**
* 检查table[i]下面有没有key与已有的映射关系的key重复，如果重复替换value
* table[i]为null时，直接跳过for循环，添加新的映射关系；
* table[i]不为null时，若存在已有的映射关系的key重复，则新value覆盖原有value并返回原有value;若不存在，则结束for循环，添加新的映射关系
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果新增的key的哈希值2和键值对e的hash相等且两者key相等，则进行覆盖
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
// 修改：返回原有的值
return oldValue;
}
}
// 统计增删次数
modCount++;
//添加新的映射关系
addEntry(hash, key, value, i);
return null; // 添加：返回null
}
//如果key是null，直接存入table[0]的位置
private V putForNullKey(V value) {
//判断是否有重复的key，如果有重复的，就替换value
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++; // 增删次数+1
//把新的映射关系存入[0]的位置，而且key的hash值用0表示
addEntry(0, null, value, 0);
return null;
}
// 哈希函数+扰动函数,为了防止一些实现比较差的 hashCode() 方法,在key的hashcode的基础上，进行无符号右移之后可以减少碰撞。
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// >>>无符号右移
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 根据哈希值和数组长度计算在table数组中的索引位置
static int indexFor(int h, int length) {
// hash & table.length-1，可以保证i在[0,table.length-1]范围内
return h & (length-1);
}
// 判断是否需要扩容，然后新增key-value键值对
void addEntry(int hash, K key, V value, int bucketIndex) {
//判断是否需要扩容
//扩容：（1）size达到临界值threshold（2）table[i]位置的链表非空
if ((size >= threshold) && (null != table[bucketIndex])) {
//table扩容为原来的2倍，并且扩容后，会重新调整所有key-value的存储位置
resize(2 * table.length);
// 重新计算，得到新的key-value的hash和index
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//存入table中
createEntry(hash, key, value, bucketIndex);
}
// 新增key-value键值对
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 头插法进行插入
table[bucketIndex] = new Entry<>(hash, key, value, e);
//个数增加
size++;
}
5. get
public V get(Object key) {
//key为null，调用对应的getForNullKey方法
if (key == null)
return getForNullKey();
//当key != null时，去获得对应值
Entry<K,V> entry = getEntry(key);
//entry等于null说明没找到，则返回null值
return null == entry ? null : entry.getValue();
}
//key为null，获取其对应的value
private V getForNullKey() {
//key为null，默认是放在哈希桶的第一个位置table[0]
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
/*
① 计算key1的hash值，调用方法hash(key1)
② 找index = table.length-1 & hash;
③ 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就返回它的value
*/
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 根据key值，通过hash方法计算出对应的hash值
int hash = (key == null) ? 0 : hash(key);
// 根据hash值计算出对应的数组下标
// 遍历 以该数组下标的数组元素为头结点的链表所有节点，寻找该key对应的值
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
// 若 hash值 & key 相等，则证明该Entry 就是要获取的键值对
// 通过equals（）判断key是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
6. remove
/*
remove和get类似，区别是在table[index]位置的链表删除key1为键的节点
① 计算key1的hash值，用这个方法hash(key1)
② 找index = table.length-1 & hash;
③ 如果table[index]不为空，那么就挨个比较，如果哪个Entry的key与它相等，就删除它，把它前面的Entry的next的值修改为被删除Entry的next
*/
map.remove(key1);
JDK8 HashMap分析
以JDK1.8.0_271为例，其结构如图所示：
key-value被封装为HashMap.Node类型或HashMap.TreeNode类型，它俩都直接或间接的实现了Map.Entry接口。
存储到table数组的可能是Node结点对象，也可能是TreeNode结点对象，它们也是Map.Entry接口的实现类。即table[index]下的映射关系可能串起来一个链表或一棵红黑树。
1. Node
public class HashMap<K,V>{
transient Node<K,V>[] table;
//Node类
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// 其它结构：略
}
//TreeNode类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red; //是红结点还是黑结点
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
//....
}
2. 属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 1 << 30
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子
static final int TREEIFY_THRESHOLD = 8; //默认树化阈值8，当链表的长度达到这个值后，要考虑变为红黑树
static final int UNTREEIFY_THRESHOLD = 6;//默认反树化阈值6，当树中结点的个数达到此阈值后，要考虑变为链表
//当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。
//当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容
static final int MIN_TREEIFY_CAPACITY = 64; //最小树化容量64
transient Node<K,V>[] table; // 底层table数组
transient int size; //记录有效映射关系的对数，也是Entry对象的个数
int threshold; //阈值，当size达到阈值时，考虑扩容
final float loadFactor; //加载因子，影响扩容的频率
3. 构造器
以下两个构造器初始化时并没有初始化table数组，还是等到第一次执行put方法是才去初始化
无参构造器table数组
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted (其他字段都是默认值)
}
含参构造器
// 构造器
public HashMap(int initialCapacity, float loadFactor) {
//校验initialCapacity合法性,[0,size)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//校验initialCapacity合法性
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//校验loadFactor合法性
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 初始容量暂时存放到 threshold ，在resize中再赋值给 newCap 进行table初始化
// HashMap 的容量必须是 2 的幂次方，并且大于或等于指定的容量参数 initialCapacity
this.threshold = tableSizeFor(initialCapacity);
}
4. put
// 计算哈希值
static final int hash(Object key) {
int h;
//如果key是null，hash是0
//如果key非null，用key的hashCode值 与 key的hashCode值高16进行异或
//即就是用key的hashCode值高16位与低16位进行了异或的干扰运算
//JDK7索引计算格式: index = hash & table.length-1
//如果用key的原始的hashCode值与table.length-1 进行按位与，那么基本上高16位没机会用上。
//这样就会增加冲突的概率，为了降低冲突的概率，把高16位加入到hash信息中。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 新增键值对
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; //数组
Node<K,V> p; //一个结点
int n, i; //n是数组的长度 i是下标
//tab和table等, 如果table是空的
if ((tab = table) == null || (n = tab.length) == 0){
/*
如果table是空的，resize()完成了
①创建了一个长度为16（默认数组长度）的数组
②threshold = 12 n = 16
*/
n = (tab = resize()).length;
}
// i = (n - 1) & hash ，bucketIndex索引 = 数组长度-1 & hash
// 相对于jdk7的IndexFor()函数：i = (n - 1) & hash，根据哈希值2计算索引
// if(p==null) 条件满足的话说明 table[i]为空，没有节点
if ((p = tab[i = (n - 1) & hash]) == null){
//把新的映射关系直接放入table[i]，作为链表的头结点
tab[i] = newNode(hash, key, value, null);
}else {
Node<K,V> e; K k;
//p是table[i]中第一个结点
//if(table[i]的第一个结点与新的映射关系的key重复)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//用e记录这个table[i]的第一个结点，后面进行value覆盖
else if (p instanceof TreeNode){ //如果table[i]第一个结点是一个树结点
//单独处理树结点
//如果树结点中，有key重复的，就返回那个重复的结点用e接收，即e!=null
//如果树结点中，没有key重复的，就把新结点放到树中，并且返回null，即e=null
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
}else {
//table[i]的第一个结点不是树结点，也与新的映射关系的key不重复
//binCount记录了table[i]下面的结点的个数
for (int binCount = 0; ; ++binCount) { //
//如果p的下一个结点是空的，说明当前的p是最后一个结点
if ((e = p.next) == null) {
//把新的结点连接到table[i]的最后
p.next = newNode(hash, key, value, null);
//如果binCount>=TREEIFY_THRESHOLD-1 （8-1=7，该链表转红黑树的阈值）
if (binCount >= TREEIFY_THRESHOLD - 1)
//要么扩容，要么树化（树化则还需要满足table数组长度大于等于MIN_TREEIFY_CAPACITY(64)）
treeifyBin(tab, hash);
break;
}
//如果key重复了，就跳出for循环，此时e结点记录的就是那个key重复的结点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;//下一次循环，e=p.next，就类似于e=e.next，往链表下移动
}
}
//如果这个e不是null，说明有key重复，就考虑替换原来的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //什么也没干
return oldValue;
}
}
++modCount;
//元素个数增加
//size达到阈值
if (++size > threshold)
resize(); //一旦扩容，重新调整所有映射关系的位置
afterNodeInsertion(evict); // 什么也没干
return null;
}
// 数组扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //oldTab原来的table
//oldCap：原来数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr：原来的阈值
int oldThr = threshold;//最开始threshold是0
//newCap：新容量
//newThr：新阈值
int newCap, newThr = 0;
if (oldCap > 0) { //说明原来不是空数组
if (oldCap >= MAXIMUM_CAPACITY) { //是否达到数组最大限制
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//newCap = 旧的容量*2 ，新容量<最大数组容量限制
//新容量：32,64，...
//oldCap >= 初始容量16
//新阈值重新算 = 24，48 ....
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //新容量是默认初始化容量16
//新阈值= 默认的加载因子 * 默认的初始化容量 = 0.75*16 = 12
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; // 阈值赋值为新阈值12，24.。。。
//创建了一个新数组，长度为newCap，16，32,64.。。
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) { //原来不是空数组
//把原来的table中映射关系，倒腾到新的table中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//e是table下面的结点
oldTab[j] = null; //把旧的table[j]位置清空
if (e.next == null) //如果是最后一个结点
newTab[e.hash & (newCap - 1)] = e; //重新计算e的在新table中的存储位置，然后放入
else if (e instanceof TreeNode) //如果e是树结点
//把原来的树拆解，放到新的table
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//把原来table[i]下面的整个链表，重新挪到了新的table中
do {
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;
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
//创建一个新结点
return new Node<>(hash, key, value, next);
}
// 树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
//MIN_TREEIFY_CAPACITY：最小树化容量64
//如果table是空的，或者 table数组的长度没有达到64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//先扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
//用e记录table[index]的结点的地址
TreeNode<K,V> hd = null, tl = null;
// do...while，把table[index]链表的Node结点变为TreeNode类型的结点
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;//hd记录根结点
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//如果table[index]下面不是空
if ((tab[index] = hd) != null)
hd.treeify(tab);//将table[index]下面的链表进行树化
}
}
put执行过程如图所示：
5. get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 查找
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table数组不为空且table[bucketIndex]第一个节点不为null，bucketIndex= (n - 1) & hash表示table数组的bucketIndex索引位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// key和first的哈希值相等，且key与first的key相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first; // 则table[bucketIndex]第一个节点就是我们要找到
// 遍历table[bucketIndex]的所有节点
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 如果是树节点，则调用树的查找方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 否则为链表，循环查找满足：key和e的哈希值相等，且key与e的key相等
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
6. remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// table数组不为空且table[bucketIndex]第一个节点不为null，bucketIndex= (n - 1) & hash表示table数组的bucketIndex索引位置，即p指向table[bucketIndex]第一个节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// key和p的哈希值相等，且key与p的key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p; // node记录p作为要删除的Node
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
// 如果是树节点，调用树的查找方法
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 否则为链表遍历比对
do {
// key和e的哈希值相等，且key与e的key相等
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e; // node记录e作为要删除的Node
break;
}
p = e; // p指向链表中要删除的e节点的上一个结点
} while ((e = e.next) != null);
}
}
// node不为null，说明该key存在，需要删除
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
// 从红黑树中删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 从链表中删除e节点，此时链表只有一个节点，删除后tab[index]为null
tab[index] = node.next;
else
// 从链表中删除，此时链表有多个节点，
p.next = node.next;
++modCount; // 修改次数+1
--size; // 键值对数量-1
afterNodeRemoval(node); // 空
return node;
}
}
return null;
}
小结
①在jdk8中，当我们创建了HashMap实例以后，底层并没有像jdk7初始化长度为16的table数组。当首次执行put方法添加(key,value)时，进行判断，如果发现tablei尚未初始化，则对数组进行初始化。
在jdk7中，threshold = 新容量capacity*负载因子loadFactor
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
jdk8中threshold扩容时翻倍；
jdk7和jdk8默认初始容量均为16，扩容时默认扩容为2倍
②jdk8中添加的key,value封装到了HashMap.Node类的对象中。而非jdk7中的HashMap.Entry。
③
jdk8中新增的元素所在的索引位置如果有其他元素，在经过一系列判断后，如果能添加，则是旧的元素指向新的元素；而jdk7中的新的元素指向旧的元素。
简言之，jdk8是类似尾插法（链表情况），jdk7类似头插法。
④
jdk7时底层的数据结构是：数组+单向链表。
jdk8时，底层的数据结构是：数组+单向链表+红黑树。
红黑树出现的时机：当某个索引位置i上的链表的长度达到8，且数组的长度超过64时，此索引位置上的元素要从单向链表改为红黑树。 红黑树进行put()/get()/remove()等操作时的时间复杂度为o(logn),相对于单向链表的时间复杂度O(n)性能更高。
static final int TREEIFY_THRESHOLD = 8;
如果索引i位置是红黑树的结构，当不断删除元素的情况下，当前索引i位置上的元素的个数低于6时，要从红黑树改为单向链表。
static final int UNTREEIFY_THRESHOLD = 6;
JavaGuide HashMap底层源码分析
