容器-Advanced

散列与散列码

标准类库中的类被用作HashMap的键,用的很好,因为它具备了键所需要的全部性质。

如果需要使用自己的类作为HashMap的键,必须同时重载hashCode()和equals()。
hashCode()不需要总是能够返回唯一的标识码(应该更关注生成速度,而不是唯一性),但是equals()方法必须严格地判断两个对象是否相同。通过hashCode()和equals()必须能够完全的确定对象的身份。

实用的hashCode()一般速度快,且有意义。也就是说,它一般是基于对象的内容生成散列码,因为在使用中,两个对象的内容是否一致一般是场景下判断是否产生了重复元素的依据。

HashMap源码

HashMap在实现上采用数组+链表的方式。产生的hash冲突通过链表来解决。

HashMap的性能相关:

  1. 容量: 表中的桶位数,当负载达到负载因子水平时,会自动以2倍的量扩容。
  2. 初始容量: 表在创建时所拥有的桶位数,要求一定是2的n次幂。
  3. 负载因子: 超过负载自动扩容,扩容开销大。但负载因子太大,空间利用虽然提高,但查询遍历等操作变慢,因为链表变长了。
  4. null: HashMap允许null的key和null的value。key为null的键值对存储在table[0]下,但不一定在表头。

此外,新增的键值对会头插到每个桶的表头。

1
2
3
4
5
6
7
8
//计算hash值的方法 通过键的hashCode来计算
static int hash(int h) {
// 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);
}

length为2的n次幂的好处:通过位运算实现取余操作,提升性能

1
2
3
static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值
return h & (length-1);
}

其他细节参考两篇解读源码的文章:

Java集合源码剖析:HashMap源码剖析

Java集合:HashMap源码剖析

0 Comments