当前课程知识点：数据结构（Data Structures） > 4. Search > 4.7 Search Operation of Hash Table > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
下面我们将学习到
如何实现哈希表中的查找操作
在哈希表中的查找过程
和哈希表中的插入过程是一致的
我们首先要计算哈希值
pos=h（k）
然后我们首先检查一下
在pos这个位置上面
数据元素的关键字
是不是就是我们要查找的k
如果pos位置它是空的
那么也就说明
我们要查找的数据
不在哈希表中
所以就返回查找不成功的结果
如何pos位置不是空的
并且所存储的数据
关键字刚好就是我们要找的k
那么说明
我们查找成功了
返回成功
最后一种情况
就是如果pos位置的关键字不等于k
那么我们在这个时候
还不能够确定关键字k
是否存在哈希表中
我们还需要根据探测函数
到下一个探测的位置上
进行关键字的比较
这里可能需要多次的探测
所以我们定义i为探测的次数
初始化的时候i=1
在第i次探测的时候
探测的位置
是在h（k）的基础上
累加探测函数p（k,i）的值
然后对M进行取模
我们更新pos的位置为探测的位置
这个探测的过程
要持续地进行
直到成功地找到k
或者查找失败
下面我们再来看看
查找函数的具体实现
这个函数有两个参数
一个是我们要查找的关键字k
另外一个是引用参数e用来去记录
查找到的数据元素的值
我们首先来计算一下k的哈希表值
home=h（k）
接下来我们就将home这个位置开始
在哈希表中进行探测
我们定义pos来记录当前探测的位置
初始化的时候
pos的值和home的值
是取同样的值
表示首先探测的位置
是h（k）这个位置
我们还定义了循环变量i
用来去表示探测的次数
初始化的时时候定义为1
在接下来的这个循
环探测的过程中
只要我们当前探测的位置
不是空的
并且当前位置的关键字不等于k
我们就需要继续探测下一个位置
下一个探测的位置的值
是等于哈希值的位置home
再加上p（k，i）的探测函数
然后对M进行取模
而这里的i++语句
实现了探测的次数i+1
整个循环过程中
它跳出的条件有两个
一个是当前探测的位置是空的情况
另外一个就是当前的位置的关键字
是等于k的情况
下面我们针就对这两种情况
分别进行处理
如果循环退出的条件
是由于当前位置的关键字是等于k的
那么也就说明
我们找到了目标关键字
所以我们把当前位置的记录的值
记录在1里面
然后返回true
另外一种情况
就是如果循环退出
是因为当前所检测的位置是空的情况
那么就说明
查找的关键字词它
不存在于哈希表中
查找是失败的
我们要返回false
下面我们来看一个具体的例子
在这个例子中
哈希函数是简单的取模函数
哈希值是等于关键字的个位数
而冲突解决策略是线性探测方法
那么我们在下面将会分析
在哈希表中
查找各个关键字的时候
需要比较关键字的次数是多少
首先我们来看一下
对关键字20的查找
由于20的个位数是0
所以我们首先在0号位置进行查找
结果通过一次关键字比较
就找到了20
我们再来看一下对39的查找
39的哈希值是9
所以我们首先从9号位置开始查找
9号存储的不是39
所以我们将继续探测下一个位置
0号位置
还不是39
所以我们继续探测1号位置
找到了39
整个过程经过了3次关键字的比较
那么其他的关键字的查找过程
也是同样的道理
我们这里就不再一一地详细讲述
但是我们这里到注意到
对关键字8的查找
我们需要比较关键字的次数
达到了5次
所以这也就说明了
不是哈希表就一定能够实现高效的查找
查找的效率
往往还取决于表中数据的密度
以及冲突发生的剧烈程度
我们要保证哈希表的高效率的查找
就必必须把哈希表的冲突率降下来
好的
我们这节课就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
