哈希表

哈希表是一个数据结构，其中插入和搜索操作都非常快而不管哈希表的大小。 这几乎是一个常数或 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语言的哈希实现，请点击这里