哈希表（Hash Table）是一种特殊的数据结构，它最大的特点就是可以快速实现查找、插入和删除。
我们知道，数组的最大特点就是：寻址容易，插入和删除困难；而链表正好相反，寻址困难，而插入和删除操作容易。那么如果能够结合两者的优点，做出一种寻址、插入和删除操作同样快速容易的数据结构，那该有多好。这就是哈希表创建的基本思想，而实际上哈希表也实现了这样的一个“夙愿”，哈希表就是这样一个集查找、插入和删除操作于一身的数据结构。
哈希表（Hash Table）：也叫散列表，是根据关键码值（key-value）而直接进行访问的数据结构，也就是我们常用到的map。
哈希函数：也称为是散列函数，是Hash表的映射函数，它可以把任意长度的输入变换成固定长度的输出，该输出就是哈希值。哈希函数能使对一个数据序列的访问过程变得更加迅速有效，通过哈希函数，数据元素能够被很快的进行定位。
哈希表和哈希函数的标准定义：若关键字为k，则其值存放在h(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为哈希函数，按这个思想建立的表为哈希表。
设计出一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。
但是，一般散列函数都面临着冲突的问题。两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。
设m和n分别表示表长和表中填入的结点数，则将α=n/m定义为散列表的装填因子(Load Factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。
哈希表的实现方法哈希表的实现就是映射函数构造，看某个元素具体属于哪一个类别。如何构造我们要考虑两个问题：
n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。
无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
所以，我哈希表的映射函数构造方法也有很多，常见的有：直接定址法、 除留余数法、 乘余取整法、 数字分析法、 平方取中法、 折叠法、 随机数法等。
1、直接定位法
Hash(key) = a·key + b (a、b为常数)
优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.
缺点：要占用连续地址空间，空间效率低。
例：关键码集合为{100，300，500，700，800，900}， 选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下：
2、除留余数法
Hash(key) = key mod p (p是一个整数)
特点：以关键码除以p的余数作为哈希地址。
关键：如何选取合适的p？
技巧：若设计的哈希表长为m，则一般取p≤m且为质数 （也可以是不包含小于20质因子的合数）。
3、乘余取整法
Hash(key) = [B*( A*key mod 1 ) ]下取整 (A、B均为常数，且0<A<1，B为整数)
特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。
例：欲以学号最后两位作为地址，则哈希函数应为： H(k)=100*(0.01*k % 1 ) 其实也可以用法2实现： H(k)=k % 100
4、数字分析法
特点：某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。
例：有一组（例如80个）关键码，其样式如下：
5、平方取中法
特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。
理由：因为中间几位与数据的每一位都相关。
例：2589的平方值为6702921，可以取中间的029为地址。
6、折叠法
特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
适用于：每一位上各符号出现概率大致相同的情况。
法1：移位法 ── 将各部分的最后一位对齐相加。
法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。
例：元素42751896, 用法1： 427＋518＋96=1041 用法2： 427 518 96—> 724+518+69 =1311
哈希表定址与解决冲突Hash表解决冲突的方法主要有以下几种：