相同哈希和相同键如何处理？

Question

这个问题并不特定于任何编程语言，我更感兴趣的是一般逻辑。

一般来说，关联映射将一个键映射到一个值。据我所知，实现要求键必须是唯一的，否则值会被覆盖。好的。

那么假设上述过程是通过某种哈希实现完成的。如果两个不同的键获得相同的哈希值怎么办？我想以底层数组的形式考虑，其索引是在所述键的哈希结果中的结果。可能有多个独特的键被映射到同一个值，是吗？如果是这样，这样的实现如何处理呢？ 处理相同哈希与处理相同键有何不同？因为相同键会导致覆盖，而相同哈希必须保留该值。
我了解哈希冲突，所以我知道链接和探测。实现是否迭代当前被哈希到特定索引的值，并确定键是否相同？
在寻找答案时，我遇到了这些链接：
1. 当重复的键放入HashMap中时会发生什么？
2. 在同一个键下具有多个值的HashMap
然而它们没有回答我的问题。我们如何区分相同的哈希和相同的键？

- shrewga

Answer 1

从索引中无法确定键的内容，因此您不能迭代值以查找有关键的任何信息。您需要确保0个冲突或存储哈希为索引的信息。

如果您的结构中仅存储值，则无法确定它们是否具有相同的键或仅具有相同的哈希值。您需要将键与值一起存储以进行区分。

- Chris

Answer 2

通过比较键值。如果您查看哈希映射的面向对象实现，通常需要在键类型上实现两种方法：

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

如果只给定哈希函数而没有等式函数，那么哈希映射将基于语言的默认等式。这并不总是理想的，因为有时需要使用不同的等式函数来比较键。例如，如果键是字符串，则应用程序可能需要进行不区分大小写的比较，然后它会传递一个在散列之前转换为小写字母的哈希函数和一个忽略大小写的等式函数。

哈希映射将键与每个相应的值一起存储。(通常，这是指最初存储的键对象的指针。)任何查找哈希映射的操作都必须在找到匹配的哈希后进行键比较，以验证键是否实际匹配。

例如，对于一个非常简单的哈希映射，它在每个桶中存储一个列表，该列表是(key, value)对的列表，并且任何查找都会比较每个列表条目的键，直到找到匹配项。伪代码如下：

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;
}

- Gilles 'SO- stop being evil'