散列算法是怎么实现的 - 不同冲突解决方式比较(二)
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);
}
}
class MyHash_MAD_独立链
{
class HashNode
{
public string Key { get; set; }
public object Value { get; set; }
}
private const int defaultSize = 10001;
//private List> lstArray = new List>(defaultSize);
private LinkedList[] lstArray = new LinkedList[defaultSize];
public MyHash_MAD_独立链()
{
int i = defaultSize;
while (i > 0)
{
lstArray[i - 1] = new LinkedList();
i--;
}
}
public object this[string key]
{
get
{
EnsureNotNull(key);
LinkedList lst;
if (obj == null)
throw new Exception("Key不存在");
return obj.Value;
}
set
{
EnsureNotNull(key);
LinkedList lst;
HashNode obj = FindByKey(key, out lst);
if (obj != null)
lst.Remove(obj);
lst.AddLast(new HashNode() { Key=key, Value=value});
}
}
private HashNode FindByKey(string key, out LinkedList lst)
{
int hashIndex = MapString2Int(key);
lst = lstArray[hashIndex];
HashNode obj = lst.FirstOrDefault(t => t.Key == key);
if (obj != null && !string.IsNullOrEmpty(obj.Key))
return obj;
return null;
}
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) % defaultSize;
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 / defa