POCO C++库学习和分析 (四)
{
UInt32 origHash = hsh;
while (_entries[hsh % _capacity])
{
if (_entries[hsh % _capacity]->key == key)
throw ExistsException();
if (hsh - origHash > _capacity)
throw PoolOverflowException("SimpleHashTable full");
hsh++;
}
pos = hsh % _capacity;
_entries[pos] = new HashEntry(key, value);
}
_size++;
return _entries[pos]->value;
}
SimpleHashTable进行搜索时，策略也一致。
[cpp]
const Value& get(const Key& key) const
/// Throws an exception if the value does not exist
{
UInt32 hsh = hash(key);
return getRaw(key, hsh);
}
const Value& getRaw(const Key& key, UInt32 hsh) const
/// Throws an exception if the value does not exist
{
UInt32 origHash = hsh;
while (true)
{
if (_entries[hsh % _capacity])
{
if (_entries[hsh % _capacity]->key == key)
{
return _entries[hsh % _capacity]->value;
}
}
else
throw InvalidArgumentException("value not found");
if (hsh - origHash > _capacity)
throw InvalidArgumentException("value not found");
hsh++;
}
}
SimpleHashTable没有提供删除数据的接口，只适用于数据量不大的简单应用。
3.2 HashTable
HashTable是拉链法的一个变种。当冲突数据发生时，存储的容器是map而不是list。其内部容器定义为：
[cpp]
HashEntryMap** _entries;
同map相比，它实际上是把一个大map分成了很多个小map，通过hash方法寻找到小map，再通过map的find函数寻找具体数据。其插入和搜索数据函数如下：
[cpp]
UInt32 insert(const Key& key, const Value& value)
/// Returns the hash value of the inserted item.
/// Throws an exception if the entry was already inserted
{
UInt32 hsh = hash(key);
insertRaw(key, hsh, value);
return hsh;
}
Value& insertRaw(const Key& key, UInt32 hsh, const Value& value)
/// Returns the hash value of the inserted item.
/// Throws an exception if the entry was already inserted
{
if (!_entries[hsh])
_entries[hsh] = new HashEntryMap();
std::pair res(_entries[hsh]->insert(std::make_pair(key, value)));
if (!res.second)
throw InvalidArgumentException("HashTable::insert, key already exists.");
_size++;
return res.first->second;
}
const Value& get(const Key& key) const
/// Throws an exception if the value does not exist
{
UInt32 hsh = hash(key);
return getRaw(key, hsh);
}
const Value& getRaw(const Key& key, UInt32 hsh) const
/// Throws an exception if the value does not exist
{
if (!_entries[hsh])
throw InvalidArgumentException("key not found");
ConstIterator it = _entries[hsh]->find(key);
if (it == _entries[hsh]->end())
throw InvalidArgumentException("key not found");
return it->second;
}
HashTable支持remove操作。
3.2 LinearHashTable
LinearHashTable按照解决冲突的方法4实现。它内部的容器为vector>,同时还存在两个控制量_split和_front：
[cpp]
std::size_t _split;
std::size_t _front;
vector> _buckets;
它的插入操作如下：
[cpp]
std::pair insert(const Value& value)
/// Inserts an element into the table.
///
/// If the element already exists in the table,
/// a pair(iterator, false) with iterator pointing to the