0
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;
}
}
並確保沒有碰撞?
預期的碰撞概率是1.0/m.bucket_count()'。 –
您正在尋找*(最小)完美哈希*。有一些開源庫。 –
@Frank:你的散列函數只有在從'T'到'size_t'的轉換時纔有效。請注意,這是散列和指針的典型實現。但是,碰撞不僅發生在散列相等時,而且當兩個不同的散列映射到同一個存儲桶時。 –