本文源代码基于 commit: 73820a60cc3c990abb351540ca27bf7689bce8ac

哈希表:开放定址法

As we all know,在需要快速搜索的场景下,哈希表提供O(1)的检索复杂度。哈希就可能会产生冲突。对冲突的处理基本上分为两大类:链表法(又称拉链法),开放定址检测法。 链表法,就是说在每个哈希槽(slot)上其实都是一个链表表头,所有落入这个槽的元素都接入这个链表。

开放定址检测法,本质就是多试几次,万一可以呢,发现本key的哈希槽被占用的时候,使用一个算法算一算下一个槽的位置,可以就占掉,不可以就再试下去。

个人觉得,这两种方法在实现和使用的时候,各有不同。链表法实现较为直观,但可能造成空间浪费。想象申请了n块内存,结果哈希值比较稀疏,值都落到了几个大链表里,就不划算。另一方面,链表法什么时机重hash也是一个问题(个人感觉),毕竟单个槽过长,搜索会退化成O(n)。开放定址检测不存在内存浪费,申请多少用多少,在扩容之前只会用这些申请的内容。重hash的时机也比较好掌握;但是在设计检测算法的时候也要注意,首要是不能产生死循环(在有足够空位的情况下,要能最终找到至少一个空位),其次二次检索的效率也要注意。比如线性检测就不太好,在哈希槽较满的情况下容易产生近O(n)的效率。

cpython中解决字典的哈希冲突使用的是开放定址法。

开放定址法的删除

链表法中要删除一个元素很容易,把他从哈希槽的链表里拿掉就好了。但开放定址法不能简单地删掉。举个例子,用线性探测(虽然不好)时,搜索其实构成了一个搜索顺序。比如搜索key为13, hash值为3(比如hash函数就是n%10)的元素能插入哪个位置,3,4,5都已经有元素了,那么搜索顺序会有

    3(have) --> 4(have) --> 5(have) --> 6(null)

ok, 找到了我的家(yeah),那么key 13就落户编号6的哈希槽。但是这个时候,用户删除了位置4的哈希槽元素,然后再去搜索key 13元素位置的时候会变成这样:

    3(have) --> 4(null) --> 5(have) --> 6(have 13)

到位置4的时候发现没有了。可能有人会问,那算法继续搜索下去就好了嘛,总会找到key 13的,但这是在知道这个key存在的情况下才有意义;如果算法这么实现的话,所有搜索不存在key的情形都会把搜索算法变成O(n),因此开放定址法的搜索止于找到该key或发现一个空位。如上,这个搜索空间就断裂了。(这个问题在cpython源码注释中也有说明)

所以开放定址法不能直接删除元素,而是应该标记删除,以确保搜索空间的完整连续性,构造出如下的搜索空间:

    3(have) --> 4(dummy) --> 5(have) --> 6(have 13)

其中,dummy就是cpython中使用的标记删除,算法跑到4处会继续向下搜索直到6的位置

cpython的搜索例程

上代码

static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
         Py_hash_t hash, PyObject **value_addr)

cpython中关于在dict中搜索的代码位于dictobject.c,函数签名如上。参数中传入一个操作的字典对象mp,查找的key,该key的hash值(传入是因为之前算过,就不要重复算了),最后一个参数是查找出来的值的引用,需要在函数内赋值(或者没找到置空)。返回值就是该key的位置,有三种可能:

  • DKIX_EMPTY
  • DKIX_DUMMY
  • 某个大于等于0的数字。

DKIX_EMPTY就是说没找到,DKIX_DUMMY就是说找到了这个key的位置,但是已经被删除了,最后就是找到的哈希槽编号的数值了。

size_t i, mask, perturb;
    PyDictKeysObject *dk;
    PyDictKeyEntry *ep0;

top:
    dk = mp->ma_keys;
    ep0 = DK_ENTRIES(dk);
    mask = DK_MASK(dk);
    perturb = hash;
    i = (size_t)hash & mask;

初始了一坨变量,其中hash & mask这个操作比较特殊。其中hash就是哈希值,mask等于dk_size-1。这个操作让i落在哈希槽范围内。这个地方当时粗看的时候我觉得很诡异,为啥与操作能到达跟取余一样的效果呢。这里不是说与操作的结果值跟取余是一样的,而是说能达到同样的收敛值域的作用。然后我做了一个不加验证的假设: cpython中字典的容量都是2^n,然后取2^n-1,让n位二进制位都是1,这样与操作,x & (2^n-1)的结果必然小于等于2^n-1。此外这段代码设置了一个tag:top,目的是在有必要的时候goto回来重新开始。

注意,这里cpython的实现是for(;;)死循环,实现上要求必要有返回。下面分几段代码分析一个例程。

    for (;;) {
        Py_ssize_t ix = dk_get_index(dk, i);
        if (ix == DKIX_EMPTY) {
            *value_addr = NULL;
            return ix;
        }
        if (ix >= 0) {
            ...
        }
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
    }

首先在每个循环例程最开始,都会用当前的i来找内存该位置的状态,如果发现这个位置是空,就直接返回了。如果发现有东西,就会进一步做一些操作来确认这块内容是不是我想要的。如果又不是DKIX_EMPTY,又不是大于等于0的某个数,按照上述的约定,就一定是DKIX_DUMMY,也就是找到了一个已删除的内容,继续做探测。

   for (;;) {
        Py_ssize_t ix = dk_get_index(dk, i);
        if (ix == DKIX_EMPTY) {
            ...
        }
        if (ix >= 0) {
            PyDictKeyEntry *ep = &ep0[ix];
            assert(ep->me_key != NULL);
            if (ep->me_key == key) {
                *value_addr = ep->me_value;
                return ix;
            }
            if (ep->me_hash == hash) {
                PyObject *startkey = ep->me_key;
                Py_INCREF(startkey);
                int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
                Py_DECREF(startkey);
                if (cmp < 0) {
                    *value_addr = NULL;
                    return DKIX_ERROR;
                }
                if (dk == mp->ma_keys && ep->me_key == startkey) {
                    if (cmp > 0) {
                        *value_addr = ep->me_value;
                        return ix;
                    }
                }
                else {
                    /* The dict was mutated, restart */
                    goto top;
                }
            }
        }
       ...
    }

以上代码就是找到了一个非空的哈希槽之后该做什么。 首先比较了搜索的key与该哈希槽存储的key是不是根本同一个指针。因为cpython会复用很多小对象。 其次会比较这个槽存储元素的hash值。因为经过哈希碰撞之后,每个槽存储的hash值并不一定是一手取与得到的。如果不一样,for循环就会进入下一个例程。has值一样,然后要比较该元素的key是否deepEqual当前的key。因为都说了哈希碰撞嘛,这个key跟key也可能是不一样但是hash值一样的。(连SHA1都可以碰撞的说…)。经过hash值一样,key相等比较之后,这个元素位”基本”上就是我们要找的元素了。

但是,这里cpython做了”看似”比较多余的事情,他比较了在代码中使用的字典还是不是要搜索的字典,被搜索到的key还是不是之前比较的key。这里用局部变量跟外部变量引用相比较,是要确定外部变量有没有被修改。这个代码为什么可以生效,目前我还没有明确的证据,因为就算这个if (dk == mp->ma_keys && ep->me_key == startkey)能成立,进入if之后就能保证这个if依然成立吗;返回值依然有可能是脏的。还需要进一步阅读代码。

检测算法

上一节的代码里,其实我真正关心的只有下面这段做检测的代码。从函数关系来说,这个探测是一种平方探测。(突然想起了时间序列里的AR(1)…)。perturb初值就是hash值,每次循环右移PERTURB_SHIFT = 5位参与运算

        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;

怎么证明这个函数关系不会陷入死循环呢?恩,我也不知道…严格证明懒,留一个随缘未解之谜吧…

我写了一个go的小代码来看这个算法会”路过”那些哈希槽。

package main

import (
	"fmt"
)

func main() {
	hash := 9
	perturb := hash
	mask := 7
	i := hash & mask
	for j:=0;j<20;j++{
		fmt.Println(i)
		perturb >>= 5
		i = cal(i, perturb, mask)
	}
}

func cal(i int, perturb int, mask int) int {
	return (i*5 + perturb + 1) & mask
}

输出的搜索空间如下:

1 -->6 --> 7 --> 4 --> 5 --> 2 --> 3 --> 0

可以看到,在这个hash:9 ,mask:7输入下,可以一次性探测到所有的8个位置。后面的输出就是重复这个序列了。(是不是很神奇呢…)

Ending

好了,本文到此为止,字典的CRUD就只介绍R的核心部分。(因为写文章很花时间的…)其他内容,有缘有心情再见。