用於堆管理系統的unordered_map。是否可以實現無碰撞設置？

unordered_map<>（C++ 11）使用散列函數在內部組織它的鍵值。碰撞概率很小(1.f/std:numeric_limits<size_t>::max()）。用於堆管理系統的unordered_map。是否可以實現無碰撞設置？

可以使用unordered_map<>作爲堆內存管理的存儲容器嗎？也就是說，如果兩個元素混淆（通過碰撞），程序的穩定性將被破壞。在我的情況下，會導致在同一個指針上反覆調用free()。（SIGSEGV）。

或者是僅當搜索關鍵字時碰撞概率才重要。並且保證兩個不同的鍵總是指不同的值？

後續問題：說unordered_map與其標準的散列函數是不適合我的應用程序。如果有人想確保可以發生碰撞，並且可以將自己限制爲最多size_t元素，那麼是否可以提供自己的散列函數來返回參數本身。例如：

template<class T> 
struct Hash 
{ 
    size_t operator()(T t) { 
    return (size_t)t; 
    } 
}

並確保沒有碰撞？

2012-05-25 ritter

預期的碰撞概率是1.0/m.bucket_count（）'。 –

您正在尋找*（最小）完美哈希*。有一些開源庫。 –

@Frank：你的散列函數只有在從'T'到'size_t'的轉換時纔有效。請注意，這是散列和指針的典型實現。但是，碰撞不僅發生在散列相等時，而且當兩個不同的散列映射到同一個存儲桶時。 –

碰撞隻影響性能，不影響容器的內容。 unordered_map採用散列函數和等式函數。兩個元素可以安全地擁有相同的散列，如果他們比較不等於，那麼他們被視爲不相等。他們只會始終在同一個哈希桶中。大桶損害了那個桶中的操作性能。

2012-05-25 09:20:22

回答