42#ifndef TEUCHOS_HASHTABLE_H
43#define TEUCHOS_HASHTABLE_H
60 template<
class Key,
class Value>
class HashPair
94 inline void put(
const Key& key,
const Value& value);
115 inline std::string
toString()
const ;
135 template<
class Key,
class Value>
141 template<
class Key,
class Value>
144 template<
class Key,
class Value>
inline
148 capacity_(
HashUtils::nextPrime(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_)
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
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++)
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++)
274 if (
i <
keys.length()-1)
rtn +=
", ";
281 template<
class Key,
class Value>
inline
286 "Hashtable<Key, Value>::get: 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 "
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
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)