面試準備 - HashTable 的C#實現 開放地址法
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;
}
}
浙公網安備 33010602011771號