查找三 哈希表的查找

要点

哈希表和哈希函数

在记录的存储位置和它的关键字之间是建立一个确定的对应关系(映射函数),使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数,根据这个原则建立的表称为哈希表(Hash Table),也叫散列表

以上描述,如果通过数学形式来描述就是:

若查找关键字为 key,则其值存放在 f(key) 的存储位置上。由此,不需比较便可直接取得所查记录

注:哈希查找与线性表查找和树表查找最大的区别在于,不用数值比较。

冲突

若 key1 ≠ key2 ,而 f(key1) = f(key2),这种情况称为冲突(Collision)。

根据哈希函数f(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这一映射过程称为构造哈希表

构造哈希表这个场景就像汽车找停车位,如果车位被人占了,只能找空的地方停。

构造哈希表

由以上内容可知,哈希查找本身其实不费吹灰之力,问题的关键在于如何构造哈希表和处理冲突。

常见的构造哈希表的方法有 5 种:

(1)直接定址法

说白了,就是小学时学过的一元一次方程

即 f(key) = a * key + b。其中,a和b 是常数。

(2)数字分析法

假设关键字是R进制数(如十进制)。并且哈希表中可能出现的关键字都是事先知道的,则可选取关键字的若干数位组成哈希地址。

选取的原则是使得到的哈希地址尽量避免冲突,即所选数位上的数字尽可能是随机的。

(3)平方取中法

取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,仅取其中的几位为地址不一定合适;

而一个数平方后的中间几位数和数的每一位都相关, 由此得到的哈希地址随机性更大。取的位数由表长决定。

(4)除留余数法

取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。

即 f(key) = key % p (p ≤ m)

这是一种最简单、最常用的方法,它不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。

注意:p的选择很重要,如果选的不好,容易产生冲突。根据经验,一般情况下可以选p为素数

(5)随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 f(key) = random(key)。

通常,在关键字长度不等时采用此法构造哈希函数较为恰当。

解决冲突

设计合理的哈希函数可以减少冲突,但不能完全避免冲突。

所以需要有解决冲突的方法,常见有两类

(1)开放定址法

如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。 当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。

例子

若要将一组关键字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。

采用除留余数法构造哈希表;采用开放定址法处理冲突。

不妨设选取的p和m为13,由 f(key) = key % 13 可以得到下表。

需要注意的是,在上图中有两个关键字的探查次数为 2 ,其他都是1。

这个过程是这样的:

a. 12 % 13 结果是12,而它的前面有个 25 ,25 % 13 也是12,存在冲突。

我们使用开放定址法 (12 + 1) % 13 = 0,没有冲突,完成。

b. 35 % 13 结果是 9,而它的前面有个 9,9 % 13也是 9,存在冲突。

我们使用开放定址法 (9 + 1) % 13 = 10,没有冲突,完成。

(2)拉链法

将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。

在这种方法中,哈希表中每个单元存放的不再是记录本身,而是相应同义词单链表的头指针。

例子

如果对开放定址法例子中提到的序列使用拉链法,得到的结果如下图所示:

实现一个哈希表

假设要实现一个哈希表,要求

a. 哈希函数采用除留余数法,即 f(key) = key % p (p ≤ m)

b. 解决冲突采用开放定址法,即 f2(key) = (f(key)+i) % size (p ≤ m)

(1)定义哈希表的数据结构

class HashTable {
 public int key = 0; // 关键字
 public int data = 0; // 数值
 public int count = 0; // 探查次数
}

(2)在哈希表中查找关键字key

根据设定的哈希函数,计算哈希地址。如果出现地址冲突,则按设定的处理冲突的方法寻找下一个地址。

如此反复,直到不冲突为止(查找成功)或某个地址为空(查找失败)。

/**
 * 查找哈希表
 * 构造哈希表采用除留取余法,即f(key) = key mod p (p ≤ size)
 * 解决冲突采用开放定址法,即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
 * ha为哈希表,p为模,size为哈希表大小,key为要查找的关键字
 */
public int searchHashTable(HashTable[] ha, int p, int size, int key) {
 int addr = key % p; // 采用除留取余法找哈希地址

 // 若发生冲突,用开放定址法找下一个哈希地址
 while (ha[addr].key != NULLKEY && ha[addr].key != key) {
        addr = (addr + 1) % size;
    }

 if (ha[addr].key == key) {
 return addr; // 查找成功
    } else {
 return FAILED; // 查找失败
    }
}

(3)删除关键字为key的记录

在采用开放定址法处理冲突的哈希表上执行删除操作,只能在被删记录上做删除标记,而不能真正删除记录。

找到要删除的记录,将关键字置为删除标记DELKEY。

public int deleteHashTable(HashTable[] ha, int p, int size, int key) {
 int addr = 0;
    addr = searchHashTable(ha, p, size, key);
 if (FAILED != addr) { // 找到记录
        ha[addr].key = DELKEY; // 将该位置的关键字置为DELKEY
 return SUCCESS;
    } else {
 return NULLKEY; // 查找不到记录,直接返回NULLKEY
    }
}

(4)插入关键字为key的记录

将待插入的关键字key插入哈希表 先调用查找算法,若在表中找到待插入的关键字,则插入失败; 若在表中找到一个开放地址,则将待插入的结点插入到其中,则插入成功。 

public void insertHashTable(HashTable[] ha, int p, int size, int key) {
 int i = 1;
 int addr = 0;
    addr = key % p; // 通过哈希函数获取哈希地址
 if (ha[addr].key == NULLKEY || ha[addr].key == DELKEY) { // 如果没有冲突,直接插入
        ha[addr].key = key;
        ha[addr].count = 1;
    } else { // 如果有冲突,使用开放定址法处理冲突
 do {
            addr = (addr + 1) % size; // 寻找下一个哈希地址
            i++;
        } while (ha[addr].key != NULLKEY && ha[addr].key != DELKEY);

        ha[addr].key = key;
        ha[addr].count = i;
    }
}

(5)建立哈希表

先将哈希表中各关键字清空,使其地址为开放的,然后调用插入算法将给定的关键字序列依次插入。

public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
 int i = 0;
 
 // 将哈希表中的所有关键字清空
 for (i = 0; i < ha.length; i++) {
        ha[i].key = NULLKEY;
        ha[i].count = 0;
    }

 // 将关键字序列依次插入哈希表中
 for (i = 0; i < list.length; i++) {
 this.insertHashTable(ha, p, size, list[i]);
    }
}

完整代码

哈希查找之JAVA实现

  1 class HashTable {
  2 public int key = 0; // 关键字
  3 public int data = 0; // 数值
  4 public int count = 0; // 探查次数
  5 }
  6 
  7 public class HashSearch {
  8 
  9 private final static int MAXSIZE = 20;
 10 private final static int NULLKEY = 1;
 11 private final static int DELKEY = 2;
 12 private final static int SUCCESS = 0; 
 13 private final static int FAILED = 0xFFFFFFFF;
 14 
 15 /**
 16      * 查找哈希表
 17      * 构造哈希表采用除留取余法,即f(key) = key mod p (p ≤ size)
 18      * 解决冲突采用开放定址法,即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
 19      * ha为哈希表,p为模,size为哈希表大小,key为要查找的关键字
 20  */
 21 public int searchHashTable(HashTable[] ha, int p, int size, int key) {
 22 int addr = key % p; // 采用除留取余法找哈希地址
 23 
 24  // 若发生冲突,用开放定址法找下一个哈希地址
 25 while (ha[addr].key != NULLKEY && ha[addr].key != key) {
 26             addr = (addr + 1) % size;
 27         }
 28 
 29 if (ha[addr].key == key) {
 30 return addr; // 查找成功
 31         } else {
 32 return FAILED; // 查找失败
 33         }
 34     }
 35 
 36 /**
 37      * 删除哈希表中关键字为key的记录
 38      * 找到要删除的记录,将关键字置为删除标记DELKEY
 39  */
 40 public int deleteHashTable(HashTable[] ha, int p, int size, int key) {
 41 int addr = 0;
 42         addr = searchHashTable(ha, p, size, key);
 43 if (FAILED != addr) { // 找到记录
 44             ha[addr].key = DELKEY; // 将该位置的关键字置为DELKEY
 45 return SUCCESS;
 46         } else {
 47 return NULLKEY; // 查找不到记录,直接返回NULLKEY
 48         }
 49     }
 50 
 51 /**
 52      * 将待插入的关键字key插入哈希表
 53      * 先调用查找算法,若在表中找到待插入的关键字,则插入失败;
 54      * 若在表中找到一个开放地址,则将待插入的结点插入到其中,则插入成功。
 55  */
 56 public void insertHashTable(HashTable[] ha, int p, int size, int key) {
 57 int i = 1;
 58 int addr = 0;
 59         addr = key % p; // 通过哈希函数获取哈希地址
 60 if (ha[addr].key == NULLKEY || ha[addr].key == DELKEY) { // 如果没有冲突,直接插入
 61             ha[addr].key = key;
 62             ha[addr].count = 1;
 63         } else { // 如果有冲突,使用开放定址法处理冲突
 64 do {
 65                 addr = (addr + 1) % size; // 寻找下一个哈希地址
 66                 i++;
 67             } while (ha[addr].key != NULLKEY && ha[addr].key != DELKEY);
 68 
 69             ha[addr].key = key;
 70             ha[addr].count = i;
 71         }
 72     }
 73 
 74 /**
 75      * 创建哈希表
 76      * 先将哈希表中各关键字清空,使其地址为开放的,然后调用插入算法将给定的关键字序列依次插入。
 77  */
 78 public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
 79 int i = 0;
 80 
 81 // 将哈希表中的所有关键字清空
 82 for (i = 0; i < ha.length; i++) {
 83             ha[i].key = NULLKEY;
 84             ha[i].count = 0;
 85         }
 86 
 87 // 将关键字序列依次插入哈希表中
 88 for (i = 0; i < list.length; i++) {
 89 this.insertHashTable(ha, p, size, list[i]);
 90         }
 91     }
 92 
 93 /**
 94      * 输出哈希表
 95  */
 96 public void displayHashTable(HashTable[] ha) {
 97 int i = 0;
 98         System.out.format("pos:\t", "pos");
 99 for (i = 0; i < ha.length; i++) {
100             System.out.format("%4d", i);
101         }
102         System.out.println();
103 
104         System.out.format("key:\t");
105 for (i = 0; i < ha.length; i++) {
106 if (ha[i].key != NULLKEY) {
107                 System.out.format("%4d", ha[i].key);
108             } else {
109                 System.out.format("    ");
110             }
111         }
112         System.out.println();
113 
114         System.out.format("count:\t");
115 for (i = 0; i < ha.length; i++) {
116 if (0 != ha[i].count) {
117                 System.out.format("%4d", ha[i].count);
118             } else {
119                 System.out.format("    ");
120             }
121         }
122         System.out.println();
123     }
124 
125 public static void main(String[] args) {
126 int[] list = { 3, 112, 245, 27, 44, 19, 76, 29, 90 };
127         HashTable[] ha = new HashTable[MAXSIZE];
128 for (int i = 0; i < ha.length; i++) {
129             ha[i] = new HashTable();
130         }
131 
132         HashSearch search = new HashSearch();
133         search.createHashTable(ha, list, 19, MAXSIZE);
134         search.displayHashTable(ha);
135 
136     }
137 
138 }

参考资料 《数据结构习题与解析》(B级第3版)

相关阅读 欢迎阅读 程序员的内功——算法 系列

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 子集题目代码

683
来自专栏电光石火

java判断list为空

if(null == list || list.size() ==0 ){ }

1768
来自专栏软件开发 -- 分享 互助 成长

C++ STL 中erase()的使用需要小心

C++ STL极大的方便了用户编写程序,但是同时一不小心也会犯一些错误,如erase()造成迭代器失效经常会引起错误。 错误示例: std::lis...

19110
来自专栏决胜机器学习

PHP数据结构(二十四) ——堆排序

PHP数据结构(二十四)——堆排序 (原创内容,转载请注明来源,谢谢) 一、定义 堆排序也属于一种选择排序,效率较高且空间占用相对较少。 堆的定义:n个元...

3529
来自专栏拭心的安卓进阶之路

Java 集合深入理解(9):Queue 队列

今天心情不太好,来学一下 List 吧! 什么是队列 队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我...

1818
来自专栏分布式系统进阶

Librdkafka的基础数据结构 1 --- 队列

两个元素: tqh_first: 指向队列的第一个成员; tqh_last: 存的是队列里的最后一个元素的 next指针的变量地址, 这个二级指针太有用了,...

592
来自专栏codingforever

经典算法巡礼(一) -- 排序之冒泡排序

事实上,她重复地遍历需要排序的元素,一次比较相邻的两个元素,如果不满足预先定义的比较条件,则交换;否则继续下一组元素比较,直至遍历完成需要排序的所有元素。当然,...

222
来自专栏猿人谷

(重点)链式栈

顺序栈的实现在于使用了数组这个基本数据结构,数组中的元素在内存中的存储位置是连续的,且编译器要求我们在编译期就要确定数组的大小,这样对内存的使用效率并不高,一来...

1849
来自专栏计算机视觉与深度学习基础

Leetcode 127 Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the...

19210
来自专栏专知

关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3 题目 Rotate an array of n elements to...

3488

扫码关注云+社区