如何在通用散列表实现中对通用键进行散列？ [英] How to hash generic key in generic hash table implementation?
问题描述
我正在使用泛型来实现哈希表，比如用c＃实现的Dictionary，但是我被卡在了哈希函数部分。我成功地重写了泛型中的哈希表的非泛型实现，但您会注意到在代码中我不知道如何哈希Tkey。
class Node< T，U>
{
public T key;
公共U值;
公共节点< T，U>下一个;
public Node（T key，U value，Node< T，U> next）
{
this.key = key;
this.value = value;
this.next = next;
}
}
公共类HashTable< T，U>
{
int length;
节点< T，U> []桶;
public HashTable（int length）
{
this.length = length;
buckets = new Node< T，U> [length];
$ b $ public void Display（）
{
for（int bucket = 0; bucket< buckets.Length; bucket ++）
{
节点< T，U>当前=桶[桶];
Console.Write（bucket +：）;
while（current！= null）
{
Console.Write（[+ current.key +，+ current.value +]）;
current = current.next;
}
Console.WriteLine（）;
// private int Hash（T Tkey）...
////非通用版本的散列函数
private int Hash（string str）
{
int h = 0;
foreach（var str in）
h = 127 * h + s;
返回h％长度;
$ b ////
public void Insert（T key，U value）
{
int bucket = Hash（key）;
bucket [bucket] = new Node< T，U>（key，value，bucket [bucket]）;
}
public U Search（T key）
{
Node< T，U> current = bucket [Hash（key）];
while（current！= null）
{
if（current.key.Equals（key））
return current.value;
current = current.next;
}
抛出新的异常（键+未找到）;
}
附带 GetHashCode（） 方法，应该用于这些情况。
一些类带有一个很好的实现，其他类只是继承 System.Object 并且不要覆盖它。
从MSDN文档：
GetHashCode 方法的默认实现不保证不同对象的唯一返回值。此外，.NET Framework不保证 GetHashCode 方法的默认实现，并且它返回的值在不同版本的.NET Framework之间将保持不变。因此，此方法的默认实现不能用作散列目的的唯一对象标识符。 >方法可以被派生类型覆盖。值类型必须重写此方法以提供适合该类型的散列函数，并在散列表中提供有用的分布。为了唯一性，哈希码必须基于实例字段或属性的值而不是静态字段或属性。
I'm implementing hash table using generics, like Dictionary implemented in c#, but I'm stuck in Hash function part. I successufuly rewritten non-generic implementation of Hash table in generic one but you will notice in code that I have no idea how to hash Tkey.
class Node<T, U>
{
public T key;
public U value;
public Node<T, U> next;
public Node(T key, U value, Node<T, U> next)
{
this.key = key;
this.value = value;
this.next = next;
}
}
public class HashTable<T,U>
{
int length;
Node<T,U>[] buckets;
public HashTable(int length)
{
this.length = length;
buckets = new Node<T,U>[length];
}
public void Display()
{
for (int bucket = 0; bucket<buckets.Length; bucket++)
{
Node<T,U> current = buckets[bucket];
Console.Write(bucket + ":");
while (current != null)
{
Console.Write("["+current.key+","+current.value+"]");
current=current.next;
}
Console.WriteLine();
}
}
// private int Hash(T Tkey) ...
//// non-generic version of hash function
private int Hash(string str)
{
int h=0;
foreach(var s in str)
h=127*h+s;
return h%length;
}
////
public void Insert(T key, U value)
{
int bucket = Hash(key);
buckets[bucket] = new Node<T,U>(key, value, buckets[bucket]);
}
public U Search(T key)
{
Node<T,U> current = buckets[Hash(key)];
while (current != null)
{
if (current.key.Equals(key))
return current.value;
current= current.next;
}
throw new Exception(key+ "Not found");
}
The base object class in C# comes with the GetHashCode() method which should be used for these situations.
Some classes come with a good implementation, others just inherit the method from System.Object and do not override it.
From the MSDN documentation:
The default implementation of the GetHashCode method does not guarantee unique return values for different objects. Furthermore, the .NET Framework does not guarantee the default implementation of the GetHashCode method, and the value it returns will be the same between different versions of the .NET Framework. Consequently, the default implementation of this method must not be used as a unique object identifier for hashing purposes.
The GetHashCode method can be overridden by a derived type. Value types must override this method to provide a hash function that is appropriate for that type and to provide a useful distribution in a hash table. For uniqueness, the hash code must be based on the value of an instance field or property instead of a static field or property.
这篇关于如何在通用散列表实现中对通用键进行散列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
