2.JDK1.7中HashMap底层原理分析
2020-09-09 本文已影响0人
Junma_c631
一、hashmap的简单介绍
JDK1.7中，hashmap的数据结构，采用数组加链表的形式存在；
我们都知道hashmap中最常用的两个方法put（key,value）和get（key）
put方法在进行添加元素是怎么做的呢？这里会涉及到哪些逻辑？
1.table数组长度计算
1.根据key调用hash（）算法生成hash值-h
2.根据h和数组长度计算数组下标
3.利用头插法把元素插入entriy链表中
4.数组的扩容机制 等等。
1.1hashMap的数据结构可以用下图表示
image.png
1.2hashMap中的属性介绍
//transient修饰的变量不参与序列化
//默认table数组的初始长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//table数组可扩展的最大长度2的30次方1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子和table数组的扩容有关
//threshold=table数组长度*loadFactory
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空table常量
static final Entry<?,?>[] EMPTY_TABLE = {};
//键值对数组，默认指向空数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//keyvalue总个数
transient int size;
//数组需要扩容时的临界值，当插入元素时的size达到临界值时，需要对数组进行扩容
//threshold=loadFactor*table数组长度
int threshold;
//加载因子
final float loadFactor;
//修改次数fail-fast机制有关
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//hash种子,数组扩容时，是否需要重新计算hash值的判断因子
transient int hashSeed = 0;
1.3hashMap构造器简单介绍
//在不指定参数创建hashmap时会调用此构造函数
public HashMap() {
//调用有参构造器传参为(16,0.75f)
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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;
threshold = initialCapacity;
init();
}
二、HashMap的put方法以及由此延伸的问题点介绍
2.1put方法介绍
public V put(K key, V value) {
//第一次put数组是空数组
if (table == EMPTY_TABLE) {
//根据扩展临界值创建定长数组
inflateTable(threshold);
}
if (key == null)
//处理空值
return putForNullKey(value);
//根据key生成hash值
int hash = hash(key);
//根据hash值和table数组长度生成需要存入元素的数组下标
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;
}
}
//修改次数，跟fast-fail机制有关，每次put、remove等修改操作modCount都会++
modCount++;
//上面循环没有找到存在的key的情况下就会选择添加节点。
addEntry(hash, key, value, i);
return null;
}
2.2第一次put时生成一个2的幂次方数组并让table指向该数组
private void inflateTable(int toSize) {
// 获取一个大于等于toSize的最近的2的幂次方数
int capacity = roundUpToPowerOf2(toSize);
//根据数组长度和加载因子计算扩展临界值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//table引用指向新数组
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
//找到一个最近的大于等于numer的2的幂次方数,作为table数组容量，所以table的容量是一个2的幂次方数.
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;
}
调用该方法前number-1后先左移一位，相当于翻了倍
Integer.highestOneBit((number - 1) << 1)
那17举例来查看计算规律
17 -----0001 0001
1-----0000 1000
|-------0001 1001
2-----0000 0110
|-------0001 1111
4-----0000 0001
|-------0001 1111
8-----0000 0000
|-------0001 1111
...
...
|--------0001 1111
上面的过程可以看出规律，就是最终把高位一下的所有数字变成1:
0001 0001---------->0001 1111
然后:
--------------0001 1111
-->>>1-----0000 1111
相减--------0001 0000
最终结果为:16
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
2.3当key为null的情况put方法怎么处理
hashMap支持key为null的情况
会把key为null的值放到table[0]链表里面。
private V putForNullKey(V value) {
//获取数组下标为0的entry头节点进行遍历
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
//如果已经存在key为null的值，更新最新的值，更新后返回
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//如果原来不存在key为null的值，添加到table[0]的Entry链表中
addEntry(0, null, value, 0);
return null;
}
2.4key的hash算法
为什么需要对hashcode再次进行那么多位运算？
我们看下面获取下标的运算
高位[0111] &运算任意修改都不影响获取的数组下标
比如 0111 0010 、0110 0010、0011 0010 获取到的
数组下标没有任何变化，这就导致在算数组下标时，不那么离散
也就是高位没有参与数组下标的运算。
进行一些位运算后使hashcode更离散，让高位也参与到数组下标的运算。
290 0111 0010
(16-1)15 0000 1111
final int hash(Object k) {
int h = hashSeed;//默认0
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//异或运算相同则为0，不相同则为1
h ^= k.hashCode();
//
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
2.5当前需要插入或更新的<key,value>数组下标的计算
获取数组下标的两个特性:
1.小于数组长度 默认0-15
2.下标需要充分离散
与运算:两个为1才为1
例如如下运算:
290 0111 0010
(16-1)15 0000 1111
与运算 0000 0010 最终结果为2
1560&(16-1)-----8
1261&(16-1)-----13
1131&(16-1)-----11
8510&(16-1)-----14
1530&(16-1)-----10
1246&(16-1)-----14
从上面运算结果看，无论h是多大的数，和(2的幂次方-1)做与运算后都会在 【0~（2的幂次方-1）】范围内
从而可以看出来为什么table数组大小一定是2的幂次方数：
因为在计算数组下标的时候会用到2的幂次方-1的低位特性，与操作计算数组下标要比取余%操作效率更高
static int indexFor(int h, int length) {
//对hash值和(数组下标-1)进行&运算
return h & (length-1);
}
2.6添加Entry节点以及hashMap的table数组扩容
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);
}
hashmap的扩容
size:所有链表中node元素的总个数.
扩容条件:
1.当元素总个数大于等于扩展因子
2.当前需要插入的table[index]中链表不为空
为什么要满足这个条件呢？
最大限度的靠近，使一个table[index]中只存储一个entrynode，
使链表的长度最小化。这样会最大限度的增加get(key)的效率。
扩容的长度是原数组大小的2倍:[2 * table.length]
/**
数组扩容
*/
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, initHashSeedAsNeeded(newCapacity));
//table指向新的table数组
table = newTable;
//给扩展因子重新赋值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
数组扩容时老数组中元素转移到新数组，新下标的生成规律
数组扩容后新的元素下标的规律：
第一种扩容场景：
old:
hash: 0101 0101
16-1 : 0000 1111
&操作之后: 0000 0101 index:5
new:
hash: 0101 0101
32-1 : 0001 1111
&操作之后: 0001 0101 index=oldtable.length+5=16+5=31
第二种扩容场景：
old:
hash: 0100 0101
16-1 : 0000 1111
&操作之后: 0000 0101 index:5
new:
hash: 0100 0101
32-1 : 0001 1111
&操作之后: 0000 0101 index=5
扩容后下标只能是两个位置：要么是扩容后的原位置
要么是：原数组长度+原位置下标号
老数组元素转移到新数组中的转移过程
1当前entry的next引用指向新数组的头元素
2.再把新数组的头元素设置成当前entry(相当于是头插法移植到新数组)
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;
//一般不进行重新计算hash值，key的hash正常是固定的
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//根据新的数组长度和节点的hash值重新算下标
int i = indexFor(e.hash, newCapacity);
//e.next引用指向新数组的头元素
e.next = newTable[i];
//再把新数组的头元素设置成当前entry(相当于是头插法移植到新数组)
newTable[i] = e;
//循环条件
e = next;
}
}
}
2.7元素插入采用头插法
void createEntry(int hash, K key, V value, int bucketIndex) {
//获取table数组下标为bucketIndex的entry头节点
Entry<K,V> e = table[bucketIndex];
//利用头插法，插入链表元素。
table[bucketIndex] = new Entry<>(hash, key, value, e);
//元素个数+1
size++;
}
三、HashMap的快速失败机制 fast-fail
hashMap中维护了一个属性modCount,每次对hashMap的修改操作modCout都会modCout++
在创建keySet().iterator()迭代器的时候，会把modCout属性赋值给迭代器expectedModCount，
我们都知道hashMap是线程不安全的，使用迭代器提供的方法时会先判断modCout是否和expectedModCount相等，
如果不相等证明在使用迭代器的同时有线程修改了hashmap的元素，这时候就会快速抛异常失败操作。
四、头插法和尾插法的探讨？
在put方法内部，会循环遍历Entry的链表，无论头插法还是尾插法对于put方法来说都一样，
都避免不了循环节点来判断是否包含了这个key。
五、多线程情况下调用put方法数组扩容会存在什么问题
可能会出现死循环。
数组扩容时，运用头插法进行插入新的列表，这时候链表的顺序和原数组的中链表的顺序
是倒过来了，也就是entry中next的指向
发生了变化，多线程情况下，扩容时，如果新增加了两个新的数组，再进行扩容时，某一个新增加的数组的链表元素指向了
另外一个新增加的元素，这种情况下可能会出现一个封闭的循环链表一直循环。
