哈希表的几种实现方式与比较
版权声明
- 本文原创作者：谷哥的小弟
- 作者博客地址：http://blog.csdn.net/lfdfhl
哈希表概述
哈希表（Hash Table）是一种常用的数据结构，用于实现键值对的映射关系。它通过哈希函数将键映射到一个特定的索引位置，然后在该位置存储相应的值。这样可以实现快速的插入、删除和查找操作，使得哈希表在很多场景下具有高效的性能。
哈希表的主要组成部分和工作原理如下：
-
1、哈希函数（Hash Function）： 这是哈希表的核心。哈希函数接受一个键作为输入，并输出一个固定大小的哈希值。这个哈希值通常是一个整数，它将键映射到哈希表中的一个索引位置。一个好的哈希函数应该尽量避免冲突，即不同的键映射到相同的索引位置。
当我们使用哈希表时，我们首先需要选择一个合适的哈希函数。一个好的哈希函数应该具备以下特点：
确定性： 对于相同的输入，哈希函数应始终产生相同的输出。
高效性： 计算哈希值的过程应该是高效的，不论输入的大小如何。
均匀性： 哈希函数应该尽可能均匀地分布键，以减少冲突的可能性。 -
2、数组（Array）： 哈希表内部通常使用一个数组来存储键值对。每个索引位置对应一个桶（Bucket），每个桶可以存储一个或多个键值对。
-
3、冲突处理： 由于哈希函数的输出空间可能小于键的实际空间，不同的键可能被映射到相同的索引位置，这就是冲突。哈希表需要解决冲突的方法，常见的有两种：链表法（Separate Chaining）： 每个桶使用一个链表来存储具有相同哈希值的键值对。开放地址法（Open Addressing）： 当发生冲突时，线性地探查下一个空闲的桶，或者通过其他探查方法找到下一个可用的位置。
-
4、装载因子（Load Factor）： 为了避免哈希表变得过满，我们引入了装载因子（Load Factor），它是哈希表中已存储键值对的数量与桶的总数之比。当装载因子超过某个阈值时，我们可以选择调整哈希表的大小，例如，通过重新哈希，增加数组的大小，从而减小装载因子。也就是说：装载因子表示哈希表中已存储键值对的数量与桶的总数之比。装载因子越大，冲突可能越多，性能可能下降。为了保持性能，通常需要在装载因子达到某个阈值时，对哈希表进行调整（例如，重新哈希，增加桶的数量）。
-
5、查找、插入和删除： 通过哈希函数计算键的哈希值，找到对应的索引位置，然后执行相应的操作。由于哈希表的平均时间复杂度是常数级别的，这些操作通常非常高效。
总体而言，哈希表是一种强大的数据结构，适用于需要快速查找、插入和删除的场景。在实际应用中，选择合适的哈希函数和解决冲突的方法对于哈希表的性能至关重要。
哈希表常见操作
当使用哈希表时，通常涉及以下几种常见操作：插入（Insertion）、查找（Search）、删除（Deletion）。在哈希表中，通常没有专门的“修改”一说，因为哈希表的设计更加注重于快速的插入、查找和删除操作。这些操作的详细介绍如下：
插入（Insertion）
首先，计算键的哈希值，通过哈希函数找到对应的索引位置。如果该位置上没有其他键值对，直接将键值对存储在该位置；如果发生冲突，根据解决冲突的方法（如链表法或开放地址法），找到下一个可用的位置并存储。
查找（Search）
首先，计算键的哈希值，通过哈希函数找到对应的索引位置。如果该位置上有键值对，则根据解决冲突的方法在链表或探查路径上查找键，找到则返回相应的值；如果没有找到，说明键不存在于哈希表中。
删除（Deletion）
首先，计算键的哈希值，通过哈希函数找到对应的索引位置。如果该位置上有键值对，则根据解决冲突的方法在链表或探查路径上查找键。如果找到，删除该键值对；如果没有找到，说明键不存在于哈希表中。
哈希表常见操作的代码实现
在此，分别用C语言、Java语言、Python语言实现哈希表的插入（Insertion）、查找（Search）、删除（Deletion）。
C语言版
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义哈希表中每个节点的结构
typedef struct Node {
char *key;
int value;
struct Node *next; // 链表用于处理冲突
} Node;
// 定义哈希表的结构
typedef struct HashTable {
int size;
Node **table; // 数组用于存储链表的头节点
} HashTable;
// 哈希函数，简单地使用字符串的ASCII码之和模哈希表的大小
int hash(char *key, int size) {
int sum = 0;
for (int i = 0; key[i] != '\0'; i++) {
sum += key[i];
}
return sum % size;
}
// 初始化哈希表
HashTable *initHashTable(int size) {
HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
hashTable->size = size;
// 为哈希表的每个桶分配内存
hashTable->table = (Node **)malloc(sizeof(Node *) * size);
for (int i = 0; i < size; i++) {
hashTable->table[i] = NULL;
}
return hashTable;
}
// 插入操作
void insert(HashTable *hashTable, char *key, int value) {
// 计算哈希值
int index = hash(key, hashTable->size);
// 创建新节点
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->key = strdup(key); // 复制字符串
newNode->value = value;
newNode->next = NULL;
// 如果该位置为空，直接插入
if (hashTable->table[index] == NULL) {
hashTable->table[index] = newNode;
} else {
// 否则，将新节点插入链表的头部
newNode->next = hashTable->table[index];
hashTable->table[index] = newNode;
}
}
// 查找操作
int search(HashTable *hashTable, char *key) {
// 计算哈希值
int index = hash(key, hashTable->size);
// 在链表中查找键值对
Node *current = hashTable->table[index];
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value; // 找到键，返回对应的值
}
current = current->next;
}
return -1; // 未找到键
}
// 删除操作
void delete(HashTable *hashTable, char *key) {
// 计算哈希值
int index = hash(key, hashTable->size);
// 在链表中查找键值对
Node *current = hashTable->table[index];
Node *prev = NULL;
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
// 找到键，删除节点
if (prev == NULL) {
// 如果是链表的头节点
hashTable->table[index] = current->next;
} else {
prev->next = current->next;
}
// 释放内存
free(current->key);
free(current);
return;
}
prev = current;
current = current->next;
}
}
// 释放哈希表的内存
void destroyHashTable(HashTable *hashTable) {
for (int i = 0; i < hashTable->size; i++) {
Node *current = hashTable->table[i];
while (current != NULL) {
Node *next = current->next;
free(current->key);
free(current);
current = next;
}
}
free(hashTable->table);
free(hashTable);
}
int main() {
// 初始化哈希表
HashTable *hashTable = initHashTable(10);
// 插入键值对
insert(hashTable, "apple", 5);
insert(hashTable, "banana", 8);
insert(hashTable, "orange", 12);
// 查找键值对
printf("Value for 'apple': %d\n", search(hashTable, "apple"));
printf("Value for 'banana': %d\n", search(hashTable, "banana"));
printf("Value for 'orange': %d\n", search(hashTable, "orange"));
printf("Value for 'grape': %d\n", search(hashTable, "grape")); // 不存在的键
// 删除键值对
delete(hashTable, "banana");
// 再次查找键值对
printf("Value for 'banana' after deletion: %d\n", search(hashTable, "banana"));
// 释放哈希表的内存
destroyHashTable(hashTable);
return 0;
}
Java语言版
import java.util.LinkedList;
// 定义哈希表的键值对节点
class HashNode {
String key;
int value;
public HashNode(String key, int value) {
this.key = key;
this.value = value;
}
}
// 定义哈希表
class HashTable {
private static final int DEFAULT_SIZE = 10;
private LinkedList<HashNode>[] table;
public HashTable() {
// 初始化哈希表数组，每个桶用链表存储
table = new LinkedList[DEFAULT_SIZE];
for (int i = 0; i < DEFAULT_SIZE; i++) {
table[i] = new LinkedList<>();
}
}
// 哈希函数，简单地使用字符串的hashCode并取余
private int hash(String key) {
return key.hashCode() % DEFAULT_SIZE;
}
// 插入操作
public void insert(String key, int value) {
int index = hash(key);
LinkedList<HashNode> list = table[index];
// 检查是否已存在相同的键，如果是则更新值
for (HashNode node : list) {
if (node.key.equals(key)) {
node.value = value;
return;
}
}
// 否则，将新键值对加入链表
list.add(new HashNode(key, value));
}
// 查找操作
public int search(String key) {
int index = hash(key);
LinkedList<HashNode> list = table[index];
// 在链表中查找键值对
for (HashNode node : list) {
if (node.key.equals(key)) {
return node.value; // 找到键，返回对应的值
}
}
return -1; // 未找到键
}
// 删除操作
public void delete(String key) {
int index = hash(key);
LinkedList<HashNode> list = table[index];
// 在链表中查找键值对并删除
for (HashNode node : list) {
if (node.key.equals(key)) {
list.remove(node);
return;
}
}
}
}
public class Main {
public static void main(String[] args) {
// 初始化哈希表
HashTable hashTable = new HashTable();
// 插入键值对
hashTable.insert("apple", 5);
hashTable.insert("banana", 8);
hashTable.insert("orange", 12);
// 查找键值对
System.out.println("Value for 'apple': " + hashTable.search("apple"));
System.out.println("Value for 'banana': " + hashTable.search("banana"));
System.out.println("Value for 'orange': " + hashTable.search("orange"));
System.out.println("Value for 'grape': " + hashTable.search("grape")); // 不存在的键
// 删除键值对
hashTable.delete("banana");
// 再次查找键值对
System.out.println("Value for 'banana' after deletion: " + hashTable.search("banana"));
}
}
Python语言版
class HashNode:
def __init__(self, key, value):
self.key = key
self.value = value
class HashTable:
def __init__(self, size=10):
# 初始化哈希表，每个桶用链表存储
self.size = size
self.table = [[] for _ in range(size)]
# 哈希函数，简单地使用字符串的哈希值并取余
def _hash(self, key):
return hash(key) % self.size
# 插入操作
def insert(self, key, value):
index = self._hash(key)
bucket = self.table[index]
# 检查是否已存在相同的键，如果是则更新值
for node in bucket:
if node.key == key:
node.value = value
return
# 否则，将新键值对加入链表
bucket.append(HashNode(key, value))
# 查找操作
def search(self, key):
index = self._hash(key)
bucket = self.table[index]
# 在链表中查找键值对
for node in bucket:
if node.key == key:
return node.value # 找到键，返回对应的值
return -1 # 未找到键
# 删除操作
def delete(self, key):
index = self._hash(key)
bucket = self.table[index]
# 在链表中查找键值对并删除
for node in bucket:
if node.key == key:
bucket.remove(node)
return
if __name__ == "__main__":
# 初始化哈希表
hash_table = HashTable()
# 插入键值对
hash_table.insert("apple", 5)
hash_table.insert("banana", 8)
hash_table.insert("orange", 12)
# 查找键值对
print("Value for 'apple':", hash_table.search("apple"))
print("Value for 'banana':", hash_table.search("banana"))
print("Value for 'orange':", hash_table.search("orange"))
print("Value for 'grape':", hash_table.search("grape")) # 不存在的键
# 删除键值对
hash_table.delete("banana")
# 再次查找键值对
print("Value for 'banana' after deletion:", hash_table.search("banana"))
性能比较与小结
以上使用了三种不同编程语言实现哈希表的插入（Insertion）、查找（Search）、删除（Deletion）的相同点与不同点并分析它们的执行效率。
相同点
-
基本思想相同： 无论是用 C、Java 还是 Python 实现，它们都采用了哈希表这一数据结构，并使用了相似的基本思想，即通过哈希函数将键映射到哈希表中的位置，并处理冲突。
-
处理冲突方式相似： 三种实现都使用了链表法来处理冲突，即在哈希表的每个桶中使用链表来存储相同哈希值的键值对。这是一种简单而常见的冲突解决方式。
-
包含插入、查找、删除操作： 无论使用哪种编程语言，这三种实现都包含了插入、查找和删除这三种基本操作，这是哈希表的核心功能。
不同点
- 语法和代码结构
C 语言使用了显式的内存管理，包括 malloc 和 free，而且数组索引从 0 开始。C 代码通常更接近底层，需要程序员手动管理内存。
Java 使用了面向对象的风格，对内存管理有自动的垃圾回收机制。它的语法结构更加高级，使用了类和面向对象的概念。
Python 具有简洁的语法和动态类型，对于链表的操作更加方便，同时也不需要显式地处理内存。
- 哈希函数实现
C 语言的哈希函数使用了简单的 ASCII 码之和取余的方式。
Java 使用了字符串的 hashCode 方法，并取余哈希表大小。
Python 使用了内置的 hash 函数，并取余哈希表大小。
- 数据结构的表示
C 使用了数组和指针表示哈希表，链表的节点也是手动分配的内存。
Java 使用了类表示哈希表和链表，利用 Java 的面向对象特性。
Python 使用了类似于 Java 的面向对象表示法，但在语法上更为简洁。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！