Hash
我曾在很多C＋＋書籍中看到作者們抱怨標(biāo)準(zhǔn)庫中沒有實(shí)現(xiàn)hash_set或hase_map，并非常自信地聲稱在下一個(gè)標(biāo)準(zhǔn)庫中一定會(huì)增加這兩個(gè)。我搜索的幫助文檔后，很遺憾地沒有發(fā)現(xiàn)相關(guān)庫。難道C＋＋的狂熱愛好者把這么重要的庫給忘記了嗎？Boost.Functional/hash庫引進(jìn)了我的注意，遵循它的指引，我一步一步發(fā)發(fā)現(xiàn)的散列表的蹤跡。
hash <boost/functional/hash.hpp>
觀察頭文件的寫法，就知道hash是functional庫中的一員，更進(jìn)一步，如果你用過STL中的<functional>，那么多半你也猜到，hash是一個(gè)函數(shù)。不太完全正確，實(shí)事上它是一個(gè)函數(shù)對象。boost中實(shí)現(xiàn)的散列表，使用的散列函數(shù)就是它（至于boost中有那些散列函數(shù)，以后再列舉）。
如果直接使用hash，先創(chuàng)建一個(gè)實(shí)例并像函數(shù)一樣調(diào)用它：
hash<string> string_hash;
size_t h = string_hash(“Love”);
它支持的類型有
integers
floats
pointers
strings
擴(kuò)展類型有
arrays
std::pair
標(biāo)準(zhǔn)容器
定制的類型擴(kuò)展
如何定制類型
要編寫一個(gè)hash可用的類型，兩個(gè)必須實(shí)現(xiàn)的功能是operator== 和 hash_value，參考下面的實(shí)現(xiàn)：
namespace library {
struct book {
int id;
std::string titile;
};
std::size_t hash_value(const book& b) {
boost::hash<int> hasher;
return hasher(b.id); // 可以自己寫哈希函數(shù)
}
bool operator== (const book& a, const book& b) const {
return a.id == b.id;
}
}; // namespace library
結(jié)合散列值
縱觀上面的hash使用方法，只能對一個(gè)參數(shù)可hash值。庫也提供了多個(gè)參數(shù)，示例：
class point {
int x, y;
public:
… …
bool operator==(const point& other) const {
return x == other.x && y == other.y;
}
friend std::size_t hash_value(const point& p) {
std::size_t seed = 0;
boost::hash_combin(seed, p.x); // combin 的順序不同，得出的結(jié)果也不同
boost::hash_combin(seed, p.y);
return seed;
};
Unordered <boost/unordered_set.hpp> ,<boost/unordered_map.hpp>
這個(gè)庫實(shí)現(xiàn)了無序關(guān)聯(lián)容器。從某種意義上說，它就是我們需要的散列表。
與有序關(guān)聯(lián)容器不同的是，它不需要比較，而是需要hash值。我下面列出它的聲明，以求不要理解錯(cuò)了。
namespace boost {
template <
class Key,
class Hash = boost::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::alloctor<Key> >
class unordered_set;
}
如果class不是標(biāo)準(zhǔn)庫里的類型，那么hash和equal_to的非常關(guān)鍵了。
使用
unordered_set、unordered_map與set、map在使用上基本一致。請參考它們的寫法。
更深層次的探索
散列表一個(gè)不可避免的問題即是“沖突”，解決沖突的方法有很多，有分離鏈表法、線性探測等。據(jù)我所知道，分離鏈表法是在各種庫最常用的方法。unordered的實(shí)現(xiàn)用到了桶（bucket），這屬于分離鏈表的變體。每桶對應(yīng)的是索引，桶里可以有很多元素，它們都是“沖突”的。
線性探測中，一個(gè)非常重要的數(shù)據(jù)就是：裝填因子λ，它是散列表中的元素個(gè)數(shù)與散列表大小的比值。對于探測散列表，λ≈0.5；對于分離鏈表，λ≈1。在手冊中，unordered中負(fù)載因子（load factor）的解釋是“the average number of elements per bucket”，平均每個(gè)桶中元素的個(gè)數(shù)，在數(shù)學(xué)上，此處的負(fù)載因子與前面的裝填因子λ等價(jià)。
以下幾個(gè)函數(shù)用于控制桶的大小
X( size_type n) 構(gòu)造一個(gè)新容器，帶有n個(gè)桶
X( InputIterator i, InputIterator j, size_type n) 構(gòu)造有n個(gè)的容器，插入?yún)^(qū)間[i, j)。
float load_factor( ) const 每個(gè)桶中的平均數(shù)量
float max_load_factor( ) const 當(dāng)前最大的負(fù)載因子
float max_load_factor( float z) 修改最大負(fù)載因子，z做為參數(shù)
void rehash( size_type n) 修改桶使至少為n個(gè)，且負(fù)載因子小于最大負(fù)載因子
除了 rehash 以外，其它成員函數(shù)如何影響桶的數(shù)量并沒有規(guī)定，insert 操作僅當(dāng)插入導(dǎo)致負(fù)載因子大于或等于最大負(fù)載因子時(shí)允許使得迭代器失效。對于多數(shù)實(shí)現(xiàn)來說，這意味著只有當(dāng)此事發(fā)生時(shí)，插入操作才會(huì)改變桶的數(shù)量。因此，迭代器只會(huì)在調(diào)用 insert 和 rehash 時(shí)才可能失效，而指向容器中的元素的指針和引用則永不失效。
轉(zhuǎn)自：http://hi.baidu.com/ani_di/blog/item/41406ce6df3c1f24b83820c1.html