精品综合国产一区二区三区码码_美女视频图片一区二区三区_ZZIJZZIJ亚洲日本少妇_久久人妻精品一区_国产乱人偷精品人妻_亚洲一区二区三区爽爽爽_国产一区二区三区欧美亚洲_午夜多人内射国产精品一区二区援交视频_成年人免费看黄色视频高潮片_亚洲a人成_一级黄色电影免费无码_欧美成人久久久_亚洲一区二区三区四区五区xx_色婷婷激情一区二区三区_一级片一级片一级片一级片

對(duì)于輸入值的可逆“混合”運(yùn)算而得到。

常用HASH函數(shù)

·直接取余法：f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一個(gè)質(zhì)數(shù)。

·乘法取整法：f(x):=trunc((x/maxX)*maxlongit) mod maxM，主要用于實(shí)數(shù)。

·平方取中法：f(x):=(x*x div 1000 ) mod 1000000); 平方后取中間的，每位包含信息比較多。

構(gòu)造方法

散列函數(shù)能使對(duì)一個(gè)數(shù)據(jù)序列的訪問(wèn)過(guò)程更加迅速有效，通過(guò)散列函數(shù)，數(shù)據(jù)元素將被更快地定位。

（詳細(xì)構(gòu)造方法可以參考hash函數(shù)中的【哈希表的構(gòu)造方法】）

1．直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）

2． 數(shù)字分析法

3． 平方取中法

4． 折疊法

5． 隨機(jī)數(shù)法

6． 除留余數(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)生同義詞。

處理沖突方法

1．開(kāi)放尋址法；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，稱(chēng)線性探測(cè)再散列；

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

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

2． 再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)散列函數(shù)地址，直到?jīng)_突不再發(fā)生，這種方法不易產(chǎn)生“聚集”，但增加了計(jì)算時(shí)間。

3． 鏈地址法(拉鏈法)

4． 建立一個(gè)公共溢出區(qū)

查找性能分析

散列表的查找過(guò)程基本上和造表過(guò)程相同。一些關(guān)鍵碼可通過(guò)散列函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵碼在散列函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過(guò)程。所以，對(duì)散列表查找效率的量度，依然用平均查找長(zhǎng)度來(lái)衡量。

查找過(guò)程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：

1．散列函數(shù)是否均勻；

2. 處理沖突的方法；

3．散列表的裝填因子。

散列表的裝填因子定義為：α= 填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度

α是散列表裝滿(mǎn)程度的標(biāo)志因子。由于表長(zhǎng)是定值，α與“填入表中的元素個(gè)數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。

實(shí)際上，散列表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。

了解了hash基本定義，就不能不提到一些著名的hash算法，MD5和SHA-1可以說(shuō)是應(yīng)用最廣泛的Hash算法，而它們都是以MD4為基礎(chǔ)設(shè)計(jì)的。

常用hash算法的介紹：

（1)MD4

MD4(RFC 1320)是 MIT 的Ronald L. Rivest在 1990 年設(shè)計(jì)的，MD 是 Message Digest（消息摘要） 的縮寫(xiě)。它適用在32位字長(zhǎng)的處理器上用高速軟件實(shí)現(xiàn)——它是基于 32位操作數(shù)的位操作來(lái)實(shí)現(xiàn)的。

（2)MD5

MD5(RFC 1321)是 Rivest 于1991年對(duì)MD4的改進(jìn)版本。它對(duì)輸入仍以512位分組，其輸出是4個(gè)32位字的級(jí)聯(lián)，與 MD4 相同。MD5比MD4來(lái)得復(fù)雜，并且速度較之要慢一點(diǎn)，但更安全，在抗分析和抗差分方面表現(xiàn)更好。

（3)SHA-1及其他

SHA1是由NIST NSA設(shè)計(jì)為同DSA一起使用的，它對(duì)長(zhǎng)度小于2^64的輸入，產(chǎn)生長(zhǎng)度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設(shè)計(jì)時(shí)基于和MD4相同原理,并且模仿了該算法。