传统hash表

传统hash表是将key的hash值与value的数组下标对应实现，也就是将key的hash值经过某种运算得到一个整数值，这个值就是value列表的下标，就是key对应的value值

下面描述几个常用的概念：

• hash函数：用于将key转换为hash值得函数
• 冲突：即使很少得可能，但是不同的key可能得到相同的hash值，这时就冲突了
• 负载因子：表中元素的个数和桶中容量的对比：a = len(桶)/cap(桶)

解决冲突的方式

• 开放地址法或者线性探测法：即从冲突的位置往后探测，找到一个空闲的位置将冲突的元素放入；那么在查找的过程中，比如一个数hash值对应的位置是之前冲突的位置，比较key的值，key值不等，那么就按照之前插入的办法往后找，直到找到或者确认没有
• 链式寻址法：也就是在冲突的位置插入一个单链表，将所有冲突的hash值存入这个链表中
• 再hash法：用另外的hash算法来计算
• 建立公共移除区：凡是冲突的元素就放入移除区

为什么会发生冲突

打个比方：md5计算，就是无论多大的数据传入，出来的都是128位长度，即32位的16进制字符串，128位可以代表的个数是2^128-1个？，理想情况下如果我使用2^128个数插入，是不是就一定会导致冲突。当然和具体的算法也有关系，好的算法，可以尽量避免冲突。

swiss table

部分概念说明：

• group：一个 Group 就是 8 个槽位（slots）的存储单元
• slot：插槽，用于存储单个key-value的
• 控制字节：group的前部分，一个slot的控制字节是7位，加上状态位就是8位，有多少个slot有多少个控制字节，如果有8个slot，那么就有8个控制字节

插入流程：

1 计算key的64位hash值，并分为H1：高57位，H2：低7位

2 找到起始group id，并且依照顺序检查group，看是否key在此group中，起始group id是startIdx = H1 & (numGroups - 1) // numGroups 是 2 的幂；numGroups就是group的数量，如果在起始group没有，那么往后找idx_i = (startIdx + (i + i*i) / 2) % numGroups, i = 0,1,2,…，i=0时就是startIdx

3 如何知道key在group中呢？就是通过匹配控制字节；先把H2首位填充0复制扩展7份，那么就是8个H2共8字节，与控制字节进行XOR异或计算，这样只要和H2匹配上的都是0x00,这里还没排除排除控制位的干扰：异或的结果做与计算：xor & 0x7F7F7F7F7F7F7F7F，这样就只保留低7位的计算结果，这样全为0的字节就是与H2匹配的slot了，那么如果提取全为0的部分：

go
result = masked + 0x7F7F7F7F7F7F7F7F
// 上面的操作后，全为0的部分，最高位还是0 ，只要是非0 的部分，最高位是1
result = ^result                    // 取反，匹配的字节最高位变成 1
result = result & 0x8080808080808080  // 只保留最高位

4 将最高位提取出来：

go
最后一步，将 result 的各个字节最高位提取出来，压缩成一个 8 位整数：
bits = (result >> 7) & 0x010101010101010         // 每个字节最高位移到最低位
bits = bits * 0x0101010101010101            // 乘法将所有字节的最低位移到最高字节
bits = bits >> 56                           // 取出最高字节（即8个位）
这样一个字节中，1的位置就是对应匹配的了