欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashMap底层实现原理

程序员文章站 2022-06-04 21:42:03
...

大家都知道HashMap是存储key-value形式的集合,允许key和value为null。那么HashMap底层到底是如何实现的呢?今天查了一些资料,简单记录一下。
HashMap底层通过数组和链表实现。数组可以理解,那么链表是用来做什么的呢?这是因为两个不同的对象,hashCode是可能相等的。为了在数组存储hashCode相等的两个不同对象,实际上,一个数组里面的元素,是一个链表。当根据hashCode,得到数组的索引时,先去数组中该处是否已经有值,如果有,再去判断两个对象是否相等,如果相等,则替换旧值,如果不等,则在链表尾部添加元素。
看一下HashMap的put方法:

public V put(K key, V value) {  
    // HashMap允许存放null键和null值。  
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。  
    if (key == null)  
        return putForNullKey(value);  
    // 根据key的keyCode重新计算hash值。  
    int hash = hash(key.hashCode());  
    // 搜索指定hash值在对应table中的索引。  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。  
    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;  
        }  
    }  
    // 如果i索引处的Entry为null,表明此处还没有Entry。  
    modCount++;  
    // 将key、value添加到i索引处。  
    addEntry(hash, key, value, i);  
    return null;  
}  

通过上面方法可以清楚的看出,当遇到hashCode相等的情况时,是如何处理的。
仔细看一下代码,我们发现,数组索引的位置并不是直接通过hashCode得到的,而是先调用了hash()方法,从新计算hash值,然后再通过indexFor()方法计算,才最终得到数组的索引。为什么不直接使用hashCode呢?带着这个疑问,我们依次看看上面两个方法:

static int indexFor(int h, int length) {  
    return h & (length-1);  
} 

先看indexFor方法,它对length-1进行了与操作,当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。而HashMap底层数组的长度总是 2 的 n 次方,这是HashMap在速度上的优化。
按道理讲,这样就可以了得到索引了,为何还要下面的hash方法呢?先看看hash()方法的作用是什么

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以看出,它是对hashCode的高16位和低16位做了一个异或操作。这样就相当于,我们在执行indexFor()方法时,引入了高16位的数据,减少了hash碰撞的可能性。从而get请求查询需要遍历链表的情况表少,查询操作更快。

引用:http://www.importnew.com/18633.html

相关标签: hashmap