package hashtable;
//哈希表实现,雇员.
public class HashTableDemo {
}
//雇员信息类
class Emp{
public int id;
public String name;
public Emp next;
public void Emp(int id,String name) {
this.id = id;
this.name = name;
}
}
//雇员链表
class EmpLinkedList{
//头节点
private Emp head;
//添加雇员信息,相当于尾插法
public void add(Emp emp) {
if(head == null) {
head =emp;
return;
}
//辅助指针,当前指针
Emp cur = head;
while(true) {
if(cur.next==null) {
break;
}
cur = cur.next;
}
//while结束后,说明到了最后一个节点,将emp加入链表
cur.next = emp;
}
//遍历雇员信息
public void list(int no) {
if(head == null) {
System.out.println("第"+(no+1)+"链表为空");
return;
}
System.out.println("当前链表信息为");
Emp cur = head;
while(true) {
System.out.printf("==>id=%d name=%s\t",cur.id,cur.name);
if(cur.next == null) {
break;
}
cur = cur.next;
}
System.out.println();
}
//通过id遍历雇员信息
public Emp findEmpById(int id) {
if(head == null) {
System.out.println("链表为空");
return null;
}
Emp cur = head;
while(true) {
if(cur.id == id) {//如果找到
break;
}
//如果没找到结束条件为
if(cur.next == null) {
//因为上一个if和当前if说明现在这个节点也不是,并且已经是最后一个节点了
cur = null;//这个设置只是给下面用来return的。
break;
}
cur = cur.next;
}
return cur;
}
}
//HashTable
class HashTable{
private EmpLinkedList[] empLinkedListArray;
private int size;
//构造函数
public void HashTable(int size) {
//初始化empLinkedListArray
empLinkedListArray = new EmpLinkedList[size];
//初始化每个链表
for(int i=0;i<size;i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
//添加雇员
public void add(Emp emp) {
//先通过散列函数得到应该放在哪个链表中,再添加emp
empLinkedListArray[hashFun(emp.id)].add(emp);
}
//编写散列函数
public int hashFun(int id) {
return id % size;
}
//遍历hashtable
public void list() {
for(int i =0;i<size;i++) {
empLinkedListArray[i].list(i);
}
}
//通过id查找雇员信息
public void findEmpById(int id) {
//确定在哪条链表no
int no = hashFun(id);
Emp emp =empLinkedListArray[no].findEmpById(id);
if(emp!=null) {
System.out.printf("在第%d条链表中找到==>id=%d name = %s\n", (no+1),id,emp.name);
}else {
System.out.println("在哈希表中没有改雇员信息");
}
}
}
调用过程外部调用table里的方法,table里的数组点方法即调用list里的方法。?
|