一、关于哈希表
1.哈希表的定义
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。把关键码值转化为数组下标的映射函数叫做散列函数（“Hash 函数”），存放记录的数组叫做散列表，散列函数计算得到的值叫做散列值。（散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。）
如下图
2.散列函数
从定义里，可以看出散列函数十分关键，一般我们定义散列函数为 hash(key)，其中 key是关键码值 (Key value)，hash(key) 的值表示经过散列函数计算得到的散列值。
散列函数设计的基本要求：
1. 散列值是一个非负整数；
2. 如果 key1 = key2，那么 hash(key1) == hash(key2)；
3. 如果 key1 ≠ key2，那么 hash(key1) ≠ hash(key2)。
工业界著名哈希算法：MD5、SHA、CRC
构建哈希函数的几种方法：
1.直接定址法
取关键字或者关键字的某个线性函数为Hash地址。
2.平方取中法
对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取{72，89，00}作为Hash地址。
3.折叠法
将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。
4.除留取余法
如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。
5.数字分析法
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
6.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址。通常用于关键字长度不等时采用此法。
3.散列冲突（哈希冲突）
在上面的要求3里面，实际上只存在理论的可能性，在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不存在的。像上述三种工业界的算法，也都无法避免这种情况，这种情况称为散列冲突。并且，数组存储空间的有限，也会加大散列冲突的概率。
比如，在新华字典里，你本来查找的是“按”，但是却找到“安”字，你又得向后翻一两页，才能找到“按”。在计算机里面同理。如果想要完全避开这种情况的出现，只能给每个字典去新开一页，然后每个字在索引里面都有对应的页码，这样就可以完全避免冲突，但是其会导致空间增大，这与我们所说的存储空间有限有些矛盾。
因此，我们我们需要使用一些方法来解决散列冲突问题。解决方法主要有开放定址法(open addressing)、再哈希法、链地址法（拉链法(Open Hashing)）和建立一个公共溢出区四种方法。
（1）开放定址法(open addressing)
核心思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m i=1，2，…，n,其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：
1) 线性探测再散列
di=1，2，3，…，m-1
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。2) 二次探测再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2)
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。3) 伪随机探测再散列
di=伪随机数序列。
具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。
(2) 再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key），i=1，2,3，…,n.
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
(3) 拉链法
基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。
(4) 建立公共溢出区
基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表.(注意：在这个方法里面是把元素分开两个表来存储)
4.关于哈希表的性能
由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击（有兴趣的人可以搜一下基于哈希冲突的拒绝服务攻击），一般也不会出现这种情况。
二、leetcode编程练习
第一题（两数之和（1））：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
代码：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dict1 = {}
lengh = len(nums)
#遍历一遍列表其时间复杂度为O(n)
for index in range(lengh):
#目标值减去第一个值得到另一个数值
num = target - nums[index]
#如果在字典中则返回
if num in dict1:
return [dict1[num], index]
#如果num不在字典中，则将第一个数值及其索引添加在字典中
else:
dict1[nums[index]] = index
运行结果：
第二题（Happy number(202)）：
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例:
输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
代码：
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
dict1 = {}
while True:
l = list(map(int,list(str(n))))
m = 0
for i in l:
m += i**2
if m in dict1:
print(dict1)
return False
if m == 1:
print(dict1)
return True
dict1[m] = m
n = m
运行结果：
参考内容：
https://www.cnblogs.com/yangecnu/p/Introduce-Hashtable.html
https://www.jianshu.com/p/dbe7a1ea5928
http://www.cnblogs.com/s-b-b/p/6208565.html
https://blog.csdn.net/My_heart_/article/details/52442573
https://time.geekbang.org/column/article/64233
