HashMap中indexFor方法解析

男娘i 2022-10-02 10:41 210阅读 0赞

### HashMap中indexFor方法解析 ###

最近在准备面试，所以重新看了下HashMap的源码，在put方法中计算数组下标值index的indexFor()方法：

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

h & (length-1)：其中h为key用hash()算法算出的哈希值，length为数组的长度，且length总是为2的n次幂。  
这个计算我一直不能理解，找了一些资料发现都说 h & (length-1)的结果和 h & length 的结果是相同。  
可是我计算几次发现并不相同。  
最后才发现是怎么回事，先看下面一个例子:  
假设：length为8  
length不减1的情况

int length = 8;
    for (int i = 0; i < 20; i++) { 
    			System.out.println(i +" = "+(i & length));
    		}

输出结果：

0 = 0
    1 = 0
    2 = 0
    3 = 0
    4 = 0
    5 = 0
    6 = 0
    7 = 0
    8 = 8
    9 = 8
    10 = 8
    11 = 8
    12 = 8
    13 = 8
    14 = 8
    15 = 8
    16 = 0
    17 = 0
    18 = 0
    19 = 0

length-1的情况

int length = 8;
    for (int i = 0; i < 20; i++) {
    			System.out.println(i +" = "+(i  & (length-1));
    		}

输出结果：

0 = 0
    1 = 1
    2 = 2
    3 = 3
    4 = 4
    5 = 5
    6 = 6
    7 = 7
    8 = 0
    9 = 1
    10 = 2
    11 = 3
    12 = 4
    13 = 5
    14 = 6
    15 = 7
    16 = 0
    17 = 1
    18 = 2
    19 = 3

发现不同了吗？  
其实可以发现因为length的值总是2的n次幂，只用当length-1时，取到的结果才是我们想要的h%length的结果。  
至于为什么用位运算，想必大家都知道，位运算比取模运算要快。

发表评论取消回复

表情：

评论列表（有 0 条评论，210人围观）

还没有评论，来说两句吧...

相关阅读

相关 HashMap 底层解析

HashMap是线程不安全的 HashMap中存储的内容： key ，value HashMap中存储结构：数组+链表+红黑树（jdk8） HashMap中存储位置：数组

我会带着你远行/ 2023年08月17日 17:22/ 0 赞/ 67 阅读

相关 HashMap_get方法实现解析

1 get() / Returns the value to which the specified key is mapped, or {@code nul

「爱情、让人受尽委屈。」/ 2023年03月14日 10:57/ 0 赞/ 5 阅读

相关 JAVA中的HashMap用法解析

Map=>HashMap SortedMap==>TreeMap 1.如何创建Map集合 2.如何添加Map集合 3.如何遍历Map集合 4.Map集合常用

野性酷女/ 2022年10月08日 05:51/ 0 赞/ 239 阅读

相关 HashMap中indexFor方法解析

HashMap中indexFor方法解析最近在准备面试，所以重新看了下HashMap的源码，在put方法中计算数组下标值index的indexFor()方法：

男娘i/ 2022年10月02日 10:41/ 0 赞/ 211 阅读

相关 HashMap源码解析

一、HashMap概述　　HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步

不念不忘少年蓝@/ 2022年07月12日 14:07/ 0 赞/ 370 阅读

相关 HashMap源码解析

来不及整理电子版，先献丑把笔记本拍几张，随后整理。有人问，什么年代了，还手写笔记，哈哈，如果不亲自手写一遍，我是真心记不住。很多API不用知道工作原理一样可以使用，所以

本是古典何须时尚/ 2022年05月10日 03:50/ 0 赞/ 382 阅读

相关 HashMap源码解析

源码博客相关博客写了那么多，突然想起来都没有写一篇我们日常开发中最常见的HashMap,今天简单补一下！ HashMap简介： `HashMap` 是应用更加广泛的哈希

左手的ㄟ右手/ 2022年04月22日 06:08/ 0 赞/ 410 阅读

相关 HashMap容量解析

HashMap中有一个有参的构造方法，传递的参数是map初始化的容量。那么给定的参数，HashMap就一定给分配参数对应的容量吗？比如，我传7进去，HashMap就会给分配7个

短命女/ 2022年04月16日 01:55/ 0 赞/ 300 阅读

相关 HashMap源码解析

以下针对JDK 1.8版本中的HashMap进行分析。概述哈希表基于`Map`接口的实现。此实现提供了所有可选的映射操作，并且允许键为`null`，值也为`null

太过爱你忘了你带给我的痛/ 2022年04月05日 10:13/ 0 赞/ 487 阅读

相关 hashMap源码解析

源码来自jdk：1.8，和其他jdk版本可能有少许差异。一.hashMap的实现原理 hashMap底层是一个有Node组成的数组，每个Node都有一个key

冷不防/ 2022年03月25日 06:58/ 0 赞/ 452 阅读