雜湊表

雜湊表是一個資料結構，其中插入和搜尋操作都非常快而不管雜湊表的大小。 這幾乎是一個常數或 O(1)。雜湊表使用陣列作為儲存媒介，並使用雜湊技術來生成索引，其中的元素是被插入或查詢。

雜湊

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

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

線性探測

正如我們所看到的，可能要發生的是所使用的雜湊技術來建立已使用陣列的索引。在這種情況下，我們可以直到找到一個空的單元，通過檢視下一個單元搜尋陣列中下一個空的位置。這種技術被稱為線性探測。

基本操作

以下是這是繼雜湊表的主要的基本操作。

• 搜尋 ? 在雜湊表中搜尋一個元素。

• 插入 ? 在雜湊表中插入元素。

• 刪除 ? 刪除雜湊表的元素。

資料項

定義有一些基於鍵的資料資料項，在雜湊表中進行搜尋。

struct DataItem {
   int data;   
   int key;
};

雜湊方法

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

int hashCode(int key){
   return key % SIZE;
}

搜尋操作

當一個元素要被搜尋。通過計算 key 的雜湊碼並定位使用該雜湊碼作為索引陣列的元素。使用線性探測得到元素，如果沒有找到，再計算雜湊程式碼元素繼續向前。

struct DataItem *search(int key){               
   //get the hash 
   int hashIndex = hashCode(key);   
	
   //move in array until an empty 
   while(hashArray[hashIndex] != NULL){
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   return NULL;        
}

插入操作

當一個元素將要插入。通過計算鍵的雜湊程式碼，找到使用雜湊碼作為索引在陣列中的索引。使用線性探測空的位置，如果一個元素在計算雜湊碼被找到。

void insert(int key,int data){
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1){
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

刪除操作

當一個元素要被刪除。計算通過鍵的雜湊程式碼，找到使用雜湊碼作為索引在陣列中的索引。使用線性探測得到的元素，如果沒有找到，再計算雜湊碼的元素向前。當找到，儲存虛擬專案也保持雜湊表完整的效能。

struct DataItem* delete(struct DataItem* item){
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] != NULL){
	
      if(hashArray[hashIndex]->key == key){
         struct 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;        
}

要檢視 C語言的雜湊實現，請點選這裡