Teuchos Package Browser (Single Doxygen Collection) Version of the Day
Loading...
Searching...
No Matches
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
50#include "Teuchos_Array.hpp"
51#include "Teuchos_HashUtils.hpp"
52
53namespace 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
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
129
130 mutable size_t nHits_;
131 mutable double avgDegeneracy_;
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
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
158 {
160 = data_[hashCode(key) % capacity_];
161
162 for (int i=0; i<candidates.length(); i++)
163 {
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 {
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 {
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 {
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
292 = data_[hashCode(key) % capacity_];
293
294 accumulateAvgFill(candidates.length());
295
296 for (int i=0; i<candidates.length(); i++)
297 {
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
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 {
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
Templated array class derived from the STL std::vector.
Teuchos header file which uses auto-configuration information to include necessary C++ headers.
Utilities for generating hashcodes.
int size(const Comm< Ordinal > &comm)
Get the number of processes in the communicator.
Helper class for Teuchos::Hashtable, representing a single <key, value> pair.
Key key_
Templated key variable.
HashPair()
Empty constructor.
Value value_
Templated value variable.
HashPair(const Key &key, const Value &value)
Basic <key, value> constructor.
Utilities for generating hashcodes. This is not a true hash ! For all ints and types less than ints i...
static int nextPrime(int newCapacity)
Templated hashtable class.
double density() const
Return the density of the hashtable (num entries / capacity)
std::string toString() const
Write to a std::string.
void setRehashDensity(double rehashDensity)
Set the density at which to do a rehash.
Array< Array< HashPair< Key, Value > > > data_
void accumulateAvgFill(int n) const
const Value & get(const Key &key) const
Get the value indexed by key.
int nextPrime(int newCap) const
void arrayify(Array< Key > &keys, Array< Value > &values) const
Get lists of keys and values in Array form.
int size() const
Get the number of elements in the table.
void put(const Key &key, const Value &value)
Put a new (key, value) pair in the table.
double avgDegeneracy() const
Return the average degeneracy (average number of entries per hash code).
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.
void remove(const Key &key)
Remove from the table the element given by key.
Concrete serial communicator subclass.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
std::ostream & operator<<(std::ostream &os, BigUInt< n > a)
std::string toString(const HashSet< Key > &h)