TPIE

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

138  : 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:66
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:69
tpie::chaining_hash_table::resize
void resize(size_t z)
Resize table to given number of buckets and clear contents.
Definition: hash_map.h:120

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

143  {
144  if (size == 0) return buckets.size();
145  for(size_t i=0; true; ++i)
146  if (buckets[i].value != unused) return i;
147  }
tpie::chaining_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:66
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:69
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 106 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().

106  {
107  first_free = 0;
108  for (size_t i=0; i < buckets.size(); ++i) {
109  buckets[i].value = unused;
110  buckets[i].next = static_cast<index_t>(i+1);
111  }
112  for (typename array<index_t>::iterator i=list.begin(); i != list.end(); ++i)
113  *i = std::numeric_limits<index_t>::max();
114  }
tpie::array< index_t >::iterator
array_iter_base< index_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
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:69
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 152 of file hash_map.h.

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

152 {return buckets.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::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 195 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.

195  {
196  size_t hv = h(val) % list.size();
197  size_t cur = list[hv];
198  size_t prev = std::numeric_limits<size_t>::max();
199 
200  while (!e(buckets[cur].value, val)) {
201  prev = cur;
202  cur = buckets[cur].next;
203  }
204 
205  if (prev == std::numeric_limits<size_t>::max())
206  list[hv] = buckets[cur].next;
207  else
208  buckets[prev].next = buckets[cur].next;
209 
210  buckets[cur].next = first_free;
211  buckets[cur].value = unused;
212  first_free = cur;
213  --size;
214  }
tpie::chaining_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:66
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:526
tpie::chaining_hash_table::unused
value_t unused
Special constant indicating an unused table entry.
Definition: hash_map.h:69
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 158 of file hash_map.h.

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

158  {
159  size_t v = list[h(value) % list.size()];
160  while (v != std::numeric_limits<index_t>::max()) {
161  if (e(buckets[v].value, value)) return v;
162  v = buckets[v].next;
163  }
164  return buckets.size();
165  }
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::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 95 of file hash_map.h.

95 {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 101 of file hash_map.h.

101 {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 173 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().

173  {
174  // First, look for the value in table.
175  size_t hv = h(val) % list.size();
176  size_t v = list[hv];
177  while (v != std::numeric_limits<index_t>::max()) {
178  if (e(buckets[v].value, val)) return std::make_pair(v, false);
179  v = buckets[v].next;
180  }
181  // It wasn't found. Insert into free bucket.
182  v = first_free;
183  first_free = buckets[v].next;
184  buckets[v].value = val;
185  buckets[v].next = list[hv];
186  list[hv] = v;
187  ++size;
188  return std::make_pair(v, true);
189  }
tpie::chaining_hash_table::size
size_t size
Number of buckets in hash table.
Definition: hash_map.h:66
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::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 75 of file hash_map.h.

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

75  {
76  return array<index_t>::memory_coefficient() *sc + array<bucket_t>::memory_coefficient();
77  }
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::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 83 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().

83  {
84  return array<index_t>::memory_coefficient() * 100.0
85  + array<index_t>::memory_overhead() + sizeof(chaining_hash_table)
86  + array<bucket_t>::memory_overhead()
87  - sizeof(array<index_t>)
88  - sizeof(array<bucket_t>);
89  }
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:135
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::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 120 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().

120  {
121  buckets.resize(z);
122  size_t x=static_cast<size_t>(99+static_cast<double>(z)*sc)|1;
123  while (!is_prime(x)) x -= 2;
124  list.resize(x);
125  clear();
126  }
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:106
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::chaining_hash_table< value_t, hash_t, equal_t, index_t >::size

Number of buckets in hash table.

Definition at line 66 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 69 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: