哈希表(Hash table)
哈希表(Hash table,也叫散列表),是根据关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
哈希函数应具有计算简单,记录分布均匀的特点。
常用的哈希函数:
除留余数法:
哈希冲突:不同的关键字,映射到同一个象,如:
处理冲突的方法:
例如:H(key) = key %11,
关键字:19,01,23,14,55,68,11,82,36,
构造哈希表(表长=11)
地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
关键字 | 01 | 19 | |||||||||
探测次数 | 1 | 1 |
此时H(23) = 23 %11 = 1,地址1处已有关键字01,产生了哈希冲突,如何解决呢?
可采用 :Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),继续判断地址,根据di的取值规则不同,可分为以下几种方法:
开放定址法:(再散列法)
- 线性探测再散列
,即取当前冲突的位置的下一位地址,如何还是冲突,继续取下一位。
地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
关键字 | 55 | 01 | 23 | 14 | 68 | 11 | 82 | 36 | 19 | ||
探测次数 | 1 | 1 | 2 | 1 | 3 | 6 | 2 | 5 | 1 |
平均查找长度 ASL=(1+1+2+1+3+6+2+5+1)/9=2.44
2. 二次探测再散列
,
3. 随机探测再散列
再哈希法:
同时构造多个不同的哈希函数 H1(key)冲突,试用 H2(key), H3(key), …
链地址法:
将所有哈希地址为 的元素构成一个称为同义词链的单链表。并将单链表的头指针存在哈希表的第 个单元中。
因而查找、插入和删除主要在同义词链中进行,链地址法适用于经常进行插入和删除的情况。
如:用链地址法处理冲突的结果如图所示:
0 --> 55 --> 11 1 --> 01 --> 23 2 --> 68 3 --> 14 --> 36 4 5 --> 82 6 7 8 --> 19 9 10
则本例的平均查找长度 ASL=(16+23)/9=1.33
建立公共溢出区:
所有冲突记录存入溢出区。
装填因子:
哈希表的平均查找长度与记录个数 n 不直接相关,而是取决于装填因子和处理冲突的方法。
装填因子:
n 个记录, m 个地址空间。
上一篇: 哈希表hash table
推荐阅读
-
create table 使用select查询语句创建表的方法分享
-
使用表类型(Table Type-SqlServer)实现百万级别的数据一次性毫秒级别插入
-
C#中哈希表(HashTable)用法实例详解(添加/移除/判断/遍历/排序等)
-
Bootstrap Table 双击、单击行获取该行及全表内容
-
Mysql中use表警告:Reading table information for completion of table and column names You can turn off this feature to get a quicker startup with -A
-
Powershell使用嵌套哈希表实例 嵌套哈希表的2种写法例子
-
PowerShell函数用Hash表传参实例
-
oracle drop table(表)数据恢复方法
-
mysql派生表(Derived Table)简单用法实例解析
-
Java 哈希函数 哈希表 动态容量 链地址法 简介+实现