当前课程知识点：数据结构（Data Structures） > 4. Search > 4.3 Definition of Hash Table > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
接下来我们将学习到一类
支持快速查找的数据结构 哈希表
哈希表的查找方式比较特别
和我们之前所学习到的
基于关键字比较的方式有所不同
那么有什么特别的地方呢
下面我们来学习一下
我们先来看一下哈希表的相关定义
哈希表的核心是一个哈希函数
Hash Function
或者称为叫散列函数
这个函数先要把一个数据的关键字的值
映射到数组中存放这个数据的位置
如果我们能够定义这样的一种
从关键字到存储地址的映射函数
那么给定任意的关键字
我们就可以通过计算哈希函数的值
直接定位到我们要查找的关键字
这种查找的方式可以用一步到位来形容
和我们之前所学习到的
通过关键字比较来去查找有很大的不同
理想的情况下
这种查找可以在常数时间内完成
为了支持这种快速查找
在插入数据的时候
我们也必须采用类似的步骤
先采用哈希函数
计算出数据的存储的位置
然后再把数据插入到对应的位置上面去
这种基于哈希函数来去定位的数组
称为哈希表或者叫Hash Table
在实际应用中
哈希函数可以有各种不同的形式
一种最为简单的形式就是线性函数
h(k) = k
也就是说把关键字为k的数据
存放到哈希表中第k个位置上面
我们可以看出基于这种简单的哈希函数
哈希表的地址空间范围
和关键字的取值范围是一样大的
这有可能会带来一些空间代价的问题
具体是什么问题呢
下面我们来看一下
在实际的运用中
我们往往会遇到下面这种情况
比如我们有100个记录
每个记录的关键字的取值范围
是从0-16383
如果我们采用的是线性哈希函数 h(k) = k
那么也就意味着
哈希表的地址空间的范围也是从0-16383
也就是说这个哈希表的空间代价
是16000多个存储单元
而这么大的空间
仅仅用来去存放100个记录
空间的利用率非常的低的
由于关键字的取值范围
一般情况下它都会非常的大
更好的解决方案是
哈希函数h(k)要把关键字映射到
一个相对比较小的取值范围
从而可以使用
更小的哈希表来去进行数据的存储
下面我们来介绍一些常用的哈希函数
要定义一个函数
需要满足一些必要的约束条件
首先哈希函数的返回值
必须是落在哈希表的地址范围之内
对于长度为M的哈希表来说
地址范围也是从0-(M - 1)
其次 哈希函数能够把关键字
均匀地映射到哈希表的存储地址上
这样就能够保证
新到来的数据能够均匀地插入到哈希表中
从而尽可能地避免多个数据
被映射到同一个位置上造成冲突
围绕这些基本的约束
下面我们来看一些具体的哈希函数的设计
哈希函数的设计和关键字的类型
有着密切的联系
不同类型的关键字
适用于不同类型的哈希函数
这里我们首先介绍
整数关键字它的哈希函数的设计方法
一种用得比较多的方法是取模法
简单地说
就是将关键字对哈希表的大小M
进行模运算
这样就能够保证哈希函数的返回值
是落在0-(M - 1)的取值范围内的
下面我们来看一个简单的例子
在这个例子中我们可以看到M=16
那么对16进行取模运算
实际上就是返回关键字的低4位的值
返回值只和关键字的
低4比特的数值有关系
而与其它比特位是没有关联的
所以这也导致了所有关键字的取值
恰巧是低位重叠的会比较多
那么这种简单的取模方法
会导致不均匀的映射
这不是我们想要的
我们来看一种改良的方法 平方取中法
这种方法的核心是让哈希函数的返回值
和关键字的所有比特位都相关
具体的方法是我们先对关键字来求平方
然后取出平方结果的中间r个比特
作为返回值
r是取决于哈希表的大小M
对于M=16的情况下r是取4
取出中间4个比特
使得取值范围是落在0-15之间的
在这个例子中我们可以看到
关键字进行平方之后
它的中间4个比特位
是关键字所有比特位参与运算的结果
所以这样可以使得哈希函数的返回值
更加能够均匀地分散在取值范围内
在学习了整数关键字的哈希函数设计之后
下面我们来学习针对字符串关键字
如何去设计哈希函数
一种最为常见的哈希函数就是求和取模法
也就是把字符串中所有的字符累加起来
然后再去对哈希表的大小M取模
比如这个例子中字符串China
我们可以将所有的字母 China进行累加
然后再去对哈希表的大小取模
我们就可以完成这个哈希函数
求和取模的方法是非常简单的
但是有不足的地方
如果我们的关键字 字符串都比较短
比如人名字符串
那么累加起来的结果就会比较小
这样会使得我们哈希函数的返回值
会集中在比较小的区间
这和我们前面所学习到的
哈希函数的设计理念 均匀映射是冲突的
那么一种常见的改进方法是
在UNIX系统中广泛应用的ELF哈希函数
我们这里不去细讲函数的实现
我们主要是通过一个动画
来展示一下函数的主要原理
这个函数为了获得比较大的返回值
它不是通过字符累加来去计算哈希值的
而是通过字符移位
来去实现哈希函数的计算
在这张图中
我们展示的是由8个字符构成的字符串
每个字符我们用不同的色块来去表示
这里我们定义一个key指针
去指向当前需要叠加的这个字符
定义一个h整数
用来记录哈希函数的返回值
首先我们将第一个字符的值
记录在h的低8位
然后当我们要叠加第二个字符的时候
我们先让h向左平移四个比特
然后再将第二个字符
累加到h的低8位上面去
这种平移的方式
可以使得h的值快速增长
每平移一次增长16倍
接下来我们继续平移4个比特
然后继续叠加第3个字符
如此反复
平移 叠加
当数据平移到最高位的时候
h到高4位再折回来和第4位进行叠加
然后再继续平移
通过这种方式
我们可以使得h的值有了较快的增长
在程序的最后
我们再对h进行一个取模操作
就能够实现将关键字
均匀地映射到整个地址空间中去
好了 这节课我们就讲到这里
下节课我们再见
-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
