j03*_*03m 3 c# hashmap data-structures
我在C#中写了一个hashmap作为自学练习.我想将链接实现为碰撞处理技术.起初我以为我只是使用GetHashCode作为我的哈希算法,但我很快发现使用GetHashCode返回的数字并不总是可行的(如果你想索引和数组,那么int的大小会导致内存不足.数字和数字可以是负数:().所以,我提出了一种缩小数字的kludgey方法(参见MyGetHashCode).
有没有人对此实现(哈希函数和一般情况)有任何指针/提示/批评？提前致谢!
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace HashMap
{
class Program
{
public class MyKVP<T, K>
{
public T Key { get; set; }
public K Value { get; set; }
public MyKVP(T key, K value)
{
Key = key;
Value = value;
}
}
public class MyHashMap<T, K> : IEnumerable<MyKVP<T,K>>
where T:IComparable
{
private const int map_size = 5000;
private List<MyKVP<T,K>>[] storage;
public MyHashMap()
{
storage = new List<MyKVP<T,K>>[map_size];
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public IEnumerator<MyKVP<T, K>> GetEnumerator()
{
foreach (List<MyKVP<T, K>> kvpList in storage)
{
if (kvpList != null)
{
foreach (MyKVP<T, K> kvp in kvpList)
{
yield return kvp;
}
}
}
}
private int MyGetHashCode(T key)
{
int i = key.GetHashCode();
if (i<0) i=i*-1;
return i / 10000;
}
public void Add(T key, K data)
{
int value = MyGetHashCode(key);
SizeIfNeeded(value);
//is this spot in the hashmap null?
if (storage[value] == null)
{
//create a new chain
storage[value] = new List<MyKVP<T, K>>();
storage[value].Add(new MyKVP<T, K>(key, data));
}
else
{
//is this spot taken?
MyKVP<T, K> myKvp = Find(value, key);
if (myKvp != null) //key exists, throw
{
throw new Exception("This key exists. no soup for you.");
}
//if we didn't throw, then add us
storage[value].Add(new MyKVP<T, K>(key, data));
}
}
private MyKVP<T, K> Find(int value, T key)
{
foreach (MyKVP<T, K> kvp in storage[value])
{
if (kvp.Key.CompareTo(key) == 0)
{
return kvp;
}
}
return null;
}
private void SizeIfNeeded(int value)
{
if (value >= storage.Length)
{
List<MyKVP<T, K>>[] temp = storage;
storage = new List<MyKVP<T, K>>[value+1];
Array.Copy(temp, storage, temp.Length);
}
}
public K this[T key]
{
get
{
int value = MyGetHashCode(key);
if (value > storage.Length) { throw new IndexOutOfRangeException("Key does not exist."); }
MyKVP<T, K> myKvp = Find(value, key);
if (myKvp == null) throw new Exception("key does not exist");
return myKvp.Value;
}
set
{
Add(key, value);
}
}
public void Remove(T key)
{
int value = MyGetHashCode(key);
if (value > storage.Length) { throw new IndexOutOfRangeException("Key does not exist."); }
if (storage[value] == null) { throw new IndexOutOfRangeException("Key does not exist."); }
//loop through each kvp at this hash location
MyKVP<T, K> myKvp = Find(value, key);
if (myKvp != null)
{
storage[value].Remove(myKvp);
}
}
}
static void Main(string[] args)
{
MyHashMap<string, int> myHashMap = new MyHashMap<string, int>();
myHashMap.Add("joe", 1);
myHashMap.Add("mike", 2);
myHashMap.Add("adam", 3);
myHashMap.Add("dad", 4);
Assert.AreEqual(1, myHashMap["joe"]);
Assert.AreEqual(4, myHashMap["dad"]);
Assert.AreEqual(2, myHashMap["mike"]);
Assert.AreEqual(3, myHashMap["adam"]);
myHashMap.Remove("joe");
try
{
if (myHashMap["joe"] == 3) { }; //should throw
}
catch (Exception)
{
try { myHashMap.Add("mike",1); }
catch (Exception) {
foreach (MyKVP<string, int> kvp in myHashMap)
{
Console.WriteLine(kvp.Key + " " + kvp.Value.ToString());
}
return;
}
}
throw new Exception("fail");
}
}
}
Remove方法永远不应该抛出异常.您正在尝试删除项目.如果已经删除,则不会造成任何伤害..Net中的所有集合类都使用bool作为返回值来指示项目是否真的被删除.
不要抛出异常,抛出特定的异常.浏览Collection命名空间中的所有异常以查找合适的命名空间.
添加TryGetValue
使用KeyValuePair,它已经是.Net的一部分,而不是创建自己的.
添加一个可以定义地图大小的构造函数.
抛出异常包括抛出异常的详细信息.例如,不要写"This key exists",而是写string.Format("Key' {0}"已存在",key)
您的哈希方法是固定范围的.这意味着单个项目可能会导致创建214748个桶(如果它的哈希码重新设置为214747).更常用(并且几乎总是更好的方法)是从初始大小开始,该初始大小要么已知(由于域的知识)对于所有值足够大,要么从小开始并且在适当时使hashmap自身调整大小.通过重新探测,需要调整大小的明显程度是需要多少重新调整.在您尝试使用链接时,您需要保持平均和最大链尺寸.这可以减少更糟糕的查找时间,从而使您的平均查找时间更接近最佳情况O(1).
这种散列的两种最常见的方法(因此也就是初始表大小)要么使用素数,要么使用2的幂.前者被认为(虽然在这一点上存在一些争论)以提供更好的密钥分配,而后者允许更快的计算(两种情况都对输入哈希进行模数,但是已知数量为2的幂) ,模数可以快速完成二进制和操作).在链接时使用2的幂的另一个优点是可以测试链以查看调整哈希值是否实际上会导致该链被拆分(如果你有一个8值表并且有一个链它的哈希值都是17,1或33,那么表格大小加倍仍会使它们处于同一个链中,但是它会重新分配它们四倍.
您没有提供替换语义的方法,这通常适用于.NET字典类型(如果已经有一个带有该键的项目,则添加将会出错,但不会分配给索引).
你试图超过桶数的检索错误对用户没有意义,用户不关心桶是否存在,只关键(他们根本不知道你的实现是如何工作的) .未找到密钥的两种情况都应该抛出相同的错误(System.Collections.Generic.KeyNotFoundException具有恰当的语义,因此您可以重用它.).
List在这种情况下使用a 相当重.一般来说,我不赞成任何人说BCL系列太重了,但是当涉及到滚动你自己的系列时,通常要么是因为(1)你想要从练习中学习,或者(2)BCL系列不适合你的目的.如果(1)你应该学习如何完成你开始的工作,如果(2)你需要确保List没有你找到的任何失败Dictionary.
对于不了解实现细节的人,以及不一致的错误(该桶中是否存在其他东西不是他们应该关心的东西),您的删除都会引发无意义的错误.由于删除不存在的项目是无害的,因此更常见的是仅返回指示项目是否存在的bool,并让用户决定是否表示错误.在物品被移除后继续搜索整个桶也是浪费.
你的实现现在允许null键,这是合理的(实际上,文档IDictionary<TKey, TValue>说明实现可能会也可能不会这样做).但是,你拒绝它们的方式是通过NullReferenceException尝试调用GetHashCode()null返回引起的,而不是检查并抛出一个ArgumentNullException.用户收到NullReferenceException建议集合本身为null.因此这是一个明显的错误.