資料結構與算法 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