我要评论手动实现哈希表
哈希表的定义
哈希表的定义：
- 哈希函数：将任意长度的输入（一般是字符串）映射到一个固定长度的输出（一般是整数）上，这个映射函数称为哈希函数。
- 哈希表：是一种数据结构，它以某种方式将键（key）映射到值（value）上。
- 哈希表的特点：
- 哈希表的存储空间是有限的，当元素的数量超过了存储空间时，就会出现哈希冲突。
- 哈希表的查找、插入、删除操作的时间复杂度都为o(1)。
手动实现哈希表
手动实现哈希表的步骤如下：
- 定义哈希表的结构，包括哈希表的大小，以及哈希表的数组。
- 定义哈希函数，将键映射到数组的索引上。
- 定义节点的结构，包括节点的键和值，以及指向下一个节点的指针。
- 定义插入、查找、删除操作。
- 测试哈希表。
下面是实现的代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 手动实现哈希表
// 哈希表长定义
#define hash_size 1000001
// 哈希函数
#define hash(x) ((x) % hash_size)
// 节点的定义
struct node {
int key;
int value;
struct node *next;
};
// 哈希表的结构
struct hashtable {
struct node *table[hash_size];
};
// 创建哈希表
struct hashtable *createhashtable() {
struct hashtable *ht = (struct hashtable *)malloc(sizeof(struct hashtable));
memset(ht->table, 0, sizeof(ht->table));
return ht;
}
// 插入元素
void insert(struct hashtable *ht, int key, int value) {
// 先查找是否存在该元素
int index = hash(key);
// 遍历链表
struct node *p = ht->table[index];
while (p) {
if (p->key == key) {
p->value = value;
return;
}
p = p->next;
}
// 元素不存在，插入到链表头
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->key = key;
newnode->value = value;
newnode->next = ht->table[index];
ht->table[index] = newnode;
}
// 查找元素
int search(struct hashtable *ht, int key) {
int index = hash(key);
struct node *p = ht->table[index];
while (p) {
if (p->key == key) {
return p->value;
}
p = p->next;
}
return -1;
}
// 删除元素
void delete(struct hashtable *ht, int key) {
int index = hash(key);
struct node *p = ht->table[index];
struct node *q = null;
while (p) {
if (p->key == key) {
if (q) {
q->next = p->next;
} else {
ht->table[index] = p->next;
}
free(p);
return;
}
q = p;
p = p->next;
}
}
// 测试代码
int main() {
// 测试哈希表
struct hashtable *ht = createhashtable();
// 插入元素
insert(ht, 1, 10);
insert(ht, 2, 20);
insert(ht, 3, 30);
// 查找元素
printf("%d\n", search(ht, 2)); // 20
// 删除元素
delete(ht, 2);
// 查找元素
printf("%d\n", search(ht, 2)); // -1
return 0;
}
哈希冲突
当多个元素映射到同一个索引时，称为哈希冲突。常见的哈希冲突解决方法有开放寻址法、链表法、再散列法。
开放寻址法
开放寻址法是指当发生哈希冲突时，重新探测一个空闲位置，直到找到一个空闲位置为止。
void insert(struct hashtable *ht, int key, int value) {
int index = hash(key);
int i = 0;
while (ht->table[index] != null) {
// 探测下一个位置
index = (index + i) % hash_size;
i++;
}
// 找到空闲位置
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->key = key;
newnode->value = value;
newnode->next = ht->table[index];
ht->table[index] = newnode;
}
链表法
链表法是指将哈希表的数组元素指向链表，每个链表中存储同一哈希值的所有元素。
struct node {
int key;
int value;
struct node *next;
};
struct hashtable {
struct node **table;
};
void insert(struct hashtable *ht, int key, int value) {
int index = hash(key);
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->key = key;
newnode->value = value;
newnode->next = ht->table[index];
ht->table[index] = newnode;
}
int search(struct hashtable *ht, int key) {
int index = hash(key);
struct node *p = ht->table[index];
while (p) {
if (p->key == key) {
return p->value;
}
p = p->next;
}
return -1;
}
void delete(struct hashtable *ht, int key) {
int index = hash(key);
struct node *p = ht->table[index];
struct node *q = null;
while (p) {
if (p->key == key) {
if (q) {
q->next = p->next;
} else {
ht->table[index] = p->next;
}
free(p);
return;
}
q = p;
p = p->next;
}
}
struct hashtable *createhashtable() {
struct hashtable *ht = (struct hashtable *)malloc(sizeof(struct hashtable));
ht->table = (struct node **)malloc(sizeof(struct node *) * hash_size);
memset(ht->table, 0, sizeof(ht->table));
return ht;
}
再散列法
再散列法是指当发生哈希冲突时，重新计算哈希值，直到找到一个空闲位置为止。
void insert(struct hashtable *ht, int key, int value) {
int index = hash(key);
while (ht->table[index] != null) {
// 重新计算哈希值
key = (key + 1) % hash_size;
index = hash(key);
}
// 找到空闲位置
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->key = key;
newnode->value = value;
newnode->next = ht->table[index];
ht->table[index] = newnode;
}
哈希表的应用
- 字符串查找(涉及到字符串哈希)：字符串查找是哈希表的典型应用。
- 缓存：缓存是哈希表的另一个典型应用。
- 数据库索引：数据库索引也是哈希表的一种应用。
- 哈希函数的设计：哈希函数的设计可以影响哈希表的性能。
- 哈希表的扩展：哈希表的扩展可以实现动态哈希表。
发表评论