boost库之Hash – 兔子的技术博客 – C++博客

boost库之Hash - 兔子的技术博客 - C++博客
boost库之Hash
Hash

我曾在很多C＋＋书籍中看到作者们抱怨标准库中没有实现hash_set或hase_map，并非常自信地声称在下一个标准库中一定会增加这两个。我搜索的帮助文档后，很遗憾地没有发现相关库。难道C＋＋的狂热爱好者把这么重要的库给忘记了吗？Boost.Functional/hash库引进了我的注意，遵循它的指引，我一步一步发发现的散列表的踪迹。

hash

观察头文件的写法，就知道hash是functional库中的一员，更进一步，如果你用过STL中的，那么多半你也猜到，hash是一个函数。不太完全正确，实事上它是一个函数对象。boost中实现的散列表，使用的散列函数就是它（至于boost中有那些散列函数，以后再列举）。

如果直接使用hash，先创建一个实例并像函数一样调用它：

hash 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 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 ,

这个库实现了无序关联容器。从某种意义上说，它就是我们需要的散列表。

与有序关联容器不同的是，它不需要比较，而是需要hash值。我下面列出它的声明，以求不要理解错了。

namespace boost {

template <

class Key,

class Hash = boost::hash,

class Pred = std::equal_to,

class Alloc = std::alloctor >

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
原文链接: https://www.cnblogs.com/lexus/archive/2013/03/28/2986380.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍