Hash table handling hash collisions by linear probing. More...
#include <tpie/hash_map.h>
Public Member Functions | |
void | clear () |
Clear contents of hash table. More... | |
void | resize (size_t element_count) |
Resize table to given number of buckets and clear contents. More... | |
linear_probing_hash_table (size_t ee, value_t u, const hash_t &hash, const equal_t &equal) | |
Construct a hash table. More... | |
size_t | find (const value_t &value) const |
Find bucket entry containing given value, or end() if not found. More... | |
size_t | end () const |
Return index greater than any buckets in use. More... | |
size_t | begin () const |
Return first bucket entry in use. More... | |
value_t & | get (size_t idx) |
Get contents of a bucket by its index. More... | |
const value_t & | get (size_t idx) const |
Get contents of a bucket by its index. More... | |
std::pair< size_t, bool > | insert (const value_t &val) |
Insert value into hash table. More... | |
void | erase (const value_t &val) |
Erase value from table. More... | |
Static Public Member Functions | |
static double | memory_coefficient () |
Return the memory coefficient of the structure. More... | |
static double | memory_overhead () |
Return the memory overhead of the structure. More... | |
Public Attributes | |
size_t | size |
Number of buckets in hash table. More... | |
value_t | unused |
Special constant indicating an unused table entry. More... | |
Hash table handling hash collisions by linear probing.
value_t | Value to store. |
hash_t | Hash function to use. |
equal_t | Equality predicate. |
index_t | Index type into bucket array. Always size_t. |
Definition at line 225 of file hash_map.h.
|
inline |
Construct a hash table.
ee | Number of buckets in initial hash table. |
u | Special value to be used to indicate unused entries in table. |
hash | Hashing function. |
equal | Equality predicate. |
Definition at line 278 of file hash_map.h.
References tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::resize().
Referenced by tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::memory_overhead().
|
inline |
Return first bucket entry in use.
Definition at line 306 of file hash_map.h.
References tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::size, tpie::array< T, Allocator >::size(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::unused.
|
inline |
Clear contents of hash table.
Definition at line 259 of file hash_map.h.
References tpie::array< T, Allocator >::begin(), tpie::array< T, Allocator >::end(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::unused.
|
inline |
Return index greater than any buckets in use.
Definition at line 300 of file hash_map.h.
References tpie::array< T, Allocator >::size().
|
inline |
Erase value from table.
val | Value to erase. |
Definition at line 343 of file hash_map.h.
References tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::find(), tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::size, tpie::array< T, Allocator >::size(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::unused.
|
inline |
Find bucket entry containing given value, or end() if not found.
value | Sought value. |
Definition at line 286 of file hash_map.h.
References tpie::array< T, Allocator >::size(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::unused.
Referenced by tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::erase().
|
inline |
Get contents of a bucket by its index.
idx | The index of the bucket to fetch. |
Definition at line 316 of file hash_map.h.
|
inline |
Get contents of a bucket by its index.
idx | The index of the bucket to fetch. |
Definition at line 322 of file hash_map.h.
|
inline |
Insert value into hash table.
val | Value to insert. |
Definition at line 328 of file hash_map.h.
References tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::size, tpie::array< T, Allocator >::size(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::unused.
|
inlinestatic |
Return the memory coefficient of the structure.
Allocating a structure with n elements will use at most bytes. This does not include memory overhead incurred if the structure is allocated using new.
Definition at line 242 of file hash_map.h.
References tpie::array< T, Allocator >::memory_coefficient().
|
inlinestatic |
Return the memory overhead of the structure.
Definition at line 250 of file hash_map.h.
References tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::linear_probing_hash_table(), tpie::array< T, Allocator >::memory_coefficient(), and tpie::array< T, Allocator >::memory_overhead().
|
inline |
Resize table to given number of buckets and clear contents.
z | New size of hash table. |
Definition at line 268 of file hash_map.h.
References tpie::is_prime(), tpie::array< T, Allocator >::resize(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::unused.
Referenced by tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::linear_probing_hash_table().
size_t tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::size |
Number of buckets in hash table.
Definition at line 233 of file hash_map.h.
Referenced by tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::begin(), tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::erase(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::insert().
value_t tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::unused |
Special constant indicating an unused table entry.
Definition at line 236 of file hash_map.h.
Referenced by tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::begin(), tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::clear(), tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::erase(), tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::find(), tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::insert(), and tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::resize().