Poco

template < class Value, class HashFunc = Hash < Value >>

class LinearHashTable

File Information

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

Bucket

typedef std::vector < Value > Bucket;

BucketIterator

typedef typename Bucket::iterator BucketIterator;

BucketVec

typedef std::vector < Bucket > BucketVec;

BucketVecIterator

typedef typename BucketVec::iterator BucketVecIterator;

ConstPointer

typedef const Value * ConstPointer;

ConstReference

typedef const Value & ConstReference;

Hash

typedef HashFunc Hash;

Pointer

typedef Value * Pointer;

Reference

typedef Value & Reference;

ValueType

typedef Value ValueType;

Constructors

LinearHashTable inline

LinearHashTable(
    std::size_t initialReserve = 64
);

Creates the LinearHashTable, using the given initialReserve.

LinearHashTable inline

LinearHashTable(
    const LinearHashTable & table
);

Creates the LinearHashTable by copying another one.

Destructor

~LinearHashTable inline

~LinearHashTable();

Destroys the LinearHashTable.

Member Functions

begin inline

ConstIterator begin() const;

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

begin inline

Iterator begin();

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

buckets inline

std::size_t buckets() const;

Returns the number of allocated buckets.

clear inline

void clear();

Erases all elements.

count inline

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

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

empty inline

bool empty() const;

Returns true iff the table is empty.

end inline

ConstIterator end() const;

Returns an iterator pointing to the end of the table.

end inline

Iterator end();

Returns an iterator pointing to the end of the table.

erase inline

void erase(
    Iterator it
);

Erases the element pointed to by it.

erase inline

void erase(
    const Value & value
);

Erases the element with the given value, if it exists.

find inline

ConstIterator find(
    const Value & value
) const;

Finds an entry in the table.

find inline

Iterator find(
    const Value & value
);

Finds an entry in the table.

insert inline

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 = inline

LinearHashTable & operator = (
    const LinearHashTable & table
);

Assigns another LinearHashTable.

size inline

std::size_t size() const;

Returns the number of elements in the table.

swap inline

void swap(
    LinearHashTable & table
);

Swaps the LinearHashTable with another one.

bucketAddress protected inline

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

bucketAddressForHash protected inline

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

calcSize protected static inline

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

merge protected inline

void merge();

split protected inline

void split();

Securely control IoT edge devices from anywhere   Connect a Device