散列表的查找

た入场券 2023-02-28 05:24 134阅读 0赞

对给定的关键字key，用一个函数H(key)计算出元素地址，由此而得散列表（Hash表，哈希表），其中函数H(key)称为散列函数

此函数值称为散列地址。

然而，在实际应用中，会出现这样的情况：

k1≠k2，但H(k1)=H(k2) ，

称这种现象为冲突现象，k1,k2为同义词。

针对冲突——如何解决冲突呢？

构造好的散列函数，以免冲突

由于冲突不可避免，因此，确切地说是减少冲突 & 妥善处理冲突

--------------------

# 构造散列函数的基本方法 #

**直接定址法**：H(k)= k 或者 H(k)= ak+b （a，b为任意正整数）

**除留余数法**：H(k)= k % p 其中p≤m,m为数组规模的最大质数。

**平方取中法：**  例：325在平方后取105625中间两位，即56作为它的散列地址。

![20200720143250937.png][]

**折叠法：**

如 身份证号码：340104198805061532

先进行分组：340 104 198 805 061 532

![20200720143424479.png][]

**数值分析法**

![20200720143452263.png][]

--------------------

处理冲突：

开放地址法   Hi(k)=(H(k) + di ) % m，i=1,2,…,q  q<=m

线性探测法：Hi(k)=(H(k)+i)%m，m为表的规模最大质数

二次探测法        Hi(k) = ( H(k) + i2 ) % m

伪随机数

拉链法

再散列法      →H(k)→H1(k)→H2(k)→ …… →Hi(k)

--------------------

例：设散列表地址范围为0—9，散列函数H(K)=K%7，采用**线性探测法**处理冲突，将下列数据依次插入下表中：

23,34,56,12,8,14,35,25

![20200720144007266.png][]

ASL=(1+1+1+4+5+1+1+4)/8=18/8

用此法来构造散列表可能会造成数据***堆积*****。**

装填因子——元素占空间的比例，一般建议在0.7-0.85之间

--------------------

拉链法（链表法）——将同义词构成一个链表

**例**：散列函数H(K)=K%7，采用拉链法将下列数据依次插入下表中    23，34，56，12，8，14，35，25

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

ASL=(1\*6+2\*1+3\*1)/8 =11/8

--------------------

在散列表中查找元素的过程和构造的过程基本一致：    对给定关键字k，由散列函数H计算出该元素的地址H(k)。

若表中该位置为空，则查找失败。

否则，比较关键字，若相等，查找成功，否则根据构造表时所采用的处理方法找下一个地址，直至找到关键字等于k的元素（成功）或者找到空位置（失败）为止。

一般在用链地址法构造的表中进行查找，比在用线性探测法构造的表中进行查找，查找长度要小。

[20200720143250937.png]: /images/20230209/6a3834ee5c7c47278cd9d84eb269ebad.png
[20200720143424479.png]: /images/20230209/d9594677237b443982620891bb3c64be.png
[20200720143452263.png]: /images/20230209/53de95d9731d4b3581d1b71be6b3e527.png
[20200720144007266.png]: /images/20230209/b20c30652a514306a97a60006afb6626.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20230209/6f3ea31d9caa4815ac10fe3b589523a1.png