索引对象的哈希函数

Question

说，我有一个 class 索引所有从它创建的对象，从 0，...，n-1（使用创建对象的静态计数器）。由于这些对象在 HashSets 和 Dictionaries 中使用，我们需要一个 Hash 函数。

有什么理由不使用这个索引作为Hash值吗？

Answer 1

不使用索引作为哈希函数的一个原因是您想要跨不同实例进行复制。

假设您在实体系统中使用 Dictionaty，并且您的键是任何给定组件的实体和组件类型的组合。查找组件时，您希望能够从实体、组件类型创建一个新键，并使其等同于具有相同实体和组件类型的键。通过这种方式，静态递增索引不是可行的方法，因为它会导致表示相同值的对象具有不同的哈希码，从而导致它无法用作字典中的键。

另一个原因是，在生命周期延长的程序中，您可能有任意数量的对象超过运行类型 - 比方说数据库驱动程序上的事务管理器。在这种情况下，您实际上可能运行是整数值（如果允许负数或使用 uint，则约为 42 亿个值）。在这种情况下，哈希码不足以保证唯一性——这是哈希码的正常行为，但很可能是过度优化的陷阱。

Answer 2

您当然可以使用它，但如果您这样做，则意味着每个单独的对象实例都被那些基于散列的结构视为不同的对象。如果您希望能够考虑不同的对象实例 "equal" 那么此方法将不起作用。

如果这实际上是您的目标，则根本没有理由覆盖默认的 equality/hash-code 语义。默认实现将比较对象引用，导致每个对象与其他所有对象 "different" 。所以省点力气，别费心去做任何事情。

Answer 3

这是 HashSet

上包含的 actual code

private int[] m_buckets;
private Slot[] m_slots;

public bool Contains(T item) {
    if (m_buckets != null) {
        int hashCode = InternalGetHashCode(item);
        // see note at "HashSet" level describing why "- 1" appears in for loop
        for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
            if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item)) {
                return true;
            }
        }
    }
    // either m_buckets is null or wasn't found
    return false;
}

private int InternalGetHashCode(T item) {
    if (item == null) {
        return 0;
    } 
    return m_comparer.GetHashCode(item) & Lower31BitMask;
}

internal struct Slot {
    internal int hashCode;      // Lower 31 bits of hash code, -1 if unused
    internal T value;
    internal int next;          // Index of next entry, -1 if last
}

你要注意的关键是它调用 GetHashCode() 然后它对结果做 hashCode % m_buckets.Length 以确定它应该遍历存储在 m_slots 中的哪个单链表根。

最好的算法会在 hashCode % m_buckets.Length 中均匀分布值，因此所有链表的长度都相同。从 0 开始并向上计数可以完美地做到这一点，所以是的，如果您可以获得一个唯一的对象的固定索引并且只是向上计数，那就是一个完美的哈希码。

索引对象的哈希函数

Hash function for indexed objects

c#

hashset

gethashcode