Hash

我曾在很多C＋＋書籍中看到作者們抱怨標準庫中沒有實現hash_set或hase_map，并非常自信地聲稱在下一個標準庫中一定會增加這兩個。我搜索的幫助文檔后，很遺憾地沒有發現相關庫。難道C＋＋的狂熱愛好者把這么重要的庫給忘記了嗎？Boost.Functional/hash庫引進了我的注意，遵循它的指引，我一步一步發發現的散列表的蹤跡。

hash        <boost/functional/hash.hpp>

觀察頭文件的寫法，就知道hash是functional庫中的一員，更進一步，如果你用過STL中的<functional>，那么多半你也猜到，hash是一個函數。不太完全正確，實事上它是一個函數對象。boost中實現的散列表，使用的散列函數就是它（至于boost中有那些散列函數，以后再列舉）。

如果直接使用hash，先創建一個實例并像函數一樣調用它：

       hash<string> string_hash;

       size_t h = string_hash(“Love”);

它支持的類型有

integers

floats

pointers

strings

擴展類型有

arrays

std::pair

標準容器

定制的類型擴展

如何定制類型

要編寫一個hash可用的類型，兩個必須實現的功能是operator== 和 hash_value，參考下面的實現：

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); // 可以自己寫哈希函數

       }

       bool operator== (const book& a, const book& b) const {

              return a.id == b.id;

       }

}; // namespace library

結合散列值

縱觀上面的hash使用方法，只能對一個參數可hash值。庫也提供了多個參數，示例：

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 的順序不同，得出的結果也不同

              boost::hash_combin(seed, p.y);

              return seed;

};

Unordered      <boost/unordered_set.hpp> ,<boost/unordered_map.hpp>

這個庫實現了無序關聯容器。從某種意義上說，它就是我們需要的散列表。

與有序關聯容器不同的是，它不需要比較，而是需要hash值。我下面列出它的聲明，以求不要理解錯了。

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不是標準庫里的類型，那么hash和equal_to的非常關鍵了。

使用

unordered_set、unordered_map與set、map在使用上基本一致。請參考它們的寫法。

更深層次的探索

散列表一個不可避免的問題即是“沖突”，解決沖突的方法有很多，有分離鏈表法、線性探測等。據我所知道，分離鏈表法是在各種庫最常用的方法。unordered的實現用到了桶（bucket），這屬于分離鏈表的變體。每桶對應的是索引，桶里可以有很多元素，它們都是“沖突”的。

線性探測中，一個非常重要的數據就是：裝填因子λ，它是散列表中的元素個數與散列表大小的比值。對于探測散列表，λ≈0.5；對于分離鏈表，λ≈1。在手冊中，unordered中負載因子（load factor）的解釋是“the average number of elements per bucket”，平均每個桶中元素的個數，在數學上，此處的負載因子與前面的裝填因子λ等價。

以下幾個函數用于控制桶的大小

X( size_type n)                                  構造一個新容器，帶有n個桶

X( InputIterator i, InputIterator j, size_type n)            構造有n個的容器，插入區間[i, j)。

float load_factor( ) const                            每個桶中的平均數量

float max_load_factor( ) const             當前最大的負載因子

float max_load_factor( float z)             修改最大負載因子，z做為參數

void rehash( size_type n)                     修改桶使至少為n個，且負載因子小于最大負載因子

除了 rehash 以外，其它成員函數如何影響桶的數量并沒有規定，insert 操作僅當插入導致負載因子大于或等于最大負載因子時允許使得迭代器失效。對于多數實現來說，這意味著只有當此事發生時，插入操作才會改變桶的數量。因此，迭代器只會在調用 insert 和 rehash 時才可能失效，而指向容器中的元素的指針和引用則永不失效。

轉自：http://hi.baidu.com/ani_di/blog/item/41406ce6df3c1f24b83820c1.html