哈希表

哈希表是一個數據結構，其中插入和搜索操作都非常快而不管哈希表的大小。 這幾乎是一個常數或 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語言的哈希實現，請點擊這裏