一.概述
HashMap是基于 Map 接口的实现，元素以键值对的方式存储，并且允许使用null建和null值，因为key不允许重复，因此只能有一个键为null,另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。
在了解HashMap之前，需要对它所使用的数据结构所了解，在jdk1.8之前HashMap的底层实现 数据结构:数组+链表。在jdk1.8之后的HashMap 数据结构:数组+链表+红黑树（特殊的平衡二叉树）。
数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)。
线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
二.JDK1.7版本的HashMap
HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，Entry的属性包括：key、value、hash值和指向下一个Entry对象的next指针。链表是用来解决Hash冲突（碰撞）。Hash冲突（碰撞）：当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，无法直接插入。
哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
HashMap总体存储结构图：
JDK1.7版本源码?
重要参数
1.capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
2. loadFactor：负载因子，默认为 0.75。
3. threshold：扩容的阈值，等于 capacity * loadFactor
类的定义：基于Map接口的实现类，继承了AbstractMap抽象类，实现了Cloneable接口和Serializable接口，可实现序列化和拷贝。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable构造方法
HashMap提供了四个构造函数：
//构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
} //构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} //构造一个带指定初始容量和加载因子的空 HashMap。
public HashMap7(int initialCapacity, float loadFactor) {
//对initialCapacity进行异常处理
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 = initialCapacity;
//一个空方法用于未来的子对象扩展
init();
}
void init() {
} //包含“子Map”的构造函数
//即 构造出来的HashMap包含传入Map的映射关系
//加载因子 & 容量 = 默认
public HashMap(Map<? extends K, ? extends V> m) {
// 设置容量大小 & 加载因子 = 默认
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
// 该方法用于初始化 数组 & 阈值，下面会详细说明
inflateTable(threshold);
// 将传入的子Map中的全部元素逐个添加到HashMap中
putAllForCreate(m);
}Entry内部类实现源码如下，详细详细看注释。Entry主要作用也就是用来存储HashMap中的Key和Value，通过HashCode计算出Entry对象应该去的数组下标位置。?
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;// 键
V value;//值
Entry<K,V> next;//下一个节点，解决哈希冲突
int hash;//哈希值
/**
*构造方法，创建一个Entry
* 参数：哈希值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;
}
//判断2个Entry是否相等，必须key和value都相等，才返回true
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;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* 当向HashMap中添加元素时，即调用put(k,v)时，
* 对已经在HashMap中k位置进行v的覆盖时，会调用此方法
* 此处没做任何处理
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* 当从HashMap中删除了一个Entry时，会调用该函数
* 此处没做任何处理
*/
void recordRemoval(HashMap<K,V> m) {
}
}
常用的方法
V get(Object key); // 获得指定键的值
V put(K key, V value); // 添加键值对
void putAll(Map<? extends K, ? extends V> m); // 将指定Map中的键值对 复制到 此Map中
V remove(Object key); // 删除该键值对
boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value); // 判断是否存在该值的键值对；是 则返回true
Set<K> keySet(); // 单独抽取key序列，将所有key生成一个Set
Collection<V> values(); // 单独value序列，将所有value生成一个Collection
void clear(); // 清除哈希表中的所有键值对
int size(); // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空
?变量
// 1. 容量（capacity）： HashMap中数组的长度
// 默认容量 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
// a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）
// b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）
// 实际加载因子
final float loadFactor;
// 默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）
// a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
// b. 扩容阈值 = 容量 x 加载因子
int threshold;
// 4. 其他
// 存储数据的Entry类型 数组，长度 = 2的幂
// HashMap的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单向链表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// HashMap的大小，即 HashMap中存储的键值对的数量
transient int size;加载因子的详细说明：?
hash计算?
/**
* 作用：计算传入数据的哈希码（哈希值、Hash值）
* 做了9次扰动处理 = 4次位运算 + 5次异或运算
*/
//将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
static final int hash(int h) {
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 计算存储位置的函数分析：indexFor(hash, table.length)
*/
static int indexFor(int h, int length) {
return h & (length-1);
// 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
}存放键值对，put()方法?
public V put(K key, V value) {
/**
* 若哈希表没有初始化(table为空)
* 使用构造函数时设置的阈值(即初始容量) 初始化 数组table
*/
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
/**
* 判断key是否为空值null
* 若key == null，则将该键-值 存放到数组table 中的第1个位置，即table [0]
* （本质：key = Null时，hash值 = 0，故存放到table[0]中）
* 该位置永远只有1个value，新传进来的value会覆盖旧的value
*/
if (key == null)
return putForNullKey(value);
/**
* 若 key ≠ null，则计算存放数组 table 中的位置（下标、索引）
* 根据键值key计算hash值
*/
int hash = hash(key);
//根据hash值 最终获得 key对应存放的数组Table中位置
int i = indexFor(hash, table.length);
//判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;//返回旧的value
}
}
modCount++;
// 若该key不存在,则将“key-value”添加到table中
addEntry(hash, key, value, i);
return null;
}获取数据get()?
public V get(Object key) {
//当key == null时，则到以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
if (key == null)
return getForNullKey();
//当key ≠ null时,去获得对应值
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//当key == null时，则到以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
private V getForNullKey() {
if (size == 0) {
return null;
}
// 遍历以table[0]为头结点的链表，寻找 key==null 对应的值
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 从table[0]中取key==null的value值
if (e.key == null)
return e.value;
}
return null;
}
/**
* 当key ≠ null时，去获得对应值
*/
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;
}
static int indexFor(int h, int length) {
//若 hash值 &(length-1) 寻找对应的下表
return h & (length-1);
}?其他方法
//作用：判断HashMap是否为空，即无键值对；size == 0时 表示为 空
public boolean isEmpty() {
return size == 0;
}
//作用：返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
public int size() {
return size;
}
//清空哈希表，即删除所有键值对
//将数组table中存储的Entry全部置为null、size置为0
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
//作用：将指定Map中的键值对 复制到 此Map中
//原理：类似Put函数
public void putAll(Map<? extends K, ? extends V> m) {
//统计需复制多少个键值对
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
//若table还没初始化，先用刚刚统计的复制数去初始化table
if (table == EMPTY_TABLE) {
inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
}
//若需复制的数目 > 阈值，则需先扩容
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
//开始复制（实际上不断调用Put函数插入）
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
//删除该键值对
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
//计算hash值
int hash = (key == null) ? 0 : hash(key);
//计算存储的数组下标位置
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
// 若删除的是table数组中的元素（即链表的头结点）
// 则删除操作 = 将头结点的next引用存入table[i]中
if (prev == e)
table[i] = next;
//否则 将以table[i]为头结点的链表中，当前Entry的前1个Entry中的next 设置为 当前Entry的next（即删除当前Entry = 直接跳过当前Entry）
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
//判断是否存在该键的键值对；是 则返回true
//调用get（），判断是否为Null
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
//作用：判断是否存在该值的键值对；是 则返回true
public boolean containsValue(Object value) {
// 若value为空，则调用containsNullValue()
if (value == null)
return containsNullValue();
// 若value不为空，则遍历链表中的每个Entry，通过equals（）比较values 判断是否存在
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;//返回true
return false;
}
// value为空时调用的方法
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}扩容resize（）
在扩容过程中，在将旧数组上的数据 转移到 新数组上时，转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况。设重新计算存储位置后不变，即扩容前 = 1->2->3，扩容后 = 3->2->1。此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态 = 线程不安全
//当容量不足时（容量 > 阈值），则扩容（扩到2倍）
void resize(int newCapacity) {
//保存旧数组（oldtable）
Entry[] oldTable = table;
//保存旧容量(oldcapacity)
int oldCapacity = oldTable.length;
//若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根据新容量（2倍容量）新建1个数组，即新table
Entry[] newTable = new Entry[newCapacity];
//将旧数组上的数据（键值对）转移到新table中，从而完成扩容
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//新数组table引用到HashMap的table属性上
table = newTable;
//重新设置阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//将旧数组上的数据（键值对）转移到新table中，从而完成扩容
void transfer(Entry[] newTable, boolean rehash) {
//获取新数组的大小 = 获取新容量大小
int newCapacity = newTable.length;
//通过遍历旧数组，将旧数组上的数据（键值对）转移到新数组中
for (Entry<K,V> e : table) {
while(null != e) {
//遍历以该数组元素为首的链表
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//重新计算每个元素的存储位置
int i = indexFor(e.hash, newCapacity);
//将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
e.next = newTable[i];
newTable[i] = e;
//访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
e = next;
}
}
}三.JDK1.8版本的HashMap
JDK1.8版本对HashMap进行了一些修改，与1.7版本最大的不同就是利用了红黑树，所以1.8版本的HashMap的组成是由数组+链表+红黑树组成。我们在查找的时候，根据hash值能够快速定位到数组的具体下标，但是之后去链表中查找具体的Entry结点必须要一个一个查找下去，整体的时间复杂度就为O(n)。为了降低时间复杂度，在Java8中，规定了当链表中的元素超过8个以后，就会将链表转换为红黑树，在这些位置进行查找的时候就可以降低时间复杂度度O(log(N))。
1.8版本结构图
?红黑树的原理
红黑树是二分搜索树一种，主要是为了避免出现极端情况，导致二分搜索树的成为链表结构。所以诞生出了红黑树，尽量避免出现极端情况。而平衡二叉树是一种自平衡的二分搜索树，一旦结点的左右高度差大于1，就会自动平衡，采取自己内部处理措施。平衡二叉树的弊端就在于频繁的去处理自平衡问题，极大的影响到了代码本身的执行效率，所以便诞生了红黑树。红黑树保证了对元素查找、删除和插入的时间复杂度控制在O(logn)，不会存在极端情况下的O(n)。
红黑树的特性:
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。?[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。?
?JDK1.8源码
继承体系、构造方法和1.7版本完全相同
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
transient Node<K,V>[] table;//结点数组
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
}
?构造方法：
//构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造一个带指定初始容量和加载因子的空 HashMap。
public HashMap7(int initialCapacity, float loadFactor) {
//对initialCapacity进行异常处理
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 = initialCapacity;
//一个空方法用于未来的子对象扩展
init();
}
void init() {
}
//包含“子Map”的构造函数
//即 构造出来的HashMap包含传入Map的映射关系
//加载因子 & 容量 = 默认
public HashMap(Map<? extends K, ? extends V> m) {
// 设置容量大小 & 加载因子 = 默认
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
// 该方法用于初始化 数组 & 阈值，下面会详细说明
inflateTable(threshold);
// 将传入的子Map中的全部元素逐个添加到HashMap中
putAllForCreate(m);
}?常量
//容量（capacity）：必须是2的幂 & <最大容量（2的30次方）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
//加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
final float loadFactor; // 实际加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子 = 0.75
//扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）
//扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
//扩容阈值 = 容量 x 加载因子
int threshold;
//其他
transient Node<K,V>[] table; // 存储数据的Node类型 数组，长度 = 2的幂；数组的每个元素 = 1个单链表
transient int size;// HashMap的大小，即 HashMap中存储的键值对的数量
/**
* 与红黑树相关的参数
*/
//桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
//桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
//最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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;
}
}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);
}常用方法?
V get(Object key); // 获得指定键的值
V put(K key, V value); // 添加键值对
void putAll(Map<? extends K, ? extends V> m); // 将指定Map中的键值对 复制到 此Map中
V remove(Object key); // 删除该键值对
boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value); // 判断是否存在该值的键值对；是 则返回true
Set<K> keySet(); // 单独抽取key序列，将所有key生成一个Set
Collection<V> values(); // 单独value序列，将所有value生成一个Collection
void clear(); // 清除哈希表中的所有键值对
int size(); // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空hash计算
/** 作用：让key的hash值的高16位也参与路由运算
* 异或：相同则返回0，不同返回1
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//将key的hashcode值异或value的hashcode值
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}get方法获取value
public V get(Object key) {
Node<K,V> e;
//计算需获取数据的hash值
//通过getNode（）获取所查询的数据
// 获取后，判断数据是否为空
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
//tab：引用当前hashMap的散列表
//first：桶位中的头元素
//e：临时node元素
//n：table数组长度
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//第一种情况：定位出来的桶位元素 即为咱们要get的数据
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//说明当前桶位不止一个元素，可能 是链表 也可能是 红黑树
if ((e = first.next) != null) {
//第二种情况：桶位升级成了 红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//第三种情况：桶位形成链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
删除结点
public V remove(Object key) {
Node<K,V> e;
//传入removeNode（）方法
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) {
//tab：引用当前hashMap中的散列表
//p：当前node元素
//n：表示散列表数组长度
//index：表示寻址结果
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//说明路由的桶位是有数据的，需要进行查找操作，并且删除
//node：查找到的结果
//e：当前Node的下一个元素
Node<K,V> node = null, e; K k; V v;
//第一种情况：当前桶位中的元素 即为 你要删除的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
//说明，当前桶位 要么是 链表 要么 是红黑树
if (p instanceof TreeNode)//判断当前桶位是否升级为 红黑树了
//第二种情况
//红黑树查找操作，下一期再说
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//第三种情况
//链表的情况
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//判断node不为空的话，说明按照key查找到需要删除的数据了
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//第一种情况：node是树节点，说明需要进行树节点移除操作
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//第二种情况：桶位元素即为查找结果，则将该元素的下一个元素放至桶位中
else if (node == p)
tab[index] = node.next;
else
//第三种情况：将当前元素p的下一个元素 设置成 要删除元素的 下一个元素。
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}转换成红黑树?
当数组中的某个单链表的长度大于8时，就会调用此方法就行链表转换成红黑树的方法。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}总结?
相同点：
- 默认初始容量都是16，默认加载因子都是0.75。容量必须是2的指数倍数
- 扩容时都将容量增加1倍
- 根据hash值得到桶的索引方法一样，都是i=hash&(cap-1)
- 初始时表为空，都是懒加载，在插入第一个键值对时初始化
- 键为null的hash值为0，都会放在哈希表的第一个桶中
不同点：
- 最为重要的一点是，底层结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构
- 主要区别是插入键值对的put方法的区别。1.8中会将节点插入到链表尾部，而1.7中会将节点作为链表的新的头节点
- JDk1.8中一个键的hash是保持不变的，JDK1.7时resize()时有可能改变键的hahs值
- rehash时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序
- JDK1.8是通过hash&cap==0将链表分散，而JDK1.7是通过更新hashSeed来修改hash值达到分散的目的
?