Hash表简介
基本思想
哈希存储的基本思想是根据当前待存储数据的特征，以记录关键字(key)为自变量，设计一个哈希函数Hash，根据Hash计算出对应的函数值Hash（key），以这个值（哈希地址）作为数据元素的地址，并将数据元素存入到相应地址的存储单元中。按照这个思想构造的表就叫做哈希表（Hash table，也叫散列表）
查找时再根据要查找的关键字key采用同样的函数计算出哈希地址，然后根据Hash（key）直接到相应的存储单元中去取要找的数据元素即可。
建立步骤
step 1：取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。
step 2：根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step 2，直到找到能用的存储地址为止。
问题
对于n个数据元素的集合，总能找到关键字与存放地址一一对应的函数。假设最大关键字为m，可以分配m个数据元素存放单元，选取函数Hash（key）=key即可，但是这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关键字的集合比哈希地址集合大得多（tips：这里的大不是说个数，而是总体所用空间），因而经过哈希函数变换后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突（Collision）。映射到同一哈希地址上的关键字称为同义词。可以说，冲突不可能避免，只能尽可能减少。
Hash表实现
通过文章前面的了解我们可以知道，具体去实现Hash表需要我们完成：1）Hash函数构造；2）制定解决冲突的方案。
Hash函数构造
构造哈希函数的方法有很多，总的原则是尽可能简单，以便提高转换速度，且要尽可能将关键字集合空间均匀的映射到地址集合空间中，同时尽可能降低冲突发生的概率。
下面是一些常用的哈希函数构造方法：
-
直接地址法
Hash(key) = a*key + b（a、b为常数） -
除数留余法
H(key) = key % p (p ≤ m)取关键字除以p的余数作为哈希地址，p最好选择一个小于或等于m（哈希地址集合的个数）的某个最大素数，也可以是不包含小于20质因子的合数。
哈希表长度 8 16 32 64 128 256 512
最大素数 7 13 31 61 127 251 503 数字分析法
设关键字集合中，每个关键字均由m位组成，每位上可能有r中不同的符号。数字分析法根据r种不同符号及在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应是各种符号在该位上出现的概率大致相同。平方取中法
对关键字平方后，按哈希表大小，取中间的若干位作为哈希地址。折叠法（Folding）
比如key=135790，要求Hash(key)是2位数的散列值。那么我们将key变为13+57+90=160，然后去掉高位“1”,此时Hash(key)=60，这就是他们的哈希关系，这样做的目的就是地址与每一位的key都相关，来做到“散列地址”尽可能分散的目地。
冲突处理方法
影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。
解决冲突的方法有以下两种：
-
开放地址法
所谓开放定址法，即由关键字得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素。我们需要寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。常用的找空哈希地址方法有下列三种。
（1）线性探测法Hi=(Hash(key)+di)%m(1=<i<m)其中，Hash(key)为哈希函数，m为哈希表长度，di为增量序列1,2…,m-1，i为探测次数。
（2）二次探测法地址增量序列为：di=12,−12,22,−22,...,q2,−q2（q≤m/2）d_i = 1^2, -1^2,2^2,-2^2 ,...,q^2,-q^2 （q ≤ m/2）di=12,−12,22,−22,...,q2,−q2（q≤m/2）
（3）双哈希函数探测法Hi =( H(key) + i * RH(key) )%m ( i = 1,2,3,..., m-1 )H(Key) , RH(Key) 是两个哈希函数，m为哈希表长度。
先用第一个哈希函数对关键字计算哈希地址，一旦产生地址冲突，再用第二个函数确定移动的步长因子，最后通过步长因子序列由探测函数寻找空余的哈希地址。H1 = ( a+b )%m , H2 = ( a + 2b )%m , ... , Hm-1 = ( a+(m-1)*b )%m 链地址法
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。
leetcode两数之和python实现
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]
基于Hash思想的实现
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
Hash_dict = {}
for i in range(len(nums)):
Hash_dict[nums[i]] = i
for i in range(len(nums)):
temp = target - nums[i]
if temp in Hash_dict & i != Hash_dict[temp]:
return [i,Hash_dict[temp]]