Hash Table Implementation in C++

Discussion in 'C++' started by Diane, Apr 4, 2006.

  1. Diane

    Diane Guest

    Hi everybody. Does anyone have any sample hash table implementation for
    separate chaining? I'm trying to implement it myself, but I'm stuck.
    Thanks!
    Diane, Apr 4, 2006
    #1
    1. Advertising

  2. Diane

    red floyd Guest

    Diane wrote:
    > Hi everybody. Does anyone have any sample hash table implementation for
    > separate chaining? I'm trying to implement it myself, but I'm stuck.
    > Thanks!
    >


    Why don't you show us what you currently have?
    red floyd, Apr 4, 2006
    #2
    1. Advertising

  3. Diane

    Diane Guest

    Please find below my code. I need an array of lists which are of type
    Info. My problem is that I;m not quite sure if I should use an pointer
    to a list ( see private member variable of class HashTable) or not. And
    if i must use pointers, how should i modify my code? Thanks!

    #include <iostream>
    #include <string>
    #include <list>
    #include <vector>
    #include <algorithm>


    using namespace std;



    template <class Type>
    struct Info
    {
    Info(const string& k, const Type& myData)
    {
    key = k;
    data = myData;
    occupied=false;
    hasBeenOccupied = false;
    }

    const string& getKey() const
    { return key; }

    // Overloaded operators
    bool operator==(const Info& rhs) const
    { return getKey() == rhs.getKey(); }
    bool operator!=(const Info& rhs) const
    { return !(*this == rhs); }

    string key;
    Type data;
    bool occupied;
    bool hasBeenOccupied;
    };



    template <class Info>
    class HashTable
    {
    public:
    // constructor and destructor
    HashTable(int currentSize);
    ~HashTable();


    // other functions
    bool put(const Info& x); // enter data into table
    void remove(const Info& x); // delete from table
    bool isIn(const Info& x) const; // is key in table
    bool isEmpty() const; // is table empty

    int getTableSize() { return tableSize; }

    // hash functions
    int myhash(const Info& x, int tableSize) const;

    private:
    vector<std::list <Info> > myLists; // the array of lists
    int tableSize;
    int numberInTable; // number of items in table
    };



    // Class Implementation

    template <class Info>
    HashTable<Info>::HashTable(int currentSize)
    {
    numberInTable = 0;
    tableSize = currentSize;

    // myLists = new vector<std::list<Info> > [currentSize];

    for (int i = 0; i < tableSize; i++)
    {
    myLists.clear();
    }
    }



    template <class Info>
    HashTable<Info>::~HashTable()
    {}



    // global main hash function
    int hash(const string& key, int tableSize)
    {
    int index = 0;

    for (int j = 0; j < key.length(); j++)
    {
    index += key[j];
    }

    return index % tableSize;
    }



    // my hash function takes an Info object as argument
    template <class Info>
    int HashTable<Info>::myhash(const Info& x, int tableSize) const
    {
    int index = hash(x.key, tableSize);

    index %= myLists.size();

    if (index < 0)
    {
    index += myLists.size();
    }

    return index;
    }


    // insert data into hash table
    template <class Info>
    bool HashTable<Info>::put(const Info& x)
    {
    int index = myhash(x, tableSize);

    list<Info> & thelist = myLists[index];
    if( find(thelist.begin(), thelist.end(), x) != thelist.end() )
    {
    return false;
    }

    thelist.push_back(x);


    return true;

    }
    Diane, Apr 4, 2006
    #3
  4. Diane

    Guest

    Why don't you use STL's hash_set or hash_map?

    Regarding your question, if you use pointers to the list you'll save
    few bytes, but you'll have to implement your own copy constructor,
    assignment operator and destructor of the HashTable.
    BTW, you don't need to "clear" the lists in the constructor, the lists
    will start clean.

    Yuval.
    , Apr 4, 2006
    #4
  5. Diane

    loufoque Guest

    wrote :
    > Why don't you use STL's hash_set or hash_map?


    Those are nonèstandard SGI extensions.

    The standard one is unordered_map, but it is in TR1.
    It's already available in namespace std::tr1 of some compilers.
    loufoque, Apr 4, 2006
    #5
  6. Diane

    Howard Guest

    [OT] Re: Hash Table Implementation in C++

    "loufoque" <> wrote in message
    news:44324d92$0$9479$...
    > wrote :
    >> Why don't you use STL's hash_set or hash_map?

    >
    > Those are nonhstandard SGI extensions.
    >


    (What's SGI? Silicon Graphics, Inc.? Standard Graphical Interface?)

    -Howard
    Howard, Apr 4, 2006
    #6
  7. Diane

    Marcus Kwok Guest

    Re: [OT] Re: Hash Table Implementation in C++

    >> wrote :
    >>> Why don't you use STL's hash_set or hash_map?


    > "loufoque" <> wrote in message
    > news:44324d92$0$9479$...
    >> Those are nonhstandard SGI extensions.


    Howard <> wrote:
    > (What's SGI? Silicon Graphics, Inc.? Standard Graphical Interface?)


    SGI is Silicon Graphics, Inc.

    http://www.sgi.com/tech/stl/

    --
    Marcus Kwok
    Marcus Kwok, Apr 4, 2006
    #7
  8. On 3 Apr 2006 16:06:56 -0700, "Diane" <> wrote:
    >Hi everybody. Does anyone have any sample hash table implementation for
    >separate chaining? I'm trying to implement it myself, but I'm stuck.
    >Thanks!


    Try http://www.koders.com/

    Good luck!
    Roland Pibinger
    Roland Pibinger, Apr 4, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ryan Kaskel
    Replies:
    1
    Views:
    551
    Ryan Kaskel
    Apr 26, 2006
  2. Jim Cobban
    Replies:
    8
    Views:
    530
    Jerry Coffin
    Apr 17, 2008
  3. aki

    Hash table Implementation

    aki, Mar 29, 2011, in forum: C Programming
    Replies:
    3
    Views:
    760
    Jorgen Grahn
    Apr 6, 2011
  4. rp
    Replies:
    1
    Views:
    499
    red floyd
    Nov 10, 2011
  5. Srijayanth Sridhar
    Replies:
    19
    Views:
    598
    David A. Black
    Jul 2, 2008
Loading...

Share This Page