Java中的HashMap实现。桶索引计算是如何工作的？

关键词：

【中文标题】Java中的HashMap实现。桶索引计算是如何工作的？【英文标题】：HashMap implementation in Java. How does the bucket index calculation work? 【发布时间】：2012-06-08 09:47:28 【问题描述】：

我正在查看 Java 中 HashMap 的实现，但我一直卡在某个地方。indexFor函数是怎么计算出来的？

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

谢谢

【问题讨论】：

【参考方案1】：

哈希本身由您尝试存储的对象的hashCode() 方法计算。

您在此处看到的是根据散列 h 计算存储对象的“桶”。理想情况下，为了避免碰撞，您将拥有与h 的最大可实现值相同数量的存储桶 - 但这可能对内存要求太高。因此，您通常拥有较少数量的具有碰撞危险的存储桶。

如果h 是 1000，但您的底层数组中只有 512 个桶，您需要知道将对象放在哪里。通常，对h 执行mod 操作就足够了，但这太慢了。鉴于HashMap 的内部属性，即底层数组总是 具有等于2^n 的桶数，Sun 的工程师可以使用h & (length-1) 的想法，它使用bitwise AND由所有1 组成的数字，实际上只读取哈希的n 最低位（这与h mod 2^n 相同，只是快得多）。

例子：

     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 488 in decimal which is a result of 1000 mod 512)

【讨论】：

现在有意义吗，还是我应该详细说明内部原理？ 非常解释得很好。我印象深刻。 这是否意味着如果最低 9 位左右一致，但较高位不同，哈希桶可能包含具有不同 hashCodes 的键？ @pbabcdefp 是的，没错。这就是为什么 good hash function 将其结果乘以素数的主要原因之一 - 即使值略有不同，它也会尝试实现非常不同的哈希值。 @Slanec 谢谢。这是我在 SO 上看到的最清晰的答案之一。 （+1）。【参考方案2】：

不是在计算hash，而是在计算bucket。

表达式h & (length-1) 使用length-1 对h 进行逐位AND，这就像一个位掩码，只返回h 的低位，从而使h % length 的超快速变体。

【讨论】：

你能在这里解释一下这个计算吗？ 这是否假定 length 是 2 的幂？ @LarsH 好吧，如果它是 2 的幂会好得多，然后你就可以清楚地切掉高阶位。碰巧的是，HashMap 的实现从大小 16 开始，并且在调整大小时确实乘以 2。如果不是 2 的幂，它仍然可以工作，但是您希望 length -1 尽可能多地“打开”位，以平衡桶之间的分布 那么是不是说在HashMap中总是有16个桶（初始容量）？因为如果是h % length，那么就不能再创建bucket了。 @unclebob 根据我之前的评论，该算法依赖于 length 是 2 的幂（HashMap 总是如此）。 7 不是 2 的幂。【参考方案3】：

上面的回答很好但是我想多解释一下为什么Java可以使用indexFor来创建索引

例如，我有一个这样的HashMap（这个测试是在Java7上的，我看到Java8改变了HashMap很多但是我觉得这个逻辑还是很好的）

// Default length of "budget" (table.length) after create is 16 (HashMap#DEFAULT_INITIAL_CAPACITY)
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("A",1); // hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5
hashMap.put("B",2); // hash("B")=70, indexFor(hash,table.length)=70&(16-1) = 6
hashMap.put("P",3); // hash("P")=85, indexFor(hash,table.length)=85&(16-1) = 5
hashMap.put("A",4); // hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5
hashMap.put("r", 4);// hash("r")=117, indexFor(hash,table.length)=117&(16-1) = 5

您可以看到键为"A" 的条目索引和键为"P" 的对象和键为"r" 的对象具有相同的索引（= 5）。这是我执行上面的代码后的调试结果

图片中的表格在这里

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable 
    transient HashMap.Entry<K, V>[] table;
    ...

=> 我明白了 如果索引不同，新条目将添加到表中 如果索引相同且hash相同，新值将更新 如果索引相同且hash不同，则新条目将指向旧条目（如LinkedList）。那你知道为什么Map.Entry有字段next

static class Entry<K, V> implements java.util.Map.Entry<K, V> 
        ...
        HashMap.Entry<K, V> next;

您可以通过阅读HashMap中的代码再次验证它。

现在，您可以认为 HashMap 将永远不需要更改大小 (16)，因为 indexFor() 总是返回值 不会正确。 如果你看HashMap代码

 if (this.size >= this.threshold ...) 
      this.resize(2 * this.table.length);

HashMap 将在size >= threadhold 时调整表格大小（双倍表格长度）

threadhold 是什么？ threadhold 计算如下

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75F;
...
this.threshold = (int)Math.min((float)capacity * this.loadFactor, 1.07374182E9F); // if capacity(table.length) = 16 => threadhold = 12

size 是什么？ size 计算如下。 当然，这里的size不是table.length。 每当您将新条目放入HashMap 和HashMap 时都需要创建新条目（注意HashMap 在密钥相同时不会创建新条目，它只会覆盖现有条目的新值）然后size++

void createEntry(int hash, K key, V value, int bucketIndex) 
    ...
    ++this.size;

希望对你有帮助

【讨论】：

【参考方案4】：

它正在计算将存储条目（键值对）的哈希映射的桶。存储桶 id 为hashvalue/buckets length。

哈希映射由桶组成；对象将根据桶 id 放置在这些桶中。

根据它们的hash code / buckets length 值，任何数量的对象实际上都可以落入同一个桶中。这称为“碰撞”。

如果多个对象落入同一个桶中，在搜索时会调用它们的equals()方法进行消歧。

碰撞次数与存储桶的长度成反比。

【讨论】：

【参考方案5】：

bucket_index = (i.hashCode() && 0x7FFFFFFFF) % hashmap_size 可以解决问题

【讨论】：

jdk1.8hashmap(代码片段)

背景HashMap是集合框架中最重要的类之一：LinkedHashMap直接继承HashMapConcurrentHashMap的实现就是HashMap+分段锁HashSet底层是HashMapTreeMap的红黑树在HashMap也有实现JDK1.8java.util.HashMap#table注释说"lengthisalwaysapoweroftwo"，为什么？哈希冲... 查看详情

hashmap源码学习

HashMap实现了Map接口，继承自AbstractMap，并且是LinkedHashMap的父类。JDK8中的HashMap在jdk8中，HashMap的底层的存储结构是一个Node对象的数组,也叫哈希桶,每个桶放的是链表，链表中的元素，就是HashMap中的元素。涉及到扩容，关于扩容的... 查看详情

如何打印存储在 Tree 中的所有单词，其中已使用 Java 中的 Hashmap 实现 trie？

】如何打印存储在Tree中的所有单词，其中已使用Java中的Hashmap实现trie？【英文标题】：HowtoprintallwordsstoredinaTree,wherintriehasbeenimplementedusingHashmapinJava?【发布时间】：2013-04-0702:53:03【问题描述】：我想打印或检索存储在Trie数据结构... 查看详情

hashmapjdk1.8实现原理(代码片段)

HashMap概述HashMap存储的是key-value的键值对，允许key为null，也允许value为null。HashMap内部为数组+链表的结构，会根据key的hashCode值来确定数组的索引(确认放在哪个桶里)，如果遇到索引相同的key，桶的大小是2，如果一个key的hashCode是... 查看详情

hashmap为啥不安全？

有两个原因存放数据时,HashMap不是线程安全的比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被... 查看详情

面试阿里：面试官问我hashmap，我是这样回答的！(代码片段)

HashMap简介HashMap采用Key/Value存储结构，每个Key对应唯一的一个Value。HashMap实现了Cloneable，可以被克隆。HashMap实现了Serializable，可以被序列化。HashMap继承了AbstractMap，实现了Map接口，具有Map的所有功能。HashMap内部属性：DEFAULT_INITIA... 查看详情

手写一个简单的hashmap(代码片段)

HashMap简介HashMap是Java中一中非常常用的数据结构，也基本是面试中的“必考题”。它实现了基于“K-V”形式的键值对的高效存取。JDK1.7之前，HashMap是基于数组+链表实现的，1.8以后，HashMap的底层实现中加入了红黑树用于提升查找... 查看详情

java中的hashmap类是做啥用的?

解决什么问题的时候需要用到HashMap类,这个类的功能是实现什么?java中HashMap类是用来存储具有键值对特征的数据。例如现在需要按照员工号来存储大量的员工信息，那么就可以使用HashMap，将员工号作为键，员工对象作为值来存储... 查看详情

java1.8hashmap源码解析桶数组+单链表+红黑树

1//非线程安全2//继承了AbstractMap3//实现了Map、Cloneable、Serializable接口4//后面2个接口是标记接口，没有抽象方法。5//表示HashMap可以浅复制、序列化和反序列化。6publicclassHashMap<K,V>extendsAbstractMap<K,V>7implementsMap<K,V>,Cloneab 查看详情

java中的hashmap类是做啥用的?

java中HashMap类是用来存储具有键值对特征的数据。例如现在需要按照员工号来存储大量的员工信息，那么就可以使用HashMap，将员工号作为键，员工对象作为值来存储到HashMap中，其中使用HashMap时需要注意，HashMap是线程不同步的，... 查看详情

hashmap实现原理探究

...Java8之后新增挺多新东西，在网上找了些相关资料，关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看。图和有些内容参考的这个文章：http://www.importnew.com/16599.htmlHashMap的存储结构如图：一个桶（bucket）上的... 查看详情

java面试整理之——java基础

1.    HashMap的源码，实现原理，JDK8中对HashMap做了怎样的优化。在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。HashMap由链表+数组组成，他的底层结构是一... 查看详情

hashmap 或 hashtable 中的重新散列过程

】hashmap或hashtable中的重新散列过程【英文标题】：Rehashingprocessinhashmaporhashtable【发布时间】：2012-05-2604:22:07【问题描述】：当大小超过maxthreshold值时，如何在hashmap或hashtable中完成重新散列过程？是否所有对都只是复制到一个新... 查看详情

hashmap底层实现原理(代码片段)

HashMap底层是如何实现的？在JDK1.8中它都做了哪些优化？在JDK1.7中HashMap是以数组加链表的形式组成的，JDK1.8之后新增了红黑树的组成结构，当链表大于8并且容量大于64时，链表结构会转换成红黑树结构，它的组成结构如下图所示... 查看详情

java——hashmap源码解析

以下针对JDK1.8版本中的HashMap进行分析。概述????哈希表基于Map接口的实现。此实现提供了所有可选的映射操作，并且允许键为null，值也为null。HashMap除了不支持同步操作以及支持null的键值外，其功能大致等同于Hashtable。这个类不... 查看详情

java中的hashmap

一、HashMap简介?HashMap是一个散列表，它存储的内容是键值对(key-value)映射。HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外... 查看详情

如何删除/计算 s3 存储桶中的对象？

】如何删除/计算s3存储桶中的对象？【英文标题】：HowdoIdelete/countobjectsinas3bucket?【发布时间】：2010-10-1615:18:07【问题描述】：所以我知道这是一个常见问题，但似乎没有任何好的答案。我有一个带有gobs（我不知道有多少）文件... 查看详情

如何实现java中hashmap的value值是对象的时候的排序

各位大虾,我的想法是可不可以将hashmap中的value值导出到List集合中,然后再利用Collections.sort()实现排序功能那要如何将value值导出到List集合中啊导出到list集合还不简单：HashMap<Key,Value>hashMap=newHashMap<Key,Value>();Collection<Valu... 查看详情