template class Poco::LinearHashTable

Overview

This class implements a linear hash table. More…

#include <LinearHashTable.h>

template <
    class Value,
    class HashFunc = Hash<Value>
    >
class LinearHashTable
{
public:
    // typedefs

    typedef Value ValueType;
    typedef Value& Reference;
    typedef const Value& ConstReference;
    typedef Value* Pointer;
    typedef const Value* ConstPointer;
    typedef HashFunc Hash;
    typedef std::vector<Value> Bucket;
    typedef std::vector<Bucket> BucketVec;
    typedef Bucket::iterator BucketIterator;
    typedef BucketVec::iterator BucketVecIterator;

    // classes

    class ConstIterator;
    class Iterator;

    // construction

    LinearHashTable(std::size_t initialReserve = 64);
    LinearHashTable(const LinearHashTable& table);

    // methods

    LinearHashTable&
    operator=(const LinearHashTable& table);

    void
    swap(LinearHashTable& table);

    ConstIterator
    begin() const;

    ConstIterator
    end() const;

    Iterator
    begin();

    Iterator
    end();

    ConstIterator
    find(const Value& value) const;

    Iterator
    find(const Value& value);

    std::size_t
    count(const Value& value) const;

    std::pair<Iterator, bool>
    insert(const Value& value);

    void
    erase(Iterator it);

    void
    erase(const Value& value);

    void
    clear();

    std::size_t
    size() const;

    bool
    empty() const;

    std::size_t
    buckets() const;

protected:
    // methods

    std::size_t
    bucketAddress(const Value& value) const;

    std::size_t
    bucketAddressForHash(std::size_t hash);

    void
    split();

    void
    merge();

    static
    std::size_t
    calcSize(std::size_t initialSize);
};

Detailed Documentation

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.

Construction

~LinearHashTable()

Destroys the LinearHashTable.

Methods

LinearHashTable&
operator=(const LinearHashTable& table)

Assigns another LinearHashTable.

void
swap(LinearHashTable& table)

Swaps the LinearHashTable with another one.

ConstIterator
begin() const

Returns an iterator pointing to the first entry, if one exists.

ConstIterator
end() const

Returns an iterator pointing to the end of the table.

Iterator
begin()

Returns an iterator pointing to the first entry, if one exists.

Iterator
end()

Returns an iterator pointing to the end of the table.

ConstIterator
find(const Value& value) const

Finds an entry in the table.

Iterator
find(const Value& value)

Finds an entry in the table.

std::size_t
count(const Value& value) const

Returns the number of elements with the given value, with is either 1 or 0.

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.

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.

void
clear()

Erases all elements.

std::size_t
size() const

Returns the number of elements in the table.

bool
empty() const

Returns true iff the table is empty.

std::size_t
buckets() const

Returns the number of allocated buckets.