Java集合系列之HashMap
Hello,大家好,喜欢看我文章的小伙伴应该都知道作者正在写Java并发编程系列的文章,但是今天要插播一些Java集合系列的文章,之后也会一直并行的写Java并发编程系列文章和Java集合系列的文章,因为一直写一个系列的文章实在是比较枯燥。而且这两个系列其实是有关联的,希望大家喜欢。好了,废话少说,今天给大家讲一讲HashMap底层的实现,结构如下:
- HashMap底层数据结构
- 核心API
- 扩容相互(容量,负载因子,2的倍数)
- 非线程安全
1. HashMap底层数据结构
HashMap底层是数组加上链表的数据结构,每一个数组的元素通过指针又引出一个链表,链表的尾部指针指向NULL,这个元素的结构如下:static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
....
}
可以看到,存储了K和V,然后一个next指针指向下一个元素。
2. 核心API
知道了存储结构是不够的,元素怎么入到这个集合里面呢?下面来看下核心的API,put和get.
put()讲解:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
//key为null时,直接丢到table[0]这个数组位置上
return putForNullKey(value);
//自己封装的hash方法,对key做完hash后加了高位运算,尽量避免Hash碰撞
int hash = hash(key);
//根据hash值`对数组长度取模`,算出应该放入索引为几的数组格子里
int i = indexFor(hash, table.length);
//如果这个格子里已经有元素了,那么就遍历执行equals方法,如果equals也一样,就用value替换掉oldValue。返回oldValue
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;
}
}
//如果这个数组隔离里没有equals一样的,把这个元素加入到链表的头部。
modCount++;
addEntry(hash, key, value, i);
return null;
}
当我们往 HashMap 中 put 元素的时候,先根据 key 的 hashCode 重新计算 hash 值,根据 hash 值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。 还可以看到,当key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value(可以为NULL) 随之保存在那里即可。
这里再顺带提一下,为什么HashMap在扩容时数组的长度必须是2的倍数(默认16),其实这和indexFor()这个方法有关系的,这个方法是根据key的hash值算出在数组对应的索引,大家可能会想到,直接用hash%数组长度不就可以保证元素尽量平均的分配到数组里,避免少的碰撞吗?但是取模的效率是比较低下的,所以这个API的实现如下:
static int indexFor(int h, int length) {
return h & (length-1);
}
h & (length-1)要和h%length的效果一样就必须保证length的长度是2的倍数,至于为什么,小弟也不知道,这是算法这块的东西了。而&符号可比%符号效率高的多了。所以大家知道了吧。数组长度为什么必须是2的倍数。 整体上看,当数组长度为 2 的 n 次幂的时候,不同的 key 算得得 index 相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。
稍微总结下put(): 当程序试图将一个key-value对放入HashMap中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部.
get()讲解:
public V get(Object key) {
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;
}
其实大家应该自己都可以看懂了,比较easy,从 HashMap 中 get 元素时,首先计算 key 的 hashCode,找到数组中对应位置的某一元素,然后通过 key 的 equals 方法在对应位置的链表中找到需要的元素。
好,存储元素和读取元素来一个总结: 简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 hash 算法来决定其在数组中的存储位置,在根据 equals 方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry 时,也会根据 hash 算法找到其在数组中的存储位置,再根据 equals 方法从该位置上的链表中取出该Entry.
3. 扩容相关(容量,负载因子,2的倍数)
当 HashMap 中的元素越来越多的时候,hash 冲突的几率也就越来越高,因为数组的默认长度是16。所以为了提高查询的效率,就要对 HashMap 的数组进行扩容,数组扩容这个操作也会出现在 ArrayList 中,这是一个常用的操作,而在 HashMap 数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是 resize。
那么 HashMap 什么时候进行扩容呢?当 HashMap 中的元素个数超过(数组大小 XloadFactor)时,就会进行数组扩容,loadFactor的默认值为 0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为 16,那么当 HashMap 中元素个数超过 16X0.75=12 的时候,就把数组的大小扩展为 2X16=32,即扩大一倍(想想前面讲过的2的倍数),然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap 中元素的个数,那么预设元素的个数能够有效的提高 HashMap 的性能。
然后顺带提下几个HashMap的构造方法:
- HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity):构建一个初始容量为initialCapacity,负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。默认的0.75其实是一个比较折中的方案了。
4. 非线程安全
稍微提一下,HashMap是非线程安全的,在多线程并发访问的时候,扩容时有可能造成数组的某个元素后的链表形成闭环,所以查询的时候就一直死循环,造成100%利用率。所以,在多线程环境下应该使用ConcurrentHashMap替代之。后面会专门讲解ConcurrentHashMap.此外,关于HashMap为什么会造成这种死循环,因为网上文章比较多我就不多余了,给大家几个传送门:
结语
好了,HashMap算是给大家说完了,后续会继续给大家分享Java集合的相关底层知识。Over,Have a good day!