Teuchos_Hashtable.hpp

Go to the documentation of this file.

// @HEADER
// ***********************************************************************
//
//                    Teuchos: Common Tools Package
//                 Copyright (2004) Sandia Corporation
//
// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
// license for use of this work by or on behalf of the U.S. Government.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
//
// ***********************************************************************
// @HEADER

#ifndef TEUCHOS_HASHTABLE_H
#define TEUCHOS_HASHTABLE_H

#include "Teuchos_ConfigDefs.hpp"
#include "Teuchos_Array.hpp"
#include "Teuchos_HashUtils.hpp"

namespace Teuchos
{
  using std::string;

  template<class Key, class Value> class HashPair
    {
    public:
      inline HashPair() : key_(), value_() {;}
      inline HashPair(const Key& key, const Value& value)
        : key_(key), value_(value) {;}

      Key key_;
      Value value_;
    };

  template<class Key, class Value> class Hashtable
    {
    public:

      inline Hashtable(int capacity=101, double rehashDensity = 0.8);

      inline bool containsKey(const Key& key) const ;

      inline const Value& get(const Key& key) const ;

      inline void put(const Key& key, const Value& value);

      inline void remove(const Key& key);

      inline int size() const {return count_;}

      inline void arrayify(Array<Key>& keys, Array<Value>& values) const ;

      inline double avgDegeneracy() const {return avgDegeneracy_;}

      inline double density() const {return ((double)count_)/((double) capacity_);}

      inline void setRehashDensity(double rehashDensity);

      inline std::string toString() const ;

    private:

      inline void rehash();
      inline int nextPrime(int newCap) const ;
      inline void accumulateAvgFill(int n) const ;


      Array<Array<HashPair<Key, Value> > > data_;
      int count_;
      int capacity_;
      mutable Value mostRecentValue_;
      mutable Key mostRecentKey_;

      mutable size_t nHits_;
      mutable double avgDegeneracy_;
      double rehashDensity_;
    };

  template<class Key, class Value>
  std::string toString(const Hashtable<Key, Value>& h);

  template<class Key, class Value>
  std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h);

  template<class Key, class Value> inline
    Hashtable<Key, Value>::Hashtable(int capacity, double rehashDensity):
    data_(),
    count_(0),
    capacity_(HashUtils::nextPrime(capacity)),
    nHits_(0),
    avgDegeneracy_(0),
    rehashDensity_(rehashDensity)
    {
      data_.resize(capacity_);
    }

  template<class Key, class Value> inline
    bool Hashtable<Key, Value>::containsKey(const Key& key) const
    {
      const Array<HashPair<Key, Value> >& candidates
        = data_[hashCode(key) % capacity_];

      for (int i=0; i<candidates.length(); i++)
        {
          const HashPair<Key, Value>& c = candidates[i];
          if (c.key_ == key)
            {
              //          (Key&) mostRecentKey_ = key;
              //(Value&) mostRecentValue_ = c.value_;
              return true;
            }
        }
      return false;
    }

  template<class Key, class Value> inline
    void Hashtable<Key, Value>::put(const Key& key, const Value& value)
    {
      int index = hashCode(key) % capacity_;

      Array<HashPair<Key, Value> >& local = data_[index];

      // check for duplicate key
      for (int i=0; i<local.length(); i++)
        {
          if (local[i].key_ == key)
            {
              local[i].value_ = value;
              return;
            }
        }

      // no duplicate key, so increment element count by one.
      count_++;

      // check for need to resize.
      if ((double) count_ > rehashDensity_ * (double) capacity_)
        {
          capacity_ = HashUtils::nextPrime(capacity_+1);
          rehash();
          // recaluate index
          index = hashCode(key) % capacity_;
        }

      data_[index].append(HashPair<Key, Value>(key, value));
    }



  template<class Key, class Value> inline
    void Hashtable<Key, Value>::rehash()
    {
      Array<Array<HashPair<Key, Value> > > tmp(capacity_);

      for (int i=0; i<data_.length(); i++)
        {
          for (int j=0; j<data_[i].length(); j++)
            {
              int newIndex = hashCode(data_[i][j].key_) % capacity_;
              tmp[newIndex].append(data_[i][j]);
            }
        }

      data_ = tmp;
    }


  template<class Key, class Value> inline
    void Hashtable<Key, Value>::arrayify(Array<Key>& keys, Array<Value>& values) const
    {
      keys.reserve(size());
      values.reserve(size());

      for (int i=0; i<data_.length(); i++)
        {
          for (int j=0; j<data_[i].length(); j++)
            {
              keys.append(data_[i][j].key_);
              values.append(data_[i][j].value_);
            }
        }
    }

  template<class Key, class Value>  inline
  std::string Hashtable<Key, Value>::toString() const
  {
    Array<Key> keys;
    Array<Value> values;
    arrayify(keys, values);

    std::string rtn = "[";
    for (int i=0; i<keys.length(); i++)
      {
        rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
          + "}";
        if (i < keys.length()-1) rtn += ", ";
      }
    rtn += "]";

    return rtn;
  }

  template<class Key, class Value>  inline
    std::string toString(const Hashtable<Key, Value>& h)
    {
      Array<Key> keys;
      Array<Value> values;
      h.arrayify(keys, values);

      std::string rtn = "[";
      for (int i=0; i<keys.length(); i++)
        {
          rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
            + "}";
          if (i < keys.length()-1) rtn += ", ";
        }
      rtn += "]";

      return rtn;
    }

  template<class Key, class Value> inline
    const Value& Hashtable<Key, Value>::get(const Key& key) const
    {
      TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
                         std::runtime_error,
                         "Hashtable<Key, Value>::get: key "
                         << Teuchos::toString(key)
                         << " not found in Hashtable"
                         << toString());

      const Array<HashPair<Key, Value> >& candidates
        = data_[hashCode(key) % capacity_];

      accumulateAvgFill(candidates.length());

      for (int i=0; i<candidates.length(); i++)
        {
          const HashPair<Key, Value>& c = candidates[i];
          if (c.key_ == key)
            {
              return c.value_;
            }
        }
      return mostRecentValue_;
    }


  template<class Key, class Value> inline
    void Hashtable<Key, Value>::remove(const Key& key)
    {
      TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
                         std::runtime_error,
                         "Hashtable<Key, Value>::remove: key "
                         << Teuchos::toString(key)
                         << " not found in Hashtable"
                         << toString());

      count_--;
      int h = hashCode(key) % capacity_;
      const Array<HashPair<Key, Value> >& candidates = data_[h];

      for (int i=0; i<candidates.length(); i++)
        {
          const HashPair<Key, Value>& c = candidates[i];
          if (c.key_ == key)
            {
              data_[h].remove(i);
              break;
            }
        }
    }

  template<class Key, class Value> inline
  void Hashtable<Key, Value>::accumulateAvgFill(int n) const
  {
    avgDegeneracy_ = ((double) nHits_)/(nHits_ + 1.0) * avgDegeneracy_ + ((double) n)/(nHits_ + 1.0);
    nHits_++;
    }

  template<class Key, class Value>  inline
    std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h)
    {
      return os << toString(h);
    }


}

#endif // TEUCHOS_HASHTABLE_H