template class Poco::HashTable

Overview

A HashTable stores a key value pair that can be looked up via a hashed key. More…

#include <HashTable.h>

template <
    class Key,
    class Value,
    class KeyHashFunction = HashFunction<Key>
    >
class HashTable
{
public:
    // typedefs

    typedef std::map<Key, Value> HashEntryMap;
    typedef HashEntryMap** HashTableVector;
    typedef HashEntryMap::const_iterator ConstIterator;
    typedef HashEntryMap::iterator Iterator;

    // construction

    HashTable(UInt32 initialSize = 251);
    HashTable(const HashTable& ht);

    // methods

    HashTable&
    operator=(const HashTable& ht);

    void
    clear();

    UInt32
    insert(
        const Key& key,
        const Value& value
        );

    Value&
    insertRaw(
        const Key& key,
        UInt32 hsh,
        const Value& value
        );

    UInt32
    update(
        const Key& key,
        const Value& value
        );

    void
    updateRaw(
        const Key& key,
        UInt32 hsh,
        const Value& value
        );

    void
    remove(const Key& key);

    void
    removeRaw(
        const Key& key,
        UInt32 hsh
        );

    UInt32
    hash(const Key& key) const;

    const Value&
    get(const Key& key) const;

    const Value&
    getRaw(
        const Key& key,
        UInt32 hsh
        ) const;

    Value&
    get(const Key& key);

    const Value&
    operator[](const Key& key) const;

    Value&
    operator[](const Key& key);

    const Key&
    getKeyRaw(
        const Key& key,
        UInt32 hsh
        );

    bool
    get(
        const Key& key,
        Value& v
        ) const;

    bool
    getRaw(
        const Key& key,
        UInt32 hsh,
        Value& v
        ) const;

    bool
    exists(const Key& key);

    bool
    existsRaw(
        const Key& key,
        UInt32 hsh
        );

    std::size_t
    size() const;

    UInt32
    maxCapacity() const;

    void
    resize(UInt32 newSize);

    HashStatistic
    currentState(bool details = false) const;
};

Detailed Documentation

A HashTable stores a key value pair that can be looked up via a hashed key.

Collision handling is done via overflow maps(!). With small hash tables performance of this data struct will be closer to that a map than a hash table, i.e. slower. On the plus side, this class offers remove operations. Also HashTable full errors are not possible. If a fast HashTable implementation is needed and the remove operation is not required, use SimpleHashTable instead.

This class is NOT thread safe.

Construction

~HashTable()

Destroys the HashTable.

Methods

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

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

UInt32
update(
    const Key& key,
    const Value& value
    )

Returns the hash value of the inserted item.

Replaces an existing entry if it finds one

void
updateRaw(
    const Key& key,
    UInt32 hsh,
    const Value& value
    )

Returns the hash value of the inserted item.

Replaces an existing entry if it finds one

void
removeRaw(
    const Key& key,
    UInt32 hsh
    )

Performance version, allows to specify the hash value.

const Value&
get(const Key& key) const

Throws an exception if the value does not exist.

const Value&
getRaw(
    const Key& key,
    UInt32 hsh
    ) const

Throws an exception if the value does not exist.

Value&
get(const Key& key)

Throws an exception if the value does not exist.

const Key&
getKeyRaw(
    const Key& key,
    UInt32 hsh
    )

Throws an exception if the key does not exist.

returns a reference to the internally stored key. Useful when someone does an insert and wants for performance reason only to store a pointer to the key in another collection

bool
get(
    const Key& key,
    Value& v
    ) const

Sets v to the found value, returns false if no value was found.

bool
getRaw(
    const Key& key,
    UInt32 hsh,
    Value& v
    ) const

Sets v to the found value, returns false if no value was found.

std::size_t
size() const

Returns the number of elements already inserted into the HashTable.

void
resize(UInt32 newSize)

Resizes the hashtable, rehashes all existing entries. Expensive!

HashStatistic
currentState(bool details = false) const

Returns the current internal state.