专栏首页人生得意须尽欢调用 indexFor(int h, int length) 方法来计算 table 数组的哪个索引处
原创

调用 indexFor(int h, int length) 方法来计算 table 数组的哪个索引处

 对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中是这样做的:调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

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

  这个方法非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的 n 次方,这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码:

int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;  

  这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方。当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。   这看上去很简单,其实比较有玄机的,我们举个例子来说明:

  假设数组长度分别为15和16,优化后的hash码分别为8和9,那么&运算后的结果如下:

   h & (table.length-1)                     hash                             table.length-1

   8 & (15-1):                                 1000                   &              1110                   =                1000

   9 & (15-1):                                 1001                   &              1110                   =                1000
  -----------------------------------------------------------------------------------------------------------------------
   8 & (16-1):                                 1000                   &              1111                   =                1000

   9 & (16-1):                                 1001                   &              1111                   =                1001
  -----------------------------------------------------------------------------------------------------------------------

  从上面的例子中可以看出:当8、9两个数和(15−1)2

=(1110)进行“与运算&”的时候,产生了相同的结果,都为1000,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到数组中的同一个位置上形成链表,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hash值会与(15−1)2=(1110)进行“与运算&”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101(注意没有1111,因为数组长度15,最大下标14)这几个位置永远都不能存放元素了,空间浪费相当大。也就是数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!

  而当数组长度为16时,即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1(比如(24−1)2

=1111),这使得在低位上&时,得到的和原hash的低位相同,加之hash(int h)方法对key的hashCode的进一步优化,加入了高位计算,就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。   所以说,当数组长度为2的n次幂的时候,不同的key算得的index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

并且扩容的时候不必全部重新计算hash,只需要判断最高位。

2) 读取:

public V get(Object key) {  
    if (key == null)  
        return getForNullKey();  
    int hash = hash(key.hashCode());  
    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.equals(k)))  
            return e.value;  
    }  
    return null;  
}  

  有了上面存储时的hash算法作为基础,理解起来这段代码就很容易了。从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

  归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,再根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HashMap的实现原理

    Tanyboye
  • HashMap的实现原理

    HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒...

    哲洛不闹
  • java中HashMap详解

    当程序试图将多个 key-value 放入 HashMap 中时,以如下代码片段为例:

    用户5640963
  • 大牛带你深入解读HashMap

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

    慕容千语
  • 【深入理解java集合系列】HashMap实现原理

    HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺...

    爱笑的架构师
  • Java HashMap那点事

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

    Java后端工程师
  • Java中HashMap详解

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

    哲洛不闹
  • 深入浅出学Java-HashMap

    HashMap在JDK1.8之前的实现方式 数组+链表,但是在JDK1.8后对HashMap进行了底层优化,改为了由 数组+链表+红黑树实现,主要的目的是提高查...

    Java架构师必看
  • JDK源码分析之集合04HashMap

    代码改变世界-coding
  • 【小家java】HashMap原理、TreeMap、ConcurrentHashMap的原理、性能、安全方面大解析-----看这一篇就够了

    综上:lambda遍历是首选。当lambda不适用(比如一边遍历一边需要移除等等),entrySet的遍历方式是最优的方式选择。

    YourBatman
  • HashMap实现原理及源码分析

    哈希表(hash table)也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈...

    java乐园
  • HashMap源码阅读

    HashMap是Map家族中使用频度最高的一个,下文主要结合源码来讲解HashMap的工作原理。 1. 数据结构 HashMap的数据结构主要由数组+链表+红黑...

    butterfly100
  • HashMap底层实现详解

      HashMap是基于哈希表的Map接口的非同步实现(Hashtable跟HashMap很像,唯一的区别是Hashtalbe中的方法是线程安全的,也就是同步的...

    IT小马哥
  • 说一下HashMap的实现原理?

    本文会对java集合框架中的对应实现HashMap的实现原理进行讲解,然后会对JDK7的HashMap源码进行分析(JDK8会有所不同,需要了解的可自行阅读JD...

    趣学程序-shaofeer
  • 深入浅出理解HashMap1.8源码设计思想&手写HashMapV1.0

    数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O...

    须臾之余
  • HashMap 与 ConcrrentHashMap 使用以及源码原理分析

    数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为...

    小勇DW3
  • HashSet/HashMap详解

    HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

    似水的流年
  • HashMap实现原理

    HashMap的主干是一个数组,假设我们有3个键值对dnf:1,cf:2,lol:3,每次放的时候会根据hash函数来确定这个键值对应该放在数组的哪个位置,即i...

    Java识堂
  • java中HashMap详解

    通过HashMap、HashSet 的源代码分析其 Hash 存储机制 实际上,HashSet 和 HashMap 之间有很多相似之处,对于 HashSet ...

    哲洛不闹

扫码关注云+社区

领取腾讯云代金券