为了便于理解，以下源码分析以 JDK 1.7 为主。
存储结构HashMap 内部的存储结构是一个 Entry 类型的数组 table。 transient Entry[] table;
Entry 是 Map 的内部类，用于存储键值对，它包含了四个属性：key，value，hash 值和 next 指针。从 next 指针可以看出， table 数组中的每个位置被当成一个桶，一个桶存放一个 Entry 类型的链表。HashMap 使用拉链法来解决哈希冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry，即 hashCode % table.length 相等的 Entry 存放在同一个桶（链表）中。 
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
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;
}
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<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");Copy to clipboardErrorCopied
新建一个 HashMap，默认大小为 16； 插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115=3。 插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118=6。 插入 <K3,V3> 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118=6，插在 <K2,V2> 前面。
应该注意到链表的插入是以头插法方式进行的，例如上面的 <K3,V3> 不是插在 <K2,V2> 后面，而是插入在链表头部。 查找需要分成两步进行： 
put 操作public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 键为 null 单独处理，所有 HashMap 允许 key 为 null
if (key == null)
return putForNullKey(value);
int hash = hash(key);
// 确定桶下标
int i = indexFor(hash, table.length);
// 先找出是否已经存在键为 key 的键值对，如果存在的话就更新这个键值对的值为 value
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
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;
}
HashMap 允许插入键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法，也就无法确定该键值对的桶下标，只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。 private V putForNullKey(V 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 ;
addEntry(0, null, value, 0);
return null;
}
使用链表的头插法，也就是新的键值对插在链表的头部，而不是链表的尾部。 void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
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 ;
}Copy to clipboardErrorCopied
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
get 操作相对于 put 过程，get 过程是非常简单的。 public V get(Object key) {
// 之前说过，key 为 null 的话，会被放到 table[0]，所以只要遍历下 table[0] 处的链表就可以了
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 确定桶下标，然后从头开始遍历链表，直到找到为止
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
确定桶下标无论是 put 还是 get 操作都需先确定一个键值对所在的桶下标，计算桶下标通过哈希和取模两步实现： int hash = hash(key);
int i = indexFor(hash, table.length);
1. 计算 hash 值 final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}Copy to clipboardErrorCopied
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
2. 取模 令 x = 1<<4，即 x 为 2 的 4 次方，它具有以下性质： x : 00010000
x-1 : 00001111
令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数： y : 10110010
x-1 : 00001111
y&(x-1) : 00000010
这个性质和 y 对 x 取模效果是一样的： y : 10110010
x : 00010000
y%x : 00000010
我们知道，位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能。 确定桶下标的最后一步是将 key 的 hash 值对桶个数取模：hash % capacity，如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算。 static int indexFor(int h, int length) {
return h & (length-1);
}
扩容-基本原理设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 O(N/M)。 为了让查找的成本降低，应该尽可能使得 N/M 尽可能小，因此需要保证 M 尽可能大，也就是说 table 要尽可能大。HashMap 采用动态扩容来根据当前的 N 值来调整 M 值，使得空间效率和时间效率都能得到保证。 和扩容相关的参数主要有：capacity、size、threshold 和 load_factor。 | capacity | table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。 | | size | 键值对数量。 | | threshold | size 的临界值，当 size 大于等于 threshold 就必须进行扩容操作。 | | loadFactor | 装载因子，table 能够使用的比例，threshold = capacity * loadFactor。 |
static final int DEFAULT_INITIAL_CAPACITY = 16; //capacity默认值
static final int MAXIMUM_CAPACITY = 1 << 30; //capacity最大值
static final float DEFAULT_LOAD_FACTOR = 0.75f; //loadFactor默认值
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;
从下面的添加元素代码中可以看出，当需要扩容时，令 capacity 为原来的两倍。 void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size >= threshold)
resize(2 * table.length);
}
扩容使用 resize() 实现，需要注意的是，扩容操作同样需要把 oldTable 的所有键值对重新插入 newTable 中，因此这一步是很费时的。 void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j ) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
扩容-重新计算桶下标在进行扩容时，需要把键值对重新放到对应的桶上。JDK 1.7 是采用根据哈希值重新计算桶下标的方式， JDK 1.8 后 HashMap 使用了一个特殊的机制，可以降低重新计算桶下标的操作。 假设原数组长度 capacity 为 16，扩容之后 new capacity 为 32： capacity : 00010000
new capacity : 00100000
对于一个 Key， 计算数组容量HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。 先考虑如何求一个数的掩码，对于 10010000，它的掩码为 11111111，可以使用以下方法得到： mask |= mask >> 1 11011000
mask |= mask >> 2 11111110
mask |= mask >> 4 11111111
mask 1 是大于原始数字的最小的 2 的 n 次方。 num 10010000
mask 1 100000000
以下是 HashMap 中计算数组容量的代码： 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;
}
JDK 1.8 链表转红黑树JDK 1.8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由数组 链表 红黑树组成。
JDK 1.7 查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，JDK 1.8 当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logn)。
参考https://cyc2018./CS-Notes/#/notes/Java 容器 https://mp.weixin.qq.com/s/usLEfjU-PJ3RbrdmJ_bw3w
来源：https://www./content-4-399701.html
|
