Teuchos Package Browser (Single Doxygen Collection)  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Teuchos_Hashtable.hpp
Go to the documentation of this file.
1 // @HEADER
2 // *****************************************************************************
3 // Teuchos: Common Tools Package
4 //
5 // Copyright 2004 NTESS and the Teuchos contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
10 #ifndef TEUCHOS_HASHTABLE_H
11 #define TEUCHOS_HASHTABLE_H
12 
17 #include "Teuchos_ConfigDefs.hpp"
18 #include "Teuchos_Array.hpp"
19 #include "Teuchos_HashUtils.hpp"
20 
21 namespace Teuchos
22 {
23  using std::string;
24 
28  template<class Key, class Value> class HashPair
29  {
30  public:
32  inline HashPair() : key_(), value_() {;}
34  inline HashPair(const Key& key, const Value& value)
35  : key_(key), value_(value) {;}
36 
38  Key key_;
40  Value value_;
41  };
42 
48  template<class Key, class Value> class Hashtable
49  {
50  public:
51 
53  inline Hashtable(int capacity=101, double rehashDensity = 0.8);
54 
56  inline bool containsKey(const Key& key) const ;
57 
59  inline const Value& get(const Key& key) const ;
60 
62  inline void put(const Key& key, const Value& value);
63 
65  inline void remove(const Key& key);
66 
68  inline int size() const {return count_;}
69 
71  inline void arrayify(Array<Key>& keys, Array<Value>& values) const ;
72 
74  inline double avgDegeneracy() const {return avgDegeneracy_;}
75 
77  inline double density() const {return ((double)count_)/((double) capacity_);}
78 
80  inline void setRehashDensity(double rehashDensity);
81 
83  inline std::string toString() const ;
84 
85  private:
86 
87  inline void rehash();
88  inline int nextPrime(int newCap) const ;
89  inline void accumulateAvgFill(int n) const ;
90 
91 
93  int count_;
94  int capacity_;
95  mutable Value mostRecentValue_;
96  mutable Key mostRecentKey_;
97 
98  mutable size_t nHits_;
99  mutable double avgDegeneracy_;
101  };
102 
103  template<class Key, class Value>
104  std::string toString(const Hashtable<Key, Value>& h);
105 
109  template<class Key, class Value>
110  std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h);
111 
112  template<class Key, class Value> inline
113  Hashtable<Key, Value>::Hashtable(int capacity, double rehashDensity):
114  data_(),
115  count_(0),
116  capacity_(HashUtils::nextPrime(capacity)),
117  nHits_(0),
118  avgDegeneracy_(0),
119  rehashDensity_(rehashDensity)
120  {
121  data_.resize(capacity_);
122  }
123 
124  template<class Key, class Value> inline
125  bool Hashtable<Key, Value>::containsKey(const Key& key) const
126  {
127  const Array<HashPair<Key, Value> >& candidates
128  = data_[hashCode(key) % capacity_];
129 
130  for (int i=0; i<candidates.length(); i++)
131  {
132  const HashPair<Key, Value>& c = candidates[i];
133  if (c.key_ == key)
134  {
135  // (Key&) mostRecentKey_ = key;
136  //(Value&) mostRecentValue_ = c.value_;
137  return true;
138  }
139  }
140  return false;
141  }
142 
143  template<class Key, class Value> inline
144  void Hashtable<Key, Value>::put(const Key& key, const Value& value)
145  {
146  int index = hashCode(key) % capacity_;
147 
148  Array<HashPair<Key, Value> >& local = data_[index];
149 
150  // check for duplicate key
151  for (int i=0; i<local.length(); i++)
152  {
153  if (local[i].key_ == key)
154  {
155  local[i].value_ = value;
156  return;
157  }
158  }
159 
160  // no duplicate key, so increment element count by one.
161  count_++;
162 
163  // check for need to resize.
164  if ((double) count_ > rehashDensity_ * (double) capacity_)
165  {
166  capacity_ = HashUtils::nextPrime(capacity_+1);
167  rehash();
168  // recaluate index
169  index = hashCode(key) % capacity_;
170  }
171 
172  data_[index].append(HashPair<Key, Value>(key, value));
173  }
174 
175 
176 
177  template<class Key, class Value> inline
179  {
180  Array<Array<HashPair<Key, Value> > > tmp(capacity_);
181 
182  for (int i=0; i<data_.length(); i++)
183  {
184  for (int j=0; j<data_[i].length(); j++)
185  {
186  int newIndex = hashCode(data_[i][j].key_) % capacity_;
187  tmp[newIndex].append(data_[i][j]);
188  }
189  }
190 
191  data_ = tmp;
192  }
193 
194 
195  template<class Key, class Value> inline
197  {
198  keys.reserve(size());
199  values.reserve(size());
200 
201  for (int i=0; i<data_.length(); i++)
202  {
203  for (int j=0; j<data_[i].length(); j++)
204  {
205  keys.append(data_[i][j].key_);
206  values.append(data_[i][j].value_);
207  }
208  }
209  }
210 
211  template<class Key, class Value> inline
213  {
214  Array<Key> keys;
215  Array<Value> values;
216  arrayify(keys, values);
217 
218  std::string rtn = "[";
219  for (int i=0; i<keys.length(); i++)
220  {
221  rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
222  + "}";
223  if (i < keys.length()-1) rtn += ", ";
224  }
225  rtn += "]";
226 
227  return rtn;
228  }
229 
230  template<class Key, class Value> inline
231  std::string toString(const Hashtable<Key, Value>& h)
232  {
233  Array<Key> keys;
234  Array<Value> values;
235  h.arrayify(keys, values);
236 
237  std::string rtn = "[";
238  for (int i=0; i<keys.length(); i++)
239  {
240  rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
241  + "}";
242  if (i < keys.length()-1) rtn += ", ";
243  }
244  rtn += "]";
245 
246  return rtn;
247  }
248 
249  template<class Key, class Value> inline
250  const Value& Hashtable<Key, Value>::get(const Key& key) const
251  {
252  TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
253  std::runtime_error,
254  "Hashtable<Key, Value>::get: key "
255  << Teuchos::toString(key)
256  << " not found in Hashtable"
257  << toString());
258 
259  const Array<HashPair<Key, Value> >& candidates
260  = data_[hashCode(key) % capacity_];
261 
262  accumulateAvgFill(candidates.length());
263 
264  for (int i=0; i<candidates.length(); i++)
265  {
266  const HashPair<Key, Value>& c = candidates[i];
267  if (c.key_ == key)
268  {
269  return c.value_;
270  }
271  }
272  return mostRecentValue_;
273  }
274 
275 
276  template<class Key, class Value> inline
277  void Hashtable<Key, Value>::remove(const Key& key)
278  {
279  TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
280  std::runtime_error,
281  "Hashtable<Key, Value>::remove: key "
282  << Teuchos::toString(key)
283  << " not found in Hashtable"
284  << toString());
285 
286  count_--;
287  int h = hashCode(key) % capacity_;
288  const Array<HashPair<Key, Value> >& candidates = data_[h];
289 
290  for (int i=0; i<candidates.length(); i++)
291  {
292  const HashPair<Key, Value>& c = candidates[i];
293  if (c.key_ == key)
294  {
295  data_[h].remove(i);
296  break;
297  }
298  }
299  }
300 
301  template<class Key, class Value> inline
303  {
304  avgDegeneracy_ = ((double) nHits_)/(nHits_ + 1.0) * avgDegeneracy_ + ((double) n)/(nHits_ + 1.0);
305  nHits_++;
306  }
307 
308  template<class Key, class Value> inline
309  std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h)
310  {
311  return os << toString(h);
312  }
313 
314 
315 }
316 
317 #endif // TEUCHOS_HASHTABLE_H
void remove(int i)
Remove the i-th element from the array, with optional boundschecking.
Templated hashtable class.
void reserve(size_type n)
Utilities for generating hashcodes. This is not a true hash ! For all ints and types less than ints i...
Array< T > & append(const T &x)
Add a new entry at the end of the array.
void arrayify(Array< Key > &keys, Array< Value > &values) const
Get lists of keys and values in Array form.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
Teuchos header file which uses auto-configuration information to include necessary C++ headers...
HashPair()
Empty constructor.
static int nextPrime(int newCapacity)
Value value_
Templated value variable.
std::string toString() const
Write to a std::string.
double avgDegeneracy() const
Return the average degeneracy (average number of entries per hash code).
Array< Array< HashPair< Key, Value > > > data_
double density() const
Return the density of the hashtable (num entries / capacity)
std::string toString(const HashSet< Key > &h)
bool containsKey(const Key &key) const
Check for the presence of a key.
Hashtable(int capacity=101, double rehashDensity=0.8)
Create an empty Hashtable.
Templated array class derived from the STL std::vector.
int nextPrime(int newCap) const
void put(const Key &key, const Value &value)
Put a new (key, value) pair in the table.
int length() const
Return number of elements in the array.
void setRehashDensity(double rehashDensity)
Set the density at which to do a rehash.
Helper class for Teuchos::Hashtable, representing a single &lt;key, value&gt; pair.
Utilities for generating hashcodes.
void accumulateAvgFill(int n) const
HashPair(const Key &key, const Value &value)
Basic &lt;key, value&gt; constructor.
const Value & get(const Key &key) const
Get the value indexed by key.
int size() const
Get the number of elements in the table.
void remove(const Key &key)
Remove from the table the element given by key.
Replacement for std::vector that is compatible with the Teuchos Memory Management classes...
Key key_
Templated key variable.