42#ifndef TEUCHOS_HASHTABLE_H
43#define TEUCHOS_HASHTABLE_H
60 template<
class Key,
class Value>
class HashPair
91 inline const Value&
get(
const Key& key)
const ;
94 inline void put(
const Key& key,
const Value& value);
100 inline int size()
const {
return count_;}
109 inline double density()
const {
return ((
double)count_)/((
double) capacity_);}
115 inline std::string
toString()
const ;
119 inline void rehash();
120 inline int nextPrime(
int newCap)
const ;
121 inline void accumulateAvgFill(
int n)
const ;
127 mutable Value mostRecentValue_;
128 mutable Key mostRecentKey_;
130 mutable size_t nHits_;
131 mutable double avgDegeneracy_;
132 double rehashDensity_;
135 template<
class Key,
class Value>
141 template<
class Key,
class Value>
144 template<
class Key,
class Value>
inline
148 capacity_(
HashUtils::nextPrime(capacity)),
153 data_.resize(capacity_);
156 template<
class Key,
class Value>
inline
160 = data_[hashCode(key) % capacity_];
175 template<
class Key,
class Value>
inline
178 int index = hashCode(key) % capacity_;
183 for (
int i=0;
i<
local.length();
i++)
196 if ((
double) count_ > rehashDensity_ * (
double) capacity_)
198 capacity_ = HashUtils::nextPrime(capacity_+1);
201 index = hashCode(key) % capacity_;
209 template<
class Key,
class Value>
inline
214 for (
int i=0;
i<data_.length();
i++)
216 for (
int j=0;
j<data_[
i].length();
j++)
218 int newIndex = hashCode(data_[
i][
j].key_) % capacity_;
227 template<
class Key,
class Value>
inline
230 keys.reserve(size());
231 values.reserve(size());
233 for (
int i=0;
i<data_.length();
i++)
235 for (
int j=0;
j<data_[
i].length();
j++)
237 keys.append(data_[
i][
j].key_);
238 values.append(data_[
i][
j].value_);
243 template<
class Key,
class Value>
inline
248 arrayify(
keys, values);
250 std::string
rtn =
"[";
251 for (
int i=0;
i<
keys.length();
i++)
253 rtn +=
"{" + Teuchos::toString(
keys[
i]) +
", " + Teuchos::toString(values[
i])
255 if (
i <
keys.length()-1)
rtn +=
", ";
262 template<
class Key,
class Value>
inline
267 h.arrayify(
keys, values);
269 std::string
rtn =
"[";
270 for (
int i=0;
i<
keys.length();
i++)
272 rtn +=
"{" + Teuchos::toString(
keys[
i]) +
", " + Teuchos::toString(values[
i])
274 if (
i <
keys.length()-1)
rtn +=
", ";
281 template<
class Key,
class Value>
inline
286 "Hashtable<Key, Value>::get: key "
287 << Teuchos::toString(key)
288 <<
" not found in Hashtable"
292 = data_[hashCode(key) % capacity_];
304 return mostRecentValue_;
308 template<
class Key,
class Value>
inline
313 "Hashtable<Key, Value>::remove: key "
314 << Teuchos::toString(key)
315 <<
" not found in Hashtable"
319 int h = hashCode(key) % capacity_;
333 template<
class Key,
class Value>
inline
336 avgDegeneracy_ = ((
double) nHits_)/(nHits_ + 1.0) * avgDegeneracy_ + ((
double) n)/(nHits_ + 1.0);
340 template<
class Key,
class Value>
inline
343 return os << toString(
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.
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...
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.
const Value & get(const Key &key) const
Get the value indexed by key.
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.
Smart reference counting pointer class for automatic garbage collection.
RCP(ENull null_arg=null)
Initialize RCP<T> to NULL.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
The Teuchos namespace contains all of the classes, structs and enums used by Teuchos,...