TPIE

v1.1rc1-6-g0c97303
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t > Class Template Reference

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...
 

Detailed Description

template<typename value_t, typename hash_t, typename equal_t, typename index_t>
class tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >

Hash table handling hash collisions by linear probing.

Template Parameters
value_tValue to store.
hash_tHash function to use.
equal_tEquality predicate.
index_tIndex type into bucket array. Always size_t.

Definition at line 288 of file hash_map.h.

Constructor & Destructor Documentation

template<typename value_t , typename hash_t , typename equal_t , typename index_t >
tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::linear_probing_hash_table ( size_t  ee,
value_t  u,
const hash_t &  hash,
const equal_t &  equal 
)
inline

Construct a hash table.

Parameters
eeNumber of buckets in initial hash table.
uSpecial value to be used to indicate unused entries in table.
hashHashing function.
equalEquality predicate.

Definition at line 341 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().

342  :
343  h(hash), e(equal), size(0), unused(u) {resize(ee);}
tpie::linear_probing_hash_table::resize
void resize(size_t element_count)
Resize table to given number of buckets and clear contents.
Definition: hash_map.h:331
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:299
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:296

Member Function Documentation

template<typename value_t , typename hash_t , typename equal_t , typename index_t >
size_t tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::begin ( ) const
inline

Return first bucket entry in use.

Definition at line 369 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.

369  {
370  if (size == 0) return elements.size();
371  for(size_t i=0; true; ++i)
372  if (elements[i] != unused) return i;
373  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:299
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:296
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
void tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::clear ( )
inline

Clear contents of hash table.

Definition at line 322 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.

322  {
323  for (typename array<value_t>::iterator i=elements.begin(); i != elements.end(); ++i)
324  *i = unused;
325  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:299
tpie::array< value_t >::iterator
array_iter_base< value_t, true > iterator
Iterator over an array.
Definition: array.h:152
tpie::array::end
iterator end()
Return an iterator to the end of the array.
Definition: array.h:288
tpie::array::begin
iterator begin()
Return an iterator to the beginning of the array.
Definition: array.h:274
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
size_t tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::end ( ) const
inline

Return index greater than any buckets in use.

Definition at line 363 of file hash_map.h.

References tpie::array< T, Allocator >::size().

363 {return elements.size();}
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
void tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::erase ( const value_t &  val)
inline

Erase value from table.

Parameters
valValue to erase.

Definition at line 406 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.

406  {
407  size_t slot = find(val);
408  size_t cur = (slot+1) % elements.size();
409  assert(size < elements.size());
410  while (elements[cur] != unused) {
411  size_t x = h(elements[cur]) % elements.size();
412  if (x <= slot && (cur > slot || x > cur)) {
413  elements[slot] = elements[cur];
414  slot = cur;
415  }
416  cur = (cur+1) % elements.size();
417  }
418  elements[slot] = unused;
419  --size;
420  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:299
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:296
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
tpie::linear_probing_hash_table::find
size_t find(const value_t &value) const
Find bucket entry containing given value, or end() if not found.
Definition: hash_map.h:349
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
size_t tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::find ( const value_t &  value) const
inline

Find bucket entry containing given value, or end() if not found.

Parameters
valueSought value.

Definition at line 349 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().

349  {
350  size_t v = h(value) % elements.size();
351  while (elements[v] != unused) {
352  if (e(elements[v], value)) return v;
353  v = (v + 1) % elements.size();
354  }
355  return elements.size();
356  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:299
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
value_t& tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::get ( size_t  idx)
inline

Get contents of a bucket by its index.

Parameters
idxThe index of the bucket to fetch.

Definition at line 379 of file hash_map.h.

379 {return elements[idx];}
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
const value_t& tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::get ( size_t  idx) const
inline

Get contents of a bucket by its index.

Parameters
idxThe index of the bucket to fetch.

Definition at line 385 of file hash_map.h.

385 {return elements[idx];}
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
std::pair<size_t, bool> tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::insert ( const value_t &  val)
inline

Insert value into hash table.

Parameters
valValue to insert.
Returns
(index, new)-pair, where index contains the index of the entry, and new is true if the entry wasn't already in the table.

Definition at line 391 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.

391  {
392  size_t v = h(val) % elements.size();
393  while (elements[v] != unused) {
394  if (e(elements[v],val)) {return std::make_pair(v, false);}
395  v = (v + 1) % elements.size();
396  }
397  ++size;
398  elements[v] = val;
399  return std::make_pair(v, true);
400  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:299
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:296
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
static double tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::memory_coefficient ( )
inlinestatic

Return the memory coefficient of the structure.

Allocating a structure with n elements will use at most $ \lfloor \mathrm{memory\_coefficient} \cdot n + \mathrm{memory\_overhead} \rfloor $ bytes. This does not include memory overhead incurred if the structure is allocated using new.

Returns
The memory coefficient of the structure.

Definition at line 305 of file hash_map.h.

References tpie::array< T, Allocator >::memory_coefficient().

305  {
306  return array<value_t>::memory_coefficient() *sc;
307  }
tpie::array::memory_coefficient
static double memory_coefficient()
Return the memory coefficient of the structure.
Definition: array.h:360
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
static double tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::memory_overhead ( )
inlinestatic

Return the memory overhead of the structure.

See also
memory_coefficient()
Returns
The memory overhead.

Definition at line 313 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().

313  {
314  return array<value_t>::memory_coefficient() * 100.0
315  + array<value_t>::memory_overhead() + sizeof(linear_probing_hash_table) - sizeof(array<value_t>);
316  }
tpie::linear_probing_hash_table::linear_probing_hash_table
linear_probing_hash_table(size_t ee, value_t u, const hash_t &hash, const equal_t &equal)
Construct a hash table.
Definition: hash_map.h:341
tpie::array::memory_coefficient
static double memory_coefficient()
Return the memory coefficient of the structure.
Definition: array.h:360
tpie::array::memory_overhead
static double memory_overhead()
Return the memory overhead of the structure.
Definition: array.h:367
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
void tpie::linear_probing_hash_table< value_t, hash_t, equal_t, index_t >::resize ( size_t  element_count)
inline

Resize table to given number of buckets and clear contents.

Parameters
zNew size of hash table.

Definition at line 331 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().

331  {
332  size_t x=(99+static_cast<size_t>(static_cast<float>(element_count)*sc))|1;
333  while (!is_prime(x)) x -= 2;
334  elements.resize(x, unused);
335  }
tpie::is_prime
bool is_prime(size_type i)
Check if i is a prime.
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:299
tpie::array::resize
void resize(size_t size, const T &elm)
Change the size of the array.
Definition: array.h:431

Member Data Documentation

template<typename value_t , typename hash_t , typename equal_t , typename index_t >
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 296 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().

template<typename value_t , typename hash_t , typename equal_t , typename index_t >
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 299 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().

The documentation for this class was generated from the following file:
  • from TPIE v1.1rc1-6-g0c97303 (browse source). Generated on Fri Mar 31 2017 00:00:12 by Doxygen 1.8.7