Dsa Using Java 简明教程

DSA using Java - Hash Table

Overview

哈希表是一种数据结构，其中插入和搜索操作非常快，与哈希表的大小无关。它几乎是常量或 O(1)。哈希表使用数组作为存储介质，并使用哈希技术来生成元素被插入或被定位到的索引。

HashTable is a datastructure in which insertion and search operations are very fast irrespective of size of the hashtable. It is nearly a constant or O(1). Hash Table uses array as a storage medium and uses hash technique to generate index where an element is to be inserted or to be located from.

Hashing

哈希是一种将一系列键值转换为一系列数组索引的技术。我们将使用模运算符来获得一系列键值。考虑一个大小为 20 的哈希表示例，以下项目需要存储。项目采用 (key,value) 格式。

Hashing is a technique to convert a range of key values into a range of indexes of an array. We’re going to use modulo operator to get a range of key values. Consider an example of hashtable of size 20, and following items are to be stored. Item are in (key,value) format.

(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

我们可以看到，可能发生使用哈希技术创建的索引已经是数组的已用索引。在这种情况下，我们可以通过查看下一个单元格来搜索数组中的下一个空闲位置，直到我们找到一个空闲单元格。这种技术称为线性探查。

As we can see, it may happen that the hashing technique used create already used index of the array. In such case, we can search the next empty location in the array by looking into the next cell until we found an empty cell. This technique is called linear probing.

Sr.No.	Key	Hash	Array Index	After Linear Probing, 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

Basic Operations

以下是哈希表的基本主要操作。

Following are basic primary operations of a hashtable which are following.

Search − search an element in a hashtable.
Insert − insert an element in a hashtable.
delete − delete an element from a hashtable.

DataItem

定义一个具有某些数据和键的数据项，根据该键在哈希表中进行搜索。

Define a data item having some data, and key based on which search is to be conducted in hashtable.

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;
   }
}

Hash Method

定义一种哈希方法，用于计算数据项键的哈希代码。

Define a hashing method to compute the hash code of the key of the data item.

public int hashCode(int key){
   return key % size;
}

Search Operation

每当要搜索元素时。计算已传递键的哈希代码，并使用该哈希代码作为数组中的索引来定位该元素。如果在计算的哈希代码中没有找到元素，请使用线性探测获得元素。

Whenever an element is to be searched. Compute the hash code of the key passed and locate the element using that hashcode as index in the array. Use linear probing to get element ahead if element not found at computed hash code.

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

每当要插入元素时。计算已传递键的哈希代码，并使用该哈希代码作为数组中的索引来定位该索引。如果在计算的哈希代码中找到了某个元素，请对空位置使用线性探测。

Whenever an element is to be inserted. Compute the hash code of the key passed and locate the index using that hashcode as index in the array. Use linear probing for empty location if an element is found at computed hash code.

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

每当要删除元素时。计算已传递键的哈希代码，并使用该哈希代码作为数组中的索引来定位该索引。如果在计算的哈希代码中找不到元素，请使用线性探测获得元素。找到后，在那里存储一个虚拟项来保持哈希表的完整性能。

Whenever an element is to be deleted. Compute the hash code of the key passed and locate the index using that hashcode as index in the array. Use linear probing to get element ahead if an element is not found at computed hash code. When found, store a dummy item there to keep performance of hashtable intact.

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");
      }
   }
}

如果我们编译并运行上述程序，它将生成以下结果 -

If we compile and run the above program then it would produce following result −

 ~~  (1,20)  (2,70)  (42,80)  (4,25)  ~~  ~~  ~~  ~~  ~~  ~~  ~~ (12,44)  (13,78)  (14,32)  ~~  ~~  (17,11)  (37,97)  ~~
Element found: 97
Element not found