HashMap 的存储方式

    选择打赏方式

在 HashMap 中存放的一系列键值对,其中键为某个我们自定义的类型。放入 HashMap 后,我们在外部把某一个 key 的属性进行更改,然后我们再用这个 key 从 HashMap 里取出元素,这时候 HashMap 会返回什么?

这是一个很有趣的事情,如果不知道HashMap的存储方式,那很难做出正确的回答!


要解答这个问题,首先需要了解HashMap是如何put元素的。


    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }



addEntry为存放元素的方法,该方法的第一个参数是由int hash = hash(key); 得到的。

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }


addEntry方法中使用了createEntry方法存放,注意bucketIndex 是由indexFor方法计算出来的,影响它的因素是hash值和table.length

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
在createEntry方法中可以看到,存入的位置只和bucketIndex有关,而bucketIndex值是put的时候由key的hash值通过indexFor方法计算出来的。



接着我们看一下HashMap是如何获取一个值的



    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
主要还是getEntry方法



    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;
    }


现在清楚了,获取值是使用key的hash值来定位在table的位置的。如果key在put之后改变过属性,而这些属性又影响了hashCode的计算结果,那就会导致获取不到value。那为什么不会获取到错误的value呢?因为在获取到value之后还会对保存的e.hash和key的hash进行对比,比对结果显然不会一样,所以最终导致获取到null。


此外在JDK1.7中,发现resize方法中有可能会重新计算key的hash值,这将会给答案增添变数,至于何时会调用rehash分支进行重新hash计算尚未找到答案。



WRITTEN BY

avatar
版权声明:若无特殊注明,本文皆为《 iasuna 》原创,转载请保留文章出处。
本文链接:HashMap 的存储方式 http://www.iasuna.com/post-12.html
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框

吃奶的力气提交吐槽中...


既然没有吐槽,那就赶紧抢沙发吧!