定义：哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
特点：
1、大大降低数据的存储和查找消耗的时间；
2、内存消耗较大；
3、使得编码更容易。
什么是哈希表？特点是什么
简单说就是按照哈希函数关系建立的表
具体内容请参考数据结构相关知识~
下面引用一些别的地方
1 基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
2 函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a) 除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
b) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。
3 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。
4 支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ，A 为存储的数组。
初始化比较容易，例如
const empty=maxlongint// 用非常大的整数代表这个位置没有存储元素
p=9997 // 表的大小
procedure makenull
var i:integer
begin
for i:=0 to p-1 do
A[i]:=empty
End
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
function h(x:longint):Integer
begin
h:= x mod p
end
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate
function locate(x:longint):integer
var orig,i:integer
begin
orig:=h(x)
i:=0
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i)
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
//素存储的单元，要么表已经满了
locate:=(orig+i) mod S
end
插入元素
procedure insert(x:longint)
var posi:integer
begin
posi:=locate(x) //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error//error 即为发生了错误，当然这是可以避免的
end
查找元素是否已经在表中
procedure member(x:longint):boolean
var posi:integer
begin
posi:=locate(x)
if A[posi]=x then member:=true
else member:=false
end
这些就是建立在哈希表上的常用基本运算。
什么是哈希表?它们与字典的关系是什么?
序列类型用有序的数字键做索引将数据以数组的形式存储。一般索引值与所存储的数据毫无关系。还可以用另一种方式来存储数据:基于某种相关值，比如说一个字符串。我们在日常生活中一直这么做。把人们的电话号码按照他们的姓记录在电话簿上，按照时间在日历或约会薄上添加事件，等等。在这些例子中，你的键就是和数据项相关的值。哈希表是一种数据结构:它按照我们所要求的去工作。哈希表中存储的每一条数据，叫做一个值(value)，是根据与它相关的一个被称作为键(key)的数据项进行存储的。键和值合在一起被称为“键-值对”(key-value pairs)。哈希表的算法是获取键，对键执行一个叫做哈希函数的操作，并根据计算的结果，选择在数据结构的某个地址中来存储你的值。任何一个值存储的地址皆取决于它的键。正因为这种随意性，哈希表中的值是没有顺序的。你拥有的是一个无序的数据集。你所能获得的有序集合只能是字典中的键的集合或者值的集合。方法Keys()或values()返回一个列表，该列表是可排序的。你还可以用items()方法得到包含键、值对的元组的列表来排序。由于字典本身是哈希的，所以是无序的。哈希表一般有很好的性能，因为用键查询相当快。序列类型用有序的数字键做索引将数据以数组的形式存储。一般索引值与所存储的数据毫无关系。还可以用另一种方式来存储数据:基于某种相关值，比如说一个字符串。我们在日常生活中一直这么做。把人们的电话号码按照他们的姓记录在电话簿上，按照时间在日历或约会薄上添加事件，等等。在这些例子中，你的键就是和数据项相关的值。哈希表是一种数据结构:它按照我们所要求的去工作。哈希表中存储的每一条数据，叫做一个值(value)，是根据与它相关的一个被称作为键(key)的数据项进行存储的。键和值合在一起被称为“键-值对”(key-value pairs)。哈希表的算法是获取键，对键执行一个叫做哈希函数的操作，并根据计算的结果，选择在数据结构的某个地址中来存储你的值。任何一个值存储的地址皆取决于它的键。正因为这种随意性，哈希表中的值是没有顺序的。你拥有的是一个无序的数据集。你所能获得的有序集合只能是字典中的键的集合或者值的集合。方法Keys()或values()返回一个列表，该列表是可排序的。你还可以用items()方法得到包含键、值对的元组的列表来排序。由于字典本身是哈希的，所以是无序的。哈希表一般有很好的性能，因为用键查询相当快。
哈希表（散列表）
哈希表，也叫散列表，是根据关键码值(key value)直接访问的数据结构。也就是说，它通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数叫 散列函数 ，存放记录的表叫 散列表 。
优点：一对一的查找效率很高；
缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。
由于数组是连续的，于是可以根据下标在O(1)的读写任何元素，因此它的时间效率是很高的。我们可以根据数组时间效率高的优点，用数组来实现简单的哈希表：把数组的下标设为哈希表的键值，而把数组中每一个数字设为哈希表的值，这样每一个下标及数组中就形成了键-值的配对。有了这样的哈希表，我们就能在O(1)的时间内查找，从而快速、高效的解决很多问题。
就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标。将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）
数组的特点是： 寻址容易，插入和删除困难 ；
链表的特点是： 寻址困难，插入和删除容易
我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”。如下图所示。
左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
好的散列函数=计算简单+分布均匀（计算得到的散列地址分布均匀）
散列冲突：不同的关键字经过散列函数的计算得到了相同的散列地址。
最直观的一种，上图使用的就是这种散列法，公式：
index = value % 16
学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。
求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：
如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。
平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。
1，对于16位整数而言，这个乘数是40503
2，对于32位整数而言，这个乘数是2654435769
3，对于64位整数而言，这个乘数是11400714819323198485
这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。
对我们常见的32位整数而言，公式：
如果用这种斐波那契散列法的话，那上面的图就变成这样了：
用斐波那契散列法调整之后会比原来的取摸散列法好很多。
1.建立一个缓冲区，把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时，发现找的不对，就在缓冲区里找。
2.进行再探测。就是在其他地方查找。探测的方法也可以有很多种。
（1）在找到查找位置的index的index-1，index+1位置查找，index-2，index+2查找，依次类推。这种方法称为线性再探测。
（2）在查找位置index周围随机的查找。称为随机在探测。
（3）再哈希。就是当冲突时，采用另外一种映射方式来查找。
哈希表—什么是哈希表
哈希表是一种数据结构～
哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录， 那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。 (关键字就是所要存储的数据，存储位置相当于数组的索引)
当然，可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1，而是由关键字(数据本身)通过哈希函数得到
eg1. 将26个小写字母存储到数组 int [26] a。
a对应a[0]，b对应a[1]，c对应a[3]……以此类推。
那么，数组 int [26] a 就是一个哈希表！
例1中，关键字(小写字母)是如何得到自己对应的索引(存储位置)的呢？
关键字的ASCII值减去a的ASCII值！
上面说过，关键字通过哈希函数得到索引，所以，f(ch)就是本例题的哈希函数。
这样，我们就在关键字和数字(存储位置)之间建立了一个确定的对应关系f。
关键字与数字是一一对应的，由于数组本身支持随机访问，所以，当查找关键字时，只需要O(1)的查找操作，也就是实现了不经过任何比较，一次便能得到所查记录。
哈希表中 哈希函数的设计 是相当重要的，这也是建哈希表过程中的关键问题之一。
假如，我们所要存储的数据其关键字是一个人的身份证号(18位数字)，这个时候我们该怎么计算关键字对应的索引呢？
比如一个人的身份证号是 411697199702076425，我们很难像例1那样直接让关键字与数字建立一一对应的关系，并且保证数字适合作为数组的索引。
在这种情况下，通过哈希函数计算出的索引，即使关键字不同，索引也会有可能相同。这就是 哈希冲突
当索引相同时，我们该怎么存储数据呢？如何解决哈希冲突，是我们建哈希表的另一个关键问题。
哈希表充分体现了空间换时间这种经典的算法思想。
关键字是大整数时，比如上面我们举的身份证号例子，411697199702076425
假如我们能开辟一个 999999999999999999 大的空间，这样就能直接把身份证号作为关键字存储到数组中，这样可以用O(1)时间完成各项操作
假如我们只有 1 的空间，我们需要把所有信息存储到这个空间中(也就是所有数据都会产生哈希冲突)，我们只能用O(n)时间完成各项操作
事实上，我们不可能开辟一个如此大的空间，也不可会开辟如此小的空间
无限空间时，时间为O(1)
1的空间时，时间为O(n)
而哈希表就是在二者之间产生一个平衡，即 空间和时间的平衡 。
1.哈希函数的设计
2.解决哈希冲突
3.哈希表实现时间和空间的平衡
后续会详细说明这三个关键问题～
相关推荐：
