散列表实现--分离链接法与平方探测法

//separate chaining
template
class HashTable
{
  public:
    explicit HashTable(int size = 101) : theLists(nextPrime(size))
      { makeEmpty(); }
    bool contains(const HashedObj & x) const
    {
      const list & whichList = theLists[myhash(x)];
      return find(whichList.begin(), whichList.end(), x)!=whichList.end();
    }
    void makeEmpty()
    {
      for(int i=0; i)
        theLists[i].clear();
    }
    bool insert(const HashedObj & x);
    {
      list & whichList = theLists[myhash(x)];
      if(find(whichList.begin(), whichList.end(), x)!=whichList.end())
        return false;
      whichList.push_back(x);
      if(++currentSize>theLists.size())
        rehash();
      return true;
    }
    bool remove(const HahsedObj & x)
    {
      list & whichList = theLists[myhash(x)];
      list::iterator itr = find(whichList.begin(), whichList.end(), x);
      if(itr == whichList.end())
        return false;
      whichList.erase(itr);
      --currentSize;
      return true;
    }
  private:
    vector> theLists;    //The array of Lists
    int currentSize;
    void rehash()
    {
      vector> oldLists = theLists;
      theLists.resize(nextPrime(2*theLists.size()));
      for(int j=0; j)
        theLists[j].clear();
      currentSize = 0;
      for(int i=0; i)
      {
        list::iterator itr = oldLists[i].begin();
        while(itr!=oldLists[i].end())
          insert(*itr++);
      }
    }
    int myhash(const HashedObj & x) const
    {
      int hashVal = hash(x);
      hashVal %= theLists.size();
      if(hashVal < 0)
        hashVal += theLists.size();
      return hashVal;
    }
};

//quadratic probing
template
class HashTable
{
  public:
    explicit HashTable(int size = 101) : array(nextPrime(size))
    { makeEmpty(); }
    bool contains(const HashedObj & x) const
    { return isActive(findPos(x)); }
    void makeEmpty()
    {
      currentSize = 0;
      for(int i=0; i)
        array[i].info = EMPTY;
    }
    bool insert(const HashedObj & x)
    {
      int currentPos = findPos(x);
      if(isActive(currentPos))
        retur false;
      array[currentPos] = HashEntry(x, ACTIVE);
      if(++currentSize>array.size()/2)
        rehash();
      return true;
    }
    bool remove(const HashedObj & x)
    {
      int currentPos = findPos(x);
      if(!isActive(currentPos))
        return false;
      array[currentPos].info = DELETED;
      --currentSize;
      return true;
    }
    enum EntryType{ACTIVE, EMPTY, DELETED};
  private:
    struct HashEntry
    {
      HashedObj element;
      EntryType info;
      HashEntry(const HashedObj & e = HashedObj(), EntryType i = EMPTY)
    : element(e), info(i) {}
    };
    vector array;
    int currentSize;
    bool isActive(int currentPos) const
    {
      return array[currentPos].info == ACTIVE;
    }
    int findPos(const HashedObj & x) const
    {
      int offset = 1;
      int currentPos = myhash(x);
      while(array[currentPos].info != EMPTY && 
    array[currentPos].element!=x)
      {
        currentPos += offset;
        offset += 2;
        if(currentPos >= array.size())
          currentPos -= array.size();
      }
      return currentPos;
    }
    void rehash()
    {
      vector oldArray = array;
      array.resize(nextPrime(2*oldArray.size()));
      for(int j=0; j)
        array[j].info = EMPTY;
      currentSize = 0;
      for(int i=0; i)
        if(oldArray[i].info == ACTIVE)
          insert(oldArray[i].element);
    }
    int myhash(const HashedObj & x) const
    {
      int hashVal = hash(x);
      hashVal %= theLists.size();
      if(hashVal < 0)
        hashVal += theLists.size();
      return hashVal;
    }
};