如何处理相同的散列与相同的密钥？

这个问题不是特定于任何编程语言，我对通用逻辑更感兴趣。如何处理相同的散列与相同的密钥？

通常情况下，关联地图采用一个键并将其映射到一个值。据我所知，实现要求密钥是唯一的，否则值会被覆盖。好的。

因此，让我们假设以上是通过一些散列实现完成的。如果两个不同的键获得相同的散列值？我正在考虑这种形式的底层数组，其索引是由所述键上的散列引起的。可能有多个唯一键映射到相同的值是？如果是这样，那么这样的实现如何处理呢？如何处理相同的散列不同于处理相同的键？由于相同键导致覆盖和相同散列有保留价值。
我知道哈希与碰撞，所以我知道链接和探测。实现迭代遍历当前的值散列到一个特定的索引，并确定密钥是否相同？
虽然我正在寻找我在这些连结传来了回答：
1. What happens when a duplicate key is put into a HashMap?
2. HashMap with multiple values under the same key
他们不但是回答我的问题。我们如何区分相同的哈希与相同的密钥？

来源

2017-07-04 shrewga

通过比较键。如果你看一下哈希映射的面向对象的实现，你会发现，他们通常需要要在关键型实现了两个方法：如果只是哈希函数可以被赋予和没有平等功能

bool equal(Key key1, Key key2); 
int hash(Key key);

，这将哈希映射限制为基于该语言的默认相等性。这并不总是令人满意的，因为有时键需要与不同的相等函数进行比较。例如，如果键是字符串，则应用程序可能需要执行不区分大小写的比较，然后它会传递一个散列函数，该散列函数在散列之前转换为小写，以及一个忽略大小写的等价函数。

哈希映射将密钥与每个对应的值一起存储。（通常，这是指向最初存储的关键对象的指针）。查找哈希映射的任何查找都必须在找到匹配的哈希值后进行关键比较，以验证关键字是否匹配。例如，对于在每个桶中存储列表的非常简单的哈希映射，该列表将是（键，值）对的列表，并且任何查找比较每个列表条目的键直到它找到匹配。伪代码：

Array<List<Pair<Key, Value>>> buckets; 
Value lookup(Key k_sought) { 
    int h = hash(k_sought); 
    List<Pair<Key, Value>> bucket = buckets[h]; 
    for (kv in bucket) { 
     Key k_found = kv.0; 
     Value v_found = kv.1; 
     if (equal(k_sought, k_found)) { 
      return v_found; 
     } 
    } 
    throw Not_found; 
}

来源

2017-07-04 07:05:12 Gilles

您无法从索引中知道密钥是什么，因此您无法遍历这些值以查找有关密钥的任何信息。您将不得不保证0个冲突或存储散列信息以提供索引。

如果您的结构中只存储了值，则无法判断它们是否具有相同的密钥或相同的散列值。您需要存储密钥以及知道的值。

来源

2017-07-04 06:53:33 Chris

如何处理相同的散列与相同的密钥？

回答

相关问题