如何檢查我的自定義哈希在hash_map中是否有用？

我已經爲stdext :: hash_map中的自定義鍵寫了一個自定義散列，並且希望檢查hasher是否好。我使用的是VS 2008提供的STL。我知道，典型的檢查是檢查桶之間分配的均勻性。如何檢查我的自定義哈希在hash_map中是否有用？

我應該如何正確組織這樣的檢查？我想到的一個解決方案是修改STL源以向hash_map添加一個方法，該方法遍歷存儲區並執行主題。有沒有更好的方法？

也許，從hash_map派生並在那裏創建這樣的方法？

來源

2010-03-03 flashnik

我會通過stl :: hash_map運行一個（大）數據集。一旦這樣做，我會使用下面的方法

從hash_map收集所有桶結果：

size_type elems_in_bucket (size_type __n) const;

最後，我會做計算標準偏差（SD）的ELEM到 - 分發。

我會做上述不同的哈希函數。無論哪個散列函數導致最小SD都是贏家（對於此數據集）。

來源

2010-03-03 23:28:50 Arun

是的，這將是完美的，但我沒有這個成員開箱即用。我應該定義_HAS_TRADITIONAL_STL嗎？它會導致哪些副作用？ – flashnik 2010-03-03 23:36:00

我找到了:)在我編譯器的STL（MS VS 2008）中，這個方法被稱爲'bucket_size'。萬分感謝！ – flashnik 2010-03-03 23:58:34

@flashnik：不客氣。如果您有任何後續問題，請隨時評論回來。 – Arun 2010-03-04 00:07:16

最好的辦法可能是將哈希算法應用於整數數組並計算每個哈希桶命中的次數，給出真實世界的數據。（我建議真的把STL排除在這個等式之外）

如果你最終發現你的計數與大量實際數據有很大的偏差，那麼你的哈希算法會在那裏產生大量的衝突有充足的空（或更空）桶可用。

請注意，'高偏差'是一個相對項。一個好的散列算法是一個確定性的隨機過程，任何隨機過程都有可能產生奇怪的結果，因此經常測試，測試良好，並且儘可能將實際問題域用作測試和控件的來源。

來源

2010-03-03 23:24:48 Sniggerfardimungus

是的，這就是我要做的。但AFAIK我不能在hash_map之外訪問bucket（和其中的項目數量）。現在我看到兩種方法：修改STL源代碼或使用適當的方法從hash_map派生自己的類。我更喜歡第二種解決方案。還有其他方法嗎？ – flashnik 2010-03-03 23:28:32

...這就是爲什麼user30997在firts段落中表示將STL帶出圖片並且僅僅通過真實數據和遞增計數器運行你的散列方法。 – vladr 2010-03-03 23:30:22

嗯，恐怕不同的STL實現可以用不同的哈希結果來工作。例如，如果_Mask是'2^N -1'，使用'this-> comp（_Keyval）＆_Mask'來確定一個busket工作正常。而_Mask由hasher仿函數決定（它是hasher提供的min_buckets的乘法）。在任何其他情況下，它不等同於提醒'this-> comp（_Keyval）％_Mask'。 – flashnik 2010-03-03 23:42:57

如何檢查我的自定義哈希在hash_map中是否有用？

回答

相關問題