00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #ifndef TEUCHOS_HASHTABLE_H
00030 #define TEUCHOS_HASHTABLE_H
00031
00036 #include "Teuchos_ConfigDefs.hpp"
00037 #include "Teuchos_Array.hpp"
00038 #include "Teuchos_HashUtils.hpp"
00039
00040 namespace Teuchos
00041 {
00042 using std::string;
00043
00047 template<class Key, class Value> class HashPair
00048 {
00049 public:
00051 inline HashPair() : key_(), value_() {;}
00053 inline HashPair(const Key& key, const Value& value)
00054 : key_(key), value_(value) {;}
00055
00057 Key key_;
00059 Value value_;
00060 };
00061
00067 template<class Key, class Value> class Hashtable
00068 {
00069 public:
00070
00072 inline Hashtable(int capacity=101, double rehashDensity = 0.8);
00073
00075 inline bool containsKey(const Key& key) const ;
00076
00078 inline const Value& get(const Key& key) const ;
00079
00081 inline void put(const Key& key, const Value& value);
00082
00084 inline void remove(const Key& key);
00085
00087 inline int size() const {return count_;}
00088
00090 inline void arrayify(Array<Key>& keys, Array<Value>& values) const ;
00091
00093 inline double avgDegeneracy() const {return avgDegeneracy_;}
00094
00096 inline double density() const {return ((double)count_)/((double) capacity_);}
00097
00099 inline void setRehashDensity(double rehashDensity);
00100
00102 inline std::string toString() const ;
00103
00104 private:
00105
00106 inline void rehash();
00107 inline int nextPrime(int newCap) const ;
00108 inline void accumulateAvgFill(int n) const ;
00109
00110
00111 Array<Array<HashPair<Key, Value> > > data_;
00112 int count_;
00113 int capacity_;
00114 mutable Value mostRecentValue_;
00115 mutable Key mostRecentKey_;
00116
00117 mutable int nHits_;
00118 mutable double avgDegeneracy_;
00119 double rehashDensity_;
00120 };
00121
00122 template<class Key, class Value>
00123 std::string toString(const Hashtable<Key, Value>& h);
00124
00128 template<class Key, class Value>
00129 std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h);
00130
00131 template<class Key, class Value> inline
00132 Hashtable<Key, Value>::Hashtable(int capacity, double rehashDensity)
00133 : data_(), count_(0), capacity_(HashUtils::nextPrime(capacity)),
00134 nHits_(0), avgDegeneracy_(0), rehashDensity_(rehashDensity)
00135 {
00136 data_.resize(capacity_);
00137 }
00138
00139 template<class Key, class Value> inline
00140 bool Hashtable<Key, Value>::containsKey(const Key& key) const
00141 {
00142 const Array<HashPair<Key, Value> >& candidates
00143 = data_[hashCode(key) % capacity_];
00144
00145 for (int i=0; i<candidates.length(); i++)
00146 {
00147 const HashPair<Key, Value>& c = candidates[i];
00148 if (c.key_ == key)
00149 {
00150
00151
00152 return true;
00153 }
00154 }
00155 return false;
00156 }
00157
00158 template<class Key, class Value> inline
00159 void Hashtable<Key, Value>::put(const Key& key, const Value& value)
00160 {
00161 int index = hashCode(key) % capacity_;
00162
00163 Array<HashPair<Key, Value> >& local = data_[index];
00164
00165
00166 for (int i=0; i<local.length(); i++)
00167 {
00168 if (local[i].key_ == key)
00169 {
00170 local[i].value_ = value;
00171 return;
00172 }
00173 }
00174
00175
00176 count_++;
00177
00178
00179 if ((double) count_ > rehashDensity_ * (double) capacity_)
00180 {
00181 capacity_ = HashUtils::nextPrime(capacity_+1);
00182 rehash();
00183
00184 index = hashCode(key) % capacity_;
00185 }
00186
00187 data_[index].append(HashPair<Key, Value>(key, value));
00188 }
00189
00190
00191
00192 template<class Key, class Value> inline
00193 void Hashtable<Key, Value>::rehash()
00194 {
00195 Array<Array<HashPair<Key, Value> > > tmp(capacity_);
00196
00197 for (int i=0; i<data_.length(); i++)
00198 {
00199 for (int j=0; j<data_[i].length(); j++)
00200 {
00201 int newIndex = hashCode(data_[i][j].key_) % capacity_;
00202 tmp[newIndex].append(data_[i][j]);
00203 }
00204 }
00205
00206 data_ = tmp;
00207 }
00208
00209
00210 template<class Key, class Value> inline
00211 void Hashtable<Key, Value>::arrayify(Array<Key>& keys, Array<Value>& values) const
00212 {
00213 keys.reserve(size());
00214 values.reserve(size());
00215
00216 for (int i=0; i<data_.length(); i++)
00217 {
00218 for (int j=0; j<data_[i].length(); j++)
00219 {
00220 keys.append(data_[i][j].key_);
00221 values.append(data_[i][j].value_);
00222 }
00223 }
00224 }
00225
00226 template<class Key, class Value> inline
00227 std::string Hashtable<Key, Value>::toString() const
00228 {
00229 Array<Key> keys;
00230 Array<Value> values;
00231 arrayify(keys, values);
00232
00233 std::string rtn = "[";
00234 for (int i=0; i<keys.length(); i++)
00235 {
00236 rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
00237 + "}";
00238 if (i < keys.length()-1) rtn += ", ";
00239 }
00240 rtn += "]";
00241
00242 return rtn;
00243 }
00244
00245 template<class Key, class Value> inline
00246 std::string toString(const Hashtable<Key, Value>& h)
00247 {
00248 Array<Key> keys;
00249 Array<Value> values;
00250 h.arrayify(keys, values);
00251
00252 std::string rtn = "[";
00253 for (int i=0; i<keys.length(); i++)
00254 {
00255 rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
00256 + "}";
00257 if (i < keys.length()-1) rtn += ", ";
00258 }
00259 rtn += "]";
00260
00261 return rtn;
00262 }
00263
00264 template<class Key, class Value> inline
00265 const Value& Hashtable<Key, Value>::get(const Key& key) const
00266 {
00267 TEST_FOR_EXCEPTION(!containsKey(key),
00268 std::runtime_error,
00269 "Hashtable<Key, Value>::get: key "
00270 << Teuchos::toString(key)
00271 << " not found in Hashtable"
00272 << toString());
00273
00274 const Array<HashPair<Key, Value> >& candidates
00275 = data_[hashCode(key) % capacity_];
00276
00277 accumulateAvgFill(candidates.length());
00278
00279 for (int i=0; i<candidates.length(); i++)
00280 {
00281 const HashPair<Key, Value>& c = candidates[i];
00282 if (c.key_ == key)
00283 {
00284 return c.value_;
00285 }
00286 }
00287 return mostRecentValue_;
00288 }
00289
00290
00291 template<class Key, class Value> inline
00292 void Hashtable<Key, Value>::remove(const Key& key)
00293 {
00294 TEST_FOR_EXCEPTION(!containsKey(key),
00295 std::runtime_error,
00296 "Hashtable<Key, Value>::remove: key "
00297 << Teuchos::toString(key)
00298 << " not found in Hashtable"
00299 << toString());
00300
00301 count_--;
00302 int h = hashCode(key) % capacity_;
00303 const Array<HashPair<Key, Value> >& candidates = data_[h];
00304
00305 for (int i=0; i<candidates.length(); i++)
00306 {
00307 const HashPair<Key, Value>& c = candidates[i];
00308 if (c.key_ == key)
00309 {
00310 data_[h].remove(i);
00311 break;
00312 }
00313 }
00314 }
00315
00316 template<class Key, class Value> inline
00317 void Hashtable<Key, Value>::accumulateAvgFill(int n) const
00318 {
00319 avgDegeneracy_ = ((double) nHits_)/(nHits_ + 1.0) * avgDegeneracy_ + ((double) n)/(nHits_ + 1.0);
00320 nHits_++;
00321 }
00322
00323 template<class Key, class Value> inline
00324 std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h)
00325 {
00326 return os << toString(h);
00327 }
00328
00329
00330 }
00331
00332 #endif // TEUCHOS_HASHTABLE_H