与开放地址法思想不同，它不用再次寻找数组位置,采用链表方式存储重复的位置
//链表结点
public class Link {
private int iData;//节点数据
public Link next;//当前节点的连接节点
public Link(int it) {
iData=it;
}
public int getKey() {
return iData;
}
public void displayLink() {
System.out.print(iData+" ");
}
}
//有序链表
public class SortedList {
private Link first;
public SortedList() {
first=null;
}
//插入
public void insert(Link theLink) {
int key=theLink.getKey();//当前节点的数值
Link previous=null;//存储前一个节点
Link current=first;//存储当前节点
while(current!=null && key>current.getKey()) {//数据是从左到右依次降低
//向后找位置
previous=current;//previous存储当前非目的节点
current=current.next;//current存储当前非目的节点的下一个节点
}
if(previous==null) {//说明插入的位置是第一个
first=theLink;
}else previous.next=theLink;//如果不是第一个，就是这样插入链表的
theLink.next=current;//上面与这一步一起完成插入操作
}
//删除
public void delete(int key) {
Link previous=null;
Link current=first;
while(current!=null && key!=current.getKey()) {
previous=current;
current=current.next;
}
if(previous==null)
first=first.next;
else
previous.next=current.next;
}
//查找
public Link find(int key) {
Link current=first;
while(current!=null && current.getKey()<=key) {
if(current.getKey()==key) {
return current;//找到了
}
current=current.next;
}
return null;
}
//显示链表
public void displayList() {
System.out.print("显示：");
Link current=first;
while(current!=null) {
current.displayLink();
current=current.next;
}
System.out.println();
}
}
//哈希表
public class HashTable {
private SortedList[] hashArray;//数组
private int arraySize;//哈希表的大小
public HashTable(int size) {//初始化
arraySize=size;
hashArray=new SortedList[arraySize];
//给每一个链表初始化
for(int j=0;j hashArray[j]=new SortedList(); } } //打印 public void displayTable() { System.out.print("table:"); for(int j=0;j System.out.print(j+" "); hashArray[j].displayList();//显示j位置的链表 } } //哈希化 public int hashFunc(int key) { return key%arraySize; } //插入 public void insert(Link theLink) { int key=theLink.getKey(); int hashVal=hashFunc(key);//哈希化 //链地址法插入 hashArray[hashVal].insert(theLink); } //删除 public void delete(int key) { int hashVal=hashFunc(key); hashArray[hashVal].delete(key); } //查找 public Link find(int key) { int hashVal=hashFunc(key); Link theLink=hashArray[hashVal].find(key); return theLink; } } import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Test { public static void main(String [] agrs) throws IOException { Link aDataItem; int akey,size,n,keysPerCell=100; System.out.print("Enter:"); size=getInt(); System.out.println("初始化："); n=getInt(); keysPerCell=10; HashTable theHashTable=new HashTable(size); for(int j=0;j akey=(int)(java.lang.Math.random()*keysPerCell*size); aDataItem=new Link(akey); theHashTable.insert(aDataItem); } while(true) { System.out.print("Enter first of show,isnert,delete ,find:"); char choice=getChar(); switch(choice){ case 's': theHashTable.displayTable(); break; case 'i': System.out.print("insert："); akey=getInt(); aDataItem=new Link(akey); theHashTable.insert(aDataItem); break; case 'd': System.out.println("输入要删除的key"); akey=getInt(); theHashTable.delete(akey); break; case 'f': System.out.println("输入要查找的key"); akey=getInt(); aDataItem=theHashTable.find(akey); if(aDataItem!=null) System.out.println("found"+akey); else System.out.println("没有找到"); break; default: System.out.println("无效的输入"); } } } public static String getString() throws IOException{ InputStreamReader isr=new InputStreamReader(System.in); BufferedReader br=new BufferedReader(isr); return br.readLine(); } public static char getChar() throws IOException{ return getString().charAt(0); } public static int getInt() throws IOException{ return Integer.parseInt(getString()); } }