曲演雜壇--HASH的一點理解

看見就非常 2015-05-25

展開全文

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

Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡模褪前讶我忾L度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

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

--==========================================================
SELECT CHECKSUM('SLDKSLKFJDSLKJFDSLAKJF;DSAKLFJDSJASLKF S')
--值為244224724

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

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

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

--====================================
--準備測試數據
SELECT name INTO HB001
FROM sys.all_objects

--===================================
--查看測試數據
SELECT name AS SourceValue,
CHECKSUM(name) AS HashKey,
ABS(CHECKSUM(name)%1000) AS HashBucket
,FROM HB001
ORDER BY HashBucket

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