Interface
public interface HashTable {
//向散列表中插入一个关键字为theKey的元素obj，若成功返回真否则返回假
boolean insert(Object theKey, Object obj);
//向散列表中查找并返回给定关键字theKey对应的元素，若查找失败返回空
Object search(Object theKey);
//从散列表中删除关键字为theKey的元素，若删除成功返回真否则返回假
boolean delete(Object theKey);
//返回散列表中已存在的元素个数
int size();
//返回散列表的容量，即散列表的空间大小m的值
int capacity();
//判断散列表是否为空，若为空则返回真 否则返回假
boolean isEmpty();
//清楚散列表的所有元素，使之变成一个空表
void clear();
//输出散列表中保存的所有关键字和对应的元素
void output();
}
Separate Chaining
public class SeqHashTable implements HashTable {
private int m; //保存散列表的容量
private Object[] key; //定义保存元素关键字的数组
private Object[] ht; //定义保存散列表的数组
private int n; //散列表中已有的元素个数
private Object tag; //元素内容被删除后的关键字删除标记
//散列函数，采用除
private int h(Object theKey){
//留余数发，若参数不是整数，应设法转换成整数
return (Integer)theKey%m;
}
public SeqHashTable(int mm, Object tag){
//假定散列表的容量至少为13
if(mm < 13){
m = 13;
}else{
m = mm;
}
n=0;
key = new Object[m];
ht = new Object[m];
this.tag = tag; //置关键字删除标记为参加tag的值
}
@Override
public boolean insert(Object theKey, Object obj) {
int d = h(theKey);
int temp = d;
while(key[d] != null && key[d].equals(tag) != true){
//用线性探测法处理冲突，寻找插入位置
if(key[d].equals(theKey) == true)
break; //元素已经存在，则退出循环
d = (d+1) % m;
if(d == temp){ //查找一周后扔无位置，应重组散列表或退出运行
System.out.println("散列表无空间，退出运行");
System.exit(1);
}
}
if(key[d] == null || key[d].equals(tag)==true){
//找到插入位置，插入新的关键字和元素并返回真
key[d] = theKey;
ht[d] = obj;
n++;
return true;
}else{ //用新元素obj修改已存在的元素并返回假
ht[d] = obj;
return false;
}
}
@Override
public Object search(Object theKey) {
int d= h(theKey);
int temp = d;
while(key[d] != null){
if(key[d].equals(theKey)){
return ht[d];
}else{
d = (d+1) % m;
}
if(d == temp)
return null;
}
return null;
}
@Override
public boolean delete(Object theKey) {
int d = h(theKey);
int temp = d;
while(key[d] != null){
if(key[d].equals(theKey)){
key[d] = tag;
ht[d] = null;
n--;
return true;
}else{
d = (d+1)%m;
}
if(d==temp){
return false;
}
}
return false;
}
@Override
public int size() {
return n;
}
@Override
public int capacity() {
return m;
}
@Override
public boolean isEmpty() {
return n==0;
}
@Override
public void clear() {
for(int i=0; i<m; i++){
key[i] = null;
ht[i] = null;
}
n=0;
}
@Override
public void output() {
for(int i=0; i<m; i++){
if(key[i]==null || key[i].equals(tag))
continue;
System.out.println("(" + key[i] + " " + ht[i] + "),");
}
System.out.println();
}
}
Open Address implementation
public class LinkHashTable implements HashTable {
private int m; //保存散列表的容量
private HashNode[] ht; //定义保存散列表的数组
private int n; //散列表中已有的元素个数
//散列函数
private int h(Object theKey){
return (Integer)theKey % m;
}
public LinkHashTable(int mm){
if(mm < 13){
m = 13;
}else{
m = mm;
}
n = 0;
ht = new HashNode[m];
}
@Override
public boolean insert(Object theKey, Object obj) {
int d = h(theKey);
HashNode p = ht[d];
// 从单链表中顺序查找关键字为theKey的节点
while(p != null){
if(p.key.equals(theKey) == true)
break;
else
p = p.next;
}
if(p != null){ //用新元素obj修改已有节点的元素值并返回假
p.element = obj;
return false;
}else{
p = new HashNode(theKey, obj);
p.next = ht[d];
ht[d] = p;
n++;
return true;
}
}
@Override
public Object search(Object theKey) {
int d = h(theKey);
HashNode p = ht[d];
while(p!=null){
if(p.key.equals(theKey))
return p.element;
else
p = p.next;
}
return null;
}
@Override
public boolean delete(Object theKey) {
int d = h(theKey);
HashNode p = ht[d], q = null; //p指向表头节点，q指向前驱节点，初始为空
while(p != null){
if(p.key.equals(theKey))
break;
else{
q = p;
p = p.next;
}
}
if(p == null) //没有删除的元素，返回false
return false;
else if(q == null) //删除的是表头节点
ht[d] = p.next;
else //删除的是非表头节点
q.next = p.next;
n--;
return true;
}
@Override
public int size() {
return n;
}
@Override
public int capacity() {
return m;
}
@Override
public boolean isEmpty() {
return n==0;
}
@Override
public void clear() {
for(int i=0; i<m; i++){
ht[i] = null;
}
n=0;
}
@Override
public void output() {
for(int i=0; i<m; i++){
HashNode p = ht[i];
while(p != null){
System.out.println("(" + p.key + " " + p.element + "),");
p = p.next;
}
}
System.out.println();
}
class HashNode {
Object key;
Object element;
HashNode next;
public HashNode(Object theKey, Object obj){
key = theKey;
element = obj;
next = null;
}
}
}