【数据结构】哈希表—C/C++实现

简介: 【数据结构】哈希表—C/C++实现



1. 哈希表

哈希表类似:

比如python中的字典用到的就是哈希表

2. 基本思路

哈希表(Hash Table),也称为散列表。基本思路是,设存储元素个数为n,设置长度为m(m>=n)的连续内存单元,以每个元素的关键字ki为自变量,通过哈希函数把 k 映射为内存单元的哈希地址h(ki),把该元素存储在此地址。

3. 哈希冲突

哈希冲突是指当两个关键字 ki 和 kj(i≠j)有ki≠kj,但h(ki)=h(kj)。

4. 哈希冲突的解决办法

开放寻址法:当发生哈希冲突时,在哈希表中找一个新的空闲位置存放元素。常见的探测序列包括线性探测法、平方探测法。

       线性探测法:从发生冲突的位置D开始,依次探测D的下一空闲地址(哈希表末尾的下

                             一个地址是表首地址 —mod 实现

      平方探测法:从发生冲突的位置D开始,来回探测D的前后空闲地址

拉链法:每个桶(槽位)都包含一个链表,用于存储所有映射到该桶的键-值对。当发生哈希冲突时,新的键-值对被添加到相应桶的数据结构中,而不会覆盖旧值。

参考链接:哈希讲解

参考链接:哈希讲解


致读者

非知之难,行之为难;非行之难,终之斯难

目录
相关文章
|
27天前
|
算法
数据结构-哈希表(二)
数据结构-哈希表(二)
30 0
|
29天前
|
存储 算法 C++
【C/C++ 数据结构 】无向图和有向图的差异
【C/C++ 数据结构 】无向图和有向图的差异
25 0
|
29天前
|
存储 算法 Serverless
【C/C++ 数据结构】深入探索数据结构中算法复杂度:从C++和数学的视角
【C/C++ 数据结构】深入探索数据结构中算法复杂度:从C++和数学的视角
46 0
|
9天前
|
存储 算法 安全
上机实验四 哈希表设计 西安石油大学数据结构
上机实验四 哈希表设计 西安石油大学数据结构
15 0
|
27天前
|
存储 缓存 Serverless
数据结构-哈希表(一)
哈希表(Hash Table),也称为散列表,是一种常见的数据结构,用于存储键值对。它通过将键映射到一个特定的索引位置来实现高效的数据访问和查找。
23 3
|
29天前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
11 0
|
29天前
|
存储 算法 数据库
【C/C++ 数据结构 】树的 四种表示方法
【C/C++ 数据结构 】树的 四种表示方法
30 0
|
29天前
|
存储 算法 C语言
【C/C++ 数据结构 树】探索C/C++中的二叉树:从理论到实践
【C/C++ 数据结构 树】探索C/C++中的二叉树:从理论到实践
60 0
|
29天前
|
存储 设计模式 算法
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
52 0
|
16天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
29 0