1

我有一个哈希表基类，我通过派生它来创建不同类型的哈希表。我只允许它接受实现我的 IHashable 接口的对象。例如 -

class LinearProbingHashTable<T> : HashTableBase<T> where T: IHashable
{
...
...
...
}

interface IHashable
{
    /**
     * Every IHashable implementation should provide an indentfying value for use in generating a hash key.
     */
    int getIdentifier();
}

class Car : IHashable
{
    public String Make { get; set; }
    public String Model { get; set; }
    public String Color { get; set; }
    public int Year { get; set; }

    public int getIdentifier()
    {
        /// ???
    }
}

任何人都可以建议一种为汽车生成标识符的好方法，哈希函数可以使用该标识符将其放入哈希表中吗？

我实际上正在寻找一种通用解决方案来为任何给定的类生成一个 id。我想为所有类 HashableObject 提供一个基类，它实现了 IHashable 及其 getIdentifier 方法。所以我可以从 HashableObject 派生，它会自动为任何实例提供标识符。这意味着我不必为添加到哈希表的每个对象编写不同的 getIdentifier 方法。

public class HashableObject : IHashable
{
  public int getIdentifier()
  {
    // Looking for code here that would generate an id for any object...
  }
}

public class Dog : HashableObject
{
  // Dont need to implement getIdentifier because the parent class does it for me
}
4

2 回答 2

1

您应该使用默认GetHashCode方法。它可以满足您的一切需求。文档。它存在于所有对象并且是虚拟的，因此您可以根据需要选择覆盖它。

我假设您知道如何为原始数据类型（整数、浮点数、字符串、非扩展对象和其他一些）生成散列并组合多个散列，所以我不会对细节感到厌烦。

如果您绝对必须编写自己的通用哈希函数，则可以使用Reflection。您将递归地散列每个数据成员，直到您到达必须手动处理这些情况的原始类型。某些具有非托管数据的数据类型可能会出现问题。特别是，一个示例是 .net 类，它具有指向具有未指定数据结构的类的指针。反射显然不能处理这种情况，也不能散列类的非托管部分。

于 2012-10-03T18:43:15.157 回答
1

我会将问题一分为二：

  1. 如何生成原始类型的哈希码：字符串、整数等。
  2. 如何将多个哈希码组合成一个哈希码

使用 (1) 然后 (2) 您可以生成任何类或结构的哈希码。

对字符串做（1）的天真方法是在字符串中添加所有字符的代码：

public static int getStringIdentifier(string str)
{
   int result = 0;
   foreach (char c in str) {
     result += (int)c;
   }
   return result;
}

类似的朴素算法可用于其他基本数据类型（最终都是字节数组......）。

做（2）的天真方法是将各种哈希码与XOR简单地结合起来：

public int getIdentifier() 
{ 
  return getStringIdentifier(Make) ^ getStringIdentifier(Model) ^ getStringIdentifier(Color);     
}

这些算法会起作用，但不会产生散列码值的良好分布——即会有冲突。

如果你想要更好的算法，你可以看看 .NET 框架是如何做到的——这里是内部用于组合多个哈希码的类的源代码，这里是String该类的源代码——包括String.GetHashCode().

正如你所看到的，它们是上面简单的变体，具有不同的起始值和更复杂的组合。

如果您想要一个适用于不同类的单一方法，方法是使用反射来检测类中包含的所有原始字段，使用原始函数计算它们的哈希码，然后将它们组合起来。不过，这很棘手，而且是特定于 .NET 的——我的偏好是创建处理原始类型的方法，然后为每个类重新定义getIdentifier()。

于 2012-10-03T19:38:02.680 回答