我们知道，数组利用下标可以随机访问数组下标对应的值，相对于链表的顺序访问，数组的下标访问是最快的(常量时间，二分查找是对数时间)。
如果反过来，怎样才能由数组的值访问到其下标的值？或者，如果存储了一份商品价格表（商品名称、价格），怎样才能通过商品名称随机访问到其价格呢？
通过散列表(散列，来自英文字hash，也有翻译成哈希的，散列表有时也叫哈希表、关联数组)，可以实现此目的。
数据在内存中的物理存储有顺序存储、链式存储、散列存储、索引存储四种方式。顺序存储通过元素的相互邻接的顺序来构造元素的逻辑关系，链式存储是通过存储额外的邻接元素地址来构造元素间的逻辑关系，索引存储是通过一分额外的索引表（关键字、地址）来构造元素间的逻辑关系（HASH索引结构不需要额外的存储空间）。散列存储则是通过散列函数将关键字直接映射为地址，以实现元素的快速查找。（索引存储在数据库较多用于检索记录，磁盘和内存的索引数据结构有所区别）
普通数组与散列（关联数组）之间最本质的区别是：数组使用数值下标来定位特定的元素，而散列使用字符串值（键）来定位元素；数组中的元素按下标排序，而散列中的元素是无序的。
1 散列函数
散列函数H(key)是这样的函数，即无论你给它什么数据(key)，它都还你一个数字。
简单理解散列表（如py的dict）的内部机制：实现、冲突和散列函数
如果用专业术语来表达的话，我们会说，散列函数“将输入映射到数字”。你可能认为散列函数输出的数字没什么规律，但其实散列函数必须满足一些要求。
I 它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都必须为4。如果不是这样，散列表将毫无用处。
II 它应将不同的输入映射到不同的数字。例如，如果一个散列函数不管输入是什么都返回1，它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。
散列函数将输入映射为数字，这有何用途呢？你可使用它来打造你的“Maggie”！
为此，首先创建一个空数组。
你将在这个数组中存储商品的价格。下面来将苹果的价格加入到这个数组中。为此，将apple作为输入交给散列函数。
散列函数的输出为3，因此我们将苹果的价格存储到数组的索引3处。
下面将牛奶（milk）的价格存储到数组中。为此，将milk作为散列函数的输入。
散列函数的输出为0，因此我们将牛奶的价格存储在索引0处。
不断地重复这个过程，最终整个数组将填满价格。
现在假设需要知道鳄梨（avocado）的价格。你无需在数组中查找，只需将avocado作为输入交给散列函数。
它将告诉你鳄梨的价格存储在索引4处。果然，你在那里找到了。
散列函数准确地指出了价格的存储位置，你根本不用查找！之所以能够这样，具体原因如下。
I 散列函数总是将同样的输入映射到相同的索引。每次你输入avocado，得到的都是同一个数字。因此，你可首先使用它来确定将鳄梨的价格存储在什么地方，并在以后使用它来确定鳄梨的价格存储在什么地方。
II 散列函数将不同的输入映射到不同的索引。avocado映射到索引4，milk映射到索引0。每种商品都映射到数组的不同位置，让你能够将其价格存储到这里。
III 散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会返回无效索引100。
刚才你就打造了一个“Maggie”！你结合使用散列函数和数组创建了一种被称为散列表（hash table）的数据结构。散列表是一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
在你将学习的复杂数据结构中，散列表可能是最有用的，也被称为散列映射、映射、字典和关联数组。散列表的速度很快！你可以立即获取数组中的元素，而散列表也使用数组来存储数据，因此其获取元素的速度与数组一样快。
你可能根本不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的散列表实现为字典，你可使用函数dict来创建散列表。
book = dict()
创建散列表book后，在其中添加一些商品的价格。
book[“apple”] = 0.67
book[“milk”] = 1.49
book[“avocado”] = 1.49
print book
{‘avocado’: 1.49, ‘apple’: 0.67, ‘milk’: 1.49}
非常简单！我们来查询鳄梨的价格。
print book[“avocado”]
1.49
散列表由键和值组成。在前面的散列表book中，键为商品名，值为商品价格。散列表将键映射到值。
2 将散列表用于查找
手机都内置了方便的电话簿，其中每个姓名都有对应的电话号码。
假设你要创建一个类似这样的电话簿，将姓名映射到电话号码。该电话簿需要提供如下功能。
添加联系人及其电话号码。
通过输入联系人来获悉其电话号码。
这非常适合使用散列表来实现！在下述情况下，使用散列表是很不错的选择。
创建映射。
查找。
创建电话簿非常容易。首先，新建一个散列表。
phone_book = dict()
顺便说一句，Python提供了一种创建散列表的快捷方式——使用一对大括号。
phone_book = {}
下面在这个电话簿中添加一些联系人的电话号码。
phone_book[“jenny”] = 8675309
phone_book[“emergency”] = 911
这就成了！现在，假设你要查找Jenny的电话号码，为此只需向散列表传入相应的键。
print phone_book[“jenny”]
8675309
如果要求你使用数组来创建电话簿，你将如何做呢？使用两个数组来相互映射，显得比较麻烦。而散列表让你能够轻松地模拟映射关系。
散列表被用于大海捞针式的查找。例如，你在访问像http://adit.io这样的网站时，计算机必须将adit.io转换为IP地址。
无论你访问哪个网站，其网址都必须转换为IP地址。
这不是将网址映射到IP地址吗？好像非常适合使用散列表啰！这个过程被称为DNS解析（DNS resolution），散列表是提供这种功能的方式之一。
3 防止重复
假设你负责管理一个投票站。显然，每人只能投一票，但如何避免重复投票呢？有人来投票时，你询问他的全名，并将其与已投票者名单进行比对。
如果名字在名单中，就说明这个人投过票了，因此将他拒之门外！否则，就将他的姓名加入到名单中，并让他投票。现在假设有很多人来投过了票，因此名单非常长。
每次有人来投票时，你都得浏览这个长长的名单，以确定他是否投过票。但有一种更好的办法，那就是使用散列表！
为此，首先创建一个散列表，用于记录已投票的人。
voted = {}
有人来投票时，检查他是否在散列表中。
value = voted.get(“tom”)
如果“tom”在散列表中，函数get将返回它；否则返回None。你可使用这个函数检查来投票的人是否投过票！
代码如下。
voted = {}
def check_voter(name):
…if voted.get(name):
…print “kick them out!”
…else:
…voted[name] = True
…print “let them vote!”
我们来测试几次。
check_voter(“tom”)
let them vote!check_voter(“mike”)
let them vote!check_voter(“mike”)
kick them out!
首先来投票的是Tom，上述代码打印let them vote!。接着Mike来投票，打印的也是let them vote!。然后，Mike又来投票，于是打印的就是kick them out!。
别忘了，如果你将已投票者的姓名存储在列表中，这个函数的速度终将变得非常慢，因为它必须使用简单查找搜索整个列表。但这里将它们存储在了散列表中，而散列表让你能够迅速知道来投票的人是否投过票。使用散列表来检查是否重复，速度非常快。
4 将散列表用作缓存
来看最后一个应用案例：缓存。如果你在网站工作，可能听说过进行缓存是一种不错的做法。下面简要地介绍其中的原理。假设你访问网站facebook.com。
(1) 你向Facebook的服务器发出请求。
(2) 服务器做些处理，生成一个网页并将其发送给你。
(3) 你获得一个网页。
例如，Facebook的服务器可能搜集你朋友的最近活动，以便向你显示这些信息，这需要几秒钟的时间。作为用户的你，可能感觉这几秒钟很久，进而可能认为Facebook怎么这么慢！另一方面，Facebook的服务器必须为数以百万的用户提供服务，每个人的几秒钟累积起来就相当多了。
为服务好所有用户，Facebook的服务器实际上在很努力地工作。有没有办法让Facebook的服务器少做些工作，从而提高Facebook网站的访问速度呢？
假设你有个侄女，总是没完没了地问你有关星球的问题。火星离地球多远？月球呢？木星呢？每次你都得在Google搜索，再告诉她答案。这需要几分钟。现在假设她老问你月球离地球多远，很快你就记住了月球离地球238 900英里。因此不必再去Google搜索，你就可以直接告诉她答案。这就是缓存的工作原理：网站将数据记住，而不再重新计算。
如果你登录了Facebook，你看到的所有内容都是为你定制的。你每次访问facebook.com，其服务器都需考虑你感兴趣的是什么内容。但如果你没有登录，看到的将是登录页面。每个人看到的登录页面都相同。Facebook被反复要求做同样的事情：“当我注销时，请向我显示主页。”有鉴于此，它不让服务器去生成主页，而是将主页存储起来，并在需要时将其直接发送给用户。
这就是缓存，具有如下两个优点。
用户能够更快地看到网页，就像你记住了月球与地球之间的距离时一样。下次你侄女再问你时，你就不用再使用Google搜索，立刻就可以告诉她答案。
Facebook需要做的工作更少。
缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！
Facebook不仅缓存主页，还缓存About页面、Contact页面、Terms and Conditions页面等众多其他的页面。因此，它需要将页面URL映射到页面数据。
当你访问Facebook的页面时，它首先检查散列表中是否存储了该页面。
具体的代码如下。
cache = {}
def get_page(url):
…if cache.get(url):
…return cache[url] # 返回缓存的数据
…else:
…data = get_data_from_server(url)
…cache[url] = data # 将数据保存到缓存
…return data
仅当URL不在缓存中时，你才让服务器做些处理，并将处理生成的数据存储到缓存中，再返回它。这样，当下次有人请求该URL时，你就可以直接发送缓存中的数据，而不用再让服务器进行处理了。
这里总结一下，散列表适合用于：
模拟映射关系；
防止重复；
缓存/记住数据，以免服务器再通过处理来生成它们。
5 使用可以最大限度减少冲突的散列函数
前面说散列函数总是将不同的键映射到数组的不同位置。
实际上，几乎不可能编写出这样的散列函数。我们来看一个简单的示例。假设你有一个数组，它包含26个位置。
而你使用的散列函数非常简单，它按字母表顺序分配数组的位置。
简单理解散列表（如py的dict）的内部机制：实现、冲突和散列函数
你可能已经看出了问题。如果你要将苹果Apple的价格存储到散列表中，分配给你的是第一个位置。
接下来，你要将香蕉Bananas的价格存储到散列表中，分配给你的是第二个位置。
一切顺利！但现在你要将鳄梨的价格存储到散列表中，分配给你的又是第一个位置。
不好，这个位置已经存储了苹果的价格！怎么办？这种情况被称为冲突（collision）：给两个键分配的位置相同。这是个问题。如果你将鳄梨的价格存储到这个位置，将覆盖苹果的价格，以后再查询苹果的价格时，得到的将是鳄梨的价格！冲突很糟糕，必须要避免。处理冲突的方式很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。
在这个例子中，apple和avocado映射到了同一个位置，因此在这个位置存储一个链表。在需要查询香蕉的价格时，速度依然很快。但在需要查询苹果的价格时，速度要慢些：你必须在相应的链表中找到apple。如果这个链表很短，也没什么大不了——只需搜索三四个元素。但是，假设你工作的杂货店只销售名称以字母A打头的商品。
等等！除第一个位置外，整个散列表都是空的，而第一个位置包含一个很长的列表！换言之，这个散列表中的所有元素都在这个链表中，这与一开始就将所有元素存储到一个链表中一样糟糕：散列表的速度会很慢。
这里的经验教训有两个。
散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。
如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很好，这些链表就不会很长！
通常有两类方法处理碰撞：开放寻址(Open Addressing)法和链接(Chaining)法。前者是将所有结点均存放在散列表T[0…m-1]中；后者通常是把散列到同一槽中的所有元素放在一个链表中，而将此链表的头指针放在散列表T[0…m-1]中。在开放寻址法中，当要插入一个元素时，可以连续地检查或探测散列表的各项，直到有一个空槽来放置待插入的关键字为止。有三种技术用于开放寻址法：线性探测、二次探测以及双重探测。
散列函数很重要，好的散列函数很少导致冲突。那么，如何选择好的散列函数呢？
本章开头是假设你在杂货店工作。你想打造一个让你能够迅速获悉商品价格的工具，而散列表的速度确实很快。
在平均情况下，散列表执行各种操作的时间都为O(1)。O(1)被称为常量时间。你以前没有见过常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。例如，你知道的，简单查找的运行时间为线性时间。
二分查找的速度更快，所需时间为对数时间。
在散列表中查找所花费的时间为常量时间。
一条水平线，看到了吧？这意味着无论散列表包含一个元素还是10亿个元素，从其中获取数据所需的时间都相同。实际上，你以前见过常量时间——从数组中获取一个元素所需的时间就是固定的：不管数组多大，从中获取一个元素所需的时间都是相同的。在平均情况下，散列表的速度确实很快。
在最糟情况下，散列表所有操作的运行时间都为O(n)——线性时间，这真的很慢。我们来将散列表同数组和链表比较一下。
在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。
因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：
较低的填装因子；
良好的散列函数。
5.1 填装因子
散列表的填装因子很容易计算。
散列表使用数组来存储数据，因此你需要计算数组中被占用的位置数。例如，下述散列表的填装因子为2/5，即0.4。
下面这个散列表的填装因子为多少呢？
如果你的答案为1/3，那就对了。填装因子度量的是散列表中有多少位置是空的。
假设你要在散列表中存储100种商品的价格，而该散列表包含100个位置。那么在最佳情况下，每个商品都将有自己的位置。这个散列表的填装因子为1。如果这个散列表只有50个位置呢？填充因子将为2。不可能让每种商品都有自己的位置，因为没有足够的位置！填装因子大于1意味着商品数量超过了数组的位置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）。
例如，假设有一个像下面这样相当满的散列表。
你就需要调整它的长度。为此，你首先创建一个更长的新数组：通常将数组增长一倍。
接下来，你需要使用函数hash将所有的元素都插入到这个新的散列表中。
这个新散列表的填装因子为3/8，比原来低多了！填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。
你可能在想，调整散列表长度的工作需要很长时间！你说得没错，调整长度的开销很大，因此你不会希望频繁地这样做。但平均而言，即便考虑到调整长度所需的时间，散列表操作所需的时间也为O(1)。
5.2 良好的散列函数
良好的散列函数让数组中的值呈均匀分布。
糟糕的散列函数让值扎堆，导致大量的冲突。
什么样的散列函数是良好的呢？你根本不用操心——天塌下来有高个子顶着。如果你好奇，可研究一下SHA函数。你可将它用作散列函数。
散列函数的结果必须是均匀分布的，这很重要。它们的映射范围必须尽可能大。最糟糕的散列函数莫过于将所有输入都映射到散列表的同一个位置。
6 散列表中涉及的相关名词
7 写在最后
你几乎根本不用自己去实现散列表，因为你使用的编程语言提供了散列表实现。你可使用Python提供的散列表，并假定能够获得平均情况下的性能：常量时间。
散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。
你可以结合散列函数和数组来创建散列表。
冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
散列表的查找、插入和删除速度都非常快。
散列表适合用于模拟映射关系。
一旦填装因子超过0.7，就该调整散列表的长度。
散列表可用于缓存数据（例如，在Web服务器上）。
散列表非常适合用于防止重复。
HASH就是把关键词直接映射为存储地址，达到快速寻址的目的，即Addr=H(key)，其中key为关键词；H为哈希函数。主要有以下几种常用的哈希函数：
除留余数法，H(key)=key MOD maxM ; maxM一般是不太接近 2^t 的一个质数。
随机数法，H(key)=random(key)，random为随机函数；
乘法取整法：H(key):=trunc((key/maxX)*maxlongit) mod maxM，主要用于实数。
平方取中法：H(key):=(key*key div 1000 ) mod 1000000); 平方后取中间的，每位包含信息比较多。
HASH索引结构不需要额外的存储空间，并且能够在O(1)的时间复杂度下准确定位到所查找的数据，将磁盘数据库中的数据查找时间代价优化至最小。Hash索引结构由于以上优点在磁盘数据库中广泛的运用。经历长久的研究，先后发展出了链接桶哈希(chainedbucket hash)，可扩展哈希(extendible hash)、线性哈希(linearhash)和修正的线性哈希(modified linear hash)。但是这些哈希算法虽然针对内存数据库进行了少许优化，但是与传统数据库中所用的哈希算法没有明显不同。到了2007年，KennethA. Ross提出了基于现代处理器的Hash预取算法将SIMD指令集融入到Hash算法中，才真正从内存索引的角度改进了哈希算法，提升数据组织的效率。
喜欢这篇文章的可以点个赞，欢迎大家留言评论，记得关注我，每天持续更新技术干货、职场趣事、海量面试资料等等
如果你对java技术很感兴趣也可以加入我的java学习群（374308445）来交流学习，里面都是同行，群验证【CSDN2】有资源共享。
不要再用"没有时间“来掩饰自己思想上的懒惰！趁年轻，使劲拼，给未来的自己一个交代！
