散列的unordered_map

從某些來源^，我得到一個長度爲20（SHA-1）的特定數據（比如文件或字節塊）的哈希緩衝區。如果這個給定的散列（認爲它是字符串，而不是散列）是而不是在地圖中找到，那麼我會提取更多信息，並將此信息與此散列一起插入。要清楚：散列的unordered_map

unordered_map<Hash_of_20_Bytes, Information>

這是我的地圖。密鑰將是一個20字節的緩衝區，並且Information是一些包含詳細信息的結構。所以，如果來源^給了我一些散列，我會查找散列到這個信息地圖，並適當地使用/生成。

重點是，在我的情況下，給定的20字節散列保證沒有任何衝突。然而，unordered_map仍然會計算密鑰的（FNV）散列（密鑰本身就是散列！）。我不能指示收集類不是來生成散列，而是使用該鍵具有唯一鍵本身（以確保O（1））？

我不確定unordered_map是否也計算整數的散列（即減少額外計算的需要）。

一種方法是使用pair<20-byte, Info>自身的向量，並進行二分搜索。然而，爲了避免哈希計算（通過散列容器）的懲罰，它會導致更多的保持向量排序的懲罰）。

來源

2017-07-07 Ajay

['std :: unordered_map']（http://en.cppreference.com/w/cpp/container/unordered_map）允許您設置要使用的散列函數。通常使用一個特殊的「類型」的密鑰，然後有專門的['std :: hash']（http://en.cppreference.com/w/cpp/utility/hash）該類型。 –

無論如何您都不能使用散列，因爲unordered_map預計size_t作爲散列，而不是20字節的緩衝區。現在

，你可以做的是提供一個非常簡單的自定義哈希函數：由於輸入已經是一個好的哈希，你可以只取前sizeof(size_t)字節和殘酷memcpy他們入size_t，丟棄所有其他人。我不知道你會得到令人難以置信的性能提升，但試用這個並不會花費太多。

我不能指示集合類不生成散列，而是使用密鑰具有唯一密鑰本身（以確保O（1））？

這裏的基本假設是有缺陷的;是的，你的密鑰已經是一個好的，行爲良好的散列，所以你不需要對它應用複雜的散列函數去獲得預期的散列屬性和你將不會得到類型「不同數據映射到相同的散列「;但是一般情況下，如果你有一個體面的散列函數，大多數衝突並不來自將同一個鍵映射到相同散列的散列函數，而是來自散列表的當前大小 - 即從多個散列值被映射到同一個存儲桶的事實。所以，再一次，你不會獲得太多收益。

來源

2017-07-07 07:22:37

'string'也可以是一個鍵。 – Ajay

@Ajay：我不明白，你的意思是說，在同一張地圖上，你想把哈希和無關的字符串作爲關鍵字' –

僅僅因爲這些關鍵字是保證無碰撞並不意味着你可以只取一個濫用公共汽車的子集，並希望能夠產生良好的散列值。 – MikeMB

對於std::unordered_map的散列器必須滿足Hash concept。所以它必須返回一個std::size_t，這是不可能超過20個字節。

因此，不可能爲此20字節散列提供標識散列器，因此即使沒有保證20字節散列的衝突，除非它可以可靠地減少到32位空間（或而不是碰撞），碰撞對於這種情況和這個容器是不可避免的。

來源

2017-07-07 07:22:14

散列的unordered_map

回答

相關問題