映射map与哈希hash, since 2022-05-09

(2022.05.09 Mon)
通过文章字典与映射map中的分析，我们注意到用list保存key并通过遍历方式查询和更改其中值用作映射的方法效率低下。这里我们引入Python的字典实现使用的方法哈希表Hash table。

直觉上，映射的访问方式支持像访问一个list的索引一样访问映射中的某个key，形如M[k]。假设映射的n个key是0到N-1之间的整数， $N>n$ ，可用一个长度为N的查询表look-up table来表示这个映射，该查询表用list实现。比如表的index 0对应的值是P，index 8对应的值是Z，index 13对应的值为m，形成k-v对的表示是(0, P)，(0, Z)，(13, m)。这种假设下，使用魔术方法__getitem__，__setitem__，__delitem__执行相应的操作，对应的复杂度都是O(1)。

上面的案例推向更一般的情况有如下挑战，

key的表达未必是整数
查询表的长度N可能出现 $N>>n$ 的情况

应对这些挑战，引入哈希函数Hash function概念。哈希函数将一般键值(general key)映射到一个表的索引(indices)上，理想情况下被映射的值分布于0到 $N-1$ 之间。实际上有可能有多个值被映射到同一个位置上，因此再次引入bucket array桶序列的概念。桶序列作为查询表，在每个索引位置/单元上可以保存多个k-v对。

哈希函数h的目标是将key k映射到[0, N-1]范围的一个整数，其中的N是哈希表中bucket array A的容量。有了这个哈希函数h，输入k的输出h(k)是在A中的索引，可以把键值对(k, v)存储在A的位置h(k)中， $A[h(k)] = (k, v)$ 。

在哈希函数h处理过程中，一旦两个不同的key生成了相同的输出，即h(k) = h(p)， $k\neq p$ ，则产生冲突(collision)。针对冲突有特定的处理方法，但是一个好的哈希函数会避免产生冲突。

一般来说，哈希函数被分为两部分，分别是

哈希编码hash code
压缩函数compression function

哈希编码负责将键k映射成一个整数，压缩函数负责将映射成的整数转换为[0, N-1]中间的一个整数，成为bucket array的一个索引。这种区分的优势在于编码部分的计算可以独立于哈希表的尺寸，因此可以开发出通用的适用于任何尺寸哈希表的编码方法。而压缩函数依赖于哈希表的尺寸。

哈希编码hash code

(2022.05.10 Tue)
哈希编码的作用是把key k转变为一个整数，可以不在桶序列的长度范围内，可以是负数。哈希编码要尽量避免编码后的key产生冲突，压缩函数将无法处理负数。
用位表达作为整数哈希编码
对于可以用二进制表达的数据类型，简单的使用其二进制代表/转译(interpretation)的整数作为哈希编码，比如key 341的哈希编码是341，浮点型键的哈希编码是其二进制位的整数型。

对于本身二进制转译小于哈希编码长度的可以使用上面方法。如果二进制转译长于哈希编码的要求，可采用下面方法。Python依赖于32位哈希编码，如果一个float型的二进制转译达到64位，则可以简单的使用前32位(high-order proportion)/后32位(low-order proportion)来作为哈希编码，忽略一半的信息。

一个更好的方法是将前32位和后32位做求和/亦或(^)操作，忽略溢出(overflow)。

但该方法对于string类型处理不够友好，比如对于组合相同但排列不同的字符串，e.g., 'stk', 'kts', 'tks'等，会产生冲突。

多项式哈希编码polynomial hash code
前面提到的用二进制转译作为哈希编码的方案对于字符处理不友好，这里引入多项式哈希编码(phc)应对字符型的编码。有 $a\neq 1$ ，某数据类型的二进制表达可以写成n-tuple的形式，即 $(x_0, x_1, ..., x_{n-1})$ ，则其phc可写为 $x_0a^{n-1}+x_1a^{n-2}+\cdots+x_{n-2}a+x_{n-1}$
考虑到计算机采用有限位数表达(finite bit representation)，phc得到的结果会周期性的溢出，进而产生冲突。实验表明， $a$ 取值在33，37，39和41时，对英语单词生成的哈希编码的冲突比较小。

循环转变哈希编码cyclic-shift hash code
多项式编码中的乘法，可被循环变化哈希编码替换。所谓循环变化，值得是对数据二进制表达的队首/队尾p位数字挪到对尾/对首。比如二进制数10101111的前3位挪到队尾是01111101。尽管这种转换毫无算数意义，但是可以实现编码。Python中的移位操作符是<<和>>。下面是实现方法。

def cyclic_shift(s):
    mask = (1 << 32) - 1 # 32位都是1
    h = 0
    for character in s:
        h = (h << 5 & mask) | (h >> 27)
        h += ord(character) # ord返回对象的ascii码，与chr相对
    return h

实验表明，移动5位时，对英语单词来说产生的冲突最小。

Python中的hash实现
Python中通过函数hash实现hash编码，使用的是前面介绍的多项式异或哈希编码。注意哈希编码的对象是不可变对象(immutable)，比如str，数字，tuple，frozenset。这种设置的目的是保证对象在生命周期内的哈希编码保持不变。如果输入为可变对象，则返回类型错误TypeError。

hash函数对应的魔术方法是__hash__。注意实现过程中保证输入是不可变对象

def __hash__(self):
    return hash((self._red, self._yellow, self._blue)) #rgb三色的值封装成tuple做hash

压缩函数compression function

哈希编码返回的结果因其范围未必符合桶序列的index范围而无法直接使用，需要压缩函数对哈希编码的结果范围做压缩，作为哈希函数的第二个步骤。

除法the division method
除法，将整数 $i$ 映射到 $i \space mod \space N$
其中的 $N$ 是桶序列的长度，固定正整数。注意到如果 $N$ 非素数则有大概率发生冲突，取素数prime将有利于将映射后的值尽可能分布在不同的值上。尽管如此，当哈希编码的分布有重复结构如 $p_iN+q$ ，则冲突将不可避免。
MAD
MAD, multiply-add-and-divide，这种方法用于消除前面方法中出现哈希编码有重复结构的情况。将哈希编码后的整数i映射到 $[(ai+b) \space mod \space p] \space mod \space N$
其中 $p$ 为素数，且 $p>N$ ，a和b随机取自 $[0, p-1]$ ， $a>0$

冲突处理方法collision-handling scheme

separate chaining
最简单的方法是在桶序列中加入新的容器，即一旦出现冲突，就在桶序列中的每个节点上加入一个新的由list实现的映射。这种冲突解决方案被称为separate chaining。

最坏的情况下，在一个bucket上的操作时间正比于每个bucket上容器的长度。假定我们使用了区分良好的哈希函数，对 $n$ 个键做哈希，桶序列的长度是 $N$ ，则每个bucket上的期望长度是 $n/N$ ，操作复杂度是 $O(\lceil n/N \rceil)$ 。这里定义 $\lambda = n/N$ 为加载因子load factor，该比例最好低于1，这样可以保证对哈希表的操作复杂度保持在 $O(1)$ 。实践证明load factor应该保持低于0.9。

open addressing开放寻址
前面介绍的处理冲突方法的缺点在于，对桶单元建立了新的数据结构，占用了更多的空间。对于存储空间受限的应用，显然不是一个最优选项。这里引入开放寻址oa的方法。oa法要求load factor最大为1，数据都保存在桶单元中。该方法有多个变体，下面介绍linear probing。

Linear probing and variants
向桶序列的位置 $j$ 插入数据 $(k, v)$ 时该位置已经被占据，也就是 $j = h(k)$ ，且 $A[j] \neq None$ ，下一步查看位置 $A[ ( j+1) \space mod \space N]$ 是否为空，如果是则填充数据，如果否则继续向下一个位置寻找 $A[ ( j+2) \space mod \space N]$ ，以此类推。这种方法要求修改__getitem__，__setitem__，__delitem__这几个特殊方法。当查找映射为 $j$ 的元素时，需要检测从 $A[j]$ 开始的连续元素，直到找到匹配键值或找到空bucket。

对于删除元素的情况考虑如下bucket array，该序列中 $A[4] = 26, A[5]= 5, A[6] = 37, A[7] = 16, A[8] = None$ ，有 $h(k) = 4$ 。当向桶序列中插入这个哈希值，则一次检查4,5,6,7,8这些位置，直到位置8发现空值，则向位置8插入 $(k, v)$ 。在插入数据之后，清理 $A[6]$ 的值37。如果仅仅将该位置对应的元素清空，则在查找位于位置8的 $(k, v)$ 时会出现错误，因为位置6已经为空，检索到此就结束检索。为应对这种情况，在位置6设置'available' marker对象。有了该marker对象占位，当进行检索时，可设置算法跳过标记了可用marker的对象位置，直到找到需要检索的位置。同时在设置桶序列的值时，即在__setitem__方法中，需要明确拥有了marker对象的位置是可以用来赋值的。

linear probing的缺点是会导致映射值聚集(map clusters)，即在桶序列上连续运行，降低检索效率。

实验证明linear probing的load factor应该保持在 $\lambda < 0.5$ 。其他open addressing方案可以略高，python自带的方法强制要求 $\lambda < 2/3$

针对映射值聚集的问题，还出现了quadratic probing，double hashing等方法。而Python的dict对象中使用的方法是迭代的尝试 $A[(h(k) + f(i)) \space mod \space N]$ ，其中 $f(i)$ 基于伪随机数生成器，可提供随机但却可重复进行的随机数序列，该序列基于初始hash编码。

Python实现

(2022.05.11 Wed)
实现哈希表的过程中我们有如下预先处理和假定：

hash function的hash code部分使用Python自带的函数hash
hash function的compression function部分使用MAD方法，即 $[(ai+b) \space mod \space p] \space mod \space N$ ，其中 $p$ 为素数，且 $p>N$ ，a和b随机取自 $[0, p-1]$ ， $a>0$
冲突处理分别采用separate chaining实现
bucket array采用Python的list实现，标记为self._table，初始元素都标记为None
定义self._n是哈希表中的distinct元素数目
如果load factor $\lambda$ 超过0.5，则double表尺寸并且rehash所有元素

内置方法说明：

_bucket_getitem(j, k)：检索桶的索引j是否有key k，返回关联值如果有的话，没有的话返回KeyError
_bucket_setitem(j, k, v)：修改桶索引j对应的key k，使其关联值变为v，如果存在则覆盖，如果不存在则加入，该方法负责对self._n的修改
_bucket_delitem(j, k)：删除桶索引j对应的key k，没有则返回KeyError
__item__：略

首先根据前文的基类MapBase生成hash基类HashMapBase

from random import randrange
class HashMapBase(MapBase):
    def __init__(self, cap=11, p=109345121):
        self._table = cap * [None]
        self._n = 0
        self._prime = p # MAD prime
        self._scale = 1 + randrange(p-1) # MAD para
        self._shift = randrange(p) # MAD para
    def _hash_function(self, k):
        return (hash(k)*self._scale + self._shift) % self._prime % len(self._table)
    def __len__(self):
        return self._n
    def __getitem__(self, k):
        j = self._hash_function(k)
        return self._bucket_getitem(j, k)
    def __setitem__(self, k, v):
        j = self._hash_function(k)
        self._bucket_setitem(j, k, v)
        if self._n > len(self._table) // 2:
            self._resize(2 * len(self._table) - 1)
    def __delitem__(self, k):
        j = self._hash_function(k)
        self._bucket_delitem(j, k)
        self._n -= 1
    def _resize(self, c):
        old = list(self.items())
        self._table = c * [None]
        self._n = 0 
        for (k,v) in old:
            self[k] = v
    def __iter__(self):
        super().__iter__(*args)

实现separate chaining类

class ChainHashMap(HashMapBase):
    def _bucket_getitem(self, j, k):
        bucket = self._table[j]
        if bucket is None:
            raise KeyError('key error ' + repr(k))
        return bucket[k]
    def _bucket_setitem(self, j, k, v):
        if self._table[j] is None:
            self._table[j] = UnsortedTableMap
        print(0)
        oldsize = len(self._table[j])
        print(1)
        self._table[j][k] = v
        print(2)
        if len(self._table[j]) > oldsize:
            self._n += 1
    def _bucket_delitem(self, j, k):
        bucket = self._table[j]
        if bucket is None:
            raise KeyError('key error')
        del bucket[k]
    def __iter__(self):
        for bucket in self._table:
            if bucket is not None:
                for key in bucket:
                    yield key

to-do：Python3.9环境中，实例化后赋值时返回TypeError: object of type 'ABCMeta' has no len()

Reference

1 Goodrich and etc., Data Structures and Algorithms in Python