關於散列表的困惑

Question

我目前正在爲一些訪談學習，並且我聽說在某些訪談中，有時會要求人們從頭開始構建數據結構，包括散列表。然而，我遇到了一些麻煩......從編程的角度來看，真正理解哈希表。我一直在使用C++構建這些數據結構，我知道使用模板我可以創建鏈表，動態數組，二叉搜索樹等，基本上可以存儲任何類型的對象（只要對象是可以存儲在散列表實例中的唯一類型）。所以我會假設我可以創建一個模板或「通用」哈希表，這取決於哈希表的實例，可以存儲特定的對象。但我有一個讓我困惑了兩兩件事：

1. 我知道，通過散列函數，不同的按鍵映射到不同的指標，構成了哈希表在數組中。但假設您使用您創建的散列表來存儲Book類型的對象，然後讓我們假設您創建另一個散列表來存儲People類型的對象。顯然，不同類型的對象將具有不同的成員屬性，其中一個屬性必須是關鍵。這是否意味着基本上你想存儲在你創建的散列表上的每個對象都必須至少有一個具有相同名稱的屬性？因爲你的散列函數必須有一些關鍵值來散列，所以它必須知道它使用的對象的哪個屬性作爲散列的關鍵字？因此，例如，您希望存儲在此哈希表中的每個對象都必須具有一個名爲「key」的屬性，您可以在使用散列函數映射到數組的索引時使用該屬性。否則，它將如何知道散列的「關鍵」？

2. 這也會導致散列函數的問題......我讀過，根據給出的數據集，一些散列函數比其他散列函數要好。因此，如果散列函數依賴於數據集，那麼您怎麼可能創建一個可存儲任何類型對象的散列表數據結構？

所以，我只是想這個？我應該學習創建一個簡單的哈希表，在爲我的面試練習時散列整數嗎？在現實生活中的散列表是一般創建的，還是人們通常會根據他們擁有的數據類型來創建不同的散列表？

如果這個問題更適合計算機科學理論堆棧交換，請讓我知道。我只是發現這些小細節讓我無法真正理解這個數據結構。

Answer 1

您需要從哈希函數中分離哈希表，這些是不同的功能。
有兩種常見的做法來保持您的哈希表通用，並仍然能夠正確地哈希對象。

1. 首先是假設你的模板類型（讓它成爲T）實現 哈希方法，並使用它。你不在乎它是如何實現的，只要你有它。
2. 另一種選擇是除了模板類型之外還有一個 模板函數hash(T)，當 聲明一個哈希表時需要提供該函數。

這基本上解決了兩個問題：用戶，誰知道數據的分佈比圖書館讀者更好地，是提供散列函數，以及提供的散列函數可以使用所提供的類型，不管什麼「鑰匙」是。

如果選擇了第二個選項，則可以爲已知類型和基元類型實現一些默認散列函數，因此用戶在使用標準類型時不需要爲該庫的每次使用重新發明輪子。