哈希表

哈希表 首页 / 结构和算法入门教程 / 哈希表

哈希表(Hash Table)是一种以关联方式存储数据的数据结构,在哈希表中,数据以数组格式存储,其中每个数据值都有其自己的唯一索引值。如果我们知道所需数据的索引,则数据访问将变得非常快。

因此,它成为一种数据结构,其中插入和搜索操作非常快,而与数据的大小无关。哈希表使用数组作为存储介质,并使用哈希技术生成要在其中插入元素或从中定位元素的索引。

Hashing散列

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

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/hash-data-structure.html

来源:LearnFk无涯教程网

Hash Function
NO Key Value 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

基本操作

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

  • 搜索 - 搜索哈希表中的元素。

  • 插入 - 在哈希表中插入一个元素。

  • 删除 - 从哈希表中删除元素。

数据项

定义具有一些数据和关键字的数据项,基于该数据项和关键字将在哈希表中进行搜索。

struct DataItem{
   int data;
   int key;
};

哈希方法

定义一种哈希方法来计算数据项键的hashCode。

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

搜索操作

每当要搜索元素时,都要计算传递的键的hashCode,并使用该hashCode作为数组中的索引来定位元素。如果在计算的hashCode中找不到元素,请使用线性探测使该元素领先。

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

插入操作

每当要插入元素时,都要计算传递的键的hashCode,并使用该hashCode作为数组中的索引来定位索引。如果在计算出的hashCode中找到了元素,则对空位置使用线性探测。

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

删除操作

每当要删除元素时,都要计算传递的键的hashCode,并使用该hashCode作为数组中的索引来找到索引。如果在计算的hashCode中找不到元素,请使用线性探测使该元素领先。找到后,在其中存储一个虚拟项目以保持哈希表的性能不变。

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语言代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define SIZE 20

struct DataItem {
   int data;   
   int key;
};

struct DataItem* hashArray[SIZE]; 
struct DataItem* dummyItem;
struct DataItem* item;

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

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

void display() {
   int i = 0;
	
   for(i = 0; i<SIZE; i++) {
	
      if(hashArray[i] != NULL)
         printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
      else
         printf(" ~~ ");
   }
	
   printf("\n");
}

int main() {
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1;  
   dummyItem->key = -1; 

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

   display();
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }

   delete(item);
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }
}
 ~~  (1,20)  (2,70)  (42,80)  (4,25)  ~~  ~~  ~~  ~~  ~~  ~~  ~~ (12,44)  (13,78)  (14,32)  ~~  ~~  (17,11)  (37,97)  ~~ 
Element found: 97
Element not found

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

零基础学Python -〔尹会生〕

快速上手Kotlin开发 -〔张涛〕

数据分析实战45讲 -〔陈旸〕

玩转webpack -〔程柳锋〕

Kafka核心技术与实战 -〔胡夕〕

Swift核心技术与实战 -〔张杰〕

分布式金融架构课 -〔任杰〕

玩转Vue 3全家桶 -〔大圣〕

深入浅出可观测性 -〔翁一磊〕

好记忆不如烂笔头。留下您的足迹吧 :)