Library: Foundation
Package: Hashing
Header: Poco/LinearHashTable.h
Description
This class implements a linear hash table.
In a linear hash table, the available address space grows or shrinks dynamically. A linear hash table thus supports any number of insertions or deletions without lookup or insertion performance deterioration.
Linear hashing was discovered by Witold Litwin in 1980 and described in the paper LINEAR HASHING: A NEW TOOL FOR FILE AND TABLE ADDRESSING.
For more information on linear hashing, see <http://en.wikipedia.org/wiki/Linear_hash>.
The LinearHashTable is not thread safe.
Value must support comparison for equality.
Find, insert and delete operations are basically O(1) with regard to the total number of elements in the table, and O(N) with regard to the number of elements in the bucket where the element is stored. On average, every bucket stores one element; the exact number depends on the quality of the hash function. In most cases, the maximum number of elements in a bucket should not exceed 3.
Member Summary
Member Functions: begin, bucketAddress, bucketAddressForHash, buckets, calcSize, clear, count, empty, end, erase, find, insert, merge, operator =, size, split, swap
Nested Classes
class ConstIterator
class Iterator
Types Aliases
Bucket
using Bucket = std::vector < Value >;
BucketIterator
using BucketIterator = typename Bucket::iterator;
BucketVec
using BucketVec = std::vector < Bucket >;
BucketVecIterator
using BucketVecIterator = typename BucketVec::iterator;
ConstPointer
using ConstPointer = const Value *;
ConstReference
using ConstReference = const Value &;
Hash
using Hash = HashFunc;
Pointer
using Pointer = Value *;
Reference
using Reference = Value &;
ValueType
using ValueType = Value;
Constructors
LinearHashTable 
LinearHashTable(
std::size_t initialReserve = 64
);
Creates the LinearHashTable, using the given initialReserve.
LinearHashTable
LinearHashTable(
const LinearHashTable & table
);
Creates the LinearHashTable by copying another one.
Destructor
~LinearHashTable
~LinearHashTable() = default;
Destroys the LinearHashTable.
Member Functions
begin
ConstIterator begin() const;
Returns an iterator pointing to the first entry, if one exists.
begin
Iterator begin();
Returns an iterator pointing to the first entry, if one exists.
buckets
std::size_t buckets() const;
Returns the number of allocated buckets.
clear
void clear();
Erases all elements.
count
std::size_t count(
const Value & value
) const;
Returns the number of elements with the given value, with is either 1 or 0.
empty
bool empty() const;
Returns true iff the table is empty.
end
ConstIterator end() const;
Returns an iterator pointing to the end of the table.
end
Iterator end();
Returns an iterator pointing to the end of the table.
erase
void erase(
Iterator it
);
Erases the element pointed to by it.
erase
void erase(
const Value & value
);
Erases the element with the given value, if it exists.
find
ConstIterator find(
const Value & value
) const;
Finds an entry in the table.
find
Iterator find(
const Value & value
);
Finds an entry in the table.
insert
std::pair < Iterator, bool > 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 existing element is returned. Otherwise, the element is inserted an a pair(iterator, true) with iterator pointing to the new element is returned.
operator =
LinearHashTable & operator = (
const LinearHashTable & table
);
Assigns another LinearHashTable.
size
std::size_t size() const;
Returns the number of elements in the table.
swap
void swap(
LinearHashTable & table
) noexcept;
Swaps the LinearHashTable with another one.
bucketAddress 
std::size_t bucketAddress(
const Value & value
) const;
bucketAddressForHash
std::size_t bucketAddressForHash(
std::size_t hash
);
calcSize 
static std::size_t calcSize(
std::size_t initialSize
);
merge
void merge();
split
void split();