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计算尚未找到答案。
iasuna 》原创,转载请保留文章出处。
本文链接:HashMap 的存储方式 http://www.iasuna.com/post-12.html
版权声明:若无特殊注明,本文皆为《
正文到此结束
发表吐槽
你肿么看?
既然没有吐槽,那就赶紧抢沙发吧!