HashMap 的 hash 方法原理是什么
在了解HashMap的原理之前, 我们先看看hash散列表是怎么工作的, 他的原理是什么。
散列表的原理是将关键字通过散列函数映射到固定的位置上, 并对原始值进行处理, 最终得到的值就是我们所说的哈希值, 即在HashMap中所表现出来的值。在JDK1.7之前,HashMap的内部实现方式是数组 + 链表,数组的下标就是哈希值,而链表则是解决哈希冲突的方案。而在JDK1.8之后,由于链表会引起频繁的GC,会对性能有影响,而添加了红黑树的设计,对冲突的解决更加高效。
比如在HashMap中,我们put一个新的键值对时,便会对新的key生成一个哈希值(hashCode),这个hashCode将会指导他在数组中的大致位置, 但有可能会存在相同的hashCode(即hash冲突),因此会通过拉链法(或者是红黑树)来使链表在当前位置上依次挂起来,这样既能保证查询时的O(1)速度,又能避免产生很多碰撞。
具体来说,当我们使用HashMap的put方法时,HashMap首先会对key进行hash计算,得到一个hash值。然后,HashMap会将这个hash值用来决定key-value存放在数组中的位置。
hash方法的实现原理
接下来是讲解hash方法的实现原理,hash方法是用来计算hashCode的,接下来是hash方法的代码实现:
static final int hash(Object key) {
int h;
// key.hashCode()计算出key的哈希值h
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在上面的实现中, 首先对键值调用key.hashCode()
方法,确定键值的哈希值h。hashCode()的具体实现可以看做是从对象的物理地址、时间等因素来生成唯一标识。
在key为null的情况下,哈希值设为0。
为什么要进行以下位运算呢,在进行哈希值计算的时候借助到了以下位运算:
h ^ (h >>> 16)
这里是采用了hash分流算法, 具体步骤如下:
- 按照hashcode和右移16的结果做异或,生成新的哈希值
- 将新的哈希值除以容量size的余数,得到下标index
- 如果当前下标没有hash冲突,则直接将其放入slots[index]中;
- 如果当前下标有hash冲突,则将当前的键值对添加到当前下标对应的链表的最后;
然而hash散列并不是完美的算法, 在极端情况下可能出现hash冲突,即不同的两个key所对应的hash值是相同的,这就需要采取一些特殊处理的策略,例如拉链法或者是一些替代性的算法,这些算法都有其优劣性。对于比较简单的key值集合来说,HashMap可以将一个键值的HashCode直接映射为一个下标,这种情况下性能最好。
下面再举个栗子: 我们以五个关键字生成的hashCode为例,说一下在HashMap中如何定位分组的过程。
String s1= "name";
String s2 = "gender";
String s3 = "age";
String s4 = "addr";
String s5 = "phone";
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
System.out.println(s3.hashCode());
System.out.println(s4.hashCode());
System.out.println(s5.hashCode());
//分别输出如下,
//名字(hashCode): 3373707
//性别(hashCode): 1967188755
//年龄(hashCode):95458899
//地址(hashCode): 3009914
//电话(hashCode): 3081039
所以, 当存储出现哈希冲突,我们可以通过维护链表的方式解决。例如, 有两个键值对[key1, value1]和[key2, value2],他们都对应了相同的哈希值h。那么,HashMap就将其存储在[h]位置的链表的尾部。这样,查询哈希表中任一键值对时,HashMap首先对该键值计算哈希值,然后找到[h]位置并遍历链表,在链表中找到一个哈希值和要查询的键值的哈希值相同的键值对。 haMap的hash方法原理和hash算法通过详细的讲解,我们已经能够对HashMap有了较全面的认识。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java面试题之HashMap 的 hash 方法原理是什么 - Python技术站