如何在泛型哈希表实现中哈希泛型键
本文关键字:泛型 哈希 实现 哈希表 | 更新日期: 2023-09-27 18:25:18
我正在使用泛型实现哈希表,就像c#中实现的Dictionary一样,但我被困在哈希函数部分。我成功地用泛型重写了哈希表的非泛型实现,但您会在代码中注意到,我不知道如何哈希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");
}
C#中的基对象类附带了GetHashCode()
方法,该方法应用于这些情况。
有些类有一个很好的实现,另一些类只是继承了System.Object
的方法,而不重写它
来自MSDN文档:
GetHashCode
方法的默认实现不保证不同对象的返回值是唯一的。此外,.NET Framework不保证GetHashCode
方法的默认实现,并且它返回的值在不同版本的.NET Framework之间是相同的。因此,此方法的默认实现不能用作哈希目的的唯一对象标识符。
GetHashCode
方法可以由派生类型重写。值类型必须重写此方法,以提供适合该类型的哈希函数,并在哈希表中提供有用的分布。为了唯一性,哈希代码必须基于实例字段或属性的值,而不是静态字段或属性。