用兩個數組創建一個哈希表

Question

有誰知道如何做到這一點以及僞代碼是什麼樣的？我們都知道一個哈希表存儲鍵，值對，並且當一個鍵被調用時，函數將返回與該鍵相關聯的值。我想要做的是瞭解創建映射函數的底層結構。例如，如果我們生活在一個除了數組之外沒有預先定義的函數的世界中，我們如何複製我們今天的哈希表？

Answer 1

事實上，一些今天的Hashmap implentations確實做出來陣列的，你建議。讓我素描是如何工作的：

Hash函數 散列函數變換鑰匙進入第一個陣列（列K）的索引。散列函數（如MD5）或更簡單的散列函數（通常包括模運算符）可用於此目的。

存儲桶 一個簡單的基於數組的Hashmap實現可以使用存儲桶來處理collies。數組K中的每個元素（'bucket'）都包含一個數組（數組P）。當添加或查詢元素時，散列函數將您指向K中正確的桶，其中包含所需的數組P.然後，遍歷P中的元素直到找到匹配的鍵，或者在P.

映射按鍵

端使用哈希 桶，你應該確保（即K的大小）桶的數量是2的冪，比方說2^b。要爲某個密鑰找到正確的桶索引，請計算哈希（密鑰），但只保留前b位。這是您的索引時轉換爲整數。

重新調整 計算密鑰的散列並找到正確的存儲區非常快。但是一旦桶變得更加飽滿，在你找到合適的桶之前，你必須迭代越來越多的物品。所以有足夠的桶來正確分配對象是非常重要的，否則你的Hashmap會變得很慢。

由於您通常不知道您需要預先在Hashmap中存儲多少對象，因此需要動態增大或縮小地圖。您可以保留對象數目的存儲數量，一旦超過一定的閾值，您可以重新創建整個結構，但是這次對於數組K而言，這個時候的數據量可能會更大或更小。通過這種方式，K中的一些桶非常滿，現在將它們的元素分配到幾個桶中，這樣性能會更好。

替代品 您也可以使用二維數組而不是陣列數組，也可以將數組P換成鏈接列表。此外，一旦一個桶包含多於一些配置數量的項目，您可以簡單地選擇重新創建（即重新縮放）散列映射，而不是保留存儲對象的總數。

您所要求的變體在Hash table Wikipedia entry中被描述爲'陣列哈希表'。

代碼 有關代碼示例，請參閱here。

希望這會有所幫助。

Answer 2

你能更精確嗎？一個數組是否包含鍵，另一個是值？

如果是這樣，這裏是Java的一個例子（但這裏也有這種語言的一些具體情況）：

for (int i = 0; i < keysArray.length; i++) { 
    map.put(keysArray[i], valuesArray[i]); 
} 

當然，你必須實例化map對象（如果你使用的是Java，我建議使用HashMap<Object, Object>而不是過時的HashTable），並測試您的陣列以避免null對象並檢查它們是否具有相同的大小。

Answer 3

您的意思是？

使用Ruby的irb作爲說明如下：

cities = ["LA", "SF", "NY"] 
=> ["LA", "SF", "NY"] 

items = ["Big Mac", "Hot Fudge Sundae"] 
=> ["Big Mac", "Hot Fudge Sundae"] 

price = {} 
=> {} 

price[[cities[0], items[1]]] = 1.29 
=> 1.29 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29} 

price[[cities[0], items[0]]] = 2.49 
=> 2.49 

price[[cities[1], items[0]]] = 2.99 
=> 2.99 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

price[["LA", "Big Mac"]] 
=> 2.49 

Answer 4

樣品說明：

在下面的源，基本上做了兩兩件事：

1.地圖表示

• 一些（名單的X號）的列表
• X爲2次方N個列表不好。 A（2冪N）-1或（2冪N）+1，或素數是好的。

實施例：

List myhashmap [hash_table_size]; 
// an array of (short) lists 
// if its long lists, then there are more collisions 

注：這是陣列的陣列，而不是兩個陣列（看不到的可能的通用散列映射，在一個很好的方法，只需2陣列）

如果你知道算法>圖論>鄰接表，這個看起來完全一樣。

2。散列函數

和散列函數轉換字符串（輸入）與數（散列值），這是一個數組

• 初始化所述散列值，以第一字符的索引（換算後爲int）
• 對於每個進一步炭，左移4位，然後加入炭（換算後爲int）

實施例，

int hash = input[0]; 
for (int i=1; i<input.length(); i++) { 
    hash = (hash << 4) + input[i] 
} 

hash = hash % list.size() 
// list.size() here represents 1st dimension of (list of lists) 
//  that is 1st dimension size of our map representation from point #1 
//  which is hash_table_size 

看到的第一個鏈接：

int HTable::hash (char const * str) const 

來源：
http://www.relisoft.com/book/lang/pointer/8hash.html
How does a hash table work?

更新
這是最好的來源：http://algs4.cs.princeton.edu/34hash/