哈希表初识

骑猪看日落 2022-05-13 04:28 189阅读 0赞

转载自：[https://www.cnblogs.com/lchzls/p/6714079.html][https_www.cnblogs.com_lchzls_p_6714079.html]

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。

哈希表简单的理解：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。

举例：

哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条...

![70][]

上面这张表即哈希表。

如果将来要查李秋梅的[成绩][Link 1]，可以用上述方法求出该记录所在位置：

李秋梅:lqm 12+17+13=42 取表中第42条记录即可。

问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？

这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。

# 哈希表算法-处理冲突的方法 #

如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：

1.再哈希法

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

虽然能够采用一些办法去减少冲突，但是冲突是无法完全避免的。因此需要根据实际情况选取解决冲突的办法。

2 .开放定址法

3.链地址法

# **哈希表算法-哈希表的构造方法** #

１、直接定址法

例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。

但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数

![521127-20170415131806033-970865841.png][]

２、数字分析法

有学生的生日数据如下：

年.月.日

75.10.03  
75.11.23  
76.03.02  
76.07.12  
75.04.21  
76.02.15  
...

经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。

3.平方取中法

对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列\{421，423，436\}，平方之后的结果为\{177241，178929，190096\}，那么可以取\{72，89，00\}作为Hash地址。

# **Hash表大小的确定** #

Hash表大小的确定也非常关键，如果Hash表的空间远远大于最后实际存储的记录个数，则造成了很大的空间浪费，如果选取小了的话，则容易造成冲突。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址。

[https_www.cnblogs.com_lchzls_p_6714079.html]: https://www.cnblogs.com/lchzls/p/6714079.html
[70]: /images/20220513/1233c0b54cb74d47823a0a163afb11d6.png
[Link 1]: http://www.hudong.com/wiki/%E6%88%90%E7%BB%A9
[521127-20170415131806033-970865841.png]: /images/20220513/eeee115f010e4a499d0c38753a1cf9ec.png

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关哈希值哈希表_哈希杰森

哈希值哈希表我最近写了一个[简单的库，可预测地对json进行哈希处理][json] 。该实用程序基于出色的[Jackson Json解析库][Jackson Json

阳光穿透心脏的1/2处/ 2023年02月25日 04:56/ 0 赞/ 50 阅读

相关哈希表

哈希表概念哈希函数设计冲突调节负载因子冲突解决闭散列开散列/哈希桶实现自己的哈希表：

谁践踏了优雅/ 2023年01月13日 04:14/ 0 赞/ 47 阅读

相关哈希表

![Center][] [Center]: /images/20220731/1379dbdc6efb4a42a0b011f0b3aa4455.png

「爱情、让人受尽委屈。」/ 2022年08月14日 04:56/ 0 赞/ 228 阅读

相关哈希表

什么是哈希表哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的[数据结构][Link 1]。也就是说，它通过把关键码

悠悠/ 2022年07月15日 12:14/ 0 赞/ 247 阅读

相关哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速

系统管理员/ 2022年06月10日 01:26/ 0 赞/ 304 阅读

相关哈希表

我们知道，通过对数组进行直接寻址（Direct Addressing），可以在 O(1) 时间内访问数组中的任意元素。所以，如果存储空间允许，可以提供一个数组，为每个可能的关键

快来打我*/ 2022年06月05日 02:20/ 0 赞/ 412 阅读

相关哈希表初识

转载自：[https://www.cnblogs.com/lchzls/p/6714079.html][https_www.cnblogs.com_lchzls_p_67140

骑猪看日落/ 2022年05月13日 04:28/ 0 赞/ 190 阅读

相关数据结构与算法系列--哈希表初识

哈希表用的是数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，没有数组，就没有哈希表。那么，数组与哈希表有什么不同呢

电玩女神/ 2022年02月22日 20:50/ 0 赞/ 268 阅读

相关哈希表

一、简介如果所有的键都是小整数，那么我们可以用一个数组来实现无序的符号表，将键作为数组的索引i而数组中i（键）处储存的就是对应的值。这样就可以快速地访问任意键的值，

旧城等待，/ 2021年12月22日 01:21/ 0 赞/ 454 阅读

相关哈希表

【一】哈希表 > 他通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数就是散列函数。 ![watermark_type_ZmFuZ3poZW5na

傷城~/ 2021年08月11日 17:13/ 0 赞/ 609 阅读