TPIE

2362a60
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 225 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 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().

279  :
280  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:268
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:236
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:233

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

306  {
307  if (size == 0) return elements.size();
308  for(size_t i=0; true; ++i)
309  if (elements[i] != unused) return i;
310  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:236
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:233
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
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 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.

259  {
260  for (typename array<value_t>::iterator i=elements.begin(); i != elements.end(); ++i)
261  *i = unused;
262  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:236
tpie::array< value_t >::iterator
array_iter_base< value_t, true > iterator
Iterator over an array.
Definition: array.h:153
tpie::array::end
iterator end()
Return an iterator to the end of the array.
Definition: array.h:321
tpie::array::begin
iterator begin()
Return an iterator to the beginning of the array.
Definition: array.h:307
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 300 of file hash_map.h.

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

300 {return elements.size();}
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
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 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.

343  {
344  size_t slot = find(val);
345  size_t cur = (slot+1) % elements.size();
346  assert(size < elements.size());
347  while (elements[cur] != unused) {
348  size_t x = h(elements[cur]) % elements.size();
349  if (x <= slot && (cur > slot || x > cur)) {
350  elements[slot] = elements[cur];
351  slot = cur;
352  }
353  cur = (cur+1) % elements.size();
354  }
355  elements[slot] = unused;
356  --size;
357  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:236
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:233
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
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:286
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 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().

286  {
287  size_t v = h(value) % elements.size();
288  while (elements[v] != unused) {
289  if (e(elements[v], value)) return v;
290  v = (v + 1) % elements.size();
291  }
292  return elements.size();
293  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:236
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
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 316 of file hash_map.h.

316 {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 322 of file hash_map.h.

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

328  {
329  size_t v = h(val) % elements.size();
330  while (elements[v] != unused) {
331  if (e(elements[v],val)) {return std::make_pair(v, false);}
332  v = (v + 1) % elements.size();
333  }
334  ++size;
335  elements[v] = val;
336  return std::make_pair(v, true);
337  }
tpie::linear_probing_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:236
tpie::linear_probing_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:233
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
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 242 of file hash_map.h.

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

242  {
243  return array<value_t>::memory_coefficient() *sc;
244  }
tpie::array::memory_coefficient
static double memory_coefficient()
Return the memory coefficient of the structure.
Definition: array.h:393
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 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().

250  {
251  return array<value_t>::memory_coefficient() * 100.0
252  + array<value_t>::memory_overhead() + sizeof(linear_probing_hash_table) - sizeof(array<value_t>);
253  }
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:278
tpie::array::memory_coefficient
static double memory_coefficient()
Return the memory coefficient of the structure.
Definition: array.h:393
tpie::array::memory_overhead
static double memory_overhead()
Return the memory overhead of the structure.
Definition: array.h:400
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 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().

268  {
269  size_t x=(99+static_cast<size_t>(static_cast<float>(element_count)*sc))|1;
270  while (!is_prime(x)) x -= 2;
271  elements.resize(x, unused);
272  }
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:236
tpie::array::resize
void resize(size_t size, const T &elm)
Change the size of the array.
Definition: array.h:485

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

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

The documentation for this class was generated from the following file: