Hash

稱散列、哈希，基本原理就是把任意長度的輸入，通過Hash算法變成固定長度的輸出。這個映射的規則就是對應的Hash算法，而原始數據映射後的二進制串就是哈希值。開發中經常使用的MD5和SHA都是歷史悠久的Hash算法。

hash算法必備

• 從hash值不可以反向推導出原始的數據
• 經過映射後的數據和原始數據沒有對應關係
• 輸入數據的微小變化會得到完全不同的hash值，相同的數據會得到相同的值
• 可以看到我們只改了一個文字，但是整個得到的hash值產生了非常大的變化。
• 哈希算法的執行效率要高效，長的文本也能快速地計算出哈希值
• hash算法的衝突概率要小

由於hash的原理是將輸入空間的值映射成hash空間內，而hash值的空間遠小於輸入的空間。根據抽屜原理，一定會存在不同的輸入被映射成相同輸出的情況。那麼作為一個好的hash算法，就需要這種衝突的概率儘可能小。

hash算法是一定會有衝突的

Hash算法原理

• 一致性哈希將整個哈希值空間組織成一個虛擬的圓環，如假設某哈希函數H的值空間為0-2^32-1（即哈希值是一個32位無符號整形），整個哈希空間環如下：
• 整個空間按順時針方向組織。0到2的32次方減1，即：2^{32} -1，在零點中方向重合。

一致性hash算法

• 一致性hash算法，是麻省理工學院1997年提出的一種算法，目前主要應用於分佈式緩存當中。
• 一致性hash算法可以有效地解決分佈式存儲結構下動態增加和刪除節點所帶來的問題。
• 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都採用了一致性hash算法，可以說一致性hash算法是分佈式系統負載均衡的首選算法。
• 解決一致性hash的負載不均問題，也可以利用虛擬層的概念，將每臺物理緩存服務器虛擬成一組虛擬緩存服務器，再將虛擬的hash值放在hash環上。每次查詢時，先找到虛擬的緩存服務器key值，再通過該值找到物理服務器信息。

這樣新加入緩存服務器時，是加入一組虛擬服務器，如果數量足夠多的話，這個新加入的緩存服務器會均勻的影響原有的緩存服務器。

實際工作中，當數據表超過500萬條或更多時，一般就會考慮到採用分庫分表；

系統使用了一臺緩存服務器還是不能滿足的時候，通常會使用多臺緩存服務器，需要考慮如何去訪問背後的庫表或緩存服務器呢，我們會在存取的時候使用相同的哈希算法定位到具體的位置。

閱讀更多 天天面試題 的文章

關鍵字: 算法 基礎 Memcached