Library: Foundation
Package: Hashing
Header: Poco/LinearHashTable.h
This class implements a linear hash table.
In a linear hash table, the available address space grows or shrinks dynamically. A linar 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 Functions: LinearHashTable, begin, bucketAddress, bucketAddressForHash, buckets, calcSize, clear, count, empty, end, erase, find, insert, merge, operator =, size, split, swap
typedef std::vector < Value > Bucket;
typedef typename Bucket::iterator BucketIterator;
typedef std::vector < Bucket > BucketVec;
typedef typename BucketVec::iterator BucketVecIterator;
typedef const Value * ConstPointer;
typedef const Value & ConstReference;
typedef Value * Pointer;
typedef Value & Reference;
typedef Value ValueType;
~LinearHashTable();
Destroys the LinearHashTable.
LinearHashTable(
std::size_t initialReserve = 64
);
Creates the LinearHashTable, using the given initialReserve.
LinearHashTable(
const LinearHashTable & table
);
Creates the LinearHashTable by copying another one.
ConstIterator begin() const;
Returns an iterator pointing to the first entry, if one exists.
Iterator begin();
Returns an iterator pointing to the first entry, if one exists.
std::size_t buckets() const;
Returns the number of allocated buckets.
void clear();
Erases all elements.
std::size_t count(
const Value & value
) const;
Returns the number of elements with the given value, with is either 1 or 0.
bool empty() const;
Returns true if and only if the table is empty.
ConstIterator end() const;
Returns an iterator pointing to the end of the table.
Iterator end();
Returns an iterator pointing to the end of the table.
void erase(
Iterator it
);
Erases the element pointed to by it.
void erase(
const Value & value
);
Erases the element with the given value, if it exists.
ConstIterator find(
const Value & value
) const;
Finds an entry in the table.
Iterator find(
const Value & value
);
Finds an entry in the table.
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.
LinearHashTable & operator = (
const LinearHashTable & table
);
Assigns another LinearHashTable.
std::size_t size() const;
Returns the number of elements in the table.
void swap(
LinearHashTable & table
);
Swaps the LinearHashTable with another one.
std::size_t bucketAddress(
const Value & value
) const;
std::size_t bucketAddressForHash(
std::size_t hash
);
static std::size_t calcSize(
std::size_t initialSize
);
void merge();
void split();