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; } }