哈希表
Last updated
Last updated
顾客来商店买东西，作为店员要快速报出价格，按顺序查找是O(n)，按二分法查找是O(logN)，按散列表是O(1)；
电话簿，姓名对应着电话。
DNS解析，你不管访问哪个网站，那个网址都会被解析成对应的IP地址。
防止重复，有人投票，你要看他是否已经投过了，那就把他的名字去和已经投过票的人的名字去做比对。这种情况下存储到列表里会很慢，但在散列表里却会很快；
缓存/记住数据，以免服务器再通过处理来生成它们。当你访问Facebook的页面时，它首先检查散列表中是否存储了该页面。仅当URL不在缓存中时，你才让服务器做些处理，并将处理生成的数据存储到缓存中，再返 回它。这样，当下次有人请求该URL时，你就可以直接发送缓存中的数据，而不用再让服务器进 行处理了。
在需要用到映射和查找时创建散列表是不错的选择。
散列函数是这样的函数：不论你给它什么东西，它都返回给你一个数字；
我们通过散列函数来创建一个空数组，给它什么输入，它就能给它特定的输出。比如先创建一个空数组，把apple当输入传给散列函数，函数返回3，那我们就可以把apple的价格比如4元存储到索引3处；
不断重复可以将这个数组填满，之后我们再向这个函数输入apple，它就会告诉我们价格存储在索引3处，时间复杂度为O(1)；
散列函数得满足一些要求：比如每次输入apple，得到的索引是固定的，不能从3变成4；并且不同的输入尽量返回不同的索引，不然就不是好的散列函数。
使用散列函数和数组创建了一种被称为散列表（hash table）的数据结构。散列表是你学习的第一种包含额外逻辑的数据结构。数组和链表都被直接映 射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
在你将学习的复杂数据结构中，散列表可能是最有用的，也被称为散列映射、映射、字典和 关联数组。散列表的速度很快！还记得第2章关于数组和链表的讨论吗？你可以立即获取数组中 的元素，而散列表也使用数组来存储数据，因此其获取元素的速度与数组一样快。 你可能根本不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的 散列表实现为字典，你可使用函数dict来创建散列表。
用这个函数检查来投 票的人是否投过票！：
查询商品价格：
要让散列函数做到每个输入都对应着不同的输出有些不现实，不同的散列函数有性能优劣之分，高级编程语言里一般都内置了优秀的散列函数，可以让数组中的值均匀分布不扎堆。
当同样地输入映射到同样的索引处就会发生冲突，在同一个索引处就会生成另外的列表，所以最糟糕的情况下，散列表的时间复杂度为O(n)；
填装因子大于1意味着商品数量超过了数组的位 置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）。
为此，你首先创建一个更长的新数组：通常将数组增长一倍。 9 接下来，你需要使用函数hash将所有的元素都插入到这个新的散列表中。
这个新散列表的填装因子为3/8，比原来低多了！填装因子越低，发生冲突的可能性越小， 散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。 你可能在想，调整散列表长度的工作需要很长时间！你说得没错，调整长度的开销很大，因 此你不会希望频繁地这样做。但平均而言，即便考虑到调整长度所需的时间，散列表操作所需的 时间也为O(1)。
包含10个元素，有20个位置，那么填充因子就是0.5；
哈希(Hash)将某个对象变换为唯一标识符，该标识符通常用一个短的随机字母和数字组成的字符串来代表。哈希可以用来实现各种数据结构，其中最常用的就是哈希表(hash table)。
哈希表通常由数组实现。
哈希表的性能取决于3个指标：
哈希函数
哈希表的大小
哈希冲突处理方式
下图展示了有数组实现的哈希表，数组的下标即为哈希值，由哈希函数计算，作为哈希表的键(key)，而数组中保存的数据即为值(value)
