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

Question

根据我的理解,我认为:

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

我对么？

现在,如果我是正确的,我有以下问题:HashMap内部使用对象的哈希码.因此,如果两个对象可以具有相同的哈希码,那么它如何HashMap使用它所使用的键？

有人可以解释HashMap内部如何使用对象的哈希码吗？

Answer 1

一个hashmap就像这样(这有点简化,但它说明了基本机制):

它有许多用于存储键值对的"桶".每个桶都有一个唯一的编号 - 这就是识别存储桶的内容.将键值对放入映射时,哈希映射将查看键的哈希码,并将该对存储在桶中,其中标识符是键的哈希码.例如:密钥的哈希码是235 - >该对存储在桶号235中.(注意,一个桶可以存储多于一个键值对).

当您在hashmap中查找值时,通过给它一个键,它将首先查看您给出的键的哈希码.然后,hashmap将查看相应的存储桶,然后通过比较它们,将比较您给出的密钥与存储桶中所有对的密钥equals().

现在,您可以看到这对于在映射中查找键值对非常有效:通过键盘的哈希码,哈希表可以立即知道在哪个桶中查找,因此它只需要测试该桶中的内容.

查看上述机制,您还可以了解密钥hashCode()和equals()方法的必要条件:

• 如果两个键相同(比较它们时equals()返回true),则它们的hashCode()方法必须返回相同的数字.如果密钥违反了这个,那么相同的密钥可能存储在不同的桶中,并且hashmap将无法找到键值对(因为它将在同一个桶中查找).

• 如果两个密钥不同,那么它们的哈希码是否相同并不重要.如果它们的哈希码相同,它们将存储在同一个桶中,在这种情况下,hashmap将用于equals()区分它们.

Answer 2

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

两个不等对象具有相同的哈希码是完全合法的.它被HashMap用作"第一遍过滤器",以便地图可以快速找到具有指定键的可能条目.然后测试具有相同哈希码的密钥与指定密钥的相等性.

您不希望要求两个不相等的对象不能具有相同的哈希代码,否则会限制您使用2 ^32个可能的对象.(这也意味着不同的类型甚至不能使用对象的字段来生成哈希码,因为其他类可以生成相同的哈希值.)

Answer 3

HashMap是一个Entry对象数组.

考虑HashMap只是一个对象数组.

看看这Object是什么:

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

每个Entry对象代表一个键值对.如果存储桶具有多个对象,则该字段next引用另一个Entry对象Entry.

有时可能会发生2个不同对象的哈希码相同.在这种情况下,两个对象将保存在一个存储桶中,并将显示为链接列表.入口点是最近添加的对象.该对象引用具有该next字段的另一个对象等.最后一个条目是指null.

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

HashMap hashMap = new HashMap();

创建的数组大小为16,默认为0.75负载平衡.

添加新的键值对

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

如果存储桶已经至少有一个元素,则会添加一个新元素并将其放置在存储桶的第一个位置.它的next字段指的是旧元素.

删除

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

Answer 4

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

总结一下:

HashMap的工作原理是散列

put(key,value): HashMap将key和value对象存储为Map.Entry.Hashmap应用hashcode(key)来获取存储桶.如果存在冲突,HashMap使用LinkedList来存储对象.

get(key): HashMap使用Key Object的hashcode查找bucket位置,然后调用keys.equals()方法识别LinkedList中的正确节点,并在Java HashMap中返回该键的关联值对象.

Answer 5

以下是版本HashMap机制的粗略描述(可能与Java 6略有不同).Java 8

数据结构

• 哈希表
  哈希值是通过hash()on key 计算的,它决定哈希表的哪个桶用于给定键.
• 链接列表 (单独)
  当存储桶中的元素数量很小时,使用单个链接列表.
• 红黑树
  当桶中元素的数量很大时,使用红黑树.

课程(内部)

• Map.Entry
  表示地图中的单个实体,即键/值实体.

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

  它可以代表:

  • 哈希桶.
    因为它有一个哈希属性.
  • 单链表中的节点(因此也是链表的头部).
• HashMap.TreeNode
  节点的树版本.

字段(内部)

• Node[] table
  桶表,(链表的头部).
  如果存储桶不包含元素,则它为空,因此只占用引用的空间.
• Set<Map.Entry> entrySet 一组实体.
• int size
  实体数量.
• float loadFactor
  在调整大小之前,指示允许哈希表的填充程度.
• int threshold
  下一个调整大小的大小.
  式:threshold = capacity * loadFactor

方法(内部)

• int hash(key)
  按键计算哈希值.

• 如何将哈希映射到存储桶？
  使用以下逻辑:

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

关于能力

在哈希表中,容量表示桶计数,它可以从中获取table.length.
也可以通过threshold和计算loadFactor,因此不需要被定义为类字段.

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

操作

• 按键查找实体.
  首先通过哈希值找到存储桶,然后循环链表或搜索排序树.
• 使用密钥添加实体.
  首先根据键的哈希值找到存储桶.
  然后尝试找到值:
  • 如果找到,请替换该值.
  • 否则,在链接列表的开头添加一个新节点,或插入到已排序的树中.
• 调整大小
  时threshold到达,将增加一倍,哈希表的容量(table.length),然后对所有的元素进行重新散列重建表.
  这可能是一项昂贵的操作.

性能

• get&put
  时间复杂度是O(1)因为:
  • 因此,通过数组索引访问存储桶O(1).
  • 每个桶中的链表长度很小,因此可以查看为O(1).
  • 树的大小也是有限的,因为当元素数量增加时会扩展容量和重新哈希,所以可以查看它O(1),而不是O(log N).

Answer 6

哈希码确定要检查的hashmap的哪个桶.如果存储桶中有多个对象,则进行线性搜索以查找存储桶中的哪个项目等于所需项目(使用equals())方法.

换句话说,如果你有一个完美的哈希码,那么hashmap访问是不变的,你将永远不必遍历一个桶(技术上你也必须有一个MAX_INT桶,Java实现可能在同一个桶中共享一些哈希码)减少空间要求).如果您有最差的哈希码(总是返回相同的数字),那么您的哈希映射访问将变为线性,因为您必须搜索地图中的每个项目(它们都在同一个桶中)才能获得您想要的内容.

大多数情况下,编写良好的哈希码并不完美,但它足够独特,可以为您提供或多或少的持续访问.

Answer 7

你错了第三点.两个条目可以具有相同的哈希码但不相等.看一下OpenJdk中HashMap.get的实现.您可以看到它检查哈希值是否相等且键是否相等.如果点三是真的,那么就没有必要检查密钥是否相等.在密钥之前比较哈希码,因为前者是更有效的比较.

如果您有兴趣进一步了解这一点,请查看Wikipedia关于Open Addressing冲突解决的文章,我认为这是OpenJdk实现使用的机制.这种机制与"桶"方法略有不同,其中一个答案提到了.

Answer 8

import java.util.HashMap;

public class Students  {
    String name;
    int age;

    Students(String name, int age ){
        this.name = name;
        this.age=age;
    }

    @Override
    public int hashCode() {
        System.out.println("__hash__");
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println("__eq__");
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Students other = (Students) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    public static void main(String[] args) {

        Students S1 = new Students("taj",22);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Output:

__ hash __

116232

__ hash __

116201

__ hash __

__ hash __

2

所以在这里我们看到,如果对象S1和S2都有不同的内容,那么我们非常确定我们重写的Hashcode方法将为两个对象生成不同的Hashcode(116232,11601).现在因为有不同的哈希码,所以它甚至不会打扰调用EQUALS方法.因为不同的Hashcode保证对象中的内容不同.

    public static void main(String[] args) {

        Students S1 = new Students("taj",21);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Now lets change out main method a little bit. Output after this change is 

__ hash __

116201

__ hash __

116201

__ hash __

__ hash __

__ eq __

1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally  calls Equal method to verify this. 


Conclusion 
If hashcode is different , equal method will not get called. 
if hashcode is same, equal method will get called.

Thanks , hope it helps. 

Answer 9

两个对象相等，意味着它们具有相同的哈希码，但反之则不然。

2 个相等的对象 ------> 它们具有相同的哈希码

2 个对象具有相同的哈希码 ----xxxxx--> 它们不相等

HashMap 中的 Java 8 更新-

您在代码中执行此操作 -

myHashmap.put("old","old-value");
myHashMap.put("very-old","very-old-value");

所以，假设返回两个按键的哈希码"old"和"very-old"是一样的。然后会发生什么。

myHashMap是一个 HashMap，假设最初你没有指定它的容量。因此，根据 java 的默认容量是 16。所以现在只要您使用 new 关键字初始化 hashmap，它就会创建 16 个存储桶。现在当你执行第一条语句时——

myHashmap.put("old","old-value");

然后"old"计算哈希码，因为哈希码也可能是非常大的整数，所以，java 内部是这样做的 - （这里的哈希是哈希码，>>> 是右移）

hash XOR hash >>> 16

这样一来就给一个更大的图片，它会返回一些指标，这将是你现在的键值对0到15之间，以"old"和"old-value"将被转换为输入对象的key和value实例变量。然后这个条目对象将存储在存储桶中，或者您可以说在特定索引处，将存储此条目对象。

仅供参考- Entry 是 Map 接口 Map.Entry 中的一个类，具有这些签名/定义

class Entry{
          final Key k;
          value v;
          final int hash;
          Entry next;
}

现在当你执行下一条语句时 -

myHashmap.put("very-old","very-old-value");

并"very-old"给出与 相同的哈希码"old"，因此这个新的键值对再次发送到相同的索引或相同的存储桶。但是由于这个bucket不是空的，那么nextEntry对象的变量就是用来存储这个新的键值对的。

并且这将被存储为每个具有相同哈希码的对象的链表，但是 TRIEFY_THRESHOLD 被指定为值 6。因此在此到达后，链表被转换为平衡树（红黑树），第一个元素作为根。