/// existing element is returned.
/// Otherwise, the element is inserted an a
/// pair(iterator, true) with iterator
/// pointing to the new element is returned.
{
std::size_t hash = _hash(value);
std::size_t addr = bucketAddressForHash(hash);
BucketVecIterator it(_buckets.begin() + addr);
BucketIterator buckIt(std::find(it->begin(), it->end(), value));
if (buckIt == it->end())
{
split();
addr = bucketAddressForHash(hash);
it = _buckets.begin() + addr;
buckIt = it->insert(it->end(), value);
++_size;
return std::make_pair(Iterator(it, _buckets.end(), buckIt), true);
}
else
{
return std::make_pair(Iterator(it, _buckets.end(), buckIt), false);
}
}
其中split函数是所有操作的关键：
[cpp]
void split()
{
if (_split == _front)
{
_split = 0;
_front *= 2;
_buckets.reserve(_front*2);
}
Bucket tmp;
_buckets.push_back(tmp);
_buckets[_split].swap(tmp);
++_split;
for (BucketIterator it = tmp.begin(); it != tmp.end(); ++it)
{
using std::swap;
std::size_t addr = bucketAddress(*it);
_buckets[addr].push_back(Value());
swap(*it, _buckets[addr].back());
}
}
从上面的代码中我们可以看到，在每次插入新元素的时候，都会增加一个新的桶，并对桶_buckets[_split]进行重新散列；在_split == _front时，会把_buckets的容积扩大一倍。通过动态的增加桶的数量，这种方法降低了每个桶的高度，从而保证了搜索的效率。
4. HashMap和HashSet
HashMap和HashSet是在LinearHashTable上的封装，使接口同stl::map和stl::set相类似，使用时非常的简单。下面来看一个例子：
[cpp]
#include "Poco/HashMap.h"
int main()
{
typedef HashMap IntMap;
IntMap hm;
for (int i = 0; i < N; ++i)
{
std::pair res = hm.insert(IntMap::ValueType(i, i*2));
IntMap::Iterator it = hm.find(i);
}
assert (!hm.empty());
for (int i = 0; i < N; ++i)
{
IntMap::Iterator it = hm.find(i);
}
for (int i = 0; i < N; ++i)
{
std::pair res = hm.insert(IntMap::ValueType(i, 0));
}
return 0;
}