一、哈希函数
哈希法又称散列法、关键字地址计算法等，相应的表成为哈希表。
基本思想：首先在元素的关键字K和元素的位置P之间建立一个对应关系f，使得P=f(K)，其中f称为哈希函数
创建哈希表时，把关键字K的元素直接存入地址为f(K)的单元;
查找关键字K的元素利用哈希函数计算出该元素的存储位置P=f(K)
二、哈希函数的构造方法
哈希函数的构造原则是：函数本身便于计算、计算出来的地址分布均匀（即对任意K，f(K)对应不同地址的概率相等）。
1、数字分析法：
如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。
2、平方取中法：
当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
3、分段叠加法：
这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
4、除留余数法：
假设哈希表长为m，为小于等于m的最大素数，则哈希函数为h(k)=k%p；其中%为模p取余运算。
三、处理冲突的方法：
当关键字集合很大时，关键字值不同的元素可能会映射到哈希表的同一地址上，即K1 != K2，但f(K1)=f(K2),这种现象称为hash冲突，实际中冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。
1、开放定址法(再散列法)
基本思想：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2,...直到找出一个不冲突的哈希地址pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=(H(key)+di)%m i=1,2,...,n
其中H（key）为哈希函数，m为表长，di称为增量序列。增量系列的取值方式不同，相应的再散列方式也不同。
1）线性探测再散列
di=1,2,3,...,m-1冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
2）二次探测再散列
di=12，-12，22，-22,...，k2，-k2（k<=m/2）冲突发生时，在表的左右进行跳跃式探测，比较灵活。
3）伪随机探测再散列：
di=伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p)%m），并给定一个随机数做起点。
2、再哈希法：
这种方法是同时构造多个不同的哈希函数：Hi=RH1 (key) i=1,2,...,k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2(key)....,直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3、拉链法（HashMap的冲突处理方式）：
基本思想：将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法应用于经常进行插入和删除的情况。
4、建立公共溢出区：
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。