关于实现源码 实现源码仓库在线查看链接： C语言实现 C++实现哈希表的理论知识哈希表的定义 哈希表也叫散列表，我们先来看看哈希表的定义： 哈希表是保存键值映射关系的查找表，通过关键字可以很快找到对应的值。 简单说来说，哈希表由两个要素构成：桶数组 和 散列函数（哈希函数）。桶数组：用于存储键值对的空间。散列函数：用于给键值对在桶数组中的位置指路。桶数组 我们可能知道，有一类基础的数据结构 线性表，而线性表又分两种，数组 和 链表。 哈希表数据结构里，存储元素的数据结构就是数组，数组里的每个单元都可以想象成一个 桶（Bucket）。 而我们每次都是把我们需要存入的键值对加入到这样的桶子中。散列函数 我们需要在元素和 桶数组 对应位置建立一种映射映射关系，这种映射关系就是 散列函数 ，也可以叫哈希函数。 比如我们平时生活中，碰到排队型的时候，都需要根据高矮来进行一定的队形调整，这个调整过程也可以看做是散列函数的一种体现。散列函数的构造 散列函数有很多类，这其中的奥妙来自于数学，而不是我们程序员需要过于操心的事情。 在Java语言中只要是继承自Object类的所有类都有默认的一个 hashcode() 方法，而对于具体过程我们不需要多想，我们来看看最常用的字符串的哈希过程：static inline size_t strHashcode(char *key) { size_t hash = 0; size_t index = 0; while (key[index] != '\0') { hash = hash * 31 + key[index++]; } return hash; } 很明显得出的 hashcode 是一个以31为底的次方数，关于为什么以31为底，我这里简单的描述一下：以31为底能很快得出比较散且比较大的二进制码（底层的01串），这样结合子掩码的与运算有利于减少哈希冲突的产生。31 * i == (i << 5) - i 因为这个等式的成立使得运算性能也有很大的提升。（编译器一般会对 31*i 进行优化的） 更多细节看看这篇文章：关于为什么选31扰动函数 和 按位与 我们通过散列函数得到一堆 01 串后，我们该怎么做？ 接下来一般就是通过和桶数组的长度取余然后得到对应的位置进行插入。这样虽然也可以，但我们有更好的方式进行替代，那就是位运算。 既然要讲位运算，那么我先讲讲一个二进制串。 在只有一个 1 的二进制串里面，我们对它再减去 1 的时候，我们很快得到它的低位掩码。 比如： 0001000 - 1 = 0000111，得到的 0000111 有什么用处呢？ 如果我们把一个 hashcode 和这个数进行按位与，则得到的结果肯定是介于 000~111 之间，也就是 0~7 之间，这个时候我们思考一下，如果把这个 0001000 看做是桶数组的长度，那么这个按位与的结果就可以当做需要存入的桶的具体位置了。 基于这个理论，我们只要桶数组长度是 2的倍数 则 hashcode%size 可用 hashcode&(size-1) 来替代。 这样做有以下好处：位运算的性能更好。便于控制 hashcode 最终得出的结果，有些时候我们得到的 hashcode不够均匀 高位的1比较多，而低位的1比较少，这个时候可以利用 hashcode^(hashcode>>16) 进行一定程度的打散，而这个打散的过程我们一般把它叫做 扰动函数 。哈希冲突 当出现键值运算结果得到的桶子位置是同一个的时候便产生了哈希冲突。 而解决哈希冲突的方案一般有以下三种： 链地址法 一旦发生哈希冲突，直接生成链表往后继续延伸。 开放地址法 简单来说就是给冲突的元素再在桶数组里找到一个空闲的位置。 而常用采用的方法有：线性探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置。平方探查法: 从冲突的位置x开始，第一次增加 1^2 个位置，第二次增加 2^2…，直至找到空闲的位置。双散列函数探查法 ...... 再哈希法 再哈希法完全可以配备以上两类方法进行使用。 当然也可单独使用，单独使用的话就行配备多个哈希函数，一个不行的话换另一个哈希函数，直到不产生哈希冲突为止。 最终的选择： 而我们常用的是 链地址法 + 再哈希 ，为了能够尽量减少内存空间的使用，我们默认从容量为 16 的桶数组开始，一旦装入的键值对超过 capacity * factor 个时，我们进行一次两倍的（左移1位）扩容，而由于扩容会导致 capacity 改变，所以通过 哈希函数 + 与运算 得出的位置也会出错，故需要经过 再哈希 。 我们其实可以继续细想，我们左移一位后，得出的结果再减一，它也仅仅多出一位掩码，而我们的 hashcode 只要在这一位上为 0 则最后得…