TPIE

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

Hash table handling hash collisions by chaining. More...

#include <tpie/hash_map.h>

Public Member Functions

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...
 
void clear ()
 Clear contents of hash table. More...
 
void resize (size_t z)
 Resize table to given number of buckets and clear contents. More...
 
 chaining_hash_table (size_t ee, value_t u, const hash_t &hash, const equal_t &equal)
 Construct a hash table. More...
 
size_t begin ()
 Return first bucket entry in use. More...
 
size_t end () const
 Return index greater than any buckets in use. More...
 
size_t find (const value_t &value) const
 Find bucket entry containing given value, or end() if not found. 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::chaining_hash_table< value_t, hash_t, equal_t, index_t >

Hash table handling hash collisions by chaining.

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 107 of file hash_map.h.

Constructor & Destructor Documentation

template<typename value_t , typename hash_t , typename equal_t , typename index_t >
tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::chaining_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 198 of file hash_map.h.

References tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::resize().

Referenced by tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::memory_overhead().

201  : h(hash), e(equal), size(0), unused(u) {resize(ee);};
tpie::chaining_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:129
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:132
tpie::chaining_hash_table::resize
void resize(size_t z)
Resize table to given number of buckets and clear contents.
Definition: hash_map.h:183

Member Function Documentation

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

Return first bucket entry in use.

Definition at line 206 of file hash_map.h.

References tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::size, tpie::array< T, Allocator >::size(), and tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::unused.

206  {
207  if (size == 0) return buckets.size();
208  for(size_t i=0; true; ++i)
209  if (buckets[i].value != unused) return i;
210  }
tpie::chaining_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:129
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:132
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
void tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::clear ( )
inline

Clear contents of hash table.

Definition at line 169 of file hash_map.h.

References tpie::array< T, Allocator >::begin(), tpie::array< T, Allocator >::end(), tpie::array< T, Allocator >::size(), and tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::unused.

Referenced by tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::resize().

169  {
170  first_free = 0;
171  for (size_t i=0; i < buckets.size(); ++i) {
172  buckets[i].value = unused;
173  buckets[i].next = static_cast<index_t>(i+1);
174  }
175  for (typename array<index_t>::iterator i=list.begin(); i != list.end(); ++i)
176  *i = std::numeric_limits<index_t>::max();
177  }
tpie::array< index_t >::iterator
array_iter_base< index_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
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:132
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
size_t tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::end ( ) const
inline

Return index greater than any buckets in use.

Definition at line 215 of file hash_map.h.

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

215 {return buckets.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::chaining_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 258 of file hash_map.h.

References tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::size, tpie::array< T, Allocator >::size(), and tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::unused.

258  {
259  size_t hv = h(val) % list.size();
260  size_t cur = list[hv];
261  size_t prev = std::numeric_limits<size_t>::max();
262 
263  while (!e(buckets[cur].value, val)) {
264  prev = cur;
265  cur = buckets[cur].next;
266  }
267 
268  if (prev == std::numeric_limits<size_t>::max())
269  list[hv] = buckets[cur].next;
270  else
271  buckets[prev].next = buckets[cur].next;
272 
273  buckets[cur].next = first_free;
274  buckets[cur].value = unused;
275  first_free = cur;
276  --size;
277  }
tpie::chaining_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:129
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:132
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
size_t tpie::chaining_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 221 of file hash_map.h.

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

221  {
222  size_t v = list[h(value) % list.size()];
223  while (v != std::numeric_limits<index_t>::max()) {
224  if (e(buckets[v].value, value)) return v;
225  v = buckets[v].next;
226  }
227  return buckets.size();
228  }
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::chaining_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 158 of file hash_map.h.

158 {return buckets[idx].value;}
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
const value_t& tpie::chaining_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 164 of file hash_map.h.

164 {return buckets[idx].value;}
template<typename value_t , typename hash_t , typename equal_t , typename index_t >
std::pair<size_t, bool> tpie::chaining_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 236 of file hash_map.h.

References tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::size, and tpie::array< T, Allocator >::size().

236  {
237  // First, look for the value in table.
238  size_t hv = h(val) % list.size();
239  size_t v = list[hv];
240  while (v != std::numeric_limits<index_t>::max()) {
241  if (e(buckets[v].value, val)) return std::make_pair(v, false);
242  v = buckets[v].next;
243  }
244  // It wasn't found. Insert into free bucket.
245  v = first_free;
246  first_free = buckets[v].next;
247  buckets[v].value = val;
248  buckets[v].next = list[hv];
249  list[hv] = v;
250  ++size;
251  return std::make_pair(v, true);
252  }
tpie::chaining_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:129
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::chaining_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 138 of file hash_map.h.

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

138  {
139  return array<index_t>::memory_coefficient() *sc + array<bucket_t>::memory_coefficient();
140  }
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::chaining_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 146 of file hash_map.h.

References tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::chaining_hash_table(), tpie::array< T, Allocator >::memory_coefficient(), and tpie::array< T, Allocator >::memory_overhead().

146  {
147  return array<index_t>::memory_coefficient() * 100.0
148  + array<index_t>::memory_overhead() + sizeof(chaining_hash_table)
149  + array<bucket_t>::memory_overhead()
150  - sizeof(array<index_t>)
151  - sizeof(array<bucket_t>);
152  }
tpie::chaining_hash_table::chaining_hash_table
chaining_hash_table(size_t ee, value_t u, const hash_t &hash, const equal_t &equal)
Construct a hash table.
Definition: hash_map.h:198
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::chaining_hash_table< value_t, hash_t, equal_t, index_t >::resize ( size_t  z)
inline

Resize table to given number of buckets and clear contents.

Parameters
zNew size of hash table.

Definition at line 183 of file hash_map.h.

References tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::clear(), tpie::is_prime(), and tpie::array< T, Allocator >::resize().

Referenced by tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::chaining_hash_table().

183  {
184  buckets.resize(z);
185  size_t x=static_cast<size_t>(99+static_cast<double>(z)*sc)|1;
186  while (!is_prime(x)) x -= 2;
187  list.resize(x);
188  clear();
189  }
tpie::is_prime
bool is_prime(size_type i)
Check if i is a prime.
tpie::chaining_hash_table::clear
void clear()
Clear contents of hash table.
Definition: hash_map.h:169
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::chaining_hash_table< value_t, hash_t, equal_t, index_t >::size

Number of buckets in hash table.

Definition at line 129 of file hash_map.h.

Referenced by tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::begin(), tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::erase(), and tpie::chaining_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::chaining_hash_table< value_t, hash_t, equal_t, index_t >::unused

Special constant indicating an unused table entry.

Definition at line 132 of file hash_map.h.

Referenced by tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::begin(), tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::clear(), and tpie::chaining_hash_table< value_t, hash_t, equal_t, index_t >::erase().

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