数据结构与算法 6.哈希

哈希(散列)

Hash是把任意长度的输入(预映射)通过散列算法变换成固定长度的输出,该输出就是散列值
不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值
Hash算法可以将一个数据转换为一个标志,这个标志和数据源的每一个字节都有关
Hash算法很难找到逆向规律
Hash算法是一个广义的算法,也可以认为是一种思想,使用Hash算法可以提高存储空间的利用率和提高数据查询效率

哈希表 Hash Table

是根据关键码值(key value)直接进行访问的数据结构

添加、搜索、删除的流程都是类似的
    1.利用哈希函数生成key对应的index(O(1))
    2.根据index操作定位序列中的元素(O(1))

哈希表是空间换时间的应用
哈希表内部的元素,也叫Bucket(桶),整个序列叫Buckets或Bucket Array

哈希冲突 Hash Collision

哈希冲突,也叫哈希碰撞,2个不同的key,经过哈希函数计算出相同的结果
key1 != key2 , hash(key1) = hash(key2)

解决哈希冲突的常用方法
    1.开放定址(Open Addressing):按照一定规则向其他地址探索,直至遇到空桶
    2.再散列(Re-Hashing):设计多个哈希函数
    3.链地址(Separate Chaining):通过链表将同一index的元素串起来

哈希函数

哈希表中哈希函数的实现步骤如下
    1.先生成key的哈希值(必须是整数)
    2.用key的哈希值与序列的大小进行运算,生成一个索引值(索引值需要在序列内,所以要与序列长度运算)
        (1).hash_code(key) % len(table) (取模运算效率较低)
        (2).hash_code(key) & (len(table) - 1) 
            需要将序列的长度设计为 2^n,因为 2^n - 1 在二进制中值全部为 1,任何数 & 1*n 都等于该数的后n位 
            本质是取出hash_code(key)二进制格式的后n位,此值取值范围一定在 0*n - 1*n (如:0000-1111) 之间
            
良好的哈希函数
    哈希值分布更均匀 => 减少哈希冲突 => 提升哈希表的性能

常用算法
    MD4、MD5、SHA-1

生成key的哈希值

key的常见类型:
    str、int、float、自定义对象

不同类型的key,生成哈希值的方式不同,但目标是一致的
    1.尽量让每个key的哈希值是唯一的
    2.尽量让key中所有信息都参与运算
    
int
    用该整数值本身作为哈希值
    
float
    将浮点数的二进制格式转为整数值,该整数值为哈希值
    
Long 和 Double (8个字节,64位) 
    int(value ^ (value >>> 32))
    哈希值必须是int类型(4个字节),也就是32位,需要让Long和Double的64位都参与运算
    value >>> 32 :取出value的高 32bit
    value ^ (value >>> 32) : 高 32bit 与低 32bit 运算得出 32bit 的哈希值
        & : 可能只取出低 32bit
        | : 可能只取出高 32bit
        
str
    ABCD   =>   A*n^3 + B*n^2 + C*n^1 + D*n^0   =>   [(A*n + B)*n + C]*n + D  
    字符的本质就是一个整数(每个字符都有对应的ASCII值)
    乘数n取31,31是一个奇素数,31*i == (i << 5) - i
生成str的哈希值
def hash_code(s):
    hash_s = 0
    for i in s :
        c = ord(i)
        hash_s = (hash_s << 5) - hash_s + c
    return hash_s
r = 'a1b2c3'
res = hash_code(r)
print(res)

2825250864
上一篇:【算法习作】字符串处理两例


下一篇:求最小外接矩形的面积(C++实现)