哈希表中,一串连续的已填充单元叫做填充序列。增加越来越多的数据项时,填充序列变的越来越长,这叫做聚集。
为了消除原始聚集和二次聚集,可以使用另外的一个方法:再哈希法:一种依赖关键字的探测序列,而不是每个关键字都一样,那么,不同的关键字即使映射到相同的数组下标,也可以使用不同的探测序列。
方法是把关键字用不同的哈希函数再做一次哈希化,用这个结果作步长,对指定的关键字,步长在整个探测中是不变的,不同的关键字使用不同的步长。
数组实现的哈希表,开放地址法之再哈希法:
import java.io.*;
class DataItem {//数据项
private int iData; // 数据项的关键字
public DataItem(int ii)
{ iData = ii; }
public int getKey()
{ return iData; }
}
class HashTable{//数组实现的哈希表,开放地址法之再哈希法
private DataItem[] hashArray; //存数据的数组
private int arraySize;
private DataItem nonItem; //已删除标志
HashTable(int size) {//哈希表构造函数
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-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("");
}
//哈希函数1
public int hashFunc1(int key){
return key % arraySize;
}
//哈希函数2,不同于哈希函数1,用于再哈希。
public int hashFunc2(int key){
// array size must be relatively prime to 5, 4, 3, and 2
return 5 - key % 5;
}
//哈希表中插入数据
public void insert(int key, DataItem item){
int hashVal = hashFunc1(key); //求关键字的哈希值
int stepSize = hashFunc2(key); // 再探测步长的大小
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
hashVal += stepSize; //单元被占用,再探测
hashVal %= arraySize;
}
hashArray[hashVal] = item;
}
//在哈希表中删除
public DataItem delete(int key) {
int hashVal = hashFunc1(key);
int stepSize = hashFunc2(key);
while(hashArray[hashVal] != null){//直到一个空单元出现
if(hashArray[hashVal].getKey() == key){
DataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem; //作删除标记
return temp;
}
hashVal += stepSize; //再探测
hashVal %= arraySize;
}
return null;
}
//在哈希表中搜索
public DataItem find(int key){
int hashVal = hashFunc1(key);
int stepSize = hashFunc2(key);
while(hashArray[hashVal] != null) {
if(hashArray[hashVal].getKey() == key)
return hashArray[hashVal];
hashVal += stepSize;
hashVal %= arraySize;
}
return null;
}
}
public class HashDoubleApp{
public static void main(String[] args) throws IOException{
int aKey;
DataItem aDataItem;
int size, n;
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
HashTable theHashTable = new HashTable(size);
for(int j=0; j<n; j++){
aKey = (int)(java.lang.Math.random() * 2 * size);
aDataItem = new DataItem(aKey);
theHashTable.insert(aKey, 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(aKey, 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 HashDoubleApp
Enter size of hash table: 13
Enter initial number of items: 10
Enter first letter of show, insert, delete, or find: s
Table: ** 14 ** 3 17 1 6 ** 21 6 23 25 23
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 99
Enter first letter of show, insert, delete, or find: s
Table: 99 14 ** 3 17 1 6 ** 21 6 23 25 23
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 100
Enter first letter of show, insert, delete, or find: s
Table: 99 14 100 3 17 1 6 ** 21 6 23 25 23
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 101
Enter first letter of show, insert, delete, or find: s
Table: 99 14 100 3 17 1 6 101 21 6 23 25 23
Enter first letter of show, insert, delete, or find:
代码下载:
- 大小: 81.2 KB
- 大小: 43.6 KB
- 大小: 21.7 KB
- 大小: 41.9 KB
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1744810
通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥,通常应对私钥加密后再保存、如何从...
通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥,通常应对私钥加密后再保存、如何从...
第16讲 - 开放地址法 第17讲 - 链地址法 第18讲 - 图的基本概念 第19讲 - 图的搜索 第20讲 - 图的最小生成树 License Copyright (c) ChungKing. All rights reserved. Licensed under the MIT License.
开放地址法 链地址法 哈希函数 哈希化的效率 哈希化和外部存储 小结 问题 实验 编程作业 第12章 堆 堆的介绍 Heap专题applet 堆的Java代码 基于树的堆 堆排序 小结 问题 实验 编程作业 第13章...
开放地址法 链地址法 哈希函数 哈希化的效率 哈希化和外部存储 小结 问题 实验 编程作业 第12章 堆 堆的介绍 Heap专题applet 堆的Java代码 基于树的堆 堆排序 小结 问题 实验 编程作业 第13章...
- 哈希表(开放定址法) ###第六章 - 二叉堆 - 左式堆 - 二项队列 ###第七章 - 插入排序 - 希尔排序 - 堆排序 - 归并排序 - 快速排序 ###第八章 -不相交集 ###第九章 -邻接表(Versioni 1,2) -拓扑排序(Versioni 1,2)...
该程序为计算机国际象棋程序实现了许多标准方法,例如迭代加深,negascout,吸引窗口,通过SEE修剪和MVV / LVA动作排序进行的静态搜索,哈希表,历史启发式,递归空动作,无效修剪,后期动作减少,打开书本和魔术位...
总体介绍 之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说... 根据对冲突的处理方式不同,哈希表有两种实现方式,一种开放地址方式(Open addre
系统主要运用在:在系统中一些分页或者样式交互事件处理中使用到了(比如地址选择框) 前端用到了ajax AJAX即"Asynchronous Javascript And XML"(异步JavaScript和XML),是指一种创建交互式网页应用的网页开发技术。...
其他一些对数组或哈希表有用的函数包括sort(),next(),prev()和each()。 对象 使用new语句产生一个对象: class foo { function do_foo () { echo "Doing foo."; } } $bar = new foo; $bar->do_foo(); 改变变量...
面向对象的思想方法已经非常流行了,在编程语言(例如java,js)中,都运用面向对象的编程思想。在XML中,就是要将网页也作为一个对象来操作和控制,我们可以建立自己的对象和模板。与对象进行交流,如何命令对象,...