数据结构与算法 6.哈希

本文主要是介绍数据结构与算法 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

这篇关于数据结构与算法 6.哈希的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！