package cn.com.chenlly;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
/**
* @Description 哈希表发生冲突时的链地址方法算法，关键字通过哈希函数映射到哈希表单元，而插入时插入到这个单元的链表中
* 填充因子：数据项和哈希表容量的比值，在开发地址法中是1，在链地址法中>=1 桶：如果哈希表后面链接的是数组，
* 则这样的数组称为桶。
* @Company OpenData
* @Author Chenlly
* @Version 1.0
* @Data 09-03-31
*/
class Link {
public int iData;
public Link next;
// 构造方法
public Link(int nData) {
this.iData = nData;
}
}
class LinkList {
private Link first;
// 构造方法
public LinkList() {
first = null;
}
// 插入数据项到链表
public void insert(Link link) {
Link current = first;
Link previous = null;
while (current != null && link.iData > current.iData) {
previous = current;
current = current.next;
}
// 处理第一个结点的情况(头插法)
if (previous == null) {
first = link;
} else {
previous.next = link;
}
link.next = current;
}
// 在链表中搜索关键字对应的节点
public Link find(int key) {
Link current = first;
while (current != null && current.iData <= key) {
if (current.iData != key ) {
current = current.next;
} else {
return current;
}
}
return null;
}
// 在链表中删除关键字对应的节点
public void delete(int key) {
Link current = first;
Link previous = null;
//因为哈希表单元没有数据项
if (current == null) {
return ;
}
while ( current != null && current.iData != key){
//因为到了链尾
if(current.next == null){
return;
}
previous = current;
current = current.next;
}
if(previous == null){
first = first.next;
} else {
previous.next = current.next;
}
}
// 显示链表信息
public void display() {
System.out.print("List(first->end)");
Link current = first;
while (current != null) {
System.out.print(current.iData + ",");
current = current.next;
}
System.out.println("");
}
}
public class HashLinkApp {
// private static final int MAX_SIZE = 20;
private LinkList[] hashArray;
// 构造方法
public HashLinkApp(int size) {
hashArray = new LinkList[size];
// 初始化哈希表
for (int i = 0; i < hashArray.length; i++) {
hashArray[i] = new LinkList();
}
}
// 哈希函数
public int hashFun(int key) {
return key % hashArray.length;
}
// 关键字插入哈希表
public void insert(Link link) {
int hashVal = this.hashFun(link.iData);
hashArray[hashVal].insert(link);
}
// 通过关键字在哈希表中查找
public Link findById(int key) {
int hashVal = this.hashFun(key);
Link link = hashArray[hashVal].find(key);
return link;
}
// 通过关键字删除数据项
public void delete(int key) {
int hashVal = this.hashFun(key);
hashArray[hashVal].delete(key);
}
// 显示哈希表数据项信息
public void displayHashT() {
for (int i = 0; i < hashArray.length && hashArray[i] != null; i++) {
System.out.print(i + ".");
hashArray[i].display();
}
}
// 从键盘读入数据
public static String readStr() {
InputStreamReader ir = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(ir);
String str = "";
try {
str = br.readLine();
} catch (IOException ex) {
ex.printStackTrace();
}
return str;
}
// 主调函数
public static void main(String[] args) {
System.out.println("请选择操作序列");
System.out.println("1 插入数据项到哈希表");
System.out.println("2 通过关键字查找");
System.out.println("3 删除关键字对于哈希表中的数据项");
System.out.println("4 显示哈希表中的数据项信息");
System.out.println("5 退出");
System.out.println("请输入哈希表空间大小");
int size = Integer.parseInt(HashLinkApp.readStr());
HashLinkApp hashLinkApp = new HashLinkApp(size);
Link itemLink;
while (true) {
System.out.println("请输入操作序列");
int op = Integer.parseInt(HashLinkApp.readStr());
switch (op) {
case 1:
System.out.println("请输入数据项");
int key = Integer.parseInt(HashLinkApp.readStr());
itemLink = new Link(key);
hashLinkApp.insert(itemLink);
break;
case 2:
System.out.println("请输入需要查找的数据项");
int fKey = Integer.parseInt(HashLinkApp.readStr());
Link link = hashLinkApp.findById(fKey);
if (link != null) {
System.out.println("数据项" + link.iData + "已经查到");
} else {
System.out.println("数据项没有查到");
}
break;
case 3:
System.out.println("请输入需要删除的数据项");
int dKey = Integer.parseInt(HashLinkApp.readStr());
hashLinkApp.delete(dKey);
break;
case 4:
hashLinkApp.displayHashT();
break;
case 5:
default:
System.exit(0);
}// end switch
}// end while
}
}