Java版資料結構與演算法 - 散列表

---

---

概述

散列表是一種資料結構，無論散列表的大小如何，其插入和搜尋操作都非常快，接近於常數時間O(1)。散列表使用陣列作為儲存介質，並使用雜湊技術生成元素要插入或從中定位的索引。

雜湊

雜湊是一種將一系列鍵值轉換為陣列索引範圍的技術。我們將使用取模運算子來獲得一系列鍵值。考慮一個大小為20的散列表示例，以及要儲存的以下專案。專案採用(鍵，值)格式。

• (1,20)

• (2,70)

• (42,80)

• (4,25)

• (12,44)

• (14,32)

• (17,11)

• (13,78)

• (37,98)

線性探測

我們可以看到，使用的雜湊技術可能會建立已經使用的陣列索引。在這種情況下，我們可以透過檢視下一個單元格直到找到一個空單元格來搜尋陣列中的下一個空位置。這種技術稱為線性探測。

基本操作

以下是散列表的基本主要操作。

• 搜尋 - 在散列表中搜索元素。

• 插入 - 在散列表中插入元素。

• 刪除 - 從散列表中刪除元素。

資料項

定義一個數據項，它包含一些資料和一個鍵，基於該鍵在散列表中進行搜尋。

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

雜湊方法

定義一個雜湊方法來計算資料項鍵的雜湊碼。

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

散列表實現

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

演示程式

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