有效的數據結構來映射整數到整數與查找和插入，沒有分配和固定上限

Question

我正在尋找輸入的關聯數據結構，可能會利用我的用例的具體標準。

目前，我正在使用紅色/黑色樹來實現將鍵映射到值的字典（在我的情況下整數地址）。

在我的使用案例中，元素的最大數量在前面已知（1024），而且我將只能插入和搜索。搜索比插入多出20倍。在過程結束時，我清除結構並再次重複。在使用過程中不能有分配 - 只有最初的預先分配。不幸的是，STL和最新版本的C++不可用。

任何見解？

Answer 1

我最終通過一個例子here實現了一個簡單的線性探測HashTable。我使用了MurmurHash3哈希函數，因爲我的數據是隨機的。

我修改了哈希表在以下幾個方面：

1. 的大小是一個模板參數。在內部，尺寸增加了一倍。實施需要2種尺寸的力量，傳統上調整爲75％的職業。因爲我知道我將填滿散列表，我優先加倍它的容量，以保持足夠稀疏。添加少量對象時效率可能較低，但一旦容量開始填滿時效率會更高。由於我無法調整大小，我選擇將它的大小加倍。
2. 我不允許存儲值爲零的鍵。這對我的應用程序來說沒問題，它使代碼簡單。
3. 所有調整大小和刪除都被刪除，取而代之的是執行memset的單個清除操作。
4. 我選擇內聯插入和查找函數，因爲它們很小。

它比我以前的紅/黑樹實現更快。我可能做的唯一改變是重新審視散列方案，以查看源鍵中是否有某些東西可以幫助製作更便宜的散列。

Billy ONeal建議，考慮到少數元素（1024），固定陣列中的簡單線性搜索會更快。我遵循他的建議並實施了一個並排比較。在我的目標硬件（大概是第一代iPhone）上，哈希表的性能比線性搜索高出2：1。在較小的尺寸（256個元素）下，哈希表仍然優越。當然這些值是依賴於硬件的。緩存行大小和內存訪問速度在我的環境中非常糟糕。然而，其他尋求解決這個問題的人會聰明地遵循他的建議並嘗試並首先對其進行描述。