HashMap快速实现存取的原理(3)

这个方法中有两点需要注意:
      一、链的产生。
系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象,那么新添加的Entry对象将指向原有的Entry对象,形成一条Entry链,但是若bucketIndex处没有Entry对象,也就是e==null,那么新添加的Entry对象指向null,也就不会产生Entry链了。
      二、扩容问题。
      随着HashMap中元素的数量越来越多,发生碰撞的概率就越来越大,所产生的链表长度就会越来越长,这样势必会影响HashMap的速度,为了保证HashMap的效率,系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程,因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

二、读取实现:get(key)

相对于HashMap的存而言,取就显得比较简单了。通过key的hash值找到在table数组中的索引处的Entry,然后返回该key对应的value即可。

// 获取key对应的value  
public V get(Object key) {
// 若为null,调用getForNullKey方法返回相对应的value
    if (key == null)  
    // 根据该 key 的 hashCode 值计算它的 hash 码
        return getForNullKey();  
    // 获取key的hash值  
    int hash = hash(key.hashCode());  
    // 取出 table 数组中指定索引处的值,在“该hash值对应的链表”上查找“键值等于key”的元素  
    for (Entry<K,V> e = table[indexFor(hash, table.length)];  
         e != null;  
         e = e.next) {  
        Object k;  
        //判断key是否相同,若key与查找的key相同,则返回相对应的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
            return e.value;  
    }
    //没找到则返回null
    return null;  
}
 

在这里能够根据key快速的取到value除了和HashMap的数据结构密不可分外,还和Entry有莫大的关系,在前面就提到过,HashMap在存储过程中并没有将key,value分开来存储,而是当做一个整体key-value来处理的,这个整体就是Entry对象。同时value也只相当于key的附属而已。在存储的过程中,系统根据key的hashcode来决定Entry在table数组中的存储位置,在取的过程中同样根据key的hashcode取出相对应的Entry对象。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/884bacaae670bded5a95a3efe6f5752e.html