散列表(一).散列表基本内容介绍 你的名字 2021-01-10 15:37 822阅读 0赞 一说到散列表，大家脑子想到的词就是：Hashmap、key-value、查找速度快、增删速度快等等。确实，在我们平常的学习生活中，散列表是很常见、也是用的很多的数据结构。那么散列表是怎样设计出来的，为什么它既可以和数组一样查询快，又可以和链表一样快增删，本节让我们一起了解一下什么是散列表、什么是散列函数、它究竟是如何设计出来的。 **散列思想** 什么是散列思想呢？散列表还有一个英文名叫做Hashtable，也叫做“哈希表”、“hash表”，hash我们都了解，是同过一定的算法、hash算法得到一个对象的散列值，用来标识对象本身的算法。 我们来举一个例子，假如有50个同学参加数学竞赛，为了能快速方便地找到每一个人，所以每个人都设立一个编号，从1到50，代表50个学生。现在如果我们用代码去实现这一功能的话，我们可以将这50个学生放到数组中去，从数组下标为1的位置开始，放入编号为1的学生，以此类推，将学生的编号和数组的下标一一对应，当我们要找第32个学生的时候，直接arr\[32\]就可以找到这个学生了，这样，就达成了O(1)的时间复杂度。实际上，这个例子已经用到了散列思想，能够快速地找到我们想找的学生，如果你觉得不够明显的话我们可以稍加改造一下。 假如，老师说编号这样太简单了，无法明显地表面这个学生的信息，需要再加上年级、班级这些信息，变成了6位数字，比如020433，02代表大二年级、04是4班，后两位还是之前的编号，这样我们如何存储学生的编号才能很快地找到对应的学生。 思路还是那个思路，尽管6位数字作为数组的下标过长，我们可以截取编号的后两位，来作为数组的下标，去读取我们需要的数据。 这就是典型的散列思想，这里参赛选手的编号我们称作**键（key）**，用来标识学生，学生本身这个对象我们称为**值**（value）。我们把参赛编号映射为数组下标的映射方法叫做**散列函数**（**hash函数**），而经过散列函数得到的值就叫做**散列值**（hash值）。 ![1372758-20190102232602820-1884679426.png][] 通过上面的例子我们可以总结到：散列表用的就是数组支持按照下标访问数据时时间复杂度为O(1)的特性来实现的高效访问，当存储数据时，通过散列函数得到数组的下标然后将数据放入到该位置中去，然后进行读取。可以看出，散列表的实质是数组，是一种升级版的数组。 **散列函数** ** **散列函数顾名思义是个函数，用函数表示就是hash(key)。那么大家想一下，要编写一个hash函数需要注意哪些问题呢，hash函数需要满足什么呢？ 1. 散列值是一个非负整数 2. 如果key1 = key2 ，那么hash(key1) == hash(key2) 3. 如果key1 != key2，那么hash(key1) != hash(key2) 解释一下这三点，第一点很明显，数组的下标是从0开始的，肯定是非负的， 第二点，key一样，他们的hash值也一样，也是很正确的，因为数组一个下标只能对应一个值。 但是第三点我们却无法满足，当两个key的值不同的时候，他们的hash值不敢保证一定不一样。即使是著名的MD5、SHA3这些hash算法，也无法到达这一目的，所以，以数组构成的散列表，存在着**散列冲突**的问题。并且数组的长度有限，随着值的增多，散列冲突的概率也会大大增大。 我们目前无法找到一个完美地能够解决hash冲突的办法，所以，我们为了解决散列冲突，提供了以下几种思路方法。 **散列冲突** ** **刚才我们说到，再完美的hash函数也无法解决散列冲突的问题，那么，我们该如何去解决散列冲突的问题呢？常用的解决方法有两类：**开放寻址法**（open addressing）和**链表法**(chaining)。 **1.开放寻址法** 开放寻址法的思想是，如果出现了散列冲突，就重新寻找一个空闲的位置去存放该数据，那么如何去探测空闲位置呢？ 这里，我们说一个比较简单的**线性探测法，**比如我们通过散列函数计算出了散列值为6，但是数组这个位置已经有数据了，然后我们就从7开始一直往后找，直到找到空闲的位置，然后插入该元素。 但是，这里我们会遇到一些问题，比如删除的时候，我们不能单纯地把要删除的位置设置为空，为什么呢？ 因为如果这个数据本来存在，但是因为线性探测法的原因它被安排在了其他位置，当查询的时候我们会判定它为不存在。这个问题该如何解决呢？ 我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为deleted的空间时，并不是停下来，而是继续往下探测。 **结论：** 大家肯定已经发现了，线性探测法存在很多的问题。当散列表中的数据越来越多的时候，**散列冲突发生的可能性就会越来越大，空闲的位置会越来越少，查找的时间就会越来越长**。最坏情况下，查找的效率会退化为**O(n)**，所以在数据比较多的时候，**装载因子**较少的时候才会去使用开发寻址法。 什么是装载因子呢？ 我们用装载因子来表示散列表的装满程度，也就是空闲状态。公式为： 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度 装载因子越大，说明空闲越少，可能发生的冲突越多。 **2..链表法** 链表法是跟为常用的解决散列冲突的办法，学java的小朋友们应该都知道，hashmap就是通过链表法来解决的hash冲突。 原理很简单，就是通过散列函数得到的目标位置如果已经有数据的话，就形成一个链表，将冲突的数据放入链表中去，这样插入的时间复杂度依旧是O(1)，但是当链表长度过长的时候，查询数据的速率会变慢，所以在有些时候，链表会转化为树来减少查找的时间。如图所示，hashmap用链表来解决hash冲突 ![1372758-20190109192551320-1139874734.png][] **应用场景** 接下来，让我们看两个例子，感受一下哈希表是如何应用的 **1.假设我们有 10 万条 URL 访问日志，如何按照访问次数给URL进行排序** 这个问题可以分为两步，第一步是统计每个URL的访问次数，第二步根据访问次数进行排序。那具体怎么做呢？ 首先我们以URL为key，访问次数为value，存入散列表中。时间O(N)。然后根据访问次数从大到小排序，用快速排序为O(NlogN)。 **2.有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串？** 以第一个字符串数组构建散列表，字符串为key，出现次数为value。再遍历第二个字符串数组，在散列表中查找，如果value大于0，说明存在该字符串，时间复杂度为O（N） **内容小结** 今天讲了哈希表一些简单的构成、设计思想、散列函数、散列冲突等理论性知识。 散列表是数组的进化版，利用了数组支持按照下标快速访问元素的特性，达到了O(1)的时间复杂度。散列表主要的问题是散列冲突问题，常见的两种方法是开放寻址法和链表法，其中链表法是常用的解决散列冲突的方法。 散列函数的设计决定了散列冲突的概念，也就决定了散列表设计的好坏 [1372758-20190102232602820-1884679426.png]: /images/1610292998304.png [1372758-20190109192551320-1139874734.png]: /images/1610293015622.png
相关 散列表查找 定义 通过散列函数寻找某个关键字所存在的位置，利用散列技术存储在一块连续的存储空间中，这块连续的存储空间称为散列表，对应的存储位置成为散列地址。 
柔情只为你懂
布满荆棘的人生
小灰灰
àì夳堔傛蜴生んèń
不念不忘少年蓝@
淩亂°似流年
你的名字
还没有评论，来说两句吧...