[toc]
- 这篇文章主要关注的是jdk1.8中HashMap的实现。
- HashMap是一个存储键值对的集合，它是线程不安全的，允许键值是null,底层的数据结构有数组+链表+红黑树。
属性
- 静态属性
//序列化版本UID
private static final long serialVersionUID = 362498820763181265L;
/**
* 默认的初始容量是16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 树化阈值。当添加元素到桶中，如果桶中链表长度被添加到至少8，链表就转换为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 链表还原阈值。
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 最小数形化容量。桶中链表被转换为红黑树的最小容量是64
*/
static final int MIN_TREEIFY_CAPACITY = 64;
- 内部链表结点类
- HashMap 是通过拉链法来解决冲突的，当链表到一定长度再转换成红黑树。以下是链表节点。
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;
}
}
- 非静态属性
/**
* 哈希表，在第一次使用时初始化，当需要扩容时自动扩容。长度总是2的整数次幂
*/
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
/**
* map中键值对个数
*/
transient int size;
/**
* 通过容量*加载因子计算得到，当键值对的个数大于这个值就进行扩容。
* 这样做是为了减少哈希冲突。
* 浪费了一定的空间，但换来的是查找效率的提高。
*/
int threshold;
/**
* 哈希表的加载因子
*/
final float loadFactor;
构造函数
1. 带初始容量和加载因子的构造器
/**
* 带初始容量和加载因子的构造器
* 初始化时并没有创建数组，只是为loadFactor和threshold赋值，threshold记录了要初始化的容量
* @param initialCapacity 初始容量
* @param loadFactor 加载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//返回2的整数次幂作为容量
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2.其它构造器
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
hash函数(扰动函数)
//hash方法，hashCode的低十六位和高十六位异或,key为null时hash值为0
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- jdk8让hashcode的高16和低16位都参与到hash值的计算，是为了在哈希表长度较小的情况下，也能尽量的减少哈希冲突。将key的hashcode的低16位和高16位进行异或。
put操作
/**
* 添加一个键值对到哈希表中，如果键值已经存在，用新的value值替换原来的value值
* @param key
* @param value
* @return
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* @param hash key的hash值
* @param key
* @param value
* @param onlyIfAbsent 如果是true,不改变已经存在的key的value值
* @param evict
* @return 如果结点已经存在，返回之前的value,否则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//表为空初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//index=(n - 1)&hash,对应桶中位置没有结点则new一个结点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断首结点和要插入结点是否相等，首先判断hash值是否相同，再用equals()判断
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果不相等，是树节点，红黑树插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//是链表，遍历链表尾插法插入
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度大于等于8，树形化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//遍历时发现结点已存在，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//已存在结点且onlyIfAbsent是false，将value赋值给已存在结点，返回旧的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//HashMap同样要维护modCount
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
-
put操作大致流程图示
image
- HashMap 的散列函数本质上是除留余数法，为了提高效率，源码中不使用直接取模，使用了位运算提高速度。当 length 为 2 的 n 次方时，h & (length - 1) 就相当于h对 length 取模。所以，HashMap 的容量n要求是2的整数次幂,通过(n - 1) & hash计算出位置 。
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;
//先判断，只有当哈希表不为空，且表的长度大于0，且key对应的位置有结点时，再进行操作，否则直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//先判断第一个结点与key是否匹配，如果匹配，返回第一个结点
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 {
//判断结点和key是否匹配
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
resize操作
1.调用resize的两种情况
- 第一次调用 HashMap 的 put 方法时，会调用 resize 方法对 table 数组进行初始化，如果不传入指定值，默认大小为 16。
- 扩容时会调用 resize，即 size > threshold 时，table 数组大小翻倍。
2. resize方法的逻辑
- 每次扩容之后容量都是翻倍。扩容后要将原数组中的所有元素找到在新数组中合适的位置。
- 当我们把 table[i] 位置的所有 Node 迁移到 newtab 中去的时候：这里面的 node 要么在 newtab 的 i 位置（不变），要么在 newtab 的 i + n 位置。也就是我们可以这样处理：把 table[i] 这个桶中的 node 拆分为两个链表 l1 和 l2：如果 hash & n == 0，那么当前这个 node 被连接到 l1 链表；否则连接到 l2 链表。这样下来，当遍历完 table[i] 处的所有 node 的时候，我们得到两个链表 l1 和 l2，这时我们令 newtab[i] = l1，newtab[i + n] = l2，这就完成了 table[i] 位置所有 node 的迁移（rehash），这也是 HashMap 中容量一定是 2 的整数次幂带来的方便之处。
3.resize处理链表部分源码
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果桶中有元素进行处理
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//如果没有冲突的元素，直接将元素放进新表中的桶
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果是树节点
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果桶中是链表
else { // preserve order
// 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成
两个不同的链表，完成rehash
//尾插法
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
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;
}
}
}
}
- 使用HashMap时，可以提前给 HashMap 初始化一个容量，避免在插入的时候，频繁的扩容，因为扩容本身就比较消耗性能！
网友评论