stl的hash容器，在实现层面,是如何做到用key来寻址元素的?

asker160

stl的unordered_map和unordered_set都是哈希容器，这个我知道。
例如unordered_map<string,A>就是用string作为key，A类型的对象作为值

那么问题来了，哈希容器的内部实现用什么“物理手段”来寻址某个元素呢?

1. 如果容器是用一个连续分配的空间，例如数组和vector那种，那么key算出来，作为一个数组的偏移量，可以寻址。但是显然造成一个极其稀疏的存储。不能这么干。
2. 我看stl的源代码里面，这两个容器内部都是用std::list来存储元素的。我们知道list是不能随机访问的。那么如何从一个计算出来的key，来找到我要的元素呢? 不能把key作为偏移量，因为不是数组；不能把key作为二分查找的手段，因为无序。那key是怎么映射到元素的?

希望我的问题表述清楚了。还请板上的各位高手指教！

windoze

回复 6# asker160

当然不是固定的啦，所以才会有rehash这个过程，就是增加或减少bucket的数量，然后根据新的bucket分布把元素重新插进去。
有个术语叫load factor，就是指每个bucket包含的平均元素个数，这个数决定了hash table的查找速度，假设计算hash是个常数时间，那么定位bucket也是个常数时间，但在bucket里面找元素的复杂度就是O(load_factor)了，因为bucket就是个链表。
load factor太大说明hash table查找会比较慢，太小往往说明最上面的那个vector太大了，浪费了内存。

selfrun

vector+list

asker160

回复 2# selfrun


    如果是vector+list的话，如何解决我上面说的这个问题呢? 如果value在vector里面，那么key是无序的，如何用一个无序的key来定位某个元素的下标，而不需要一个无穷大的vector？
    如果value是在list里面，list不能随机寻址，又如何能定位元素呢?

谢谢。

windoze

unordered_map结构是一个vector of list of pair<key, value>
最上面是一个vector，每个元素都是一个list header，每个list都存了一堆元素，术语叫bucket。
定位过程是通过hash(key)找到bucket，然后遍历bucket找到具体的key和其对应value
hash(key)和bucket的对应关系可以是hash(key) % bucket_count，也就是说hash相同的key一定在同一个bucket里，当然一个bucket可以对应多个hash

dorodaloo

回复 4# windoze
高手就是能够将复杂的结构，
采用通俗易懂的词汇，
一下子将问题给说透了。
赞一个!

asker160

回复 4# windoze


    谢谢你的回答，我有一个问题，这个vector的大小，在创建的时候就是固定的吗? 我觉得是固定的，因为hash要对这个大小取模，那么不可能这个大小在运行时改变，hash就和原先不一样了。
    但是，这就带来一个问题，vector如果固定大小是个很小的值，容易碰撞，每次遍历一个list不值得。
    如果vector一上来就取一个很大的值，太浪费。如果我是几千个元素的hash，我上来分配一百万个元素岂不是太浪费。而且，即使我上来分配一百万个元素，如果这个hash有一亿个元素，那么每个list也有一百个元素，效率还是太低了。

    我不知道这个问题是如何解决的?

windoze

回复 7# asker160

unordered_map的rehash没有你想的那么聪明，它就是新建一个vector<list<pair<key, value>>>结构，然后把所有现在有的k/v搬过去，这个过程对于巨大的map肯定慢的受不了。
但这个过程的触发是自动的，它有一个max_load_factor属性，如果它发现当前的load_factor超过了max_factor，就自动开始rehash，在此期间你的insert操作就一直挂在那儿，等到它rehash完了才会返回。

所以在实践中，unordered_map最好一上来就估算好大概容量，然后根据这个数字设定好bucket的数量，然后把max_load_factor设成一个巨大的值让它不要做自动rehash。
如果你不这么干程序当然也能转，但时不时会卡一下，而且内存用量会突然暴涨……