HashMap详解
一、HashMap数据结构
1、HashMap数据结构
-
JDK1.7 数组+链表
-
JDK1.8及以上 数组+链表+红黑树
2、HashMap相关参数
- 默认初始容量：1 << 4（16）
/**
* The default initial capacity - MUST be a power of two.
* 默认初始容量，必须是2的指数幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 最大容量：1<<30（1073741824）
HashMap默认容量为16、最大容量为2的30次方，
可以传入参数指定初始大小，这个参数必须是2的指数幂，如果传入的参数大于2的30次方，则使用最大值2的30次方
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
当然我们可以随意指定一个大小，比如9，但是在put元素时，hashmap会将9进行处理，强制转换成2的指数幂并且大于9、最接近9的数值
- 判断map是否为空，如果是空的则处理容量大小是否满足2的指数幂要求
public V put(K key, V value) {
// 判断map是否为空，如果是空的则处理容量大小是否满足2的指数幂要求
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
- 容量大于等于最大值则使用最大值，容量大于1则强制转换成2的指数幂并且大于9、最接近9的数值，否则直接使用1
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
- 默认加载因子：0.75f
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- table数组：HashMap使用该数组存储数据
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
- 链表：HashMap存储的每个数据项为单向链表结构
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;// hash值相同的下一个元素指针
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
3、hash计算
4、hash碰撞
不同的数据计算出来的hash值是一样的，称为hash碰撞
二、HashMap扩容原理
JDK1.7 存储数据过程
1、是否存在相同hash、key
遍历整个table数组，判断数组中的元素hash值与当前hash值相同，并且key相同，则将这个元素的value更新为当前需要存储的value，并返回旧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;
}
}
2、判断不需要扩容
如果不需要则创建新的元素，并将新的元素指向老的元素
1)、从table数组中取出对应下标位置链表对象
2)、创建新的链表对象将其赋给table数组对应下标位置，并将新创建的链表对象指针指向原链表对象
void createEntry(int hash, K key, V value, int bucketIndex) {
// 1、从**table数组**中取出对应下标位置链表对象
Entry<K,V> e = table[bucketIndex];
// 2、创建新的链表对象将其赋给table数组对应下标位置，并将新创建的链表对象指针指向原链表对象
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
3、需要扩容
单线程扩容过程
1）扩容为数组原来的2倍容量
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // 扩容为2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
2）将当前数组所有数据转移到新创建的数组中
大致流程：遍历数组每个链表项，依次将链表数据插入新创建的数组的某个位置中，采用的是头插法（newTable[i] = e），即遍历链表得到的数据都是往新数组链表根节点存放，最后转移到新数组中链表中数据顺序与原数组链表数据顺序是相反的
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);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
如上图示例，将左边数组转移到右边数组下标1的位置，详细转移过程如下：
-
声明2个变量：e、next，分别指向张三、李四
-
执行e.next = newTable[i]，将张三的next指向1
-
执行newTable[i] = e，将张三移到1的位置
-
执行e = next，将e指向李四，第一遍循环结束
-
第二遍循环开始，执行Entry<K,V> next = e.next，此时next为null
-
执行e.next = newTable[i]，将李四的next指向张三
-
执行newTable[i] = e，将李四插入原来张三所在位置
-
执行e = next，将e指向null，第二遍循环结束
-
执行while(null != e) ，此时e == null不满足条件，扩容结束，可看到扩容结束后，张三与李四位置已互换
多线程扩容过程
-
假设此时有2个线程同时进入该方法执行扩容，2个线程分别创建了新数组进行扩容，并各自声明2个变量指向张三、李四，而线程二在执行Entry<K,V> next = e.next;代码之后因为某种原因卡顿了一下，此时线程一已完成第一遍循环，
-
线程二开始执行e.next = newTable[i]，newTable[i] = e;将张三移到新数组下标1位置
-
执行e = next，将e指向李四，线程二第一遍循环结束
-
线程二第二遍循环开始，执行Entry<K,V> next = e.next，将next指向null
-
执行e.next = newTable[i]，这里李四本身就指向张三
-
执行newTable[i] = e，e = next;这里newTable[i]存的是张三，因此将张三指向李四，e指向null，此时出现了闭环，李四指向张三，张三指向李四
- 当下一次执行put操作时，就出现了死循环，e永远不为空
多线程扩容引发闭环
如上过程所示