HashMap实现原理与Hash冲突

转载请注明出处,感谢大家的支持!
本文来自优优码:http://www.uucode.net/201503/hashmap-hash-col

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又会如何处理,以保证数据可以完整存放,并正常工作呢?

3.11 Hash冲突示意图

要处理好这个问题,需要进一步深入HashMap,虽然HashMap的底层实现使用的是数组,但是数组内的元素并不是简单的值,而是一个Entry类的对象。因此,对HashMap结构的贴切描述如图3.12所示。

3.12 HashMap表项结构

可以看到,HashMap的内部维护着一个Entry数组,每一个Entry表项包括key、value、next和hash几项。这里特别注意其中的next部分,他指向了另外一个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。这正是随机数据访问和链表遍历的性能差距。

发表评论

您的电子邮件地址将不会被公开. 必填昵称和邮箱 *

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

你必须启用javascript
滚动到顶部
备案号:浙ICP备08112675号-4 浙公网安备 33010502001953号