リンクを分離したハーネス・テーブルの使用-データ構造とアルゴリズムの第4版の分析

/*************************************************************************
	> File Name: HashTable.h
	> Author:keson
	> Mail:[email protected]
	> Created Time: 2014 11 25      21 37 31 
 ************************************************************************/
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<string>
using namespace std;

class hashValue
{
public:
    size_t operator()(const string &key)
    {
        size_t hashVal=0;

        for(auto c:key)
           hashVal=37*hashVal+c;
        return hashVal;
    }
};

template<typename HashedObj>
class HashTable
{
friend class hashValue;
public:
    explicit HashTable(int size=101):theLists(size) {}

    bool contains(const HashedObj &x)const
    {
        auto &whichList=theLists[myhash(x)];
        return find(whichList.begin(),whichList.end(),x)!=whichList.end();
    }

    void print()
    {
         for(auto &thisList:theLists)
            for(auto &x:thisList)
             {cout<<x<<"  ";
                cout<<endl;
             }
    }

    void makeEmpty()
    {
        for(auto &thisList:theLists)
           thisList.clear();
    }

    bool hash_insert(const HashedObj &x)
    {
        auto &whichList=theLists[myhash(x)];
        if(find(begin(whichList),end(whichList),x)!=end(whichList))
           return false;
        whichList.push_back(x);
        if(++currentSize>theLists.size())
           rehash();
        return true;
    }

    bool hash_insert(HashedObj &&x)
    {
        auto &whichList=theLists[myhash(std::move(x))];
        if(find(begin(whichList),end(whichList),x)!=end(whichList))
          return false;
        whichList.push_back(std::move(x));
        if(++currentSize>theLists.size())
         rehash();
        return true;
    }


    bool remove(const HashedObj &x)
    {
        auto &whichList=theLists[myhash(x)];
        auto itr=find(whichList.begin(),whichList.end(),x);

        if(itr==whichList.end())
           return false;

        whichList.erase(itr);
        --currentSize;
        return true;
    }


private:
    vector<list<HashedObj>> theLists;
    int currentSize;

    void rehash()
    {
        vector<list<HashedObj>> oldLists=theLists;
        //create new double-sized,empty table
        theLists.resize(2*theLists.size());

        for(auto &thisList:theLists)
            thisList.clear();

        //copy table over
        currentSize=0;
        for(auto &thisList:oldLists)
           for(auto &x:thisList)
              hash_insert(std::move(x));
    }

    size_t myhash(const HashedObj &x) const
    {
       static    hashValue hf;
        return hf(x)%theLists.size();
    }

};

int main()
{
    HashTable<string>  a;
    a.hash_insert("abc");
    a.print();


}