import java.io.*;
class DataItem { //数据
private int iData; // data item (key)
public DataItem(int ii) {
iData = ii;
}
public int getKey(){
return iData;
}
}
class HashTable{//数组实现的哈希表,开放地址法之线性探测
private DataItem[] hashArray; //存放数据的数组
private int arraySize;
private DataItem nonItem; //用作删除标志
public HashTable(int size) {//构造函数
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1); // deleted item key is -1
}
public void displayTable(){//显示哈希表
System.out.print("Table: ");
for(int j=0; j<arraySize; j++)
{
if(hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
//哈希函数
public int hashFunc(int key)
{
return key % arraySize;
}
//在哈希表中插入数据
public void insert(DataItem item){
int key = item.getKey(); // 获取数据的键值
int hashVal = hashFunc(key); // 计算其哈希值
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
++hashVal; // 插入位置被占,线性探测下一位置
hashVal %= arraySize; // 不让超过数组的大小
}
hashArray[hashVal] = item; // 找到空位后插入
}
//在哈希表中删除
public DataItem delete(int key) {
int hashVal = hashFunc(key); // 计算其哈希值
while(hashArray[hashVal] != null){
if(hashArray[hashVal].getKey() == key){
DataItem temp = hashArray[hashVal]; // 记录已删除的数据
hashArray[hashVal] = nonItem; // 删除它
return temp;
}
++hashVal; // 到下一单元找
hashVal %= arraySize;
}
return null; // 没有找到要删除的数据
}
//在哈希表中查找
public DataItem find(int key) {
int hashVal = hashFunc(key); //哈希这个键
while(hashArray[hashVal] != null) { // 直到空的单元
if(hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // 找到
++hashVal; // 去下一单元找
hashVal %= arraySize; // 不让超过数组的大小
}
return null; // 没有找到
}
}
public class HashTableApp{//测试
public static void main(String[] args) throws IOException {
DataItem aDataItem;
int aKey, size, n, keysPerCell;
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
keysPerCell = 10;
HashTable theHashTable = new HashTable(size);
for(int j=0; j<n; j++){
aKey = (int)(java.lang.Math.random() * keysPerCell * size);
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
}
while(true){
System.out.print("Enter first letter of ");
System.out.print("show, insert, delete, or find: ");
char choice = getChar();
switch(choice){
case 's':
theHashTable.displayTable();
break;
case 'i':
System.out.print("Enter key value to insert: ");
aKey = getInt();
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
break;
case 'd':
System.out.print("Enter key value to delete: ");
aKey = getInt();
theHashTable.delete(aKey);
break;
case 'f':
System.out.print("Enter key value to find: ");
aKey = getInt();
aDataItem = theHashTable.find(aKey);
if(aDataItem != null)
{
System.out.println("Found " + aKey);
}
else
System.out.println("Could not find " + aKey);
break;
default:
System.out.print("Invalid entry\n");
}
}
}
public static String getString() throws IOException{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
}
运行:
C:\java>java HashTableApp
Enter size of hash table: 20
Enter initial number of items: 10
Enter first letter of show, insert, delete, or find: s
Table: ** ** ** 143 24 85 166 ** ** 89 30 ** ** ** 34 15 ** 17 ** 59
Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 89
Enter first letter of show, insert, delete, or find: s
Table: ** ** ** 143 24 85 166 ** ** -1 30 ** ** ** 34 15 ** 17 ** 59
Enter first letter of show, insert, delete, or find: f
Enter key value to find: 17
Found 17
Enter first letter of show, insert, delete, or find:
源码下载:
分享到:
相关推荐
线性探测哈希使用哈希表的线性探测实现
(1) 建立一个哈希表,哈希函数为除留余数法,处理冲突的方法为线性探测再散列或二次探测再散列。 (2) 往哈希表中依次存入插入多个单词。 (3) 显示哈希表的存储情况。 (4) 计算哈希表的平均查找长度。 (5) ...
哈希表 使用线性探测和外部链接作为冲突策略的哈希表的 Java 实现(参见 pdf)
该项目使用线性探测来处理冲突,将随机数的插入和冲突可视化到哈希表中。 您可以在下载与此项目关联的 JAR 文件,也可以自己编译该项目。 该项目使用 SimpleGUI,这是一个提供对 Java 图形和 GUI 输入的简化访问的库...
哈希表:单独链接,线性探测 图形 无向图:DFS,BFS 有向图:循环检测,拓扑排序,图遍历 最小生成树:Prim,Kruskal 短路:Dijkstra,Bellman-Ford 细绳 字符串排序:LSD基数排序,MSD基数排序,3向基数快速排序...
通过使用哈希表反转索引哈希函数SSF:简单求和功能PAF:多项式累加函数
哈希表 线性探测 二次探测 双重探测 单独链接 二进制搜索树 迭代二叉搜索树 递归二进制搜索树 具有内部类的二进制搜索树 堆 最小堆 最大堆 图表 种类 加权的 未加权 定向的 加权定向 未加权定向 无向 加权无向 未...
线性探测哈希表, 格雷厄姆扫描,和 kd 树。 Part II 专注于图和字符串处理算法。 主题包括: 深度优先搜索, 广度优先搜索, 拓扑排序, Kosaraju-Sharir, 克鲁斯卡尔 总理, 迪基斯特拉, 贝尔曼-福特, 福特-福...
主题包括联合查找、二分搜索、堆栈、队列、袋子、插入排序、选择排序、shellsort、快速排序、三路快速排序、归并排序、堆排序、二叉堆、二分搜索树、红黑树、分离链和线性探测哈希表、格雷厄姆扫描和 kd 树。 第二...
线性探测 多项式探测 散列探测的散列 联合查找 后缀树 算法 图表 分布式文件系统 BFS 拓扑排序 克鲁斯卡尔 MST 总理 MST 强连接组件 迪杰斯特拉 最大流量 计算机科学问题 问题清单 力码 - O(n) 动态规划 最长公共子...
拼写检查器创建了一个线性探测哈希表并用它来执行文档的拼写检查。
主题包括联合查找,二进制搜索,堆栈,队列,包,插入排序,选择排序,shellsort,quicksort,3向quicksort,mergesort,heapsort,binary堆,binary搜索树,red-black树,分离链和线性探测哈希表,Graham扫描和kd...