Java哈希映射如何使用相同的哈希代码处理不同的对象？

Question

根据我的理解，我认为：

1. 两个对象拥有相同的哈希代码是完全合法的
2. 如果两个对象相等（使用equals（）方法），则它们具有相同的哈希代码
3. 如果两个对象不相等，则它们不能具有相同的哈希代码

我说得对吗

如果我是对的，我有以下问题： HashMap在内部使用对象的哈希代码。因此，如果两个对象可以具有相同的哈希代码，那么HashMap如何跟踪它使用的键

有人能解释一下HashMap如何在内部使用对象的hashcode吗

Answer 1

hashcode确定hashmap要检查的bucket。如果bucket中有多个对象，则会进行线性搜索，以查找bucket中的哪个项等于所需项（使用equals()）方法

换句话说，如果您有一个完美的hashcode，那么hashmap访问是恒定的，您将永远不必迭代一个bucket（从技术上讲，您还必须有MAX_INT bucket，Java实现可能在同一个bucket中共享一些hash码，以减少空间需求）。如果你有最差的hashcode（总是返回相同的数字），那么你的hashmap访问就会变成线性的，因为你必须搜索map中的每一项（它们都在同一个bucket中）才能得到你想要的

大多数情况下，一个编写良好的哈希代码并不完美，但它的独特性足以让您或多或少地不断访问

Answer 2

hashmap的工作原理如下（这有点简化，但它说明了基本机制）：

它有许多“bucket”，用来存储键值对。每个bucket都有一个唯一的编号，这就是bucket的标识。当您将密钥-值对放入映射时，hashmap将查看密钥的哈希代码，并将该对存储在标识符为密钥哈希代码的bucket中。例如：密钥的哈希代码为235->；该对存储在存储桶编号235中。（请注意，一个bucket可以存储多个键值对）

当您在hashmap中查找一个值时，通过给它一个键，它将首先查看您所给键的哈希代码。hashmap随后将查看相应的bucket，然后将您提供的密钥与bucket中所有对的密钥进行比较，方法是将它们与equals()进行比较

现在，您可以看到这对于在映射中查找键值对是如何非常有效：通过键的哈希代码，哈希映射立即知道要在哪个bucket中查找，因此它只需根据该bucket中的内容进行测试

查看上述机制，您还可以看到对键的hashCode()和equals()方法有哪些必要的要求：

• 如果两个键相同（equals()在比较它们时返回true），则它们的hashCode()方法必须返回相同的数字。如果键违反了这一点，那么相等的键可能存储在不同的bucket中，hashmap将无法找到键值对（因为它将在同一个bucket中查找）

• 如果两个键不同，那么它们的哈希代码是否相同并不重要。如果它们的哈希代码相同，它们将存储在同一个bucket中，在这种情况下，hashmap将使用equals()来区分它们

Answer 3

你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html找到很好的信息

总结如下：

HashMap根据哈希原理工作

put（key，value）：HashMap将key和value对象存储为Map。进入Hashmap应用hashcode（键）来获取bucket。如果存在冲突，HashMap将使用LinkedList存储对象

get（key）：HashMap使用key对象的hashcode找出bucket位置，然后调用key。方法来标识LinkedList中的正确节点，并在Java HashMap中返回该键的关联值对象

Answer 4

HashMap是Entry对象的数组

将{{CD1}}视为一个对象数组。

看看这个Object是什么：

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

每个Entry对象表示一个键值对。如果一个bucket有多个Entry，则字段next引用另一个Entry对象

有时可能会发生两个不同对象的哈希代码相同的情况。在这种情况下，两个对象将保存在一个bucket中，并显示为链表。 入口点是最近添加的对象。此对象引用另一个具有next字段的对象，依此类推。最后一项是指null

使用默认构造函数创建HashMap时

HashMap hashMap = new HashMap();

创建的阵列大小为16，默认负载平衡为0.75

添加新的键值对

1. 计算密钥的哈希代码
2. 计算元素应放置的位置hash % (arrayLength-1)（桶号）
3. 如果您尝试使用已保存在HashMap中的键添加值，则该值将被覆盖
4. 否则，元素将添加到铲斗中

如果bucket已经至少有一个元素，则会添加一个新元素并将其放置在bucket的第一个位置。它的next字段引用旧元素

删除

1. 计算给定密钥的哈希代码
2. 计算桶数hash % (arrayLength-1)
3. 获取对bucket中第一个Entry对象的引用，并通过equals方法迭代给定bucket中的所有条目。最终我们将找到正确的Entry。 如果未找到所需的元素，则返回null

Answer 5

这里是对HashMap机制的粗略描述，对于Java 8版本，（可能与Java6稍有不同）

---

数据结构

• 哈希表
  哈希值是通过hash()键计算的，它决定对给定的键使用哈希表的哪个bucket
• 链表（单个）
  当bucket中的元素计数很小时，将使用单链接列表
• 红黑树
  当桶中的元素计数较大时，将使用红黑树

---

类（内部）

• Map.Entry
  表示映射中的单个实体，即键/值实体

• HashMap.Node
  节点的链接列表版本

  它可以代表：

  • 散列桶
    因为它有一个散列属性
  • 单链表中的节点，（因此也是linkedlist的头）
• HashMap.TreeNode
  节点的树版本

---

字段（内部）

• Node[] table
  桶表（链表的头）
  若一个bucket不包含元素，那个么它是空的，所以只占用引用的空间
• Set<Map.Entry> entrySet 一组实体
• int size
  实体数目
• float loadFactor
  在调整大小之前，指示允许哈希表的填充程度
• int threshold
  要调整大小的下一个大小
  公式：threshold = capacity * loadFactor

---

方法（内部）

• int hash(key)
  按键计算散列

• 如何将哈希映射到bucket
  使用以下逻辑：

  static int hashToBucket(int tableSize, int hash) {
      return (tableSize - 1) & hash;
  }
  

---

关于容量

在哈希表中，容量意味着桶计数，它可以从table.length获得
也可以通过threshold和loadFactor计算，因此无需定义为类字段

可以通过以下方式获得有效容量：capacity()

---

操作

• 按键查找实体
  首先通过哈希值查找bucket，然后循环链表或搜索排序树
• 添加具有密钥的实体
  首先根据key的散列值找到bucket
  然后尝试查找值：
  • 如果找到，则替换该值
  • 否则，请在链表的开头添加一个新节点，或插入到排序树中
• 调整大小
  当到达threshold时，将使哈希表的容量加倍（table.length），然后对所有元素执行重新哈希以重建表
  这可能是一个昂贵的手术

---

演出

• 获取&；放置
  时间复杂度为O(1)，因为：
  • Bucket是通过数组索引访问的，因此O(1)
  • 每个bucket中的链表长度很小，因此可以看作O(1)
  • 树的大小也受到限制，因为它将扩展容量&；当元素计数增加时重新散列，因此可以将其视为O(1)，而不是O(log N)

Answer 6

你的第三个断言是不正确的

两个不相等的对象具有相同的哈希代码是完全合法的。它被HashMap用作“第一通过滤器”，以便映射可以快速找到具有指定键的可能的条目。然后测试具有相同哈希代码的密钥是否与指定的密钥相等

您不希望要求两个不相等的对象不能具有相同的哈希代码，否则会将您限制为2个可能的对象。（这也意味着不同的类型甚至不能使用对象的字段生成哈希代码，因为其他类可以生成相同的哈希。）