散列表如何在流行語言中內部實現？

有人可以談談像Python，Ruby這樣的流行語言如何在符號查找的內部實現哈希表？他們是否使用經典的「帶有鏈接列表的數組」方法，或者使用平衡樹？散列表如何在流行語言中內部實現？

我需要一個簡單的（更少的LOC）和快速的方法來索引用C編寫的DSL中的符號。想知道別人發現的最有效和實用的。

來源

2009-05-24 CDR

也許你要問「是如何實現的地圖......」哈希表不是實現地圖的唯一途徑！ – Artelius 2009-05-24 06:57:44

好評。但問題是我已經基於計算出的符號散列來構建基礎工作。順便說一下，除了散列之外，還有其他什麼方法實現，我認爲每個人都使用它？ – CDR 2009-05-24 09:25:24

地圖有時也用二叉樹構建。它通常在鍵類型不可用時使用，或者您希望保留地圖中數據的特定順序（以便您可以從A到Z迭代）。 – Crashworks 2009-05-24 10:26:18

您提到的經典「散列桶」數組用於我見過的每個實現中。

其中一個最有教育意義的版本是Tcl語言中的散列實現，文件tcl/generic/tclHash.c。文件中超過一半的行是解釋的所有內容的詳細信息：分配，搜索，不同的哈希表類型，策略等註釋：實現Tcl語言的代碼是，確實是可讀。

來源

2009-05-24 07:29:39 zvr

平衡樹排除哈希表的目的，因爲哈希表可以提供查找（分期付款）的恆定時間，而平衡樹上的平均查找是O（log（n））。

如果您有足夠的存儲桶，並且您的鏈接列表實現使用池分配器而不是malloc（）分別從堆堆中獲取每個節點，則單獨鏈接（帶有鏈接列表的數組）會非常有效。我已經發現，只要適當調整，它就像其他任何技術一樣具有表現力，並且寫起來非常簡單快捷。嘗試從1/8開始，以源數據爲單位。

您還可以使用open addressing進行二次或多項式探測，as Python does。

來源

2009-05-24 06:22:15 Crashworks

對數打敗恆定時間？ – 2009-05-24 07:01:00

Attractive Chaos有一個comparison of Hash Table Libraries和一個update。的源代碼可用，但在C和C++

來源

2009-05-24 07:24:02 Lear

什麼Crashworks的意思是說是....

哈希表的目的是恆定的時間查找，添加和刪除。在算法方面，所有操作的操作是O（1）攤銷。而在使用樹的情況下......對於平衡樹，最壞情況的操作時間將是O（log n）。 N是節點的數量。但是，我們真的把哈希實現爲樹嗎？

來源

2009-05-24 07:24:34

Perl使用帶有鏈接列表的數組來保存衝突。它有一個簡單的啓發式方法，可根據需要自動將數組大小加倍。還有一些代碼可以在哈希之間共享密鑰以節省一點內存。您可以在「HV」下的日期但仍然相關的Perl Illustrated Guts中閱讀。如果你真的冒險，你可以挖掘到hv.c。

散列算法過去非常簡單，但現在使用Unicode可能會複雜得多。由於該算法是可預測的，因此存在DoS攻擊，攻擊者通過該攻擊生成會導致散列衝突的數據。例如，作爲POST數據發送到網站的密鑰的大量列表。 Perl程序可能會將其拆分並將其轉儲爲散列，然後將其全部推送到一個存儲桶中。結果散列是O（n）而不是O（1）。在服務器上投入大量的POST請求，可能會阻塞CPU。結果Perl現在用一些隨機數據擾亂了散列函數。

你也可能想看看how Parrot implements basic hashes，它比Perl 5的實現更不可怕。

至於「最高效和實用」，使用別人的散列庫。爲了上帝的緣故，不要爲了生產而自己寫一本。那裏已經有一些健壯而有效的人。

來源

2009-05-24 07:51:21 Schwern

如果你可以閱讀Java，你可能要檢查出的源代碼，它的各種地圖的實現，特別是HashMap，TreeMap和ConcurrentSkipListMap。後兩個保持鍵的順序。

Java的HashMap使用您在每個存儲桶位置提及鏈接的標準技術。它使用相當弱的32位散列碼並將密鑰存儲在表中。 Numerical Recipes的作者還給出了一個基本上像Java一樣構造的散列表的例子（用C表示），但其中（a）從數組中分配桶列表的節點，（b）使用更強大的64位散列代碼並免除在表格中存儲密鑰。

來源

2009-05-24 14:26:36

Lua表使用utterly ingenious implemenation對於任意鍵的行爲類似於「桶的數組」，但如果使用連續整數作爲鍵，則它與數組具有相同的表示形式和空間開銷。在實現中，每個表具有散列部分和陣列部分。

我覺得這是非常酷:-)

來源

2009-05-26 03:39:12

散列表如何在流行語言中內部實現？

回答

相關問題