在 python3 中hash

help(hash)Help?on?built-in?function?hash?in?module?builtins:hash(obj,?/)Return?the?hash?value?for?the?given?object.#返回給定對(duì)象的哈希值Two?objects?that?compare?equal?must?also?have?the?same?hash?value,?but?thereverse?is?not?necessarily?true.#兩個(gè)比較相等的對(duì)象也必須有相同的散列值，但是逆轉(zhuǎn)不一定是正確的。

????Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-p_w_picpath），通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。

????一個(gè)典型的空間換時(shí)間的算法，根據(jù)哈希出來的關(guān)鍵字進(jìn)行快速的查詢

構(gòu)造方法：

????① 直接尋址法

????????取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，

????????其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）

????② 數(shù)字分析法

????????分析一組數(shù)據(jù)的某些特征，比如，比如在學(xué)校里用學(xué)生的年齡來作為標(biāo)識(shí)的話，會(huì)有很大

????????的沖突率，如果利用學(xué)生的學(xué)號(hào)作為標(biāo)識(shí)的話，沖突率就會(huì)大大下降，因此數(shù)字分析就是

????????找出這些特征的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)成沖突幾率較低的散列地址

????③ 平方取中法

????????先平方 后取中 生成散列地址

????④ 折疊法

????????均勻分割 分別取和 生成散列地址

????⑤ 隨機(jī)數(shù)法

????????選擇一隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)值作為散列地址，通常用于關(guān)鍵字長(zhǎng)度不同的場(chǎng)合。

????⑥ 除留余數(shù)法

????????取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) =?

????????key MOD p, p<=m。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。

????????對(duì)p的選擇很重要，一般取素?cái)?shù)或m，若p選的不好，容易產(chǎn)生同義詞。

處理沖突的方法

? ?① 開放尋址法：Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中H(key)為散列函數(shù)，m為散列表長(zhǎng)，

????di為增量序列，可有下列三種取法：? ?

????1).di=1,2,3,…，m-1，稱線性探測(cè)再散列；

????2)． di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)稱二次探測(cè)再散列；

????3)． di=偽隨機(jī)數(shù)序列，稱偽隨機(jī)探測(cè)再散列。

????② 再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函數(shù)，即在同義詞產(chǎn)生地址沖突

????? 時(shí)計(jì)算另一個(gè)散列函數(shù)地址，直到?jīng)_突不再發(fā)生，這種方法不易產(chǎn)生“聚集”，但增加了計(jì)

??????算時(shí)間。

????③ 鏈地址法（拉鏈法）

????④ 建立一個(gè)公共溢出區(qū)

轉(zhuǎn)載于:https://blog.51cto.com/zj734627415/1931913

總結(jié)

以上是生活随笔為你收集整理的python hash的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。