Insert Items in Hash Table Container.

This is a discussion on Insert Items in Hash Table Container. within the C++ Programming forums, part of the General Programming Boards category; I am going to create an method to insert Items inside the hash table, However, i don't really know what ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    77

    Insert Items in Hash Table Container.

    I am going to create an method to insert Items inside the hash table, However, i don't really know what I should code inside the method.

    Should I use push or pop because it is based on a list container for my private attribute.

    Here is my code.
    hashtable.h
    Code:
    //HashTable.h
    #ifndef HASHTABLE_H
    #define HASHTABLE_H
    
    #include <list>
    
    using namespace std;
    
    template <typename KEYTYPE, typename VALUETYPE>
    class HashTable
    {
    public:
    
        void        insertItem( const string& key, const VALUETYPE& value );
        VALUETYPE   getItem( const string& key ) const;
    
        void        dump() const;
    
    private:
    
    
        enum { TABLESIZE = 20 };
    
        struct KeyValuePair {
            KEYTYPE     key;
            VALUETYPE   value;
        };
    
    
        list<KeyValuePair>  hashTable[ TABLESIZE ];
    
    
        unsigned getIndex( const char* key ) const; // Hash Function
    
    
    };
    
    #include "hashtable.tem"
    
    #endif
    hashtable.tem
    Code:
    //hashtable.tem
    template <typename KEYTYPE, typename VALUETYPE>
    void HashTable<KEYTYPE,VALUETYPE>::insertItem( const string& key, const VALUETYPE& value ) {
    
    
    }
    
    template <typename KEYTYPE, typename VALUETYPE>
    void HashTable<KEYTYPE,VALUETYPE>::dump() const {
    
        for( unsigned iCtr = 0; iCtr < TABLESIZE; iCtr++ ) {
        
        	cout << "Bucket #" << iCtr << " contains: ";
        	
        	list<KeyValuePair>::const_iterator iter;
        	for( iter = hashTable[ iCtr ].begin(); iter != hashTable[ iCtr ].end(); ++iter ) {
        	    cout << '[' << iter->key.c_str() << ',' << iter->value << ']' << ' ';
        	}
        	
        	cout << endl;
        }
    }
    
    // End of file
    
     ;)
    Thanks for advice
    Last edited by joenching; 04-29-2005 at 04:40 PM.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    You have KEYTYPE, presumably for the key type, but then you use std::string in the functions as the type of the key. Either make it generic or specialize it for string keys.

    You need a hashing function. Either allow the user to specify one, or if you start off focusing on strings supply your own (search for a good hash function for strings).

    Regardless, the hash function should be separate from your insert function. Get the hashed value and then just push the value onto the appropriate list based on the result of the hash. That should be all the insert function needs to do - maybe one or two lines of code.

  3. #3
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    you mean what I use std::string means that one?
    Code:
    void        insertItem( const string& key, const VALUETYPE& value );
    Can you give me some advise how to create a hash function?

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Can you give me some advise how to create a hash function?
    Cheat.
    Code:
    #include <iostream>
    #include <locale>
    #include <string>
    
    using namespace std;
    
    int main()
    {
      string s = "This is a test";
      const collate<char>& coll = use_facet<collate<char> > ( locale() );
    
      cout<< coll.hash ( s.c_str(), s.c_str() + s.length() ) <<endl;
    }
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    What is the collate for?


    Code:
    const collate<char>& coll = use_facet<collate<char> > ( locale() )

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >What is the collate for?
    It's best not to ask that unless you really want me to answer. Locales and facets are foogly enough to make your head spin unless you're comfortable with the concepts.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    collate should be a class name? right?

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >collate should be a class name? right?
    It's a template class, yes.
    My best code is written with the delete key.

  9. #9
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    I am still thinking how I can insert a string and an int inside the function insert.

    Can anyone give me some suggest?

  10. #10
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    Here is my expected output:
    Bucket #0 contains: [Carol,29]
    Bucket #1 contains:
    Bucket #2 contains: [Fred,45]
    Bucket #3 contains:
    Bucket #4 contains: [Lori,38]
    Bucket #5 contains:
    Bucket #6 contains:
    Bucket #7 contains: [Sue,20]
    Bucket #8 contains: [Jane,26] [Joe,18]
    Bucket #9 contains:
    Bucket #10 contains:
    Bucket #11 contains: [Dave,23]
    Bucket #12 contains:
    Bucket #13 contains:
    Bucket #14 contains:
    Bucket #15 contains: [James,27]
    Bucket #16 contains: [Mark,34]
    Bucket #17 contains: [Beth,25]
    Bucket #18 contains:
    Bucket #19 contains:


    Dave's value is: 23
    Sue's value is: 20
    Mark's value is: 34
    Fred's value is: 45
    Jane's value is: 26
    Carol's value is: 29
    Joe's value is: 18
    Lori's value is: 38
    James' value is: 27
    Beth's value is: 25

    and this is the HashTableTest.cpp
    Code:
    //HashTableTest.cpp
    #include <cstdlib>
    #include <iostream>
    
    #include "hashtable.h"
    
    using namespace std;
    
    int main() {
    
        HashTable<string,int> hashTable;
    
        //hashTable.dump();
    
        hashTable.insertItem( "Dave", 23 );
        hashTable.insertItem( "Sue", 20 );
        hashTable.insertItem( "Mark", 34 );
        hashTable.insertItem( "Fred", 45 );
        hashTable.insertItem( "Jane", 26 );
        hashTable.insertItem( "Carol", 29 );
        hashTable.insertItem( "Joe", 18 );
        hashTable.insertItem( "Lori", 38 );
        hashTable.insertItem( "James", 27 );
        hashTable.insertItem( "Beth", 25 );
    
        cout << endl << endl;
    
        hashTable.dump();
    
        cout << endl << endl;
    
        cout << "Dave's value is: " << hashTable.getItem( "Dave" ) << endl;
        cout << "Sue's value is: " << hashTable.getItem( "Sue" ) << endl;
        cout << "Mark's value is: " << hashTable.getItem( "Mark" ) << endl;
        cout << "Fred's value is: " << hashTable.getItem( "Fred" ) << endl;
        cout << "Jane's value is: " << hashTable.getItem( "Jane" ) << endl;
        cout << "Carol's value is: " << hashTable.getItem( "Carol" ) << endl;
        cout << "Joe's value is: " << hashTable.getItem( "Joe" ) << endl;
        cout << "Lori's value is: " << hashTable.getItem( "Lori" ) << endl;
        cout << "James' value is: " << hashTable.getItem( "James" ) << endl;
        cout << "Beth's value is: " << hashTable.getItem( "Beth" ) << endl;
    
    
        return EXIT_SUCCESS;
    }
    My question is, for inserting ( "Dave", 23)

    How I can let the computer knows this items should be place in Bucket #10?
    Any algorithm can do it?
    thanks for advise.

  11. #11
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    Should I use Dave % 20 to figure out this problem?

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    > How I can let the computer knows this items should be place in Bucket #10?
    > Any algorithm can do it?
    Well if you're looking for a specific algorithm to place all those entries in the places you've suggested, then you're on your own (or go ask your tutor).

    But basically, you're looking to take some property of the name, and reduce that to a value in the range 0 .. 19, but do it in such a way that any given name has an equal probability of ending up in a random position.

    Example
    Code:
    int hashFunc ( char *key ) {
      return strlen( key ) % 20;
    }
    would be very poor (most of your entries would be in the same hash

    This might be a bit better
    Code:
    int hashFunc ( char *key ) {
      int res = 0;
      while ( *key ) res += *key++;
      return key % 20;
    }
    Returns the modulo result of say 'D' + 'a' + 'v' + 'e'
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    for my insert method:
    Code:
    template <typename KEYTYPE, typename VALUETYPE>
    void HashTable<KEYTYPE,VALUETYPE>::insertItem( const string& key, const VALUETYPE& value ) {
    	key = &key.push_front();        //push the address of key to the private attritbute key.
    	
    	value = &value.push_front();  //push the address of value to the private attribute value.
    }
    I think it is not suitable to put the algorithm inside the insert function, I should create another function to fix this problem, right?
    Also, do you think this is a good way to insert the key and the item.
    Code:
    key = &key.push_front();        //push the address of key to the private attritbute key.
    	
    	value = &value.push_front();  //push the address of value to the private attribute value.
    Some of my questions may be annoyed u guys, but i am really want to learn it because i am so interest in the data structures.

    Appericate it.

  14. #14
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    So does your code even compile?

    I would have thought it would be more like this
    Code:
    template <typename KEYTYPE, typename VALUETYPE>
    void HashTable<KEYTYPE,VALUETYPE>::insertItem( const string& key, const VALUETYPE& value ) {
        KeyValuePair thing = { key, value };
        int position = myHashFunction( key );  // compute a position
        hashTable[position].push_front(thing);  // add a thing at the given hash position
    }
    The hash function computes a position (0..19), and the fact that it's a list allows you to create entries like this
    Bucket #8 contains: [Jane,26] [Joe,18]
    to solve the hash collision problem
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  15. #15
    Registered User
    Join Date
    Mar 2005
    Posts
    77
    Do you think I should declear myHashFunction inside the private section?
    I think those code from you should work
    Code:
    int hashFunc ( char *key ) {
      int res = 0;
      while ( *key ) res += *key++;
      return key % 20;
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 09:23 PM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 06:54 PM
  5. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21