哈希表中,一串连续的已填充单元叫做填充序列。增加越来越多的数据项时,填充序列变的越来越长,这叫做聚集。
为了消除原始聚集和二次聚集,可以使用另外的一个方法:再哈希法:一种依赖关键字的探测序列,而不是每个关键字都一样,那么,不同的关键字即使映射到相同的数组下标,也可以使用不同的探测序列。
方法是把关键字用不同的哈希函数再做一次哈希化,用这个结果作步长,对指定的关键字,步长在整个探测中是不变的,不同的关键字使用不同的步长。
数组实现的哈希表,开放地址法之再哈希法:
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
分享到:
相关推荐
线性探测是开放地址法的一种,它的基本思想是:一旦发生冲突,就沿着哈希表的索引顺序线性地向前探测,直到找到一个空的位置。 线性探测的步骤如下: 1. 计算键的哈希值,得到初始位置。 2. 如果该位置为空,直接...
哈希表的关键在于如何处理哈希冲突,常见的解决方式有开放寻址法和链地址法。在这个实现中,开发者可能使用了链地址法,即当两个键值通过哈希函数得到相同的索引时,将它们链接在一个链表中。 `Info.java`可能定义...
本项目聚焦于C语言实现开放地址法的哈希表,这是一种解决哈希冲突的方法。 **哈希表简介** 哈希表是由数组和哈希函数共同组成的。哈希函数将键转换为数组下标,使得在理想情况下,每个键都能直接定位到数组中的唯一...
开放地址法是一种解决哈希冲突的基本方法,常用于哈希表的设计与实现。在Java编程中,使用开放地址法可以创建高效的数据结构,快速进行数据查找、插入和删除操作。以下将详细介绍开放地址法的基本原理,以及如何用...
在实际编程中,常见的哈希表实现如Python的内置`dict`类型、Java的`HashMap`以及C++的`std::unordered_map`,它们都提供了高效的键值对操作。这些库通常已经优化了哈希函数和冲突解决策略,使用者无需关心底层细节。...
哈希表是一种高效的数据结构,它通过特定的哈希函数将键...例如,Python中的`dict`类型、Java的`HashMap`和C++的`std::unordered_map`都是哈希表的典型实现。理解哈希表的工作原理和优化策略对于提升程序性能至关重要。
哈希表,也被称为散列表,是数据结构中一种高效的数据存储和检索工具。它通过哈希函数将数据的关键字映射到...例如,`hashTest`这个文件可能包含了相关的测试代码,你可以通过阅读和运行这些代码来加深对哈希表的理解。
处理冲突有多种策略,如开放寻址法、链地址法、再哈希法等。在这个演示程序中,描述中提到的“处理冲突的方法都相对简单”,可能意味着使用了最常用的链地址法。在链地址法中,每个数组位置上都连接着一个链表,当新...
解决冲突的方法主要有两种:开放寻址法和链地址法。开放寻址法是指当发生冲突时,寻找下一个空的槽位;链地址法则是为每个槽位维护一个链表,相同哈希值的键存储在同一链表中。 3. **负载因子**:负载因子是哈希表...
解决冲突的方法有开放寻址法、链地址法等,但这些方法会增加额外的复杂性和潜在的性能损失。 - 不适用于有序数据:如果需要保持数据的顺序,哈希表可能不是最佳选择,因为它们通常不按插入顺序或其他特定顺序存储...
`Hashtable`使用内部的解决冲突策略,可能包括开放寻址法或链地址法。当冲突发生时,哈希表会尝试找到下一个可用的存储位置。 总的来说,Java的`Hashtable`类提供了一种快速访问和管理键值对的方式,适用于需要高效...
因此,解决冲突的方法是哈希表设计的关键部分,常见的解决策略有开放寻址法和链地址法。 开放寻址法是指当冲突发生时,继续寻找下一个空的哈希地址,直到找到为止。而链地址法则是为每个数组元素维护一个链表,所有...
为了解决冲突,哈希表通常采用链地址法或开放地址法等策略。在Java的HashMap中,采用的是链地址法,即在同一索引位置上形成一个链表,存储具有相同哈希码的键值对。 `HashMap`类的基本操作包括插入、删除、查找等。...
常见的解决冲突的方法有开放寻址法(当发生冲突时,寻找下一个空槽位)和链地址法(在每个数组元素位置上挂接一个链表,冲突的键加入链表)。另外,双散列和开放定址的变种如线性探测再散列、二次探测再散列也是常用...
解决冲突的方法主要有开放寻址法、链地址法和再哈希法等。 1. 开放寻址法:当发生冲突时,不是在当前位置停下,而是继续寻找下一个空的槽位,直到找到为止。这种方法要求哈希表的大小必须是质数,以避免特定的键...
在编写Java代码时,可以使用HashMap或者自己实现哈希表,以满足题目所要求的特定功能。此外,注意代码的可读性和效率,这是面试中评价代码质量的重要标准。 通过深入理解和实践这道题,你不仅能巩固哈希表的基础...
为了避免这种情况,可以考虑使用开放寻址法或者使用红黑树作为解决冲突的方法,例如在Java的`HashMap`中。 8. **总结** Java中的哈希表是通过数组和链表结合的方式实现的,提供快速的查找、插入和删除功能。这个...
解决冲突有多种策略,常见的有开放寻址法和链地址法。开放寻址法是当发生冲突时,寻找下一个空的哈希地址,直到找到为止;而链地址法则是在每个哈希桶内维护一个链表,所有哈希到同一位置的键都挂在该链表上。 哈希...
- 哈希表的冲突处理:由于哈希表可能会有碰撞,需要确保在插入和查找时能够正确处理这种情况,例如,使用链表或者开放寻址法来解决冲突。 - 避免重复计算:在遍历哈希表时,避免对同一回旋镖进行多次计数,可以通过...