總覽

- Hash（哈希、散列）

Hash是一種 散列函數或方法 的統稱。
·
該方法就是：把任意長度的輸入通過散列算法變換成固定長度的輸出，該輸出就是散列值。—— （散列方法）
·
這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

Hash技術應用于符號表，用于構建符號表的結構、屬性填入及查找。
·
符號表： 存儲用戶標識符及其屬性信息。

之后將以符號表為例進行解析。

一、Hash函數（哈希函數、散列函數）

假定存在一個有限區域，這個區域要填寫一張含N項符號的符號表。通常希望構造一個地址函數（假定函數名為Hash，用于確定符號表中存放符號的地址），對于編譯器而言，任何符號（標識符）都有其對應的編號SYM，Hash( SYM ) 則返回一個 0 ~ N-1 間的數，以便將符號能放進符號表的限定空間內。符號表的填表和查表都依賴于 Hash( SYM ) 來獲取符號的位置。這里 Hash( SYM ) 被定義為 SYM % N，即函數返回 SYM / N 的余數。該值隨著SYM的變化，始終在0 ~ N-1 之間變化。可以說隨著SYM的變化，Hash函數返回值的集合始終在0 ~ N-1 的區間內散列分布，因此該函數被稱為散列函數，英文為Hash函數，Hash函數的返回值被稱為Hash值（散列值）。

對Hash函數的要求：

函數的計算要簡單、高效；

函數值能比較均勻地分布在 0 ~ N-1 之間。

構造Hash函數的方法有很多，通常是將符號名的編碼散列為 0 ~ N-1 之間的某一個值。由于用戶使用標識符是隨機的，而且標識符的個數也是無限的，因此，企圖構造一 一對應的函數是徒勞的。在這種情況下，除了希望函數值的分布比較均勻外，還應設法解決“地址沖突”的問題。

例如：
N = 17，Hash( SYM ) 為 SYM / N 的余數時，由于Hash( ‘05’ ) = Hash( ‘22’) = 5，此時便存在地址沖突。

符號表將Hash值相同的符號以存儲時間的先后順序，后存儲的指向先存儲的元素將其鏈接在一起。

二、Hash值（哈希值、散列值）

由以上Hash函數的介紹可知：

Hash值由Hash函數產生，即為Hash函數的返回值，是待存儲于某區間或已存儲于某區間的數據的唯一編號經過Hash函數計算之后的值，該值（Hash值）散列在目的存儲區間大小的范圍之內（如 0 ~ N-1 之間）。

在目的區間與Hash表建立映射關系之后，該區間存儲地址便與Hash值建立起了映射關系。注意該映射關系不是一 一對應的關系，因為可能存在不同的數據Hash值相同的情況。

三、HashTable（哈希表）

Hash表是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值（SYM）映射到表中一個位置來訪問記錄，以加快查找的速度。

將所有符號的哈希值對應于一個數組（表）的下標，成為哈希表。該表成為符號表中符號元素的索引表。其Hash值鏈接到該Hash值對應的符號表中的符號元素。Hash表是一個容量為N的一維數組，它的每個元素初值為null。

對于符號元素的存儲和查找，都通過Hash表進行索引，先通過Hash函數計算得到其Hash值，然后在Hash表中找到該Hash值的位置，從Hash值的鏈接進入符號表，找到元素對應存儲位置。

四、HashMap（哈希映射）

HashMap即哈希映射，指的是Hash表中Hash值向符號表元素的映射過程，是一種基于散列算法實現的快速查找的鍵值對結構。底層實現是鏈表和數組。即Hash值、Hash表與符號表的映射關系或結構。

Hash技術使用一張一維數組（Hash表）為首的鏈表通過間接方式來查填符號表。將相同Hash值的符號采用鏈表的方式連成一串，便于線性查找。符號表則將Hash值相同的符號以存儲時間的先后順序，后存儲的指向先存儲的元素將其鏈接在一起。Hash表的Hash值則指向其對應符號表中最后存儲的該Hash值的符號。

HashMap數組的每一個元素不止是一個Entry對象，也是一個鏈表的頭節點。每一個Entry對象通過Next指針指向它的下一個Entry節點。當新來的Entry映射到沖突的數組位置時，只需要插入到對應的鏈表即可：

需要注意的是，新來的Entry節點插入鏈表時，使用的是“頭插法”。至于為什么不插入鏈表尾部，是因為，后插入的Entry被查找的可能性更大，放到鏈表頭部有利于提高程序性能。

總結

以上是生活随笔為你收集整理的Hash（哈希）简述 —— Hash函数、Hash值、HashTable、HashMap的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。