#我頭新條聞#

哈希來自英文hash的翻譯。其實恰如其分應該叫散列。散列的目的就是找到一個函數能夠將一堆數字均勻分布在一維數組里。理想狀態大家存儲的位置是不同的，否則哈希函數比較糟糕。但是當兩個數字經過一次哈希發現存在同一個數組里，還會二次哈希把他存在另外一個不同地方，這就是所謂雙哈希。但是影響哈希存儲的最關鍵因素是數組大小，當足夠大大家發生碰撞機會比較少，這就是為什么內存數據庫，key值達到內存70%就要擴容。剛才看到樓上說的太簡單而且概念有些錯誤忍不住發表兩句。我們很少會用到數組加鏈表方式，因為查詢不穩定。基本通過空間換時間才能達到大o常數效率

#ICMLL實驗室 #

科研工作者、科學達人

哈希表是根據關鍵值(key)來直接訪問目標值(value)的一種數據結構。其特點就在于能夠快捷的實現信息的查詢和檢索。

比如我們在手機中存放的通訊錄就是用哈希表來實現的，即我們輸入一個聯系人的姓名，就能返回相應的電話號碼。用哈希表實現的過程就是，將聯系人姓名的字符通過一個哈希函數，映射成一個整數（哈希碼），然后根據哈希碼來索引出電話號碼。比如哈希碼為5，就表示是在存儲位置為5，因此我們就能直接取出該位置的值，并返回結果。

那么實現哈希表的關鍵就在于哈希函數的構建，也就是如何建立一個合適的索引來滿足如下條件：

1）同一個鍵每次輸入到哈希函數中，其對應的哈希碼也必須相同；

2）不同鍵對應的哈希碼不能相同。

第一個條件意味著哈希函數必須是確定性的；第二個條件則要求不能出現哈希沖突。當兩個或更多個鍵產生相同的哈希碼時就會發生沖突（hash collisions）。

比如我們現在考慮建立一個簡單的哈希表來查詢年齡,{Jim：5, Davis：7, Taylor:12, Bob:3}，如果我們選擇哈希函數為輸入鍵值的字符個數。那么在建立哈希表時，就講Jim存放在位置3處，Jack存放在位置4處。而這樣的話Jim和Bob的存儲位置就會發生沖突，不符合哈希函數的要求。但是如果我們將哈希函數替換為首字母順序存放，在這個數據中就沒有哈希沖突了。

然而萬一無法避免哈希沖突的話，我們可以用鏈接和線性探測的方法來避免哈希值發生碰撞。

鏈接就是將發生沖突的鍵值直接鏈接在鏈表的尾部；線性探測則是，如果在位置i處發生沖突，那么就檢查i+1處是否為空，為空的話就將沖突鍵值放入其中，否則繼續檢查下一個。

#楊沐白 #

互聯網算法工程師

謝邀。這個問題很有趣，哈希（Hashing）是一種用于從一組相似對象中唯一標識特定對象的技術。

一個簡單的例子

我們生活中如何使用哈希的一些例子包括：

在大學中，每個學生都會被分配一個唯一的卷號，可用于檢索有關它們的信息。

在圖書館中，每本書都被分配了一個唯一的編號，可用于確定有關圖書的信息，例如圖書館中的確切位置或已發給圖書的用戶等。

在這兩個例子中，學生和書籍都被分成了一個唯一的數字。

假設您有一個對象，并且您想為其分配一個鍵以便于搜索。 要存儲鍵/值對，您可以使用一個簡單的數組，如數據結構，其中鍵（整數）可以直接用作存儲值的索引。 但是，如果密鑰很大并且無法直接用作索引，則應使用哈希（Hashing）。

在哈希中，通過使用哈希函數將大鍵轉換為小鍵。 然后將這些值存儲在稱為哈希表的數據結構中。 哈希的想法是在數組中統一分配條目（鍵/值對）。 為每個元素分配一個鍵（轉換鍵）。 通過使用該鍵，您可以在O（1）時間內訪問該元素。 使用密鑰，算法會計算一個索引，該索引可以找到或插入條目的位置。

哈希一般分兩步執行：

• 通過使用哈希函數將元素轉換為整數。 此元素可用作存儲原始元素的索引，該元素屬于哈希表。

• 元素存儲在哈希表中，可以使用哈希鍵快速檢索它。

hash = hashfunc（key）

index = hash％array_size

在此方法中，哈希與數組大小無關，然后通過使用模運算符（％）將其縮減為索引（介于0和array_size - 1之間的數字）。

應用場景

關聯數組：哈希表通常用于實現許多類型的內存表。 它們用于實現關聯數組（索引是任意字符串或其他復雜對象的數組）。

數據庫索引：哈希表也可以用作基于磁盤的數據結構和數據庫索引（例如在dbm中）。

高速緩存：哈希表可用于實現高速緩存，即用于加速對數據的訪問的輔助數據表，其主要存儲在較慢的介質中。

對象表示：一些動態語言（如Perl，Python，JavaScript和Ruby）使用哈希表來實現對象。

提升速度：哈希函數用于各種算法，以使其計算更快。

∑編輯?|?Gemini

來源| 今日頭條

更多精彩：

? ?哈爾莫斯：怎樣做數學研究

? ?扎克伯格2017年哈佛大學畢業演講

? ?線性代數在組合數學中的應用

? ?你見過真的菲利普曲線嗎？

? ?支持向量機(SVM)的故事是這樣子的

? ?深度神經網絡中的數學，對你來說會不會太難？

? ?編程需要知道多少數學知識？

? ?陳省身——什么是幾何學

? ?模式識別研究的回顧與展望

? ?曲面論

? ?自然底數e的意義是什么？

? ?如何向5歲小孩解釋什么是支持向量機（SVM）？

? ?華裔天才數學家陶哲軒自述

? ?代數，分析，幾何與拓撲，現代數學的三大方法論

算法數學之美微信公眾號歡迎賜稿

稿件涉及數學、物理、算法、計算機、編程等相關領域，經采用我們將奉上稿酬。

投稿郵箱：math_alg@163.com

總結

以上是生活随笔為你收集整理的问答丨如何理解哈希表的工作原理？的全部內容，希望文章能夠幫你解決所遇到的問題。

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