如果Key的哈希码相同但是equals方法返回false,HashMap如何检索不同的值

我无法理解HashMap的工作模式.请帮助理解它.

假设我们有两个对象Obj1和Obj2具有与1212相同的Hashcode .现在当我们运行"=="并且等于它时返回false.

现在我使用ValueObj1和Valueobj2作为HashMap中的值,分别使用Keys Obj1和Obj2.我相信两个值都将保存在与List相同的桶中.

我的问题是HashMap如何为Obj2选择Valueobj2而为Obj1选择 ValueObj1.假设有n ..这样的对象和值.这个键 - >值关联如何在内部工作,即使哈希码相同但值不同.

假设两个条件等于未被覆盖和覆盖.

A HashMap/ HashSet每桶实现一个键列表(在Map与值一起的情况下).如果多个密钥共享相同的hashCode值,则将它们放在此列表中.

因此,搜索方法首先提取hashCode查询的密钥,然后迭代相应的列表,直到equals方法成功.如果HashSet它意味着key找到了,在a的情况下HashMap,它返回元组的另一侧:值.

因此的记忆HashMap就像:

+--------+--------+--------+--------+
|   00   |   01   |   10   |   11   |
+--------+--------+--------+--------+
    |        |        |        |
 k00/v00     _     k06/v06     _
    |                 |
 k08/v08           k14/v14
    |                 |
 k04/v04              _
    |
    _

你看到的是四个桶的顶部.每个存储桶都有一个列表(下面的项目),用于存储keys(k)和values(v)的元组.由于有这里只有四个桶,所述散列算法使用一个模4的操作,因此一个键k06与值v06将被放置在桶06 mod 4 = 02因而10.的情况下的第二密钥k14中加入14 mod 4 = 02因此10,它被简单地添加到列表中.

由于值也与它一起存储,因此可以执行快速查找操作.因此,密钥与值一起存储.

您注意到,迭代(链接)列表是一项昂贵的操作.但问题的一点HashMap是,人们希望,使用正确术语(共享相同存储桶的密钥数)的哈希冲突数量非常少.通常,人们可能期望每个桶有两个或三个元素.在性能提升因此通过选择在固定时间内正确桶实现,搜索斗要求然而线性时间(或万一有上关键的一完整的订购,人们可能会实现(平衡)二叉树的对数时间搜索) .然而,最糟糕的情况是,a HashMap可以实现,与ArrayList/ LinkedList或条目相同的性能,但给定哈希功能设计得体面,可能性非常低.

你总是可以看看代码.

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

所以它首先得到给定键的哈希值.

使用该哈希它定位表(在其他答案中称为桶).

对于存储桶中的每个条目,它会测试equals表条目键的密钥,如果是,则表示它已找到正确的项目.

通过哈希对桶进行分区可以减少使用equals比较进行线性搜索的大小.因此,您可以看到为哈希码返回固定值有多么有害.见这为良好的哈希码的计算技巧.