您现在的位置是：首页 >技术交流 >初识哈希表网站首页技术交流

初识哈希表

杰信步迈入C++之路 2024-08-31 12:01:03
简介初识哈希表

哈希表

1.引入

在这里插入图片描述

2.哈希思想

在这里插入图片描述
在这里插入图片描述
哈希既是一种查找技术，也是一种存储技术。
哈希只是通过记录的关键字定位该记录，哈希表没有表达记录之间的逻辑关系。所以，哈希主要是面向查找的存储结构。

  • 不适用于：
    ⁻ 范围查找
    ⁻ 多个记录有相同关键字

【冲突】
在这里插入图片描述

3.哈希技术的三个关键问题

  • 哈希表容量的设计
    保证n个记录能够存进去，又使得存储空间尽可能少

  • 哈希函数的设计
    如何设计一个运算过程简单、运算结果均匀的哈希函数

  • 冲突的处理方法
    如何采取合适的处理冲突方法来解决冲突

3.1 哈希表容量的设计

在这里插入图片描述

3.2 哈希技术关键之二：哈希函数

在这里插入图片描述

哈希函数构造方法

在这里插入图片描述
在这里插入图片描述

哈希函数示例：线性函数

在这里插入图片描述

哈希函数示例：除留余数法

在这里插入图片描述

3.3 哈希技术关键之三:解决冲突策略

在这里插入图片描述

开放定址法

在这里插入图片描述

开放定址法——线性探测法(Linear Probing)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

ASL的成功与不成功计算法
在这里插入图片描述

在这里插入图片描述

用线性探测法创建哈希表的查找算法

在这里插入图片描述

用线性探测法创建哈希表的插入算法

在这里插入图片描述

开放定址法——平方探测法(Quadratic Probing)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在平方探测法构造的哈希表中进行查找的算法

在这里插入图片描述

在二次探测法构造的哈希表中进行插入操作的算法

在这里插入图片描述
在这里插入图片描述

拉链法（链地址法）

在这里插入图片描述
在这里插入图片描述

在拉链法构造的哈希表中查找并插入的算法

在这里插入图片描述

解决方法的比较

在这里插入图片描述

4. 哈希查找的性能分析

在这里插入图片描述
在这里插入图片描述

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐