Dsa Using Java 简明教程
DSA using Java - Hash Table
Hashing
哈希是一种将一系列键值转换为一系列数组索引的技术。我们将使用模运算符来获得一系列键值。考虑一个大小为 20 的哈希表示例,以下项目需要存储。项目采用 (key,value) 格式。
-
(1,20)
-
(2,70)
-
(42,80)
-
(4,25)
-
(12,44)
-
(14,32)
-
(17,11)
-
(13,78)
-
(37,98)
Sr.No. |
Key |
Hash |
Array Index |
1 |
1 |
1 % 20 = 1 |
1 |
2 |
2 |
2 % 20 = 2 |
2 |
3 |
42 |
42 % 20 = 2 |
2 |
4 |
4 |
4 % 20 = 4 |
4 |
5 |
12 |
12 % 20 = 12 |
12 |
6 |
14 |
14 % 20 = 14 |
14 |
7 |
17 |
17 % 20 = 17 |
17 |
8 |
13 |
13 % 20 = 13 |
13 |
9 |
37 |
37 % 20 = 17 |
17 |
Linear Probing
我们可以看到,可能发生使用哈希技术创建的索引已经是数组的已用索引。在这种情况下,我们可以通过查看下一个单元格来搜索数组中的下一个空闲位置,直到我们找到一个空闲单元格。这种技术称为线性探查。
Sr.No. |
Key |
Hash |
Array Index |
在线性探查之后,数组索引 |
1 |
1 |
1 % 20 = 1 |
1 |
1 |
2 |
2 |
2 % 20 = 2 |
2 |
2 |
3 |
42 |
42 % 20 = 2 |
2 |
3 |
4 |
4 |
4 % 20 = 4 |
4 |
4 |
5 |
12 |
12 % 20 = 12 |
12 |
12 |
6 |
14 |
14 % 20 = 14 |
14 |
14 |
7 |
17 |
17 % 20 = 17 |
17 |
17 |
8 |
13 |
13 % 20 = 13 |
13 |
13 |
9 |
37 |
37 % 20 = 17 |
17 |
18 |
DataItem
定义一个具有某些数据和键的数据项,根据该键在哈希表中进行搜索。
public class DataItem {
private int key;
private int data;
public DataItem(int key, int data){
this.key = key;
this.data = data;
}
public int getKey(){
return key;
}
public int getData(){
return data;
}
}
Search Operation
每当要搜索元素时。计算已传递键的哈希代码,并使用该哈希代码作为数组中的索引来定位该元素。如果在计算的哈希代码中没有找到元素,请使用线性探测获得元素。
public DataItem search(int key){
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=null){
if(hashArray[hashIndex].getKey() == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= size;
}
return null;
}
Insert Operation
每当要插入元素时。计算已传递键的哈希代码,并使用该哈希代码作为数组中的索引来定位该索引。如果在计算的哈希代码中找到了某个元素,请对空位置使用线性探测。
public void insert(DataItem item){
int key = item.getKey();
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] !=null
&& hashArray[hashIndex].getKey() != -1){
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= size;
}
hashArray[hashIndex] = item;
}
Delete Operation
每当要删除元素时。计算已传递键的哈希代码,并使用该哈希代码作为数组中的索引来定位该索引。如果在计算的哈希代码中找不到元素,请使用线性探测获得元素。找到后,在那里存储一个虚拟项来保持哈希表的完整性能。
public DataItem delete(DataItem item){
int key = item.getKey();
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=null){
if(hashArray[hashIndex].getKey() == key){
DataItem temp = hashArray[hashIndex];
//assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp;
}
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= size;
}
return null;
}
HashTable Implementation
DataItem.java
package com.tutorialspoint.datastructure;
public class DataItem {
private int key;
private int data;
public DataItem(int key, int data){
this.key = key;
this.data = data;
}
public int getKey(){
return key;
}
public int getData(){
return data;
}
}
HashTable.java
package com.tutorialspoint.datastructure;
public class HashTable {
private DataItem[] hashArray;
private int size;
private DataItem dummyItem;
public HashTable(int size){
this.size = size;
hashArray = new DataItem[size];
dummyItem = new DataItem(-1,-1);
}
public void display(){
for(int i=0; i<size; i++) {
if(hashArray[i] != null)
System.out.print(" ("
+hashArray[i].getKey()+","
+hashArray[i].getData() + ") ");
else
System.out.print(" ~~ ");
}
System.out.println("");
}
public int hashCode(int key){
return key % size;
}
public DataItem search(int key){
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=null){
if(hashArray[hashIndex].getKey() == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= size;
}
return null;
}
public void insert(DataItem item){
int key = item.getKey();
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] !=null
&& hashArray[hashIndex].getKey() != -1){
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= size;
}
hashArray[hashIndex] = item;
}
public DataItem delete(DataItem item){
int key = item.getKey();
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=null){
if(hashArray[hashIndex].getKey() == key){
DataItem temp = hashArray[hashIndex];
//assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp;
}
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= size;
}
return null;
}
}
Demo Program
HashTableDemo.java
package com.tutorialspoint.datastructure;
public class HashTableDemo {
public static void main(String[] args){
HashTable hashTable = new HashTable(20);
hashTable.insert(new DataItem(1, 20));
hashTable.insert(new DataItem(2, 70));
hashTable.insert(new DataItem(42, 80));
hashTable.insert(new DataItem(4, 25));
hashTable.insert(new DataItem(12, 44));
hashTable.insert(new DataItem(14, 32));
hashTable.insert(new DataItem(17, 11));
hashTable.insert(new DataItem(13, 78));
hashTable.insert(new DataItem(37, 97));
hashTable.display();
DataItem item = hashTable.search(37);
if(item != null){
System.out.println("Element found: "+ item.getData());
}else{
System.out.println("Element not found");
}
hashTable.delete(item);
item = hashTable.search(37);
if(item != null){
System.out.println("Element found: "+ item.getData());
}else{
System.out.println("Element not found");
}
}
}
如果我们编译并运行上述程序,它将生成以下结果 -
~~ (1,20) (2,70) (42,80) (4,25) ~~ ~~ ~~ ~~ ~~ ~~ ~~ (12,44) (13,78) (14,32) ~~ ~~ (17,11) (37,97) ~~
Element found: 97
Element not found