哈希表和海量数据处理

1.哈希表
哈希表也叫做散列表，它是基于快速存取的角度设计的，是一种典型的“空间换时间”的做法。哈希表是普通数组的一种推广，因为数组可以直接寻址，故可在O(1)时间内访问数组的任意元素。
哈希表是通过关键字而直接进行访问的数据结构。也就是说，它将关键字通过某种映射到数组中某个位置，以加快查找的速度。这个映射规则称为哈希函数，存放记录的数组称为哈希表。哈希表建立了关键字和存储地址之间的一种直接映射关系。
若多个不同的关键字通过哈希函数计算得到相同的数组下标，称其发生了冲突，这些发生冲突的不同关键字称为同义词。
2.处理冲突的方法
任何哈希函数都不可能绝对避免冲突，为此必须考虑冲突发生时应如何进行处理，即为产生冲突的关键字寻找下一个“空”的Hash地址，于是提出了处理冲突的各种方法。
1）链地址法
链地址法是指所有的冲突关键字(同义词)存储在一个线性链表中，这个链表由其散列地址唯一标识。
2）开放定址法
开发定址法是指可存放新表项的空闲地址，既向它的同义词表项开发，又向它的非同义词表项开放。其数学递推公式为：
Hi=(H(key)+di)%m（哈希函数）
式中，i=1,2,…,k(k<=m-1),m为散列表表长，di为增量序列，di通常有以下几种取法：
当di=1,2,3…m-1时，称为线性探测法。其特点是，冲突发生时顺序查看表中下一个单元，直到找出一个空单元或查遍全表。
3）再散列法
当发生冲突时，利用另一个哈希函数再次计算一个地址，直到冲突不再发生，这种方法称为再哈希法。
3.海量数据处理
分治----hash映射
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的(根据同一个函数),那么这两个散列值的原始输入也是不相同的，这个特性使散列函数具有确定性的结果。
在对大文件进行处理时，若文件过大，无法一次性读入内存，可以考虑采取Hash映射方法将文件中的元素映射到不同小文件中，然后再依次处理各个小文件，最后合并处理结果，这样就降低了问题规模。
4.常用的哈希函数
直接定址法，数字分析法，平方取中法，除留余数法，折叠法等。
5.哈希函数的优缺点
优点：不论哈希表中多少数据，查找、插入、删除(有时包括删除）只需接近常量的时间即O(1)的时间级。实际上，这只需要几条机器指令。
哈希表运算得非常的快，在计算机程序中，如果需要在1秒内查找上千条记录通常使用哈希表，哈希表的速度明显比树快，树的操作通常需要O(n)的时间级。哈希表不仅速度快，编程实现也相对容易。
如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。
缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常厉害，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。
5.哈希表有多种不同的实现方法
拉链法

左边很明显是个数组，数组的每个成员包括一个指针,指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。