Hashtable是很经常在面试中遇到的数据结构，因为他的O(1)操作时间和O(n)空间
之所以自己写一份是因为：
- 加深对于hashtable的理解
- 某些公司面试的时候需要coding.......
开放地址法 Xn=(Xn-1 +b ) % size
理论上b要和size是要精心选择的，不过我这边没有做特别的处理，101的默认size是从c#源代码中抄袭的。。。。
代码尽量简单一点是为了理解方便
hashtable快满的时候扩展一倍空间，数据和标志位还有key 这三个数组都要扩展
删除的时候不能直接删除元素，只能打一个标志（因为用了开放地方方法）
目前只支持string和int类型的key（按位131进制）
非线程安全- 因为这是范例代码
支持泛型
public class Hashtable<T>
{
public Hashtable()
{
this.dataArray = new T[this.m];
this.avaiableCapacity = this.m;
this.keyArray = new int[this.m];
for (int i = 0; i < this.keyArray.Length; i++)
{
this.keyArray[i] = -1;
}
this.flagArray = new bool[this.m];
}
private int m = 101;
private int l = 1;
private int avaiableCapacity;
private double factor = 0.35;
private T[] dataArray;
private int[] keyArray;
private bool[] flagArray;
public void Add(string s, T item)
{
if (string.IsNullOrEmpty(s))
{
throw new ArgumentNullException("s");
}
if ((double)this.avaiableCapacity / this.m < this.factor)
{
this.ExtendCapacity();
}
var code = HashtableHelper.GetStringHash(s);
this.AddItem(code, item, this.dataArray, code, this.keyArray, this.flagArray);
}
public T Get(string s)
{
if (string.IsNullOrEmpty(s))
{
throw new ArgumentNullException("s");
}
var code = HashtableHelper.GetStringHash(s);
return this.GetItem(code, this.dataArray, code, this.keyArray, this.flagArray);
}
private void ExtendCapacity()
{
this.m *= 2;
this.avaiableCapacity += this.m;
T[] newItems = new T[this.m];
int[] newKeys = new int[this.m];
bool[] newFlags = new bool[this.m];
for (int i = 0; i < newKeys.Length; i++)
{
newKeys[i] = -1;
}
for (int i = 0; i < this.dataArray.Length; i++)
{
if (this.keyArray[i] >= 0 && !this.flagArray[i])
{
//var code = HashtableHelper.GetStringHash(s);
this.AddItem(
this.keyArray[i],
this.dataArray[i],
newItems,
this.keyArray[i],
newKeys,
this.flagArray);
}
}
this.dataArray = newItems;
this.keyArray = newKeys;
this.flagArray = newFlags;
// throw new NotImplementedException();
}
private int AddItem(int code, T item, T[] data, int hashCode, int[] keys, bool[] flags)
{
int address = code % this.m;
if (keys[address] < 0)
{
data[address] = item;
keys[address] = hashCode;
this.avaiableCapacity--;
return address;
}
else if (keys[address] == hashCode)
{
if (flags[address])
{
flags[address] = false;
data[address] = item;
return address;
}
throw new ArgumentException("duplicated key");
}
else
{
int nextAddress = address + this.l; //open addressing Xn=Xn-1 + b
return this.AddItem(nextAddress, item, data, hashCode, keys, flags);
}
}
private T GetItem(int code, T[] data, int hashCode, int[] keys, bool[] flags)
{
int address = code % this.m;
if (keys[address] < 0)
{
return default(T);
}
else if (keys[address] == hashCode)
{
if (flags[address])
{
return default(T);
}
return data[address];
}
else
{
int nextAddress = address + this.l; //open addressing Xn=Xn-1 + b
return this.GetItem(nextAddress, data, hashCode, keys, flags);
}
}
public void Delete(string s)
{
if (string.IsNullOrEmpty(s))
{
throw new ArgumentNullException("s");
}
var code = HashtableHelper.GetStringHash(s);
this.DeleteItem(code, this.dataArray, code, this.keyArray, this.flagArray);
}
private void DeleteItem(int code, T[] data, int hashCode, int[] keys, bool[] flags)
{
int address = code % this.m;
if (keys[address] < 0)
{
return;
//not exist
}
else if (keys[address] == hashCode)
{
if (!this.flagArray[address])
{
flags[address] = true;
this.avaiableCapacity++;
}
}
else
{
int nextAddress = address + this.l; //open addressing Xn=Xn-1 + b
this.DeleteItem(nextAddress, data, hashCode, keys, flags);
}
}
}
public class HashtableHelper
{
public static int GetStringHash(string s)
{
if (string.IsNullOrEmpty(s))
{
throw new ArgumentNullException("s");
}
var bytes = Encoding.ASCII.GetBytes(s);
int checksum = GetBytesHash(bytes, 0, bytes.Length);
return checksum;
}
public static int GetBytesHash(byte[] array, int ibStart, int cbSize)
{
if (array == null || array.Length == 0)
{
throw new ArgumentNullException("array");
}
int checksum = 0;
for (int i = ibStart; i < (ibStart + cbSize); i++)
{
checksum = (checksum * 131) + array[i];
}
return checksum;
}
public static int GetBytesHash(char[] array, int ibStart, int cbSize)
{
if (array == null || array.Length == 0)
{
throw new ArgumentNullException("array");
}
int checksum = 0;
for (int i = ibStart; i < (ibStart + cbSize); i++)
{
checksum = (checksum * 131) + array[i];
}
return checksum;
}
}