哈希表的概念请参阅他人文章，关于哈希冲突的解决这篇文章基本都整理到了，还有几个常见的面试题。

哈希表的几个概念：

映像：由哈希函数得到的哈希表是一个映像。

冲突：如果两个关键字的哈希函数值相等，这种现象称为冲突。

关于哈希函数的选取，可以参见 这篇文章；

另外常见的字符串哈希函数及c++代码实现可以看这里。

主要有：常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。 常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。

BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。

好了，进入正题： 通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：

开放定址法 这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。 查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。 这种方法有一个通用的再散列函数形式： Hi=（H（key）+di）% m i=1，2，…，n 其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。 这里只给出大致的思想，更详细的具体步骤和代码可以参见这里： 哈希表的原理及解决冲突的方法 另外，散列表的查找性能，一般有两种方法，具体可以看上面这篇文章介绍。

成功平均查找长度(ASLs) ASLs： 查找表中关键词的平均查找比较次数（其冲突次数加1） 不成功平均查找长度 (ASLu) ASLu：不在散列表中的关键词的平均查找次数（不成功） 一般方法：将不在散列表中的关键词分若干类。

解决哈希冲突主要有以下三种：

线性探测再散列 dii=1，2，3，…，m-1（m是tablesize） 这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

二次探测再散列 di=12，-12，22，-22，…，k2，-k2 （2是平方） ( k