1.简介
- hash:将任意长度的字符通过函数计算成固定长度字符的算法。
- hsah冲突：不同的字符串经过hash函数计算在hash表上得到相同的地址，产生冲突。
2.解决方法
2.1开放定址法
发生hash冲突是，根据计算得到的hash值产生另外一个值，也称为再散列法。
再次计算的方法有：
- 线性再散列
冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。 - 二次再散列
冲突发生时，在表的左右进行跳跃式探测，比较灵活。 - 伪随机再散列
具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。
如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。
如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。
如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。
2.2再哈希法
同时构造多个不同的hash函数，如果发生hash冲突则换一个hash函数再计算。
2.3链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。
2.4建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。