哈希表的几种实现方式与比较

news/2025/2/9 6:50:10/

版权声明

  • 本文原创作者：谷哥的小弟
  • 作者博客地址：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 = keyself.value = valueclass HashTable:def __init__(self, size=10):# 初始化哈希表，每个桶用链表存储self.size = sizeself.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 = valuereturn# 否则，将新键值对加入链表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)returnif __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 的面向对象表示法，但在语法上更为简洁。


http://www.ppmy.cn/news/1263962.html

相关文章

普冉（PUYA）单片机开发笔记(8): ADC-DMA多路采样

普冉（PUYA）单片机开发笔记(8): ADC-DMA多路采样

概述 上一个实验完成了基于轮询的多路 ADC 采样&#xff0c;现在尝试跑一下使用 DMA 的 ADC 多路采样。厂家例程中有使用 DMA 完成单路采样的&#xff0c;根据这个例程提供的模板&#xff0c;再加上在 STM32 开发同样功能的基础&#xff0c;摸索着尝试。 经过多次修改和测试&…
阅读更多...
二维码智慧门牌管理系统升级：社区关怀

二维码智慧门牌管理系统升级：社区关怀

文章目录 前言一、系统的工作原理二、系统功能与关怀服务三、社区关怀的意义 前言 随着科技的发展&#xff0c;生活日益智能化&#xff0c;门牌系统也随之发展。近日&#xff0c;一种新型的二维码智慧门牌管理系统正在崛起&#xff0c;以创新的方式将社区关怀融入到每一个家庭…
阅读更多...
【词云图】从excel和从txt文件，绘制以句子、词为单位的词云图

【词云图】从excel和从txt文件，绘制以句子、词为单位的词云图

从excel和从txt文件&#xff0c;绘制以句子、词为单位的词云图 写在最前面数据说明&结论 从txt文件&#xff0c;绘制以句子、词为单位的词云图自我介绍 从excel&#xff0c;绘制以句子、词为单位的词云图读取excel绘制以句子、词为单位的词云图文章标题 写在最前面 经常绘…
阅读更多...
P5 Linux 标准C库函数

P5 Linux 标准C库函数

目录 前言 01 标准输入、标准输出和标准错误 02 打开文件 fopen() 03 新建文件的权限 04 fclose()关闭文件 05 读文件和写文件 06 库函数 fseek 定位 6.1 lseek的使用 07 ftell()函数 前言 &#x1f3ac; 个人主页&#xff1a;ChenPi &#x1f43b;推荐专栏1: 《C_Chen…
阅读更多...
git标签的管理与思考

git标签的管理与思考

git 标签管理 git 如何打标签呢&#xff1f; 标签是什么? 标签 相当于一个 版本管理的一个贴纸&#xff0c;随时 可以通过标签 切换到 这个版本的状态 &#xff0c; 有人可能有疑问 git commit 就可以知道 代码的改动了&#xff0c; 为啥还需要标签来管理呢&#xff1f; …
阅读更多...
OpenHarmony北向-让更广泛的应用开发者更容易参与

OpenHarmony北向-让更广泛的应用开发者更容易参与

一、标准系统的体验 按照官方文档指导&#xff0c;这样操作&#xff0c;OH标准系统开发板就可以运行开发者开发的OpenHarmony应用了。 二、实际情况 按照开发文档上的说明&#xff0c;肯定是装不上的。因为OH不同的发行版&#xff0c;不同发行板不同的设备&#xff0c;IDE&…
阅读更多...
记录 | 报错：libssl-dev : 依赖: libssl3 (= 3.0.8-1ubuntu1.1) 但是 3.0.8-1ubuntu1.2 正要被安装

记录 | 报错：libssl-dev : 依赖: libssl3 (= 3.0.8-1ubuntu1.1) 但是 3.0.8-1ubuntu1.2 正要被安装

ubuntu 上安装 libssl-dev 失败的报错解决 报错&#xff1a; 下列软件包有未满足的依赖关系&#xff1a; libssl-dev : 依赖: libssl3 ( 3.0.8-1ubuntu1.1) 但是 3.0.8-1ubuntu1.2 正要被安装 E: 无法修正错误&#xff0c;因为您要求某些软件包保持现状&#xff0c;就是它们破…
阅读更多...
超完整的mysql安装配置方法（包含idea和navicat连接mysql,并实现建表）

超完整的mysql安装配置方法（包含idea和navicat连接mysql,并实现建表）

mysql安装配置方法 1、下载mysql2、解压到指定的安装目录3、配置初始化文件my.ini4、配置用户变量和系统变量5、初始化mysql6、安装mysql服务并启动修改密码7、使用idea连接mysql8、使用Navicat可视化工具连接mysql&#xff0c;并实现新建数据库&#xff0c;新建表 1、下载mysq…
阅读更多...
最新文章

Copyright @ 2022~2023