无锁哈希表

前段时间看到酷壳中一篇无锁哈希表的 文章，以及伯乐在线上面一篇 文章，正好研究一下这个主题。

伯乐在线上那篇号称“世界上最简单的无锁哈希表”，用开地址+线性探查实现的哈希表，然后对数据元素用原子操作，看完基本上没什么价值。原因很简单：不支持扩容。而正如酷壳上那篇文章说的，扩容才是难点。“HashMap主要有插入、删除、查找以及ReHash四种基本操作。一个典型的HashMap实现，会用到一个数组，数组的每项元素为一个节点的链表。对于此链表，我们可以利用上文提到的操作方法，执行插入、删除以及查找操作，但对于ReHash操作则比较困难。”

按常规思路，扩容时涉及了将结点从旧链中移除，将结点插入到新链，需要三次指针操作，而这三次指针操作必须同时完成，才能保证移动操作的原子性。显然这跟把冰箱门打开，把大象放进去，再把冰箱门关上一样不靠谱。因为CAS操作每次只能保证一个变量的值被原子性地验证并更新，无法满足同时验证并更新三个指针的需求。

关于无锁哈希表看过另一个实现，是用哈希树的方式，每一层32个孩子，这样就可以用字节长度做一个32位的位图，通过这个位图来保护访问的原子性。不过酷壳上的这篇比较巧妙，巧妙地避免了扩容时的节点移动操作，通过引入哨兵结点，做成了顺序插入。具体的原理就不说了，可以看原文，下面只说说我在实现过程中遇到的一些细节。

按位翻转

遇到的第一个问题就是二进制位反转。太久不玩这种底层的代码，不太顺了。第一次取出全部奇数位，跟偶数位交换位置，然后两位一组取出，交换，接着四位一组取出交换，依次做下去就可以将整个数据按位交换了。有一点类型面试题中，按单词交换"hello world"变成"world hello"的做法，先单词反转，再整句反转。

func bitReverse(v uint32) (ret uint32) { mask := []uint32{ 0x55555555, //...010101010101 0xaaaaaaaa, //...101010101010 0x33333333, //...001100110011 0xcccccccc, //...110011001100 0x0f0f0f0f, //...00001111 0xf0f0f0f0, //...11110000 0x00ff00ff, //...0000000011111111 0xff00ff00, //...1111111100000000 0x0000ffff, 0xffff0000, } ret = v for i := uint32(0); i < 5; i++ { tmp1 := ret & mask[2*i] tmp1 = tmp1 << (1 << i) tmp2 := ret & mask[2*i+1] tmp2 = tmp2 >> (1 << i) ret = tmp1 | tmp2 } return }

Go中的CompareAndSwapPointer函数就是个坑

接着是链表中的CAS操作。不得不吐糟一下Go提供的这个api真的很误导。atomic.CompareAndSwapPointer是做不出来原子地给指针赋值的，被坑惨了。因为它的第一个参数是unsafe.Pointer，而(unsafe.Pointer)(&p)编译会报错。做完类型转换得到的是一个“左值”，左值是没法取地址的。而如果先tmp := unsafe.Pointer(p)，再&tmp，这么做是无用的，改的是临时变量tmp而不是原始的p。

想取到p的地址了当参数传给CompareAndSwapPointer都是做不到的。于是我就想绕过这个，弄一个**unsafe.Pointer的东西出来，假设叫pp，再传*pp给CompareAndSwapPointer。这个也搞不定...

最后我算是明白了，unsafe.CompareAndSwapPointer这个函数完全是个鸡肋，用它根本没法完成原子性的给某个非unsafe.Pointer的指针赋值（有点绕，我的意思是说它没法给*node这种其它非unsafe.Pointer类型指针赋值）。解决方式是用atomic.CompareAndSwapUintptr这个函数。利用unsafe.Pointer可以向指针转化，以及uintptr刚好是一个指针大小。

atomic.CompareAndSwapUintptr((*uintptr)(unsafe.Pointer(&prev.next)), uintptr(unsafe.Pointer(next)), uintptr(unsafe.Pointer(p)))

递归初始化bucket

插入操作中，先判断hash & mask之后的插入位置，如果该位置未初始化，会先进行初始化再插入。初始化某个bucket是递归进行的，先递归地初始化它的父结点位置，再初始化它。其实初始化就是插入一个哨兵结点。这个是有点巧妙的地方，如果不自己动手写的话很难注意到这种细节。最后都变成调用listInsert的操作了，只要按无锁链表做就够了。无锁链表还是相对比较简单的。

我开始在想，要不要做成递归初始化这样子啊？直接在开始时就把所有哨兵结点都分配好不就行了？直到后面写rehash才明白其中的精妙：rehash其实就是新插入一些哨兵结点，说白了就是在做递归的初始化bucket的操作。所以rehash和这里本质上是同一个操作。

我还是将rehash说细点吧。在这个实现中，没有结点的移动，没有将结点从旧表中删除，再插入到新表的过程。只有插入一个哨兵将分裂后桶中的点隔开成两部分。结点插入时插入操作，扩容也是插入操作，只不过一个是插入普通节点，一个是插入哨兵结点。

关于一个线程在做扩容过程中，另一个线程做了插入，如何保持一致性的问题，那篇文章中没有细说。我实现的做法是，先更新哈希表中的桶数组，但是不更新哈希表的当前mask位数bits。然后去做扩容操作，也就是插入哨兵结点啦，这时在其它线程中看哈希表状态跟旧表没两样，而扩容线程看它差不多是个新表了。两个表共用的同一个结点的链表，插入都是链表插入，可以保证原子性。扩容完后将mask位数更新成新表位数就完成了。So easy!

好啦，无图无真相，没 代码我说个JB。