c#哈希算法的实现方法及思路
有想过hash["a1"] = datetime.now;这句是怎么实现的吗？我们来重温下学校时代就学过的哈希算法吧。
我们要写个class，实现如下主程序调用：
static void main(string[] args)
{
myhash hash = new myhash();
hash["a1"] = datetime.now;
hash["a2"] = 1;
console.writeline(convert.tostring(hash["a1"]));
console.writeline(convert.tostring(hash["a2"]));
}
一看，也确实挺简单的，就是一个所引器，如下：
class myhash
{
public object this[string key]
{
get
{
}
set
{
}
}
}
程序中要保存的对象，最终是要保存在一个数组中的，而且需要通过一个转换函数来进行string key与数组index的map，如下：
private list<list<tuple<string, object>>> lstarray = new list<list<tuple<string, object>>>(defaultsize);
private int mapstring2int(string key)
{
int hashindex=0;
char[] keyary = key.tochararray();
foreach (var c in keyary)
hashindex += (int)c;
hashindex = hashindex % lstarray.capacity;
return hashindex;
}
这个函数是遍历string key的每个char，累加，最终取模（同数组的长度），这样得出的一个value肯定就在数组范围内。
如果2个key转换出来的index相同呢？会导致冲突，一个最简单的解决办法是把数组中的每个元素变成list, 也就是说，如果string key转换后出现了相同的index，没关系，只要把那2个元素都放在那个index所标识的数组位置中即可，本文中用的是list<tuple<string, object>>。
下面是整个程序的代码：
class program
{
static void main(string[] args)
{
myhash hash = new myhash();
hash["a1"] = datetime.now;
hash["a2"] = 1;
console.writeline(convert.tostring(hash["a1"]));
console.writeline(convert.tostring(hash["a2"]));
}
}
class myhash
{
private const int defaultsize = 99999;
private list<list<tuple<string, object>>> lstarray = new list<list<tuple<string, object>>>(defaultsize);
public myhash()
{
int i = lstarray.capacity;
while(i>=0)
{
lstarray.add(new list<tuple<string,object>>());
i--;
}
}
public object this[string key]
{
get
{
ensurenotnull(key);
list<tuple<string, object>> lst;
tuple<string, object> obj = findbykey(key, out lst);
if (obj == null)
throw new exception("key不存在");
return obj.item2;
}
set
{
ensurenotnull(key);
list<tuple<string, object>> lst;
tuple<string, object> obj = findbykey(key, out lst);
if (obj!=null)
lst.remove(obj);
lst.add(new tuple<string, object>(key, value));
}
}
private tuple<string, object> findbykey(string key, out list<tuple<string, object>> lst)
{
int hashindex = mapstring2int(key);
lst = lstarray[hashindex];
tuple<string, object> obj = null;
for (var i = 0; i < lst.count; i++)
{
if (lst[i].item1 == key)
{
obj = lst[i];
break;
}
}
return obj;
}
private static void ensurenotnull(string key)
{
if (key == null || key.trim().length == 0)
throw new exception("key不能为空");
}
private int mapstring2int(string key)
{
int hashindex=0;
char[] keyary = key.tochararray();
foreach (var c in keyary)
hashindex += (int)c;
hashindex = hashindex % lstarray.capacity;
console.writeline(string.format("{0}相应的index为：{1}", key, hashindex));
return hashindex;
}
}
运行效果图：