MyHash_MAD_多槽位
MyHash_MAD_独立链
MyHash_MAD_线性探测法
然后在主程序中分别插入10000条记录，比较各自所需要的时间。
先介绍下：
MAD：
multiply-add-divide method，乘法 - 加法 - 除法（取模），如下这个公式是散列核心公式
(a*collisionIndex+b)%M, M要求是素数，a, b的取值要合理
冲突解决方式：
多槽位
当计算出的Index位置处已经被占用后，还是会在这个index的地方增加一个元素
主数组的每个元素是个列表（比如每个元素都能放5个子元素），因此每个位置都能放多个元素
独立链
基本同上
区别：主数组的每个元素对应的是一个链表
线性探测法
主数组只有一层，也就是每个数组元素只有一个空位，没有子列表
如果计算出的Index位置处已经被占用，就自动往后面查找，直到找到一个没有被占用的位置，把元素放这个空位中
code：
复制代码
class Program
{
static void Main(string[] args)
{
Timing t = new Timing();
Random rnd = new Random(DateTime.Now.Second);
MyHash_MAD_多槽位 hash = new MyHash_MAD_多槽位();
t.Start();
for (var i = 0; i < 10000; i++)
{
string key = string.Format("{0}-{1}", rnd.Next(0, 9999), rnd.Next(0, 9999));
hash[key] = i;
}
t.Stop();
t.Display("MyHash_MAD_多槽位: ");
hash.DisplayEmptyRatio();
Console.WriteLine();
rnd = new Random(DateTime.Now.Second);
MyHash_MAD_独立链 hash2 = new MyHash_MAD_独立链();
t.Start();
for (var i = 0; i < 10000; i++)
{
string key = string.Format("{0}-{1}", rnd.Next(0, 9999), rnd.Next(0, 9999));
hash2[key] = i;
}
t.Stop();
t.Display("MyHash_MAD_独立链: ");
hash2.DisplayEmptyRatio();
Console.WriteLine();
rnd = new Random(DateTime.Now.Second);
MyHash_MAD_线性探测法 hash3 = new MyHash_MAD_线性探测法();
t.Start();
for (var i = 0; i < 10000; i++)
{
string key = string.Format("{0}-{1}", rnd.Next(0, 9999), rnd.Next(0, 9999));
hash3[key] = i;
}
t.Stop();
t.Display("MyHash_MAD_线性探测法: ");
hash3.DisplayEmptyRatio();
Console.WriteLine("done.");
Console.ReadKey();
}
}
class MyHash_MAD_多槽位
{
private const int defaultSize = 10001;
private List>> lstArray = new List>>(defaultSize);
public MyHash_MAD_多槽位()
{
int i = lstArray.Capacity;
while(i>0)
{
lstArray.Add(new List>());
i--;
}
}
public object this[string key]
{
get
{
EnsureNotNull(key);
List> lst;
Tuple obj = FindByKey(key, out lst);
if (obj == null)
throw new Exception("Key不存在");
return obj.Item2;
}
set
{
EnsureNotNull(key);
List> lst;
Tuple obj = FindByKey(key, out lst);
if (obj!=null)
lst.Remove(obj);
lst.Add(new Tuple(key, value));
}
}
private Tuple FindByKey(string key, out List> lst)
{
int hashIndex = MapString2Int(key);
lst = lstArray[hashIndex];
Tuple 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)
{