我们在Java容器中谈到：有哈希表（也称为散列表）支持的HashMap、LinkedHashSet等都具有非常高的查询效率。这其中就是Hash起的作用。顺序查找的时间复杂度为O(N) ,二分查找和查找树的时间复杂度为O(logN)，而 哈希表的时间复杂度为O(1) 。不过这只是理想状态，实际并不那么完美。
1.哈希表的概念和思想 哈希表是唯一的专用于集合的数据结构。可以以常量的平均时间实现插入、删除和查找。 哈希表的思想是：用一个与集合规模差不多大的数组来存储这个集合，将数据元素的关键字映射到数组的下标，这个映射称为“散列函数”，数组称为“散列表”。查找时，根据被查找的关键字找到存储数据元素的地址，从而获取数据元素。由于任何类型的数据都能转化为一个整数型，我们假设所有的数据元素的关键字都是较小的非负整数，就可以用一个简单的数组Data保存这个集合，数据类型就是集合中的元素的类型。
开始时，给数组的每个元素赋空值，NULL。当要在集合中插入一个关键字为Key的数据元素时，就检查Data[Key]是否为空。如果为空，则吧插入的元素存储在Data[Key]中；如果不为空，则表示遇到重复元素，插入失败。
当要查找某个数据元素时，只需要根据查找的关键字Key直接取出Data[Key]的值，如果Data[Key]的值为空，则表示关键字对应的元素不存在。否则，Data[Key]就是要查找的元素。删除时，只需要将对应数组的元素设为NULL即可。每种操作的时间为一个常量。
散列函数函数的应用带来一个复杂的问题：
因为散列函数的定义域范围比值域大，两个或更多的数据元素可能被映射到同一个位置，称为“冲突或碰撞”。这种情况是不可避免的。因此，实现散列表的两个最基本的问题是：如何设计散列函数，如何解决碰撞。
2.散列函数在散列表中。插入、删除和查找都会用到散列函数。散列函数的计算速度直接影响散列表的性能。好的散列函数的一个标准就是：计算速度快。另一点就是：结点的散列地址尽可能均匀。使得冲突的机会尽可能少。
常用的散列函数包括直接定址法、保留余数法、数字分析法、平方取中法和折叠法等。
(1)直接定址法直接取关键字的值或关键字的某个线性函数的值作为散列地址。设关键字为x，那么散列地址可表示为：
H(x) = x 或 H(x) = ax + b （a、b为常数）
例如：关键字集合为{100, 400，600， 200， 800， 900}，利用直接定址法，若选取散列函数为H(x) = x/100,则散列表如下：
如果M是散列表的大小，关键字 x 的数据元素的散列地址为：H(x) = x mod M
在保留余数法中，选取合适的余数M很重要，如果选取不当，则导致大量的碰撞。
经验表明：M为素数（除了1和它本身以外不再有其他因数。）时，散列表的分布比较均匀。
(3)数字分析法在某些领域，关键字之间的区别集中在某些位上面，例如计算机的IP地址，一个IP地址由两部分组成：网络号和主机号。在同一子网中的主机的网络号是相同的。在某个网络中，我们可以将IP地址作为关键字。如果采取散列方法保存这个集合，可以选取IP地址的主机号部分作为存储地址。
更一般的说，如果在关键字集合中，每个关键字均由n位组成，分析关键字中每一位的分布规律，并从中提取分布均匀的若干位或它们的组合作为地址。
例如：右边的数据
第一列、第二列、第五列 对于不是区分关键字没有价值。
第三列只有 7 、 8 、9 三种数字。
余下的几列比较均匀，可作为散列表的地址选用。
若散列表的地址是三位，直接选取剩下的三位即可；
若散列表的地址小于三位。则选择其他方法，比如：保留余数法等等
将三位关键字映射到一个更小的值域中。