散列算法是怎么实现的 - 不同冲突解决方式比较(三)
ultSize * 100, emptyCount, defaultSize, defaultSize - emptyCount);
Console.WriteLine(msg);
}
}
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);
Tuple obj = FindElement(key);
if (obj == null)
throw new Exception("Key不存在");
return obj.Item2;
}
set
{
EnsureNotNull(key);
List> lst;
Tuple obj = FindNextEmptyPlace(key, out lst);
if (obj != null)
lst.Remove(obj);
lst.Add(new Tuple(key, value));
}
}
private Tuple FindElement(string key)
{
int hashIndex = MapString2Int(key);
while (true)
{
hashIndex = hashIndex % lstArray.Capacity;
if (lstArray[hashIndex].Count > 0)
{
List> lst = lstArray[hashIndex];
if (lst[0].Item1 == key)
{
return lst[0];
break;
}
}
hashIndex++;
}
}
private Tuple
FindNextEmptyPlace(string key, out List> lst)
{
int hashIndex = MapString2Int(key);
while (true)
{
hashIndex = hashIndex % lstArray.Capacity;
if (lstArray[hashIndex].Count == 0)
break;
hashIndex++;
}
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)
{
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 = (31 * hashIndex + 2) % lstArray.Capacity;
return hashIndex;
}
public void DisplayFlags()
{
foreach (var item in lstArray)
Console.Write(string.Format("{0}, ", item.Count));
}
public void DisplayEmptyRatio()
{
float emptyCount = 0;
foreach (var item in lstArray)
if (item.Count == 0)
emptyCount++;
string msg = string.Format("空值个数：{1}/{2}\n有值个数：{3}\n空值比例：{0}%", emptyCount / lstArray.Capacity * 100, emptyCount, lstArray.Capacity, lstArray.Capacity - emptyCount);
Console.WriteLine(msg);
}
}
