摘要：散列表其实是基于数组实现的，可以说，没有数组就没有散列表。根据下图你更能理解散列表哈希函数结合上面的理解，你应该可以想到，其实散列表的关键就在于哈希函数的实现。
1. 什么是散列表？
散列表（Hash Table）又叫做哈希表，是一种很常用的数据结构。散列表其实是基于数组实现的，可以说，没有数组就没有散列表。先来举一个简单的例子，来认识一下什么是散列表。
假如在学校的运动会上，每个运动员的胸前都会标识自己的号码，编号是1，2，3……，这样的话，我们可以很容易的将运动员信息存储在数组当中，运动员的编号就是数组的下标。但是会存在这样一种情况，假如运动员的编号不是顺序排列的，而是需要加上更多的信息，比如年级，班级，例如一个运动员的编号是15030711，15是年级，03是专业，07是班级，11是顺序号，这样的话我们该怎么存储运动员信息呢？
其实也不难，我们只需要截取运动员编号的最后两位，作为数组的下标存储在数组中，当需要根据编号查询信息的时候，我们也同样截取编号最后两位来进行查询。这就是很典型的散列思想。
选手的编号叫做 键 ， 把运动员编号转换为数组下标的方法叫做 散列函数（或哈希函数）， 通过散列函数计算得到的值叫做 散列值（或哈希值） 。
根据下图你更能理解散列表：
2. 哈希函数
结合上面的理解，你应该可以想到，其实散列表的关键就在于哈希函数的实现。哈希函数，顾名思义，其实就是一个函数，key 就是键值，经过 hash(key) 得到的值就是哈希值。
哈希函数的设计有三个原则：
通过哈希函数计算得到的哈希值是一个非负的整数。
如果 key1 = key2，那么 hash(key1) = hash(key2)。
如果 key1 != key2，那么 hash(key1) != hash(key2)。
前面两点其实很好理解，第一点，要求是一个非负的整数，这是因为数组的下标是从 0 开始的，第二点，如果 key 相同，那么通过哈希函数得到的哈希值也相同。
第三点稍微有点不好理解，key1 不等于 key2，那么哈希值也是不相等的，这只是一种理想的状况，但是在实际情况中，无法避免这种哈希冲突 。
3. 哈希冲突
哈希冲突，又叫哈希碰撞，是哈希函数可能会遇到的问题，即不同的 key 值经过哈希函数计算之后，可能得到相同的哈希值，那么这种状况该怎么解决呢？一般是通过两种方式：
开放寻址法
链表法
开放寻址法可以通过线性探测这种方式来实现，比如我们的一个 key 经过哈希函数得到哈希值之后，相应的存储位置已经被占用，那么我们遍历散列表，找到一个空闲的位置，将数据插入。
例如下图，标记为黄色的是已经有数据，标记为红色的是空闲空间，一个 key 经过 hash 哈希函数之后的存储位置为 2，但是下标为 2 的的地方已经有数据了，所以就重新探测一个空的位置。
第二种方式是链表法，这种方式会更加简单，也更加适用。例如下图，在每一存储位置，都会有相应的链表，如果哈希值相同，我们直接将数据存放在存储位置对应的链表中。
但是这种方式也可能会存在问题，比如说哈希函数设计的不合理，导致大量的数据都集中在一条链表中，这样的话，数据的插入和查找速度就会急剧退化为O(n)。针对这种情况，我们可以使用更加优秀的动态数据结构代替链表，例如红黑树、跳表等。这样，就算数据全都集中在一个节点上，数据的查询效率也不会下降得太厉害。
4. 散列表的具体应用
其实，散列表和链表在很多时候都是结合在一起使用的，接下来就看看散列表的两个具体应用：LRU（最近最少使用策略，Least Recently Used）缓存淘汰算法和 Java 的 LinkedHashMap。
1.LRU 缓存淘汰算法
首先，该怎么理解 LRU，即最近最少使用策略呢？举个简单的例子，比如你买了很多书，书架上渐渐放满了，当你有新的书的时候，需要将原来的书拿掉一些，腾出新的位置来。这样的话，你肯定会拿掉那些最近很少使用到的那些书，这就是一种最近最少使用策略。
其实可以用单链表实现一个LRU缓存淘汰算法，具体可以这样做：我们维护一个有限的缓存空间，如果空间不够，需要淘汰缓存的话，我们直接将链表头部的数据删除即可。当要缓存某个数据的时候，我们需要查找这个数据，如果找到了，将其放置在链表尾部，如果没找到，则将数据插入到链表尾部。因为涉及到的查找操作需要遍历链表，时间复杂度是O(n)，所以我们可以用散列表加上双向链表来实现，将时间复杂度降为O(1)。具体该怎么实现呢？
先来看看下面实现的图：
首先，如果空间不够，我们直接将双向链表头部的元素删除；查找一个元素，我们可以在接近 O(1) 的时间复杂度找到该元素，并且将其插入到链表的尾部；删除一个元素，由于双向链表保存了上一个链表的指针，所以能够在O(1) 的时间内删除；添加一个元素，如果此元素已经在链表中，则直接将该元素插入到链表尾部，如果不在链表中，直接将元素插入到链表尾部，如果缓存满了，则删除链表头部元素之后才添加。
2.LinkedHashMap
如果熟悉 Java 的话，肯定会经常用到 LinkedHashMap 这个容器，它与 HashMap 唯一的区别就是，LinkedHashMap 能够按照插入次序依次遍历得到数据，这个功能是怎么实现的呢？其实和上面的结构图很类似，插入到 HashMap 中的数据用双向链表连接起来，然后按照遍历链表的方法依次得到数据，这样就能够实现有序输出数据了。
好了，散列表就基本上讲完了。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/73947.html
摘要：什么是散列表和散列函数哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。根据键值从散列表中移除值。请实现散列表将和存在一个对象中即可定义一个包含和属性的类并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第五周的练习题，上周忘记发啦，这周是复习 Dictionary 和 Hash...
摘要：什么是散列表和散列函数哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。将字典的所有键名以数组的形式返回。根据键值从散列表中移除值。这是第五周的练习题，上周忘记发啦，这周是复习 Dictionary 和 HashTable。 下面是之前分享的链接： 1.每周一练 之 数据结构与算法（Stack） 2.每周一练 之 数据结构与算法（LinkedList） 3.每周一练 之 数据结构...
摘要：定义散列表是字典键值对的一种实现方式。根据键值从散列表中移除值。分离链接分离链接法在散列表的每一个位置创建一个链表并将元素存储在里面。一个表现良好的散列函数应该有较好的插入和查找性能且有较低的冲突可能性。 定义 散列表是字典（键、值对）的一种实现方式。每次在字典中获取一个值，都需要重复遍历字典，如果用散列表，字典中的每个key都对应一个确定的位置，从而不再需要遍历。以电子邮件地址簿为例...
摘要：小结实现了字典和哈希表感觉没有想象中那么困难，当然这还是开始。 本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算法之二叉搜索树 字典 不是新华字典哦，这里的字典也称作_映射_，是一种数据结构，跟set集合很相似的一种数据结构，都可以用来...
摘要：在字典中，存储的是键，值，集合可以看作值，值的形式存储元素，字典也称为映射方法描述备注向字典中添加新元素通过某个键值从字典中移除对应的数据值判断某个键值是存在于这个字典中通过键值获取对应的数据值返回字典所有元素的数量删除字典中所有元素将字典 在字典中，存储的是[键，值]，集合可以看作[值，值]的形式存储元素，字典也称为映射 方法 描述 备注 set(key,...
阅读 770·2023-04-25 15:13
阅读 1391·2021-11-22 12:03
阅读 819·2021-11-19 09:40
阅读 1899·2021-11-17 09:38
阅读 1703·2021-11-08 13:18
阅读 649·2021-09-02 15:15
阅读 1761·2019-08-30 15:54
阅读 2623·2019-08-30 11:12
