算法_散列

墨蓝 2023-02-18 01:57 47阅读 0赞

## 散列：Hashing ##

### 引入散列 ###

*  通过构造一个新的数据结构，能使得查找算法的复杂度降到O(1)，这种概念称为“散列Hashing”
 *  如果我们事先能知道要找的数据项应该出现在数据集的什么位置，就可以直接到哪个位置看看数据项是否存在即可

### 散列：基本概念 ###

*  散列表（hash table）是一种数据集，其中数据项的存储方式尤其有利于将来快速的查找定位
 *  散列表中的每一个存储位置，称为槽（slot），可用来保存数据项，每个槽有一个唯一的名称

例如：一个包含11个槽的散列表，槽的名称分别为0~10，在插入数据项之前，每个槽的值都是None，表示空槽

![空槽][20200615121416266.png]

实现从数据项到存储槽名称的转换的，称为散列函数（hash function）

*  有一种常见的散列方法是“求余数”，将数据项除以散列表的大小，得到余数作为槽号
 *  实际上“求余数”方法会以不同形式出现在所有散列函数里，因为散列函数返回的槽号必须在散列表大小范围之内，所以一般会对散列表大小求余
 *  槽被数据项占据的比例称为散列表的“负载因子”

![负载因子][20200615180035621.png]

*  数据项都保存到散列表后，要查找某个数据项是否存在表中，只需要使用同一个散列函数，对查找项进行计算，测试下返回的槽号所对应的槽中是否有数据项即可。实现了O(1)时间复杂度的查找算法
 *  假如还要保存44，h(44)=0，它会跟77被分配到同一个槽中，这种情况称为“冲突collision”

### 完美散列函数 ###

完美散列函数：对于一组给定的数据项，一个散列函数可以将每一个数据项映射到不同的槽中

*  获得完美散列函数的一种办法是扩大散列表的容量，大盗所有可能出现的数据项都能够占据不同的槽。但这种方法对于可能数据项范围过大的情况并不适用
 *  退而求其次，好的散列函数需要具备特性：冲突最少（近似完美）、计算难度低（额外开销小）、充分分散数据项（节约空间）
 *  由于完美散列函数能够对任何不同的数据生成不同的散列值，如果把散列值当做数据“指纹”或者“摘要”，这种特性被广泛应用在数据的一致性校验上
 *  作为一致性校验的数据“指纹”函数需要具备如下的特性：
    
    1.  压缩性：任意长度的数据。得到的“指纹”长度是固定的
    2.  易计算性：从原数据计算“指纹”很容易，从指纹计算原数据是不可能的
    3.  抗修改性：对原数据的微小变动，都会引起“指纹”的大修改
    4.  抗冲突性：已知原数据和“指纹”，要找到相同指纹的数据（伪造）是非常困难的

**散列函数MD5/SHA**

*  最著名的近似完美散列函数是MD5和SHA系列函数
 *  MD5（Message Digest）将任何长度的数据变换为固定长为128位（16字节）的摘要
 *  SHA（Secure Hash Algorithm）是另一组散列函数
    
    1.  SHA-0 / SHA-1 输出散列值160位（20字节）
    2.  SHA-256 / SHA-224 分别输出256位、224位
    3.  SHA-512 / SHA-384 分别输出512位、384位

**Python的散列函数库hashlib**

Python自带MD5和SHA系列的散列函数库：hashlib

*  包括md5 / sha1 / sha224 / sha256 / sha384 / sha512等6种散列函数

>>> import hashlib
    # hashlib.md5(data)函数，data参数的类型应该是bytes
    # hash前必须把数据转换成bytes类型
    >>> hashlib.md5("hello world!".encode("utf-8")).hexdigest()
    'fc3ff98e8c6a0d3087d515c0473f8677'
    >>> hashlib.sha1("hello world!".encode("utf-8")).hexdigest()
    '430ce34d020724ed75a196dfc2ad67c77772d169'

除了对单个字符进行散列计算之外，还可以用update方法对任意长的数据分部分来计算，这样不管多大的数据都不会有内存不足的问题

>>> import hashlib
    >>> m = hashlib.md5()
    >>> m.update("hello world!".encode("utf-8"))
    >>> m.update("this is part #2".encode("utf-8"))
    >>> m.update("this is part #3".encode("utf-8"))
    >>> m.hexdigest()
    'a12edc8332947a3e02e5668c6484b93a'

## 散列函数应用：区块链 ##

*  区块链是一种分布式数据库，通过网络连接的节点，每个节点保存着整个数据库所有数据，任何地点存入的数据都会完成同步
 *  区块链最本质特征是”去中心化“，不存在任何控制中心、协调中心节点，所有的节点都是平等的，无法被控制
 *  区块链由一个个区块（block）组成，区块分为头（head）和体（body）
 *  区块头记录一些元数据和链接到前一个区块的信息：生成时间、前一个区块（head+body）的散列值

![区块体记录了实际数据][20200615184536347.png]

*  由于散列具有抗修改性，任何对某个区块数据的改动必然引起散列值的变化。为了不导致这个区块脱离链条，就需要修改所有后续的区块。由于有“工作量证明”的机制，这种大规模修改不可能实现，除非掌握了全网51%以上的计算力

工作量证明：Proof of Work(POW)

*  由于区块链是大规模的分布式数据库，同步较慢，新区块的添加速度需要得到控制。目前最大规模区块链Bitcoin采用的速度是平均每10分钟生成一个区块
 *  大家不惜付出海量的计算，去抢着算出一个区块的有效散列值，最先算出的那位“矿工”才有资格把区块挂到区块链中
 *  因为有效散列值很难算出，所以控制了新区块生成的速度，便于在整个分布式网络中进行同步
 *  每个区块设置了一个难度系数Difficulty，用常数targetmax除以它，得到一个target，难度系数越高，target越小
 *  矿工的工作是，找到一个数值Nonce，把它跟整个区块数据一起计算散列，这个散列值必须小于target，才是有效的散列值
 *  由于散列值无法回推原值，这个Nonce的寻找只能靠暴力穷举，计算工作量+运气是唯一的方法
 *  在加密货币Bitcoin中，区块内包含的数据是“交易记录”，也就是“账本”，对于货币体系至关重要
 *  由于硬件摩尔定律存在，计算力将持续递增，为了维持每10分钟生成一个区块的速度，难度系数Difficulty也将持续递增。另外，为了保持货币总量不会无限量增加，每4年奖励的比特币减半

## 散列函数设计 ##

### 折叠法 ###

*  将数据项按照位数分为若干段，再将几段数字相加，最后对散列表大小求余，得到散列值

例如，对电话号码62767255，可以两位两位分成4段（62、76、72、55）相加（62+76+72+55=265），散列表包括11个槽，那么就是265%11=，所以h(62767255)=1

有时候折叠法还会包括一个隔数反转的步骤。比如 (62、76、72、55) 隔数反转为(62、67、72、55)，再累加 (62+67+72+55=256)，对11求余 (256%11=3)，所以h’(62767255)=3

*  虽然隔数反转从理论上看来毫无必要，但这个步骤确实为折叠法得到散列函数提供了一种微调手段，以便更好符合散列特性

### 平方取中法 ###

*  首先将数据项做平方运算，然后取平方数的中间两位，再对散列表的大小求余

例如，对44进行散列，首先44\*44=1936，然后取中间的93，对散列表大小11求余，93%11=5

### 非数项 ###

我们也可以对非数字的数据项进行散列，把字符串中的每个字符看作ASCII码即可

例如cat，ord(‘c’)==99，ord(‘a’)==96，ord(‘t’)==116，再将这些整数累加，对散列表大小求余：99+97+116=312，312%11=4

def hash(astring, tablesize):
        sum = 0
        for pos in range(len(astring)):
            sum += ord(astring[pos])
        return sum%tablesize
    
    print(hash('cat',11)) # 4

上述方法对所有的变位词都返回相同的散列值，为了防止这一点，可以将字符串所在的位置作为权重因子，乘以ord值。例如：`99*1+97*2+116*3=641`，641%11=3

总结：

设计散列函数方法的一个基本出发点就是散列函数不能成为存储过程和查找过程的计算负担，如果散列函数设计太过复杂，去花费大量的计算资源计算槽号，就失去了散列本身的意义

## 冲突解决方案 ##

### 空槽\_开放定址 ###

*  如果两个数据项被散列映射到同一个槽，需要一个系统化的方法在散列表中保存第二个数据项，这个过程称为“解决冲突”（如果是完美散列函数则不会有散列冲突）
 *  解决散列的一种方法就是为冲突的数据项再找一个开放的空槽来保存。最简单的就是从冲突的槽开始往后扫描，直到碰到一个空槽，如果散列表尾部还未找到，则从首部接着扫描
 *  这种寻找空槽的技术称为“开放定址open addressing”，向后逐个槽寻找的方法则是开放定址中的“线性探测linear probing”
    
    ![线性探测][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70]
 *  采用线性探测方法来解决散列冲突的话，则散列表的查找也遵循同样的规则。如果在散列位置没有找到查找项的话，就必须向后做顺序查找，直到找到查找项，或者碰到空槽（查找失败）
 *  线性探测法的一个缺点是有聚集（clustering）的趋势
 *  避免聚集的一种方法就是讲线性探测扩展，从逐个探测改为跳跃性探测。下图是“+3” 探测插入44,55,20
    
    ![跳跃性探测][20200615234550864.png]
 *  重新寻找空槽的过程可以用一个更为通用的“再散列rehashing”来概括
    
    newhashvalue = rehash(oldhashvalue)
    
    对于线性探测：rehash(pos) = (pos+1) % sizeoftable
    
    对于跳跃式探测的再散列通式是：rehash(pos) = (pos+skip) % sizeoftable
 *  跳跃式探测中，需要注意的是skip的取值，不能被散列表大小整除，否则会产生周期，造成很多空槽永远无法探测到。一个技巧是把散列表的大小设为素数，如11
 *  还可以将线性探测变为“二次探测quadratic probing”，不再固定skip的值，而是逐步增加skip值，如1,3,5,7,9，这样槽号就会是原散列值以平方数增加：h, h+1, h+4, h+9, h+16

### 数据项链Chaining ###

*  除寻找空槽的开放定址技术之外，另一种解决散列冲突的方案是将容纳单个数据项的槽扩展为容纳数据项集合(或者对数据项链表的引用)
 *  这样散列表中的每个槽就可以容纳多个数据项，如果有散列冲突发生，只需要简单地将数据项添加到数据项集合中
 *  查找数据项时则需要查找同一个槽中的整个集合，当然，随着散列冲突的增加，对数据项的查找时间也会相应增加  
    ![数据项链][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 1]

## 抽象数据类型“映射”：ADT Map ##

映射：它以一个密钥与一个数据值之间关联的无序集合作为结构。映射中的密钥都是独特的，以保证和数据值之间的一一对应关系。映射有以下相关操作：

*  `Map()` 产生一个新的空映射，返回一个空映射的集合
 *  `Put(key,val)` 往映射中添加一个新的密钥-数据值对。如果密钥已经存在，那么将旧的数据值置换为新的
 *  `get(key)` 给定一个key值，返回关联的数据，若不存在，返回None
 *  `del` 从映射中删除一个密钥-数据值对，声明形式为 `del map[key]`
 *  `len()` 返回映射中的存储密钥-数据值对的个数
 *  `in` 当表述是 `key in map` ，返回 `True` 否则返回 `False`

class HashTable:
        def __init__(self):
            self.size = 11
            # 槽，用来存储密钥
            self.slots = [None] * self.size
            # 平行表，用来存储数据值
            self.data = [None] * self.size
    
        def put(self, key, data):
            # 假设最终一定能找到一个能让新的密钥填入的槽，除非它已经在self.slots中存在
            hashvalue = self.hashfunction(key)
    
            # key不存在，未冲突
            if self.slots[hashvalue] == None:
                self.slots[hashvalue] = key
                self.data[hashvalue] = data
            else:
                # key已存在，替换val
                if self.slots[hashvalue] == key:
                    self.data[hashvalue] = data
                else:
                    nextsolt = self.rehash(hashvalue)
                    # 散列冲突，再散列，直到找到空槽或者key
                    while self.slots[nextsolt] != None and self.slots[nextsolt] != key:
                        nextsolt = self.rehash(nextsolt)
                        if self.slots[nextsolt] == None:
                            self.slots[nextsolt] = key
                            self.data[nextsolt] = data
                        else:
                            self.data[nextsolt] = data
    
        def hashfunction(self, key):
            return key % self.size
    
        def rehash(self, oldhash):
            return (oldhash+1) % self.size
    
        def get(self, key):
            # 标记散列值为查找起点
            startslot = self.hashfunction(key)
            data = None
            stop = False
            found = False
            position = startslot
            # 找到key，直到空槽或回到起点
            while self.slots[position] != None and not found and not stop:
                if self.slots[position] == key:
                    found = True
                    data = self.data[position]
                else:
                    # 未找到key,再散列，继续找
                    position = self.rehash(position)
                    if position == startslot:
                        # 回到起点，停
                        stop = True
            return data
    
        def __getitem__(self, key):
            return self.get(key)
    
        def __setitem__(self, key, data):
            self.put(key, data)
    
    
    H = HashTable()
    H[54] = 'cat'
    H[26] = 'dog'
    H.put(44, 'bird')
    print(H.slots) # [44, None, None, None, 26, None, None, None, None, None, 54]
    print(H.data) # ['bird', None, None, None, 'dog', None, None, None, None, None, 'cat']
    print(H.get(44)) # bird

散列算法分析：

*  散列在最好的情况下，可以提供O(1)常数级时间复杂度的查找性能。由于散列冲突的存在，查找比较次数就没有那么简单
 *  评估散列冲突的最重要信息就是负载因子λ，一般来说：
    
    如果λ较小，散列冲突的几率就小，数据项通常会保存再其所属的散列槽中
    
    如果λ较大，意味着散列表填充较满，冲突会越来越多，冲突解决也越复杂，也就需要更多的比较来找到空槽；如果采用数据链的话，意味着每条链上的数据项增多

![算法分析][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 2]

[20200615121416266.png]: https://img-blog.csdnimg.cn/20200615121416266.png
[20200615180035621.png]: https://img-blog.csdnimg.cn/20200615180035621.png
[20200615184536347.png]: https://img-blog.csdnimg.cn/20200615184536347.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615234048421.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[20200615234550864.png]: https://img-blog.csdnimg.cn/20200615234550864.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200615235609771.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200616125530100.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70