哈希表数据结构

更新于 2025/10/16 16:21:06

哈希算法
线性探测
基本操作
查找操作
插入操作
删除操作
完整实现

哈希表是一种以关联方式存储数据的数据结构。在哈希表中，数据以数组格式存储，其中每个数据值都有其独特的索引值。如果我们知道所需数据的索引，数据访问速度就会非常快。

因此，它成为一种数据结构，无论数据大小如何，插入和搜索操作都非常快。哈希表使用数组作为存储介质，并使用哈希技术生成要插入或定位元素的索引。

哈希

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

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

Sr.No.	Key	Hash	Array 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

线性探测

正如我们所见，哈希技术可能会被用来创建数组中已使用的索引。在这种情况下，我们可以通过查找下一个单元格来搜索数组中的下一个空位置，直到找到一个空单元格。这种技术称为线性探测。

序号	键	哈希值	数组索引	线性探测后数组索引
1	1	1 % 20 = 1	1	1
2	2	2 % 20 = 2	2	2
3	42	42 % 20 = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 = 17	17	18

基本操作

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

搜索 − 在哈希表中搜索元素。
插入 − 在哈希表中插入元素。
删除 − 从哈希表中删除元素。

数据项

定义一个包含数据和键的数据项，哈希表中将基于该数据项进行搜索。

struct DataItem {
   int data;
   int key;
};

哈希方法

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

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

搜索操作

每当要搜索元素时，计算传入键的哈希码，并使用该哈希码作为数组中的索引来定位元素。如果在计算出的哈希码处未找到该元素，则使用线性探测向前查找该元素。

struct DataItem *search(int key) {
   //获取哈希值
   int hashIndex = hashCode(key);
	
   //移动数组直到空
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //转到下一个单元格
      ++hashIndex;
		
      //环绕表格
      hashIndex %= SIZE;
   }

   return NULL;        
}

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#define SIZE 10 // 定义哈希表的大小
struct DataItem {
    int key;
};
struct DataItem *hashArray[SIZE]; // 将哈希表定义为 DataItem 指针数组
int hashCode(int key) {
    // 根据键返回哈希值
    return key % SIZE;
}
struct DataItem *search(int key) {
    // 获取哈希值
    int hashIndex = hashCode(key);

    // 在数组中移动，直到找到空槽或找到键
    while (hashArray[hashIndex] != NULL) {
        // 如果找到键，则返回相应的 DataItem 指针
        if (hashArray[hashIndex]->key == key)
            return hashArray[hashIndex];

        // 转到下一个单元格
        ++hashIndex;

        // 环绕表格
        hashIndex %= SIZE;
    }
    // 如果未找到键，则返回 NULL
    return NULL;
}

int main() {

    // 使用一些示例 DataItem 初始化哈希表
    struct DataItem item2 = {25}; // 假设键为 25
    struct DataItem item3 = {64}; // 假设键为 64
    struct DataItem item4 = {22}; // 假设键为 22
    
    // 计算每个项的哈希索引并将其放入哈希表中
    
    int hashIndex2 = hashCode(item2.key);
    hashArray[hashIndex2] = &item2;
    
    int hashIndex3 = hashCode(item3.key);
    hashArray[hashIndex3] = &item3;
    
    int hashIndex4 = hashCode(item4.key);
    hashArray[hashIndex4] = &item4;
    
    // 调用搜索函数进行测试
    int keyToSearch = 64; // 要在哈希表中搜索的键
    struct DataItem *result = search(keyToSearch);
    printf("需要搜索的元素： %d", keyToSearch);
    if (result != NULL) {
        printf("
Element found");
    } else {
        printf("
Element not found");
    }

    return 0;
}

输出

需要搜索的元素： 64
Element found

#include <iostream>
#include <unordered_map>
using namespace std;
#define SIZE 10 // 定义哈希表的大小
struct DataItem {
   int key;
};
unordered_map<int, DataItem*> hashMap; // 将哈希表定义为 unordered_map

int hashCode(int key) {
   // 根据键返回哈希值
   return key % SIZE;
}

DataItem* search(int key) {
   // 获取哈希值
   int hashIndex = hashCode(key);
   
   // 在地图中移动，直到找到空槽或找到键
   while (hashMap[hashIndex] != nullptr) {
      // 如果找到键，则返回相应的 DataItem 指针
      if (hashMap[hashIndex]->key == key)
         return hashMap[hashIndex];
      
      // 转到下一个单元格
      ++hashIndex;
      
      // 环绕表格
      hashIndex %= SIZE;
   }
   
   // 如果未找到键，则返回 NULLptr
   return nullptr;
}

int main() {
       
    // 使用一些示例 DataItem 初始化哈希表
    DataItem item2 = {25}; // 假设键为 25
    DataItem item3 = {64}; // 假设键为 64
    DataItem item4 = {22}; // 假设键为 22
    
    // 计算每个项目的哈希索引并将其放入哈希表中
    
    int hashIndex2 = hashCode(item2.key);
    hashMap[hashIndex2] = &item2;
    
    int hashIndex3 = hashCode(item3.key);
    hashMap[hashIndex3] = &item3;
    
    int hashIndex4 = hashCode(item4.key);
    hashMap[hashIndex4] = &item4;
    
    // 调用搜索函数进行测试
    int keyToSearch = 64; // 要在哈希表中搜索的键
   DataItem* result = search(keyToSearch);
   cout<<"需要搜索的元素： "<<keyToSearch;
   if (result != nullptr) {
      cout << "
Element found";
   } else {
      cout << "
Element not found";
   }
   
   return 0;
}

输出

需要搜索的元素： 64
Element found

import java.util.HashMap;
public class Main {
   static final int SIZE = 10; // 定义哈希表的大小
   static class DataItem {
      int key;
   }
   static HashMap<Integer, DataItem> hashMap = new HashMap<>(); // 将哈希表定义为 HashMap
   
   static int hashCode(int key) {
      // 根据键返回哈希值
      return key % SIZE;
   }
   static DataItem search(int key) {
      // 获取哈希值
      int hashIndex = hashCode(key);
      
      // 在地图中移动，直到找到空槽或找到键
      while (hashMap.get(hashIndex) != null) {
         // 如果找到键，则返回相应的 DataItem
         if (hashMap.get(hashIndex).key == key)
            return hashMap.get(hashIndex);
         
         // 转到下一个单元格
         ++hashIndex;
         
         // 环绕表格
         hashIndex %= SIZE;
      }
      
      // 如果未找到键，则返回 NULL
      return null;
   }
public static void main(String[] args) {
    // 使用一些示例 DataItem 初始化哈希表
    
    DataItem item2 = new DataItem();
    item2.key = 25; // 假设键为 25
    
    DataItem item3 = new DataItem();
    item3.key = 64; // 假设键为 64
    DataItem item4 = new DataItem();
    item4.key = 22; // 假设键为 22
    // 计算每个项目的哈希索引并将其放入哈希表中
    
    int hashIndex2 = hashCode(item2.key);
    hashMap.put(hashIndex2, item2);
    
    int hashIndex3 = hashCode(item3.key);
    hashMap.put(hashIndex3, item3);
    
    int hashIndex4 = hashCode(item4.key);
    hashMap.put(hashIndex4, item4);
    
    // 调用搜索函数进行测试
    int keyToSearch = 64; // 哈希表中要搜索的键
   DataItem result = search(keyToSearch);
   System.out.print("需要搜索的元素： " + keyToSearch);
      if (result != null) {
         System.out.println("
Element found");
      } else {
         System.out.println("
Element not found");
      }
   }
}

输出

需要搜索的元素： 64
Element found

SIZE = 10 # 定义哈希表的大小
class DataItem:
    def __init__(self, key):
        self.key = key
hashMap = {} # 将哈希表定义为字典
def hashCode(key):
    # 根据键返回哈希值
    return key % SIZE

def search(key):
    # 获取哈希值
    hashIndex = hashCode(key)

    # 在地图中移动，直到找到空槽或找到键
    while hashIndex in hashMap:
        # 如果找到键，则返回相应的 DataItem
        if hashMap[hashIndex].key == key:
            return hashMap[hashIndex]

        # 转到下一个单元格
        hashIndex = (hashIndex + 1) % SIZE

    # 如果未找到键，则返回 None
    return None
# 使用一些示例 DataItem 初始化哈希表
item2 = DataItem(25) # 假设键为 25
item3 = DataItem(64) # 假设键为 64
item4 = DataItem(22) # 假设键为 22
# 计算每个项的哈希索引并将其放入哈希表中
hashIndex2 = hashCode(item2.key)
hashMap[hashIndex2] = item2

hashIndex3 = hashCode(item3.key)
hashMap[hashIndex3] = item3

hashIndex4 = hashCode(item4.key)
hashMap[hashIndex4] = item4

# 调用搜索函数进行测试
keyToSearch = 64 # 要在哈希表中搜索的键
result = search(keyToSearch)
print("需要搜索的元素： ", keyToSearch)
if result:
    print("Element found")
else:
    print("Element not found")

输出

需要搜索的元素：  64
Element found

插入操作

每当要插入元素时，计算传入键的哈希码，并使用该哈希码作为数组中的索引来定位索引。如果在计算出的哈希码处找到元素，则使用线性探测查找空位置。

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

   //获取哈希值 
   int hashIndex = hashCode(key);

   //在数组中移动，直到出现空单元格或被删除的单元格
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //转到下一个单元格
      ++hashIndex;
		
      //环绕表格
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#define SIZE 4 // 定义哈希表的大小
struct DataItem {
    int key;
};
struct DataItem *hashArray[SIZE]; // 将哈希表定义为 DataItem 指针数组
int hashCode(int key) {
    // 根据键返回哈希值
    return key % SIZE;
}
void insert(int key) {
   // 使用 malloc 创建新的 DataItem
   struct DataItem *newItem = (struct DataItem*)malloc(sizeof(struct DataItem));
   
   if (newItem == NULL) {
      // 检查 malloc 是否分配内存失败
      fprintf(stderr, "Memory allocation error
");
      return;
   }
   
    newItem->key = key;
    // 如有需要，初始化其他数据成员
    
    // 计算键的哈希索引
    int hashIndex = hashCode(key);
    
    // 处理冲突（线性探测）
   while (hashArray[hashIndex] != NULL) {
      //移至下一个单元格
      ++hashIndex;
      // 如果需要的话环绕表格
      hashIndex %= SIZE;
   }
   
   // 将新的 DataItem 插入到计算出的索引处
   hashArray[hashIndex] = newItem;
}
int main() {
    // 使用不同的键调用 insert 函数来填充哈希表
    insert(42); // 插入一个键为 42 的项
    insert(25); // 插入一个键为 25 的项
    insert(64); // 插入一个键为 64 的项
    insert(22); // 插入一个键为 22 的项
    
    // 输出填充后的哈希表
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != NULL) {
         printf("Index %d: Key %d
", i, hashArray[i]->key);
      } else {
         printf("Index %d: Empty
", i);
      }
   }
   
   return 0;
}

输出

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

#include <iostream>
#include <vector>
#define SIZE 4 // 定义哈希表的大小

struct DataItem {
   int key;
};
std::vector<DataItem*> hashArray(SIZE, nullptr); // 将哈希表定义为 DataItem 指针的向量
int hashCode(int key)
{
   // 根据键返回哈希值
   return key % SIZE;
}
void insert(int key)
{
    // 使用 new 创建一个新的 DataItem（动态内存分配）
    DataItem *newItem = new DataItem;
    
    newItem->key = key;
    // 如有需要，初始化其他数据成员
    
    // 计算键的哈希索引
    int hashIndex = hashCode(key);
    
    // 处理冲突（线性探测）
   while (hashArray[hashIndex] != nullptr) {
      //移至下一个单元格
      ++hashIndex;
      // 如果需要的话环绕表格
      hashIndex %= SIZE;
   }
   
   // 将新的 DataItem 插入到计算出的索引处
   hashArray[hashIndex] = newItem;
}

int main()
{
    // 使用不同的键调用 insert 函数来填充哈希表
    
    insert(42); // 插入一个键为 42 的项
    insert(25); // 插入一个键为 25 的项
    insert(64); // 插入一个键为 64 的项
    insert(22); // 插入一个键为 22 的项
    
    // 输出填充后的哈希表
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != nullptr) {
         std::cout << "Index " << i << ": Key " << hashArray[i]->key << std::endl;
      } else {
         std::cout << "Index " << i << ": Empty" << std::endl;
      }
   }
   return 0;
}

输出

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

import java.util.Arrays;
public class Main {
   static final int SIZE = 4; // 定义哈希表的大小
   static class DataItem {
      int key;
   }
   static DataItem[] hashArray = new DataItem[SIZE]; // 将哈希表定义为 DataItem 指针数组
   static int hashCode(int key) {
      // 根据键返回哈希值
      return key % SIZE;
   }
   static void insert(int key) {
      // 创建新的数据项
      DataItem newItem = new DataItem();
      newItem.key = key;
    // 如有需要，初始化其他数据成员
    
    // 计算键的哈希索引
    int hashIndex = hashCode(key);
    
    // 处理冲突（线性探测）
      while (hashArray[hashIndex] != null) {
         //移至下一个单元格
         hashIndex++;
         // 如果需要的话环绕表格
         hashIndex %= SIZE;
      }
      // 将新的 DataItem 插入到计算出的索引处
      hashArray[hashIndex] = newItem;
   }
public static void main(String[] args) {
    // 使用不同的键调用 insert 函数来填充哈希表
    insert(42); // 插入一个键为 42 的元素
    insert(25); // 插入一个键为 25 的元素
    insert(64); // 插入一个键为 64 的元素
    insert(22); // 插入一个键为 22 的元素
    // 输出填充后的哈希表
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != null) {
         System.out.println("Index " + i + ": Key " + hashArray[i].key);
      } else {
         System.out.println("Index " + i + ": Empty");
      }
   }
   }
}

输出

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

SIZE = 4  # 定义哈希表的大小
class DataItem:
    def __init__(self, key):
        self.key = key
hashArray = [None] * SIZE  # 将哈希表定义为 DataItem 指针列表
def hashCode(key):
    # 根据键返回哈希值
    return key % SIZE

def insert(key):
    # 创建新的数据项
    newItem = DataItem(key)
    # 如有需要，初始化其他数据成员
    # 计算键的哈希索引
    hashIndex = hashCode(key)
    # 处理冲突（线性探测）
    while hashArray[hashIndex] is not None:
        # 移至下一个单元格
        hashIndex += 1
        # 如有需要，循环遍历表
        hashIndex %= SIZE

    # 将新的 DataItem 插入到计算出的索引处
    hashArray[hashIndex] = newItem
# 使用不同的键调用插入函数来填充哈希表
insert(42) # 插入键为 42 的项
insert(25) # 插入键为 25 的项
insert(64) # 插入键为 64 的项
insert(22) # 插入键为 22 的项
# 输出填充后的哈希表
for i in range(SIZE):
    if hashArray[i] is not None:
        print(f"Index {i}: Key {hashArray[i].key}")
    else:
        print(f"Index {i}: Empty")

输出

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

删除操作

每当要删除一个元素时，计算传入键的哈希码，并使用该哈希码作为数组中的索引来定位索引。如果在计算出的哈希码处未找到元素，则使用线性探测将元素向前移动。如果找到元素，则在该位置存储一个虚拟项，以保持哈希表的性能。

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

   //获取哈希值 
   int hashIndex = hashCode(key);

   //移动数组直到空
   while(hashArray[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //在已删除的位置分配一个虚拟项
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 		
      //转到下一个单元格
      ++hashIndex;
		
      //环绕表格
      hashIndex %= SIZE;
   }  
   return NULL;        
}

示例

以下是各种编程语言中哈希表删除操作的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5 // 定义哈希表的大小
struct DataItem {
   int key;
};
struct DataItem *hashArray[SIZE]; // 将哈希表定义为 DataItem 指针数组

int hashCode(int key) {
   // 在这里实现你的哈希函数
   // 根据键返回哈希值
}
void insert(int key) {
   // 使用 malloc 创建新的 DataItem
   struct DataItem *newItem = (struct DataItem*)malloc(sizeof(struct DataItem));
   if (newItem == NULL) {
      // 检查 malloc 是否分配内存失败
      fprintf(stderr, "Memory allocation error
");
      return;
   }
   
   newItem->key = key;
    // 如有需要，初始化其他数据成员
    
    // 计算键的哈希索引
    int hashIndex = hashCode(key);
    
    // 处理冲突（线性探测）
   while (hashArray[hashIndex] != NULL) {
      //移至下一个单元格
      ++hashIndex;
      // 如果需要的话环绕表格
      hashIndex %= SIZE;
   }
   
   // 将新的 DataItem 插入到计算出的索引处
   hashArray[hashIndex] = newItem;
   
   // 打印插入项的键和哈希索引
   printf("Inserted key %d at index %d
", newItem->key, hashIndex);
}
void delete(int key) {
   // 在哈希表中查找项目
   int hashIndex = hashCode(key);
   while (hashArray[hashIndex] != NULL) {
      if (hashArray[hashIndex]->key == key) {
         // 将该项目标记为已删除（可选：释放内存）
         free(hashArray[hashIndex]);
         hashArray[hashIndex] = NULL;
         return;
      }
      //移至下一个单元格
      ++hashIndex;
      // 如果需要的话环绕表格
      hashIndex %= SIZE;
   }
   // 如果找不到密钥，则打印一条消息
   printf("Item with key %d not found.
", key);
}
int main() {
    // 使用不同的键调用 insert 函数来填充哈希表
    printf("删除前的哈希表内容：
");
    insert(1); // 插入一个键为 42 的项
    insert(2); // 插入一个键为 25 的项
    insert(3); // 插入一个键为 64 的项
    insert(4); // 插入一个键为 22 的项
    int ele1 = 2;
    int ele2 = 4;
    printf("要删除的键：%d 和 %d", ele1, ele2);
    delete(ele1); // 删除一个键为 42 的项
    delete(ele2); // 删除一个键为 25 的项
    // 打印删除操作后的哈希表内容
   printf("
删除后的哈希表内容：
");
   for (int i = 1; i < SIZE; i++) {
      if (hashArray[i] != NULL) {
         printf("Index %d: Key %d
", i, hashArray[i]->key);
      } else {
         printf("Index %d: Empty
", i);
      }
   }
   return 0;
}

输出

删除前的哈希表内容：
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The key to be deleted: 2 and 4
删除后的哈希表内容：
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

#include <iostream>
using namespace std;
const int SIZE = 5; // 定义哈希表的大小
struct DataItem {
   int key;
};
struct DataItem* hashArray[SIZE]; // 将哈希表定义为 DataItem 指针数组

int hashCode(int key) {
   // 在这里实现你的哈希函数
   // 根据键返回哈希值
   
   // 一个简单的哈希函数（模除）
   return key % SIZE;
}

void insert(int key) {
    // 使用 new 创建新的 DataItem
    struct DataItem* newItem = new DataItem;
    newItem->key = key;
    // 如有需要，初始化其他数据成员
    // 计算键的哈希索引
    int hashIndex = hashCode(key);
    // 处理冲突（线性探测）
    while (hashArray[hashIndex] != nullptr) {
      //移至下一个单元格
      ++hashIndex;
      // 如果需要的话环绕表格
      hashIndex %= SIZE;
   }
   // 将新的 DataItem 插入到计算出的索引处
   hashArray[hashIndex] = newItem;
   // 打印插入项的键和哈希索引
   cout << "Inserted key " << newItem->key << " at index " << hashIndex << endl;
}
void deleteItem(int key) {
   // 在哈希表中查找项目
   int hashIndex = hashCode(key);
   while (hashArray[hashIndex] != nullptr) {
      if (hashArray[hashIndex]->key == key) {
         // 将该项目标记为已删除（可选：释放内存）
         delete hashArray[hashIndex];
         hashArray[hashIndex] = nullptr;
         return;
      }
      //移至下一个单元格
      ++hashIndex;
      // 如果需要的话环绕表格
      hashIndex %= SIZE;
   }
   // 如果找不到密钥，则打印一条消息
   cout << "Item with key " << key << " not found." << endl;
}
int main() {
    // 使用不同的键调用 insert 函数来填充哈希表
    cout<<"删除后的哈希表内容：
";
    insert(1); // 插入一个键为 42 的项目
    insert(2); // 插入一个键为 25 的项目
    insert(3); // 插入一个键为 64 的项目
    insert(4); // 插入一个键为 22 的项目
    int ele1 = 2;
    int ele2 = 4;
    cout<<"要删除的键："<<ele1<<" 和 "<<ele2<<"
";
    deleteItem(2); // 删除一个键为 42 的项目
    deleteItem(4); // 删除一个键为 25 的项目
    cout<<"删除后的哈希表内容：
";
    // 打印删除操作后哈希表的内容
   for (int i = 1; i < SIZE; i++) {
      if (hashArray[i] != nullptr) {
         cout << "Index " << i << ": Key " << hashArray[i]->key << endl;
      } else {
         cout << "Index " << i << ": Empty" << endl;
      }
   }
   return 0;
}

输出

删除前的哈希表内容：
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The key to be deleted: 2 and 4
删除后的哈希表内容：
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

public class Main {
   static final int SIZE = 5; // 定义哈希表的大小
   static class DataItem {
      int key;
      DataItem(int key) {
         this.key = key;
      }
   }
   static DataItem[] hashArray = new DataItem[SIZE]; // 将哈希表定义为 DataItem 对象的数组
   static int hashCode(int key) {
      // 在这里实现你的哈希函数
      // 根据键返回哈希值
      return key % SIZE; // 使用模运算符的简单哈希函数
   }
   static void insert(int key) {
      // 计算键的哈希索引
      int hashIndex = hashCode(key);
      // 处理碰撞（线性探测）
      while (hashArray[hashIndex] != null) {
         //移至下一个单元格
         hashIndex = (hashIndex + 1) % SIZE;
      }
      
      // 将新的 DataItem 插入到计算出的索引处
      hashArray[hashIndex] = new DataItem(key);
      
      // 打印插入项的键和哈希索引
      System.out.println("Inserted key " + key + " at index " + hashIndex);
   }
   static void delete(int key) {
      // 在哈希表中查找项目
      int hashIndex = hashCode(key);
      while (hashArray[hashIndex] != null) {
         if (hashArray[hashIndex].key == key) {
            // 将该项目标记为已删除（可选：释放内存）
            hashArray[hashIndex] = null;
            
            // 打印已删除项目的键和哈希索引
            return;
         }
         //移至下一个单元格
         hashIndex = (hashIndex + 1) % SIZE;
      }
      // 如果找不到密钥，则打印一条消息
      System.out.println("Item with key " + key + " not found.");
   }
public static void main(String[] args) {
    // 使用不同的键调用 insert 函数来填充哈希表
    System.out.println("删除前的哈希表内容： ");
    insert(1); // 插入一个键为 1 的项目
    insert(2); // 插入一个键为 2 的项目
    insert(3); // 插入一个键为 3 的项目
    insert(4); // 插入一个键为 4 的项目
    int ele1 = 2;
    int ele2 = 4;
    System.out.print("要删除的键： " + ele1 + " 和 " + ele2);
    delete(ele1); // 删除一个键为 2 的项目
    delete(ele2); // 删除一个键为 4 的项目
    // 删除操作后打印哈希表的内容
    System.out.println("
删除后的哈希表内容：");
   for (int i = 1; i < SIZE; i++) {
      if (hashArray[i] != null) {
         System.out.println("Index " + i + ": Key " + hashArray[i].key);
      } else {
        System.out.println("Index " + i + ": Empty");
      }
     }
   }
}

输出

删除前的哈希表内容： 
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The keys to be deleted: 2 and 4
删除后的哈希表内容：
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

SIZE = 5  # 定义哈希表的大小

class DataItem:
    def __init__(self, key):
        self.key = key

def hashCode(key):
    # 在这里实现你的哈希函数
    # 根据键返回哈希值
    return key % SIZE

def insert(key):
    global hashArray  # 访问全局 hashArray 变量
    # 计算键的哈希索引
    hashIndex = hashCode(key)

    # 处理碰撞（线性探测）
    while hashArray[hashIndex] is not None:
        #移至下一个单元格
        hashIndex = (hashIndex + 1) % SIZE

    # 将新的 DataItem 插入到计算出的索引处
    hashArray[hashIndex] = DataItem(key)

    # 打印插入项的键和哈希索引
    print(f"Inserted key {key} at index {hashIndex}")

def delete(key):
    global hashArray  # 访问全局 hashArray 变量
    # 在哈希表中查找项目
    hashIndex = hashCode(key)
    while hashArray[hashIndex] is not None:
        if hashArray[hashIndex].key == key:
            # 将该项目标记为已删除（可选：释放内存）
            hashArray[hashIndex] = None
            return
        #移至下一个单元格
        hashIndex = (hashIndex + 1) % SIZE

    # 如果找不到密钥，则打印一条消息
    print(f"Item with key {key} not found.")

# 将哈希表初始化为 None 值列表
hashArray = [None] * SIZE
print("删除前的哈希表内容：")
# 使用不同的键调用 insert 函数来填充哈希表
insert(1) # 插入键为 1 的项目
insert(2) # 插入键为 2 的项目
insert(3) # 插入键为 3 的项目
insert(4) # 插入键为 4 的项目
ele1 = 2
ele2 = 4
print("要删除的键： ", ele1, " 和 ", ele2)
delete(2) # 删除键为 2 的项目
delete(4) # 删除键为 4 的项目

# 删除操作后打印哈希表的内容
print("删除后的哈希表内容：")
for i in range(1, SIZE):
    if hashArray[i] is not None:
        print(f"Index {i}: Key {hashArray[i].key}")
    else:
        print(f"Index {i}: Empty")

输出

删除前的哈希表内容：
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The keys to be deleted:  2  and  4
删除后的哈希表内容：
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

完整实现

以下是上述操作在各种编程语言中的完整实现 −

C C++ Java Python

#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) {
   //获取哈希值 
   int hashIndex = hashCode(key);  
	
   //移动数组直到空
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
			
      //转到下一个单元格
      ++hashIndex;
		
      //环绕表格
      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;

   //获取哈希值 
   int hashIndex = hashCode(key);

   //在数组中移动，直到出现空单元格或被删除的单元格
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //转到下一个单元格
      ++hashIndex;	
      //环绕表格
      hashIndex %= SIZE;
   }
   hashArray[hashIndex] = item;
}
struct DataItem* delete(struct DataItem* item) {
   int key = item->key;
   //获取哈希值 
   int hashIndex = hashCode(key);
   //移动数组直到空
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 		
         //在已删除的位置分配一个虚拟项
         hashArray[hashIndex] = dummyItem; 
         return temp;
      }	
      //转到下一个单元格
      ++hashIndex;
		
      //环绕表格
      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);
   }
	
   printf("
");
}
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);
   printf("Insertion done: 
");
   printf("Contents of Hash Table: ");
   display();
   int ele = 37;
   printf("需要搜索的元素： %d", ele);
   item = search(ele);
   if(item != NULL) {
      printf("
Element found: %d
", item->key);
   } else {
      printf("
Element not found
");
   }
   delete(item);
   printf("删除后的哈希表内容： ");
   display();
}

输出

Insertion done: 
Contents of Hash Table: (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (37,97) 
需要搜索的元素： 37
Element found: 37
删除后的哈希表内容： (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (-1,-1)

#include <iostream>
#include <vector>
using namespace std;
using namespace std;
#define SIZE 20
struct DataItem {
   int data;
   int key;
};
std::vector<DataItem*> hashArray(SIZE, nullptr);
DataItem* dummyItem;
DataItem* item;
int hashCode(int key) {
   return key % SIZE;
}
DataItem* search(int key) {
   //获取哈希值 
   int hashIndex = hashCode(key);
   //移动数组直到空
   while (hashArray[hashIndex] != nullptr) {
      if (hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
         //转到下一个单元格
         //环绕表格
      hashIndex = (hashIndex + 1) % SIZE;
   }
   return nullptr;
}
void insert(int key, int data) {
   DataItem* item = new DataItem;
   item->data = data;
   item->key = key;
    //获取哈希值 
   int hashIndex = hashCode(key);
   //在数组中移动，直到出现空单元格或被删除的单元格
   while (hashArray[hashIndex] != nullptr && hashArray[hashIndex]->key != -1) {
      hashIndex = (hashIndex + 1) % SIZE;
   }
   hashArray[hashIndex] = item;
}
DataItem* deleteItem(DataItem* item) {
   int key = item->key;
   int hashIndex = hashCode(key);
   while (hashArray[hashIndex] != nullptr) {
      if (hashArray[hashIndex]->key == key) {
         DataItem* temp = hashArray[hashIndex];
         hashArray[hashIndex] = dummyItem;
         return temp;
      }
      hashIndex = (hashIndex + 1) % SIZE;
   }
   return nullptr;
}
void display() {
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != nullptr)
         cout << " (" << hashArray[i]->key << "," << hashArray[i]->data << ")";
   }
   cout << std::endl;
}
int main() {
   dummyItem = new 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);
   cout<<"Insertion Done";
   cout<<"
Contents of Hash Table: ";
   display();
   int ele = 37;
   cout<<"需要搜索的元素： "<<ele;
   item = search(ele);
   if (item != nullptr) {
      cout << "
Element found: " << item->key;
   } else {
      cout << "
Element not found" << item->key;
   }
   // Clean up allocated memory
   delete(item);
   cout<<"
删除后的哈希表内容： ";
   display();
}

输出

Insertion Done
Contents of Hash Table:  (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (37,97)
需要搜索的元素： 37
Element found: 37
删除后的哈希表内容：  (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (5,1666768001)

public class HashTableExample {
   static final int SIZE = 20;
   static class DataItem {
      int data;
      int key;
      DataItem(int data, int key) {
         this.data = data;
         this.key = key;
      }
   }
   static DataItem[] hashArray = new DataItem[SIZE];
   static DataItem dummyItem = new DataItem(-1, -1);
   static DataItem item;
   static int hashCode(int key) {
      return key % SIZE;
   }
   static DataItem search(int key) {
      int hashIndex = hashCode(key);
      
      while (hashArray[hashIndex] != null) {
         if (hashArray[hashIndex].key == key)
            return hashArray[hashIndex];
         
         hashIndex = (hashIndex + 1) % SIZE;
      }
      return null;
   }
   static void insert(int key, int data) {
       DataItem item = new DataItem(data, key);
       int hashIndex = hashCode(key);
   
       while (hashArray[hashIndex] != null && hashArray[hashIndex].key != -1) {
           hashIndex = (hashIndex + 1) % SIZE;
       }
       hashArray[hashIndex] = item;
   }
   static DataItem deleteItem(DataItem item) {
      int key = item.key;
      int hashIndex = hashCode(key);
      while (hashArray[hashIndex] != null) {
          if (hashArray[hashIndex].key == key) {
              DataItem temp = hashArray[hashIndex];
              hashArray[hashIndex] = dummyItem;
              return temp;
          }
      
          hashIndex = (hashIndex + 1) % SIZE;
      }
      return null;
   }
   static void display() {
      for (int i = 0; i < SIZE; i++) {
         if (hashArray[i] != null)
            System.out.print(" (" + hashArray[i].key + "," + hashArray[i].data + ")");
      }
      System.out.println();
   }
public static void main(String[] args) {
   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);
   System.out.print("Insertion done");
   System.out.print("
Contents of Hash Table:");
   display();
   int ele = 37;
   System.out.print("需要搜索的元素： " + ele);
   item = search(37);
   
   if (item != null) {
      System.out.println("
Element found: " + item.key);
   } else {
      System.out.println("
Element not found");
   }
   deleteItem(item);
   System.out.print("删除后的哈希表内容：");
   display();
   }
}

输出

Insertion done
Contents of Hash Table: (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (37,97)
需要搜索的元素： 37
Element found: 37
删除后的哈希表内容： (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (-1,-1)

SIZE = 20
class DataItem:
    def __init__(self, data, key):
        self.data = data
        self.key = key
# 使用 None 值初始化哈希数组
hashArray = [None] * SIZE
# 创建一个虚拟项来标记哈希表中已删除的单元格
dummyItem = DataItem(-1, -1)
# 用于保存搜索操作中找到的项的变量
item = None
# 用于计算给定键的哈希索引的哈希函数
def hashCode(key):
    return key % SIZE
# 用于通过键在哈希表中搜索项的函数
def search(key):
    # 使用哈希函数计算哈希索引
    hashIndex = hashCode(key)
    # 遍历数组直到遇到空单元格
    while hashArray[hashIndex] is not None:
        if hashArray[hashIndex].key == key:
            # Item found, return the item
            return hashArray[hashIndex]
        #移动到下一个单元格（线性探测）
        hashIndex = (hashIndex + 1) % SIZE

    # 如果循环终止而未找到该项，则表示该项不存在
    return None
# 将项插入哈希表的函数
def insert(key, data):
    # DataItem 对象的定义
    item = DataItem(data, key)
    # 使用哈希函数计算哈希索引
    hashIndex = hashCode(key)
    # 使用线性探测处理冲突（移动到下一个单元格，直到找到空单元格）
    while hashArray[hashIndex] is not None and hashArray[hashIndex].key != -1:
        hashIndex = (hashIndex + 1) % SIZE
        # 将项插入哈希表中计算出的索引处
    hashArray[hashIndex] = item
    # 从哈希表中删除项的函数
def deleteItem(item):
    key = item.key
    # 使用哈希函数计算哈希索引
    hashIndex = hashCode(key)
    # 遍历数组，直到遇到空单元格或已删除的单元格
    while hashArray[hashIndex] is not None:
        if hashArray[hashIndex].key == key:
            # 找到项目，用 dummyItem 替换该单元格，将其标记为已删除
            temp = hashArray[hashIndex]
            hashArray[hashIndex] = dummyItem
            return temp
        #移动到下一个单元格（线性探测）
        hashIndex = (hashIndex + 1) % SIZE

    # 如果循环终止而未找到该项目，则意味着该项目不存在
    return None
# 显示哈希表的函数
def display():
    for i in range(SIZE):
        if hashArray[i] is not None:
            # 打印当前索引处的项目的键和数据
            print(" ({}, {})".format(hashArray[i].key, hashArray[i].data), end="")
        else:
            # 为空单元格打印 ~~
            print(" ~~ ", end="")
    print()
if __name__ == "__main__":
    # 测试哈希表实现
    # 将一些元素插入哈希表
    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)
	print("Insertion done")
	print("Hash Table contents: ");
    # 显示哈希表
    display()
    display()
    # 搜索具有特定键 (37) 的项目
    item = search(37)
    
    # 检查是否找到该项目并打印结果
    if item is not None:
        print("Element found:", item.data)
    else:
        print("Element not found")

    # 从哈希表中删除键为 37 的项目
    deleteItem(item)
    
    # 删除后再次搜索键为 37 的项目
    item = search(37)
    
    # 检查是否找到该项目并打印结果
    if item is not None:
        print("Element found:", item.data)
    else:
        print("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

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

哈希表数据结构

哈希

线性探测

基本操作

数据项

哈希方法

搜索操作

示例

输出

输出

输出

输出

插入操作

示例

输出

输出

输出

输出

删除操作

示例

输出

输出

输出

输出

完整实现

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！