不废话，直接上代码，关键地方有注释。package test2;class DataItem{private int key;public DataItem(int data){this.key = data;}public int getKey(){return this.key;}}public class HashTable {private DataItem[] dataArray;private int arraySize;private static DataItem noItem;static{noItem = new DataItem(-1);}public HashTable(int size){if(size > 0){arraySize = size;dataArray = new DataItem[arraySize];}}public void insertDataItem(int key){//假设hash表不满DataItem data = new DataItem(key);int hashCode = getHashCode(key);while(dataArray[hashCode] != null && dataArray[hashCode] != noItem){//++hashCode;//线性探测，会产生聚集现象hashCode %= arraySize;}dataArray[hashCode] = data;}public void insertSecondaryDataItem(int key){DataItem data = new DataItem(key);int hashCode = getHashCode(key);int stepSize,i=1;while(dataArray[hashCode] != null && dataArray[hashCode] != noItem){//stepSize = i*i;hashCode = hashCode + stepSize;//二次探测，减少聚集，但会产生二次聚集现象hashCode %= arraySize;++i;}dataArray[hashCode] = data;}public void insertAgainDataItem(int key){//使用开放地址策略时，再哈希法最常用DataItem data = new DataItem(key);int hashCode = getHashCode(key);int stepSize,constant=5;while(dataArray[hashCode] != null && dataArray[hashCode] != noItem){//stepSize = constant – (key % constant);//再哈希法：stepSize = constant – (key % constant) 保证对每个关键字可能产生不同的步长hashCode = hashCode + stepSize;//再哈希法要求表的长度是一个质数，例如13。假设是15非质数，插入元素0，步长是5，那么可能的插入位置只有0,5,10hashCode %= arraySize;//假如是13，则可能的插入位置有0,5,10，2，7，12等等，，可以遍历所有剩余位置。}dataArray[hashCode] = data;}public void deleteDataItem(int key){ // 线性探测的删除方法，二次探测，再哈希法的删除方法类似于它们的插入方法；int hashCode = getHashCode(key);while(dataArray[hashCode] != null ){///if(dataArray[hashCode].getKey() == key){dataArray[hashCode] = noItem;System.out.println("delete success");return;}else{hashCode++;hashCode %= arraySize;///}}System.out.println("not found it:"+key);}public DataItem findDataItem(int key){int hashCode = getHashCode(key);while(dataArray[hashCode] != null){////if(dataArray[hashCode].getKey() == key){return dataArray[hashCode];}else{hashCode++;hashCode %= arraySize;}}return null;}public void displayDataItem(){for(int i=0; i<this.arraySize;i++){if(dataArray[i] != null){System.out.print(" "+i+","+dataArray[i].getKey()+" ");}}}public int getHashCode(int key){//hash函数if(key < 0){return -(key%arraySize);}return key%arraySize;}}
下面是链表法实现的hash表，即将hash表的每个数组元素声明为链表类型，插入删除操作遵从链表的操作即可。LinkNode/LinkList类的实现参考其他文章
class LinkListHashTable {private LinkList[] dataArray;private int arraySize;public LinkListHashTable(int size){if(size > 0){arraySize = size;dataArray = new LinkList[arraySize];for(int i=0;i<size;i++){dataArray[i] = new LinkList();}}}public void insertDataItem(int key, double key2){//链表结点存储key1和key2两个数据项，（有序插入时可减少查找不成功的时间，但增加了插入时的时间）int hashCode = getHashCode(key);dataArray[hashCode].insertFront(key, key2);}public void deleteDataItem(int key){ // 链地址法的删除方法int hashCode = getHashCode(key);LinkNode pre = dataArray[hashCode].getFirst();LinkNode current = pre;while(current != null ){///if(dataArray[hashCode].findNode(key)!= null){pre.next = current.next;System.out.println("delete success");return;}else{pre = pre.next;current = current.next;}}System.out.println("not found it:"+key);}public LinkNode findDataItem(int key){int hashCode = getHashCode(key);LinkNode temp = dataArray[hashCode].findNode(key);if(temp != null){System.out.println("find it");return temp;}else{System.out.println("not find it");return null;}}public void displayDataItem(){for(int i=0; i<this.arraySize;i++){if(dataArray[i] != null){System.out.print(" "+i+","+" ");dataArray[i].displayLinkList();System.out.println(" ");}}}public int getHashCode(int key){//hash函数if(key < 0){return -(key%arraySize);}return key%arraySize;}}下面是测试代码：class HashTableApp{public static void main(String args[]){//HashTable hashT = new HashTable(10);////hashT.insertDataItem(1);//hashT.insertDataItem(3);//hashT.insertDataItem(2);//hashT.insertDataItem(11);//hashT.insertDataItem(-1);////hashT.displayDataItem();////hashT.deleteDataItem(2);//hashT.insertDataItem(-1);//hashT.displayDataItem();LinkListHashTable linkhash = new LinkListHashTable(13);linkhash.insertDataItem(1, 1);linkhash.insertDataItem(2, 2);linkhash.insertDataItem(3, 3);linkhash.insertDataItem(11, 11);linkhash.displayDataItem();}}
那我想明天可以是我的来世。
