散列表(哈希表、Hash Table)是根基的数据构造之一，综合了数组和链表的长处，平均情形下，在查找、删除、插入把持上，都能实现O(1)的复杂度。本文介绍哈希表的内部根基道理：hash()函数的设计和辩说的解决；并简洁介绍python内部dict的实现。hash()函数：将key映射为index
哈希表中内部有一块一连的内存区域，即数组，但与数组分歧，哈希表经由 hash()函数将一个元素的key映射成该内部数组的索引，该key能够为字符串、整数、浮点数、或复杂的数据构造（好比Python的元组Tuple）。
hash例子
一个好的hash()函数的设计，需要知足平均散列假设，即每个要害字都等概率的映射为内部数组中的随意一个索引。一个极端的设计反例，所有的要害字都映射为统一个索引，这种情形下或等价于链表（若是辩说经由链表解决），或等价于数组（若是辩说用数组实现），哈希表的长处就施展不出来。
最好一个元素的key的所有位(bit) 均介入hash()的生成， 若是用除法散列法，hash(x) = x % m, 一个不太接近2的整数幂的素数，平日是一个较好的选择。辩说的解决方式
固然我们能够经由精心设计散列函数来尽量削减辩说的概率，但辩说是弗成避免的。解决辩说的常用方式有两类：一类是经由链接法(Chaining)，一类是开放寻址法(Open Addressing)。
对于一个能存放n个元素的，具有m巨细的内部数组的哈希表，界说装载因子 (Load factor)界说为a=n/m。
链接法中，辩说的元素都放在一个链表中，若是hash()设计好，链表会很短，机能也会很好。在简洁平均散列假设下，能够证实查找的复杂度为O(1+a)
此外一种方式，是开放寻址法，所有的元素存放在内部数组中，没有链表。插入一个元素，会络续测验搜检散列表，直到成功为止。映射函数 hash(key)会经由为hash(key, 0), hash(key, 1), …, hash(key, m-1)络续测验，这个过程称为探查，最长的探查次数为m，这m次探核对应的索引为 0,1,…,m-1的一个分列。
能够证实，在简洁平均散列假设下，对于一次不成功的查找，复杂度为 O(1/(1-a))，对于一次成功的查找，为O(1/a log(1/(1-a))。a越大，机能越差，举例如下:
python字典内部实现
python的字典类内部是经由Hash Table实现的，辩说解决方案为开放寻址法，需要解说的，内部的数组，会动态扩容以包管机能（看上图，经由降低装载因子，来提高机能），这也是为什么python中字典对象能够一向往里面插入元素的原因之一。具体实现详情可看cpython 的源码，对应dictobject.c文件。
能够经由插入时间的剖析，来有个感性的感触。下图中的插入时间会有毛刺现象，毛刺的发生（即插入时间的倏忽变大），应该就是在内部的数组在扩容导致。
散列表的插入时间源码
横坐标为索引；纵坐标为的插入时间总结
散列表内部的道理首要是hash()函数的设计和辩说的解决，来达到O(1)的插、删、查的复杂度。Python字典的实现，就是散列表，内部经由扩容，包管机能和易用。领略上述概念，在今后的编程中对何时用dict会提高机能会了然于胸，好比最简洁的两数之和。
