目录
- 数据结构
- 链表的作用
- 链表问题
- 数据结构简图
- 源码解析
- 重要成员变量说明
- 构造函数
- put操作
- 初始化数组
- Key为null的处理
- 计算hash
- 添加链表节点--新增Entry
- 扩容
- 缺点
- 扩容死锁分析
- 单线程扩容
- 多线程扩容
数据结构
jdk1.7的hashmap的底层结构是数组加单向链表实现的。将key的hash值进行取模获取index既即将存放的元素的数组的位置。然后到对应的链表中进行put和get操作
链表的作用
因为对数组进行取模的时候可能会遇到获取index的位置是一样的,所以可能会遇到hash碰撞冲突,而HashMap使用链表来存储hash碰撞的元素
链表问题
如果在hash碰撞发生严重的情况下,则会出现插入和获取元素时间过长的问题,jdk1.8对此进行了树化来解决这个问题,详情见jdk1.8HashMap的详解
数据结构简图
数组(绿色):hash数组(桶),数组元素是每个链表的头节点
链表(浅蓝色):解决hash冲突,不同的key映射到了数组的同一索引处,则形成链表
源码解析
重要成员变量说明
//默认初始化容量 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;
//默认空数组
static final Entry<?,?>[] EMPTY_TABLE = {};//用来存放元素得数组,默认== EMPTY_TABLE 用来判断hashMap是否真正的初始化
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//元素数量
transient int size;//构造函数时为设置的容量,初始化后为容量*负载因子
int threshold;//负载因子
final float loadFactor;
为什么负载因子的大小默认为0.75而不是1呢
这涉及到一个数学运算
根据HashMap的扩容机制,他会保证capacity的值永远都是2的幂
那么,为了保证负载因子(loadFactor) * 容量(capacity)的结果是一个整数,这个值是0.75(3/4)比较合理,因为这个数和任何2的幂乘积结果都是整数
如果我们把负载因子设置成1,容量使用默认初始值16,那么表示一个HashMap需要在"满了"之后才会进行扩容,显然会发生更多的hash碰撞
总结:负载因子默认为0.75是最适合减少hash碰撞又能保证 loadFactor*capacity的结果是一个整数的一个值
构造函数
public HashMap() {//调用下面的构造函数 16, 0.75Fthis(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 容量 负载因子
public HashMap(int initialCapacity, float loadFactor) {//容量不能小于0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//容量最大为MAXIMUM_CAPACITYif (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);//设置当前负载因子为默认负载因子this.loadFactor = loadFactor;//构造函数时threshold 为 容量threshold = initialCapacity;//空方法init();
}
put操作
public V put(K key, V value) {//如果table == EMPTY_TABLE则table没有真正的初始化,需要初始化if (table == EMPTY_TABLE) {inflateTable(threshold);}//hashmap 可以存放null keyif (key == null)return putForNullKey(value);//计算key的hashint hash = hash(key);//求出当前key要存放在数组中的下标int i = indexFor(hash, table.length);//遍历当前下标的key, 看有没有相同的key, 如果有就替换value,返回oldValuefor (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++;//说明当前位置没有相同的key,新增Entry放入链表addEntry(hash, key, value, i);//存放前key不存在 返回null作为oldValuereturn null;
}
初始化数组
private void inflateTable(int toSize) {//hashMap为了方便计算下标中的位置,所以容量需要设置为2的次方,但是没有做强制校验//如果设置的容量不是2的次方,这里会获取到比容量大 且 最小的2的次方int capacity = roundUpToPowerOf2(toSize);//获取扩容的门槛,容量 * 负载因子threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//初始化数组为2的次方的capacitytable = new Entry[capacity];//为了看一下capacity是否需要重置一下哈希种子,是为了得到的哈希值更加散列。initHashSeedAsNeeded(capacity);
}
Key为null的处理
private V putForNullKey(V value) {//如果key==null,在1.7中就会把该元素放入下标为0的位置//如果0位置已经存在元素,就需要判断是否是同一个key,如果是,就需要替换oldValue并返回//不是null的元素求得的位置也可能是0for (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++;//此时key==null,这一步表示0位置没有key==null的Entry,新增Entry入链表addEntry(0, null, value, 0);return null;
}
计算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);
}static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);
}
添加链表节点–新增Entry
void addEntry(int hash, K key, V value, int bucketIndex) {//判断是否扩容 //1.当前size >= capacity * loadFactory//2.当前下标位置不等于nullif ((size >= threshold) && (null != table[bucketIndex])) {//扩容,容量必须是2的次方,所以扩容是旧容量的2倍resize(2 * table.length);//重新计算在扩容之后hashhash = (null != key) ? hash(key) : 0;//重新计算在扩容之后的下标bucketIndex = indexFor(hash, table.length);}//放入EntrycreateEntry(hash, key, value, bucketIndex);
}void createEntry(int hash, K key, V value, int bucketIndex) {//获取到当下下标的entryEntry<K,V> e = table[bucketIndex];//采用头插法放入链表头部,e是当前下标的元素,下面Entry的构造函数时next//即把当前下标的e作为新元素的next,把next放到当前下标位置table[bucketIndex] = new Entry<>(hash, key, value, e);size++;
}
扩容
void resize(int newCapacity) {//临时保存旧tableEntry[] oldTable = table;//临时保存旧table的长度int oldCapacity = oldTable.length;//如果旧容量已经达到了最大容量,不扩容if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//创建扩容后的数组Entry[] newTable = new Entry[newCapacity];//把旧数据拷贝到新数组, initHashSeedAsNeeded(newCapacity)重置新的数组hash种子返回是否需要rehashtransfer(newTable, initHashSeedAsNeeded(newCapacity));//替换旧数组table = newTable;//重新计算扩容门槛threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;//遍历旧数组用于转移到新数组for (Entry<K,V> e : table) {//只有当前的e != null 才需要拷贝while(null != e) {//临时保存一下 next,这点也是出现回环链表 死循环的原因Entry<K,V> next = e.next;//是否重新计算hashif (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//计算在新数组中的位置int i = indexFor(e.hash, newCapacity);//其实还是头插法,如果当前位置已经有元素了,就把该元素作为e的nexte.next = newTable[i];//把e放入该位置newTable[i] = e;//把扩容前的e的next复制给e继续执行该流程,完成旧数组链表的下一个元素的转移e = next;}}
}
缺点
HashMap是线程不安全的,不安全的具体原因就是在高并发场景下,扩容可能产生死锁 (Jdk1.7存在)以及get操作可能带来的数据丢失
扩容死锁分析
死锁问题核心在于下面代码,多线程扩容导致形成的链表环! 以下代码是去除了与分析死锁无关的代码
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {//记录oldhash表中e.next Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//rehash计算出数组的位置(hash表中桶的位置) int i = indexFor(e.hash, newCapacity);//e要插入链表的头部, 所以要先将e.next指向new hash表中的第一个元素e.next = newTable[i];//将e放入到new hash表的头部newTable[i] = e;//转移e到下一个节点, 继续循环下去e = next;}}
}
单线程扩容
**假设:**hash算法就是简单的key与length(数组长度)求余。hash表长度为2,如果不扩容, 那么元素key为3,5,7按照计算(key%table.length)的话都应该碰撞到table[1]上
**扩容:**hash表长度会扩容为4重新hash,key=3 会落到table[3]上(3%4=3), 当前e.next为key(7), 继续while循环重新hash,key=7 会落到table[3]上(7%4=3), 产生碰撞,这里采用的是头插入法,所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)当前e.next为key(5), 继续while循环重新hash,key=5 会落到table[1]上(5%4=3), 当前e.next为null, 跳出while循环,resize结束
过程如下图所示:
多线程扩容
下面就是多线程同时put的情况了, 然后同时进入transfer方法中:假设这里有两个线程同时执行了put()操作,并进入了transfer()环节
while(null != e) {//线程1执行到此被调度挂起(cpu时间片轮转等发生上下文切换)//记录oldhash表中e.nextEntry<K,V> next = e.next;//rehash计算出数组的位置(hash表中桶的位置) int i = indexFor(e.hash, newCapacity);//e要插入链表的头部, 所以要先将e.next指向new hash表中的第一个元素e.next = newTable[i];//将e放入到new hash表的头部newTable[i] = e;//转移e到下一个节点, 继续循环下去e = next;
}
那么此时的状态为:
从上面的图我们可以看到,因为线程1的 e 指向了 key(3),而 next 指向了 key(7),在线程2 rehash 后,就指向了线程2 rehash 后的链表
然后线程1被唤醒了:
- 执行e.next = newTable[i],于是 key(3)的 next 指向了线程1的新 Hash 表,因为新 Hash 表为空,所以e.next = null
- 执行newTable[i] = e,所以线程1的新 Hash 表第一个元素指向了线程2新 Hash表的 key(3)。好了,e 处理完毕
- 执行e = next,将 e 指向 next,所以新的 e 是 key(7)
然后该执行 key(3)的 next 节点 key(7)了:
- 现在的 e 节点是 key(7),首先执行Entry next = e.next,那么 next 就是key(3)了
- 执行e.next = newTable[i],于是key(7) 的 next 就成了 key(3)
- 执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(7)
- 执行e = next,将 e 指向 next,所以新的 e 是 key(3)
此时的状态为:
然后又该执行 key(7)的 next 节点 key(3)了:
- 现在的 e 节点是 key(3),首先执行Entry next = e.next,那么 next 就是null
- 执行e.next = newTable[i],于是key(3) 的 next 就成了 key(7)
- 执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(3)
- 执行e = next,将 e 指向 next,所以新的 e 是 key(7)
这时候的状态如图所示:
很明显,环形链表出现了