【转载】Hashcode类,补全并简化代码:

faunus · 发表于 2014-2-23 10:36:45

原理性文章：

http://www.cnblogs.com/abatei/archive/2009/06/23/1509790.html

using System;
public static class Prime
{
public static readonly int[] primes = {
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};
public static int NextPrime(int min)
{
// min>=0
int prime = 0;
for (int i = 0; i < primes.Length; i++) if (primes[i] >= min) break;
return prime;
}
}
public class Hashtable
{
private struct bucket
{
public Object key;
public Object val;
public int hash_coll;
}
private bucket[] buckets;
private int count;
private int loadsize;
private float loadFactor;
public Hashtable() : this(0, 1.0f) { }
public Hashtable(int capacity, float loadFactor)
{
// loadFactor@[0.1f-1.0f]
this.loadFactor = loadFactor > 0.72f ? 0.72f : loadFactor;
double rawsize = capacity / this.loadFactor;
int hashsize = (rawsize > 11) ? Prime.NextPrime((int)rawsize) : 11;
buckets = new bucket[hashsize];
loadsize = (int)(this.loadFactor * hashsize);
}
public virtual void Add(Object key, Object value)
{
Insert(key, value, true);
}
private uint InitHash(Object key, int hashsize,out uint seed, out uint incr)
{
uint hashcode = (uint)GetHash(key) & 0x7FFFFFFF;
seed = (uint)hashcode; //h1
incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)hashsize - 1)));//h2
return hashcode;
}
public virtual Object this[Object key] //索引器
{
get
{
uint seed; //h1
uint incr; //h2
uint hashcode = InitHash(key, buckets.Length,
out seed, out incr);
int ntry = 0; //用于表示h(key,i)中的i值
bucket b;
int bn = (int)(seed % (uint)buckets.Length); //h(key,0)
do
{
b = buckets[bn];
if (b.key == null) //b为无冲突空位时
{ //找不到相应的键，返回空
return null;
}
if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
KeyEquals(b.key, key))
{ //查找成功
return b.val;
}
bn = (int)(((long)bn + incr) %
(uint)buckets.Length); //h(key+i)
} while (b.hash_coll < 0 && ++ntry < buckets.Length);
return null;
}
set
{
Insert(key, value, false);
}
}
private void expand()
{
int rawsize = Prime.NextPrime(buckets.Length * 2);
rehash(rawsize);
}
private void rehash(int newsize)
{
bucket[] newBuckets = new bucket[newsize];
for (int nb = 0; nb < buckets.Length; nb++)
{
bucket oldb = buckets[nb];
if ((oldb.key != null) && (oldb.key != buckets))
putEntry(newBuckets, oldb.key, oldb.val, oldb.hash_coll & 0x7FFFFFFF);
}
buckets = newBuckets;
loadsize = (int)(loadFactor * newsize);
return;
}
//在新数组内添加旧数组的一个元素
private void putEntry(bucket[] newBuckets, Object key,Object nvalue, int hashcode)
{
uint seed = (uint)hashcode; //h1
uint incr = (uint)(1 + (((seed >> 5) + 1) %
((uint)newBuckets.Length - 1))); //h2
int bn = (int)(seed % (uint)newBuckets.Length);//哈希地址
do
{ //当前位置为有冲突空位或无冲突空位时都可添加新元素
if ((newBuckets[bn].key == null)||(newBuckets[bn].key == buckets))
{ //赋值
newBuckets[bn].val = nvalue;
newBuckets[bn].key = key;
newBuckets[bn].hash_coll |= hashcode;
return;
}
//当前位置已存在其他元素时
if (newBuckets[bn].hash_coll >= 0)
newBuckets[bn].hash_coll |= unchecked((int)0x80000000);
//二度哈希h1(key)+h2(key)
bn = (int)(((long)bn + incr) % (uint)newBuckets.Length);
} while (true);
}
protected virtual int GetHash(Object key)
{ //获取哈希码
return key.GetHashCode();
}
protected virtual bool KeyEquals(Object item, Object key)
{ //用于判断两key是否相等
return item == null ? false : item.Equals(key);
}
//add:true添加，false修改
private void Insert(Object key, Object nvalue, bool add)
{
if (count >= loadsize) expand();
uint seed; //h1
uint incr; //h2
uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
int ntry = 0; //用于表示h(key,i)中的i值
int emptySlotNumber = -1; //用于记录空位
int bn = (int)(seed % (uint)buckets.Length); //索引号
do
{ //如果是有冲突空位，需继续向后查找以确定是否存在相同的键
if (emptySlotNumber == -1 && (buckets[bn].key == buckets) &&(buckets[bn].hash_coll < 0))
emptySlotNumber = bn;
if (buckets[bn].key == null) //确定没有重复键才添加
{
if (emptySlotNumber != -1) //使用之前的空位
bn = emptySlotNumber;
buckets[bn].val = nvalue;
buckets[bn].key = key;
buckets[bn].hash_coll |= (int)hashcode;
count++;
return;
}
//找到重复键
if (((buckets[bn].hash_coll & 0x7FFFFFFF) == hashcode) && KeyEquals(buckets[bn].key, key))
{ //如果处于添加元素状态，则由于出现重复键而报错
if (add) throw new ArgumentException("添加了重复的键值！");
buckets[bn].val = nvalue; //修改批定键的元素
return;
}
//存在冲突则置hash_coll的最高位为1
if (emptySlotNumber == -1)
if (buckets[bn].hash_coll >= 0)
buckets[bn].hash_coll |= unchecked((int)0x80000000);
bn = (int)(((long)bn + incr) % (uint)buckets.Length);//二度哈希
} while (++ntry < buckets.Length);
throw new InvalidOperationException("添加失败！");
}
public virtual void Remove(Object key) //移除一个元素
{
uint seed; //h1
uint incr; //h2
uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
int ntry = 0; //h(key,i)中的i
bucket b;
int bn = (int)(seed % (uint)buckets.Length); //哈希地址
do
{
b = buckets[bn];
if (((b.hash_coll & 0x7FFFFFFF) == hashcode) && KeyEquals(b.key, key))
{
buckets[bn].hash_coll &= unchecked((int)0x80000000);
if (buckets[bn].hash_coll != 0)
{ //使key指向buckets
buckets[bn].key = buckets;
}
else //原来不存在冲突
{ //置key为空
buckets[bn].key = null;
}
buckets[bn].val = null; //释放相应的“值”。
count--;
return;
} //二度哈希
bn = (int)(((long)bn + incr) % (uint)buckets.Length);
} while (b.hash_coll < 0 && ++ntry < buckets.Length);
}
public override string ToString()
{
string s = string.Empty;
for (int i = 0; i < buckets.Length; i++)
{
if (buckets[i].key != null && buckets[i].key != buckets)
{ //不为空位时打印索引、键、值、hash_coll
s += string.Format("{0,-5}{1,-8}{2,-8}{3,-8}/r/n",
i.ToString(), buckets[i].key.ToString(),
buckets[i].val.ToString(),
buckets[i].hash_coll.ToString());
}
else
{ //是空位时则打印索引和hash_coll
s += string.Format("{0,-21}{1,-8}/r/n", i.ToString(),
buckets[i].hash_coll.ToString());
}
}
return s;
}
public virtual int Count
{ //获取元素个数
get { return count; }
}
}
class MyClass
{
static void Main(string[] args)
{
Hashtable hs = new Hashtable();
hs.Add( 1, 3);
hs.Add( 2, 3);
hs.Add( 5, 3);
hs.Add( 4, 3);
Console.ReadKey();
}
}

复制代码

tmtony · 发表于 2014-2-23 10:41:38

谢谢分享,坐个沙发

帐号		自动登录	找回密码
密码			注册

主题相关群

地区相关群[您还没设置居住地]

【转载】Hashcode类,补全并简化代码:

群介绍
主题无相 (随机显示版	同地区群块其他地区)

群介绍
OFFICE-VSTO公开课 (5757567)