索引对象的哈希函数

本文关键字：函数 哈希 对象 索引 | 更新日期: 2023-09-27 18:37:02

比如说，我有一个类，它索引从 0、...、n-1 创建的所有对象（使用创建对象的静态计数器）。由于这些对象用于哈希集和字典，我们需要一个哈希函数。

有什么理由不将此索引用作哈希值吗？

索引对象的哈希函数

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

如果这实际上是你的目标，那么根本没有理由覆盖默认的相等/哈希代码语义。 默认实现将比较对象引用，导致每个对象与其他每个对象"不同"。 因此，省去自己的精力，不要费心做任何事情。

这是包含哈希集的实际代码

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 开始并计数可以完美地做到这一点，所以是的，如果你能为一个唯一的对象获得一个固定的索引，并且只是计数，这是一个完美的哈希码。

不使用索引作为哈希函数的一个原因是，您希望跨不同的实例重复。

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

另一个原因是，在具有延长生存期的程序中运行的类型上，您可能拥有任意数量的对象 - 假设数据库驱动程序上的事务管理器。在这种情况下，您实际上可能会用完整数值（如果允许负数或使用uint，则为 ~42 亿个值）。在这种情况下，哈希代码不足以确保唯一性 - 这是哈希代码的正常行为，但对于过度热心的优化来说，这是一个非常可能的陷阱。

相关文章：