哈希表基础

2023-12-29 20:45:30

设计意义:

查找性能快,比搜索二叉树更快

二叉树查找速度O(log2N),哈希表一般可以达到O(1)

构建方法:

数组+下标,关键字x通过哈希函数f(x)转换为下标

哈希函数:

根据关键字设计,主要原理是根据数组大小求模运算,数组大小一般为质数

下标冲突问题:

1,链表式解决

写结构体的时候加入next指针

2,开放地址

把下标的位置都对外开放:

a,线性探测法

如果遇到冲突,就往下一个地址寻找空位

新位置=原始位置+i

b,平方探测(二次方探测)

如果遇到冲突,就往(原始位置+i^2)的位置寻找空位。i代表查找的次数

新位置=原始位置+i^2

c,双哈希

在设计第二个哈希函数,如:hash2(key)=R-(key mod R),R要取比数组尺寸小的质数,例如:

R=7,hash2(关键字)=7-(关键字%7),其结果在1-7之间且不会等于0

遇到冲突:新位置=原始位置+i*hash2(关键字)

关于表满:

再次哈希,当哈希表的存储量超过70%,就自动新建一个新的哈希表,新表的尺寸是旧表的两倍以上,选择一个质数,把之前的数据再次通过哈希计算搬到新表里

文章来源:https://blog.csdn.net/2303_76561497/article/details/135297022
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。