Teuchos - Trilinos Tools Package  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 //
4 // Teuchos: Common Tools Package
5 // Copyright (2004) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38 //
39 // ***********************************************************************
40 // @HEADER
41 
42 #ifndef TEUCHOS_HASHTABLE_H
43 #define TEUCHOS_HASHTABLE_H
44 
49 #include "Teuchos_ConfigDefs.hpp"
50 #include "Teuchos_Array.hpp"
51 #include "Teuchos_HashUtils.hpp"
52 
53 namespace Teuchos
54 {
55  using std::string;
56 
60  template<class Key, class Value> class HashPair
61  {
62  public:
64  inline HashPair() : key_(), value_() {;}
66  inline HashPair(const Key& key, const Value& value)
67  : key_(key), value_(value) {;}
68 
70  Key key_;
72  Value value_;
73  };
74 
80  template<class Key, class Value> class Hashtable
81  {
82  public:
83 
85  inline Hashtable(int capacity=101, double rehashDensity = 0.8);
86 
88  inline bool containsKey(const Key& key) const ;
89 
91  inline const Value& get(const Key& key) const ;
92 
94  inline void put(const Key& key, const Value& value);
95 
97  inline void remove(const Key& key);
98 
100  inline int size() const {return count_;}
101 
103  inline void arrayify(Array<Key>& keys, Array<Value>& values) const ;
104 
106  inline double avgDegeneracy() const {return avgDegeneracy_;}
107 
109  inline double density() const {return ((double)count_)/((double) capacity_);}
110 
112  inline void setRehashDensity(double rehashDensity);
113 
115  inline std::string toString() const ;
116 
117  private:
118 
119  inline void rehash();
120  inline int nextPrime(int newCap) const ;
121  inline void accumulateAvgFill(int n) const ;
122 
123 
125  int count_;
126  int capacity_;
127  mutable Value mostRecentValue_;
128  mutable Key mostRecentKey_;
129 
130  mutable size_t nHits_;
131  mutable double avgDegeneracy_;
132  double rehashDensity_;
133  };
134 
135  template<class Key, class Value>
136  std::string toString(const Hashtable<Key, Value>& h);
137 
141  template<class Key, class Value>
142  std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h);
143 
144  template<class Key, class Value> inline
145  Hashtable<Key, Value>::Hashtable(int capacity, double rehashDensity):
146  data_(),
147  count_(0),
148  capacity_(HashUtils::nextPrime(capacity)),
149  nHits_(0),
150  avgDegeneracy_(0),
151  rehashDensity_(rehashDensity)
152  {
153  data_.resize(capacity_);
154  }
155 
156  template<class Key, class Value> inline
157  bool Hashtable<Key, Value>::containsKey(const Key& key) const
158  {
159  const Array<HashPair<Key, Value> >& candidates
160  = data_[hashCode(key) % capacity_];
161 
162  for (int i=0; i<candidates.length(); i++)
163  {
164  const HashPair<Key, Value>& c = candidates[i];
165  if (c.key_ == key)
166  {
167  // (Key&) mostRecentKey_ = key;
168  //(Value&) mostRecentValue_ = c.value_;
169  return true;
170  }
171  }
172  return false;
173  }
174 
175  template<class Key, class Value> inline
176  void Hashtable<Key, Value>::put(const Key& key, const Value& value)
177  {
178  int index = hashCode(key) % capacity_;
179 
180  Array<HashPair<Key, Value> >& local = data_[index];
181 
182  // check for duplicate key
183  for (int i=0; i<local.length(); i++)
184  {
185  if (local[i].key_ == key)
186  {
187  local[i].value_ = value;
188  return;
189  }
190  }
191 
192  // no duplicate key, so increment element count by one.
193  count_++;
194 
195  // check for need to resize.
196  if ((double) count_ > rehashDensity_ * (double) capacity_)
197  {
198  capacity_ = HashUtils::nextPrime(capacity_+1);
199  rehash();
200  // recaluate index
201  index = hashCode(key) % capacity_;
202  }
203 
204  data_[index].append(HashPair<Key, Value>(key, value));
205  }
206 
207 
208 
209  template<class Key, class Value> inline
211  {
212  Array<Array<HashPair<Key, Value> > > tmp(capacity_);
213 
214  for (int i=0; i<data_.length(); i++)
215  {
216  for (int j=0; j<data_[i].length(); j++)
217  {
218  int newIndex = hashCode(data_[i][j].key_) % capacity_;
219  tmp[newIndex].append(data_[i][j]);
220  }
221  }
222 
223  data_ = tmp;
224  }
225 
226 
227  template<class Key, class Value> inline
229  {
230  keys.reserve(size());
231  values.reserve(size());
232 
233  for (int i=0; i<data_.length(); i++)
234  {
235  for (int j=0; j<data_[i].length(); j++)
236  {
237  keys.append(data_[i][j].key_);
238  values.append(data_[i][j].value_);
239  }
240  }
241  }
242 
243  template<class Key, class Value> inline
245  {
246  Array<Key> keys;
247  Array<Value> values;
248  arrayify(keys, values);
249 
250  std::string rtn = "[";
251  for (int i=0; i<keys.length(); i++)
252  {
253  rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
254  + "}";
255  if (i < keys.length()-1) rtn += ", ";
256  }
257  rtn += "]";
258 
259  return rtn;
260  }
261 
262  template<class Key, class Value> inline
263  std::string toString(const Hashtable<Key, Value>& h)
264  {
265  Array<Key> keys;
266  Array<Value> values;
267  h.arrayify(keys, values);
268 
269  std::string rtn = "[";
270  for (int i=0; i<keys.length(); i++)
271  {
272  rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
273  + "}";
274  if (i < keys.length()-1) rtn += ", ";
275  }
276  rtn += "]";
277 
278  return rtn;
279  }
280 
281  template<class Key, class Value> inline
282  const Value& Hashtable<Key, Value>::get(const Key& key) const
283  {
284  TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
285  std::runtime_error,
286  "Hashtable<Key, Value>::get: key "
287  << Teuchos::toString(key)
288  << " not found in Hashtable"
289  << toString());
290 
291  const Array<HashPair<Key, Value> >& candidates
292  = data_[hashCode(key) % capacity_];
293 
294  accumulateAvgFill(candidates.length());
295 
296  for (int i=0; i<candidates.length(); i++)
297  {
298  const HashPair<Key, Value>& c = candidates[i];
299  if (c.key_ == key)
300  {
301  return c.value_;
302  }
303  }
304  return mostRecentValue_;
305  }
306 
307 
308  template<class Key, class Value> inline
309  void Hashtable<Key, Value>::remove(const Key& key)
310  {
311  TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
312  std::runtime_error,
313  "Hashtable<Key, Value>::remove: key "
314  << Teuchos::toString(key)
315  << " not found in Hashtable"
316  << toString());
317 
318  count_--;
319  int h = hashCode(key) % capacity_;
320  const Array<HashPair<Key, Value> >& candidates = data_[h];
321 
322  for (int i=0; i<candidates.length(); i++)
323  {
324  const HashPair<Key, Value>& c = candidates[i];
325  if (c.key_ == key)
326  {
327  data_[h].remove(i);
328  break;
329  }
330  }
331  }
332 
333  template<class Key, class Value> inline
335  {
336  avgDegeneracy_ = ((double) nHits_)/(nHits_ + 1.0) * avgDegeneracy_ + ((double) n)/(nHits_ + 1.0);
337  nHits_++;
338  }
339 
340  template<class Key, class Value> inline
341  std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h)
342  {
343  return os << toString(h);
344  }
345 
346 
347 }
348 
349 #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.
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).
double density() const
Return the density of the hashtable (num entries / capacity)
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.
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.
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.