当前位置：首页 > news >正文

C语言实现哈希查找之线性探测算法

news 2025/8/27 12:23:44

C语言中实现一个简单的哈希表，并包括线性探测和二次探测再散列处理冲突的功能：

1. 定义哈希表结构

首先，定义一个哈希表的结构，包括存储空间、哈希表的大小等。

2. 实现哈希函数

选择一个合适的哈希函数来计算键值的哈希值。

3. 实现插入和查找功能

使用哈希函数计算元素的哈希值，并将元素插入到哈希表中。如果发生冲突，使用线性探测或二次探测再散列来解决。

4. 计算平均查找长度 ASL

平均查找长度（ASL）可以通过模拟多次查找操作并计算平均查找步数来得到。

5. 实现线性探测和二次探测再散列

线性探测在发生冲突时，顺序查找下一个空闲位置。二次探测再散列则是在冲突时，以二次方的偏移量查找空闲位置。

下面是一个使用线性探测再散列处理冲突的C语言哈希表的简单实现：

#include <stdio.h>
#include <stdlib.h>#define TABLE_SIZE 10  // 哈希表的大小typedef struct {int key;int data;
} HashTableItem;// 使用 -1 表示空闲位置
HashTableItem* hashTable[TABLE_SIZE];unsigned int hashFunction(int key) {return key % TABLE_SIZE;
}void initHashTable() {for (int i = 0; i < TABLE_SIZE; i++) {hashTable[i] = NULL;}
}void insert(int key, int data) {unsigned int index = hashFunction(key);unsigned int startIndex = index;HashTableItem *item = (HashTableItem*) malloc(sizeof(HashTableItem));item->data = data;item->key = key;while (hashTable[index] != NULL && hashTable[index]->key != -1) {index = (index + 1) % TABLE_SIZE;// 回到起始位置，表明哈希表已满if (index == startIndex) {printf("哈希表已满\n");return;}}hashTable[index] = item;
}HashTableItem* search(int key) {unsigned int index = hashFunction(key);unsigned int startIndex = index;while (hashTable[index] != NULL) {if (hashTable[index]->key == key) {return hashTable[index];}index = (index + 1) % TABLE_SIZE;// 如果回到起始位置，则表示元素不在哈希表中if (index == startIndex) return NULL;}return NULL;
}void printHashTable() {for (int i = 0; i < TABLE_SIZE; i++) {if (hashTable[i] != NULL && hashTable[i]->key != -1) {printf("位置 %d: Key = %d, Data = %d\n", i, hashTable[i]->key, hashTable[i]->data);} else {printf("位置 %d: 空\n", i);}}
}int main() {initHashTable();insert(1, 10);insert(2, 20);insert(11, 30); // 将与键1发生冲突printHashTable();HashTableItem* item = search(11);if (item != NULL) {printf("找到键 11: Data = %d\n", item->data);} else {printf("未找到键 11\n");}return 0;
}