HashMap的put、get方法分析与Hash冲突的分析、解决

时间:2022-01-05 19:15:48
1HashMap的实现原理 简单地说,HashMap就是将key做hash算法,然后将hash值映射到内存地址,直接取得key所对应的数据。在HashMap中,底层数据结构使用的是数组,所谓的内存地址即数组的下标索引。afHashMap的高性能需要保证以下几点:
  • hash算法必须是高效的
  • hash值到内存地址(数组索引)的算法是快速的
  • 根据内存地址(数组索引)可以直接取得对应的值
首先来看第一点,hash算法的高效性。在HashMap中,hash算法有关的代码如下: 1 int hash = hash(key.hashCode()); 2 public native int hashCode(); 3 static int hash(int h) { 4 h ^= (h >>> 20) ^ (h >>> 12); 5 return h ^ (h >>> 7) ^ (h >>> 4); 6 } 第一行代码是HashMap中用于计算key的hash值。它前后分别调用了Object类的hashCode()方法和HashMap的内部函数hash()。Object类的hashCode()方法默认是native的实现,可以认为不存在性能问题。而hash()函数的实现全部基于位运算,因此,也是高效的。 注意:native方法通常比一般的方法快,因为它直接调用操作系统本地链接库的API。由于hashCode()方法是可以重载的,因此,为了保证HashMap的性能,需要确保相关的hashCode()是高效的。而位运算也比算术、逻辑运算快。 当取得key的hash值后,需要通过hash值得到内存地址: int i = indexFor(hash, table.length); static int indexFor(int h, int length) { return h & (length-1); } indexFor()函数通过将hash值和数组长度按位取与直接得到数组索引。 最后由indexFor()函数返回的数组索引直接通过数组下标便可取得对应的值。直接的内存访问速度也相当快。因此,可以认为HashMap是高性能的。 2Hash冲突 虽然上节中阐述了在理想情况下HashMap的高效性,但我们依然不得不在实际使用中考虑HashMap的一些特殊情况,这些情况有可能给HashMap带来一定的性能问题。其中,最值得关注便是hash冲突。如图3.11所示,需要存放到HashMap中的两个元素1和2,通过hash计算后,发现对应在内存中的同一个地址。此时,HashMap又会如何处理,以保证数据可以完整存放,并正常工作呢? HashMap的put、get方法分析与Hash冲突的分析、解决 3.11 Hash冲突示意图 要处理好这个问题,需要进一步深入HashMap,虽然HashMap的底层实现使用的是数组,但是数组内的元素并不是简单的值,而是一个Entry类的对象。因此,对HashMap结构的贴切描述如图3.12所示。 HashMap的put、get方法分析与Hash冲突的分析、解决 3.12 HashMap表项结构 可以看到,HashMap的内部维护着一个Entry数组,每一个Entry表项包括key、value、next和hash几项。这里特别注意其中的next部分,他指向了另外一个Entry(所以实际上HashMap的数据结构是一个列表数组,数组中每个元素是一个Entry列表,Entry列表中每个元素是一个Entry对象)。进一步阅读HashMap的put()方法源码,可以看到当put()操作有冲突时,新的Entry依然会被安放在对应的索引下标内,并替换原有的值。同时,为了保证旧值不丢失,会将新的Entry的next指向旧值。这便实现了在一个数组索引空间内,存放多个值项。因此,如图3.12所示,HashMap实际上是一个链表为元素的数组。 public V put(K key, V value) {     if (key == null)         return putForNullKey(value);     int hash = hash(key.hashCode());     int i = indexFor(hash, table.length);     for (Entry<K,V> e = table[i]; e != null; e = e.next) {         Object k;         //如果当前的key已经存在于HashMap         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {             V oldValue = e.value;            //取得旧值             e.value = value;             e.recordAccess(this);             return oldValue;                //返回旧值         }     }     modCount++;     addEntry(hash, key, value, i);                //添加当前的表项到i位置     return null; } addEntry()方法的实现如下: void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; //将新增元素放到i的位置,并让它的next指向旧的元素 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold)         resize(2 * table.length); } 基于HashMap的这种实现机制,只要hashCode()和hash()方法实现的足够好,能够尽可能的减少冲突的产生,那么对HashMap的操作几乎等价于对数组的随机访问操作,具有很好的性能。但是,如果hashCode()或者hash()方法实现较差,在大量冲突产生的情况下,HashMap事实上就退化为几个链表,对HashMap的操作等价于遍历链表,此时性能很差。 考虑一个在极端情况下的例子,假设类BadHash有着一个很槽糕的hashCode()实现:     public class BadHash{         double d;         public BadHash(double d){             this.d=d;         }         @Override         public int hashCode(){             return 1;                        //一个槽糕的hashCode()实现         }     } 类GoodHash拥有默认hashCode()方法:     public class GoodHash{         double d;         public GoodHash(double d){             this.d=d;         }     } 分别使用BadHash类和GoodHash类作为HashMap的key,产生1万一个对象并将其存入HashMap中,执行get()方法1万次。结果BadHash类相对耗时1297ms,而GoodHash类仅耗时15ms。这正是随机数据访问和链表遍历的性能差距。

再补充一下HashMap的get(key)方法的实现原理解析:
public V get(Object key) { if (key == null) // 键为null的Entry是tables[0] return getForNullKey(); // 首先根据key获取hash值,跟put方法一致 int hash = hash(key.hashCode()); // 同样通过位与运算获取Entry[] tables下标 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.equals(k))) // 当匹配到hash值相同,key相同的Entry元素时,返回Entry对象的vlaue return e.value; } return null; }