曲演雜壇--HASH的一點(diǎn)理解

2024-07-21 02:49:58

字體：大中小

供稿：網(wǎng)友

HASH，百度百科上做如下定義：

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預(yù)映射， PRe-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。

如此生硬的定義很難理解，我們來點(diǎn)看的見的，CHECKSUM就是一種典型的HASH操作

--==========================================================SELECT CHECKSUM('SLDKSLKFJDSLKJFDSLAKJF;DSAKLFJDSJASLKF S')--值為244224724SELECT CHECKSUM('中啥打算換阿盛大連水庫將盛大阿克蘇打算快樂撒旦')--值為1349490807--==============================================================SELECT CHECKSUM(REPLICATE(CAST('中啥打算換阿盛大連水庫將盛大阿克蘇打算快樂撒旦' AS nvarchar(MAX)),100000)) AS HashKey,DATALENGTH(REPLICATE(CAST('中啥打算換阿盛大連水庫將盛大阿克蘇打算快樂撒旦' AS nvarchar(MAX)),100000)) AS DataLength--HashKey=438180382--DataLength=4600000

使用CHECKSUM函數(shù)，我們可以很容易根據(jù)一個(gè)任意長度的字符串得到一個(gè)整數(shù)值，而且CHECKSUM屬于確定性函數(shù)，無論何時(shí)執(zhí)行，相同的字符串，總是能獲得同樣的整數(shù)值，CHECKSUM所得值不相同的兩個(gè)字符串一定不相同。由此，我們可以在比較兩個(gè)長字符串是否相等時(shí)，先比較CHECKSUM的值，如果CHECKSUM值不相等則判定兩個(gè)字符串不相等，如果CHECKSUM值相等則遍歷每個(gè)字符是否相等。

上述操作看起來似乎比直接比較字符串更麻煩，但是不同字符串的CHECKSUM值相等的情況并不多，因此需要遍歷每個(gè)字符判斷相等的概率會比較低。

除了散列值存儲空間更小和更容易比較外，HASH散列值還有另外一個(gè)優(yōu)點(diǎn)：固定長度和類型，如CHECKSUM返回的就是4字節(jié)的INT類型，由于類型和存儲空間相同，我們可以對散列值做進(jìn)一步操作，將散列值平均分拆到不同的存儲空間上，這樣邊有了HASH桶的概念，如我們可以將CHECKSUM返回的值做取余操作，為每個(gè)余數(shù)劃分一片區(qū)域。

--====================================--準(zhǔn)備測試數(shù)據(jù)SELECT name INTO HB001FROM sys.all_objects--===================================--查看測試數(shù)據(jù)SELECT name AS SourceValue,CHECKSUM(name) AS HashKey,ABS(CHECKSUM(name)%1000) AS HashBucket,FROM HB001ORDER BY HashBucket

當(dāng)我們有上面數(shù)據(jù)后，如果要查詢表中是否有“sp_procedure_params_rowset”,我們便可以先對“sp_procedure_params_rowset”求HashKeyH和HashBucket，先根據(jù)HashBucket找到我們要去那片區(qū)域查找數(shù)據(jù)，在根據(jù)HashKey和值去匹配這片區(qū)域的數(shù)據(jù)，因此我們需要到HashBucket=2的區(qū)域下找，而HashBucket=2的區(qū)域下有3條數(shù)據(jù)，我們只需要比較這三條數(shù)據(jù)就可以了，避免了對表中數(shù)據(jù)進(jìn)行遍歷或排序查找。