随笔：
以前在美国学Java数据结构的时候，因为当时是插班生，临时选的数据结构，其实当时还没学Java，听到hash table一脸懵逼，回公寓在goole和百度上也没有找到比较完整的解释，最近在看python数据结构的时候又重新研究了一下这个点，感觉了解的还挺透彻的，放出来和大家分享一下。
为了便于说明，我们以数据结构中的字典类型举例，基于字典来讲解哈希和哈希表的概念与应用
一、哈希和哈希表
二、哈希思想在信息领域的应用
三、哈希的设计和性质
四、常用的哈希函数
五、冲突消解技术
1.冲突的内消解：开地址技术
2.冲突的外消解：溢出区方法
一、哈希和哈希表
数据检索是计算机技术中最基本也是最常用的操作，面对大规模的数据存储，快速的查询操作是被需要的，那么如何可以以最快的速度进行数据的查找呢？
考虑计算机中数据存储和使用方式，可以得知：如果数据项连续存储，而关键码就是存储数据的地址（下标）！就可以以O(1)的时间得到所需要的数据。
但是，实际上，关键码不可能总是整数，即使是整数也不太可能有大规模的连续存储空间供一个量使用。于是，人们想出了一个方法，也就是哈希（hash，也有翻译成散列）表，其基本思想是：如果一种关键码不能或者不适合作为数据存储的下标，可以考虑通过一个变换把它们映射到另一种下标，这样子就可以把基于关键码的检索转换为基于整数下标的直接元素访问。
以字典为例，用哈希表的思想实现，具体方法是：
1）选定一个整数的下标范围（通常以0或者1开始），建立一个包括相应元素位置范围的顺序表
2）选定一个从实际关键码集合到上述下标范围的映射h：
^^在需要存入关键码为key的数据时，将其存入表中第
h（key）个位置。
^^遇到以key为关键码检索数据时，直接去找表中第 h（key）个位置的元素
这个h称为哈希函数，或者散列函数，它就是从可能的关键码集合到一个整数区间的映射
二、哈希思想在信息领域的应用
上文从字典的检索引出了哈希的概念和思想，实际上，散列的思想是在信息和计算领域逐渐发展起来的一种极其重要的思想，其应用远远超出了数据检索和存储的范围，例如：
1）文件完整性检查：定义一个哈希函数，从一个软件的所有文件内容算出一个数或者一个字符串，需要时检查实际文件的哈希值是否与其匹配
2）互联网技术中到处都使用和依靠哈希函数，用于网页传输中的各种安全性和正确性检查，包括各种网络认证和检查、各种网络协议
3）计算安全领域中大量使用散列技术，例如在各种安全协议里
三、哈希的设计和性质
一般情况下，可能的关键码集合通常都非常大，例如，假设关键码是10个字母以内的英文字符串，不难算出这个关键码集合的规模可以达到10的14次方级别，绝对不可能直接用来作为字典的下标。因此，针对一种关键码实现字典时，所用的下标集合通常都远远小于关键码集合的规模，也就是：
|KEY| >> |INDEX| 这说明，在通常情况下，哈希函数 h 是从一个大集合到一个小集合的映射，它显然不可能是单映射，必然会出现许多个不同的关键码被 h 对应到同一个 下标位置的情况，人们称这种情况为，冲突（或碰撞），一般而言，表中的元素越多，出现冲突的可能性越大，因此用一个概念 负载因子
描述这种性质的程度：
负载因子 a =
散列表中实际数据项数／散列表的基本存储区能容纳的元素个数综上，如果要用哈希技术实现检索字典，必须解决两大问题：哈希函数的设计，冲突消解机制。接下来两节分别考虑这两个问题
四、常用的哈希函数
在设计哈希函数时，应该考虑一下问题：
1）函数应能把关键码映射到值域INDEX中尽可能大的部分
2）不同关键码的哈希值在INDEX里均匀分布，有可能减少冲突
3）哈希函数的计算应该相对简单
基于这些考虑，介绍两种在工程实际中常用的哈希函数
1）除余法
关键码 key 是整数，用key除以某个不大于哈希表长度m的整数p，得到的余数（或者余数加上l，由下标开始值确定）作为哈希地址
为了存储管理方便，人们经常将m取为2的某个幂值，此时p可以取小于m的最大素数，例如，当m取128、256、512、1024时，p可以分别取127、251、503、1023。
注意，设计哈希函数的一个基本思想就是尽可能的使得到的结果没有规律，在采用除余法时，如果用偶数作为除数，就会出现偶数关键码映射到偶数哈希值，奇数关键码映射到奇数哈希值的情况，这种情况应该避免
2）基数转换法
先考虑整数关键码，取一个正整数r把关键码看作基数为r（r进制数），将其转换为十进制或二进制数，通常r取素数以减少规律性
如r取13，对于关键码335647，可转换为十进制数6758172
当遇到字符串作为关键码时，可以把一个字符看作一个整数，对字符串进行编码，再采用同样的方法，这里给一个简单的字符串哈希函数
def str_hash(s):
h1 = 0
for c in s:
h1 = h1 * 29 + ord(c) #ord转换ASCII码函数
return h1五、冲突消解技术
采用哈希思想实现字典类型，冲突是必然会出现的事件，因为哈希函数是从大集合到小集合的函数，必然会出现两个不同元素的函数值相同的情况。
对于字典的冲突处理技术有两方面要求：
1）保证当前这次存入数据项的工作能正常完成
2）保证字典的基本存储性质：在任何时候，从 任何以前存入字典而后没有删除的关键码出发，都能找到对应的数据项
这种冲突消解的方法在实现方式上可以分为两类：
1）内消解方法，即在基本存储区内部解决冲突问题
2）外消解方法，即在基本储存区之外解决问题
1.冲突的内消解：开地址技术
内消解的基本方法称为开地址法，其基本思想是：在准备插入数据并发现冲突时，设法在基本存储区里为需要插入的数据项另行安排位置。为此需要设计一种系统的而且易于计算额度位置安排模式，称为探查方式，如：
Hi = ( h ( key ) + di ) mod p
D = d0,d1,d2...这里的D是一个整数的递增序列，d0 = 0，p是一个长度不超过表长的数，在插入数据项时，如果h(key)为位置空闲就直接存入（相当于使用d0），否则d就逐个改变，直到找到空位
2.冲突的外消解：溢出区方法
外消解基数里常用的一种技术是另外设置一个益处存储区，当插入关键码的哈希表位置没有数据时就直接插入，发生冲突时就将相应数据和关键码一起存入溢出区