A question regarding hashtable
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: A question regarding hashtable

  1. #1
    Join Date
    Jul 2005
    Posts
    894

    A question regarding hashtable

    Normally we use array as a hashtable. What if the key is negative? In this case obviously array can't be used for a hashtable. Can we use map for a hashtable? Thanks.

  2. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,011

    Re: A question regarding hashtable

    Quote Originally Posted by LarryChen View Post
    Normally we use array as a hashtable. What if the key is negative? In this case obviously array can't be used for a hashtable. Can we use map for a hashtable? Thanks.
    A hashtable is a container just like an array or a map. You can use an array to implement a hash table, but they are not the same.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  3. #3
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    Re: A question regarding hashtable

    Quote Originally Posted by LarryChen View Post
    Normally we use array as a hashtable. What if the key is negative? In this case obviously array can't be used for a hashtable. Can we use map for a hashtable? Thanks.
    If the key is an integer and can be negative, you can still use an array as a hashtable. Your hash function just has to deal with it. How are you dealing with hash clashes? Are you storing the key? What are you trying to achieve?
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  4. #4
    Join Date
    Jul 2005
    Posts
    894

    Re: A question regarding hashtable

    Quote Originally Posted by 2kaud View Post
    If the key is an integer and can be negative, you can still use an array as a hashtable. Your hash function just has to deal with it. How are you dealing with hash clashes? Are you storing the key? What are you trying to achieve?
    Thanks for your reply. So what is the simply way to deal with a key that is a negative integer if I still want to use an array as a hashtable? Thanks.

  5. #5
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    Re: A question regarding hashtable

    You haven't said what is your hash algorithm or how you deal with hash clashes. Assuming you are storing the key as part of the hash table in order to deal with hash clashes, then the simplest way to deal with negative keys is simply to make the negative key postive (eg -4 to 4) and then let the algorithm (existing?) for dealing with hash clashes sort out the difference between a key of -4 and a key of 4.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #6
    Join Date
    Jul 2005
    Posts
    894

    Re: A question regarding hashtable

    Quote Originally Posted by 2kaud View Post
    You haven't said what is your hash algorithm or how you deal with hash clashes. Assuming you are storing the key as part of the hash table in order to deal with hash clashes, then the simplest way to deal with negative keys is simply to make the negative key postive (eg -4 to 4) and then let the algorithm (existing?) for dealing with hash clashes sort out the difference between a key of -4 and a key of 4.
    Actually the key is integer and value is occurrence in the hash table. The hash table is initialized to zero. If an integer exists, then value of hash table is incremented to 1. If I make the negative key positive, then my question is how to resolve the hash clashes? Thanks.

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    Re: A question regarding hashtable

    It might be easier if you posted the code you are currently using.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    Re: A question regarding hashtable

    This is some simple code that implements a class for using an array for a hash table that has key as an int and value as an int. As it deals with hash clashes, it can be used for positive and negative key values.

    Code:
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    class chash
    {
    private:
    
    	static const int maxsize = 100;
    	static const int unused = -1;
    
    	static struct entry {
    		int	key;
    		int	value;
    		bool	used;
    		int	next;
    	};
    
    	entry* htable;
    
    	int	hsize;
    
    	inline int hfunc(int key) const {
    		return abs(key) % hsize;
    	}
    
    	int findfree(int start) const;
    	void set(int ind, int key, int val);
    
    	chash(const chash& hash);
    	operator=(const chash& hash);
    
    public:
    	chash(int size = maxsize);
    
    	~chash();
    
    	bool setvalue(int key, int value);
    	bool getvalue(int key, int& value) const;
    
    	void printtable() const;
    	void printvalue(int key) const;
    };
    
    
    chash::chash(int size)
    		: hsize(size)
    {
    	htable = new entry[hsize];
    
    	for (int i = 0; i < maxsize; i++) {
    		htable[i].key = 0;
    		htable[i].value = 0;
    		htable[i].next = unused;
    		htable[i].used = false;
    	}
    }
    
    
    chash::~chash()
    {
    	delete [] htable;
    }
    
    
    void chash::set(int ind, int key, int val)
    {
    	htable[ind].used = true;
    	htable[ind].key = key;
    	htable[ind].value = val;
    	htable[ind].next = unused;
    }
    
    
    int chash::findfree(int start) const
    {
    	for (int h = (start + 1) % hsize; h != start; h = (h + 1) % hsize)
    		if (htable[h].used == false)
    			return h;
    
    	return hsize + 1;
    }
    
    
    bool chash::setvalue(int key, int value)
    {
    int ent = hfunc(key),
        newent;
    
    	if (htable[ent].used == false) {
    		set(ent, key, value);
    		return true;
    	}
    
    	if (htable[ent].key == key)
    		return (htable[ent].value == value);
    
    	if ((newent = findfree(ent)) > hsize) 
    		return false;
    
    	for (int chain = htable[ent].next; chain != unused; ent = chain, chain = htable[chain].next);
    
    	htable[ent].next = newent;
            set(newent, key, value);
    	return true;
    }
    
    
    bool chash::getvalue(int key, int& value) const
    {
    int ent = hfunc(key);
    
    	if (htable[ent].used == false)
    		return false;
    
    	do {
    		if (htable[ent].key == key) {
    			value = htable[ent].value;
    			return true;
    		}
    
    	} while ((ent = htable[ent].next) != unused);
    
    	return false;
    }
    
    
    void chash::printtable() const
    {
    	for (int i = 0; i < hsize; i++) {
    		cout << "entry " << i;
    		cout << " key " << htable[i].key;
    		cout << " value " << htable[i].value;
    		cout << " used " << htable[i].used;
    		cout << " next " << htable[i].next;
    		cout << endl;
    	}
    }
    
    
    void chash::printvalue(int key) const
    {
    int val;
    
    	cout << "key " << key;
    	if (getvalue(key, val))
    		cout << " value " << val << endl;
    	 else
    		cout << " not found" << endl;
    }
    
    
    int main()
    {
    chash table;
    
    	table.setvalue(5, 15);
    	table.setvalue(7, 17);
    	table.setvalue(345, 45);
    	table.setvalue(105, 115);
    	table.setvalue(6, 16);
    	table.setvalue(-8, -78);
    	table.setvalue(-108, 88);
    
    	//table.printtable();
    
    	table.printvalue(5);
    	table.printvalue(6);
    	table.printvalue(7);
    	table.printvalue(105);
    	table.printvalue(345);
    	table.printvalue(55);
    	table.printvalue(205);
    	table.printvalue(-8);
    	table.printvalue(-108);
    	table.printvalue(-99);
    	table.printvalue(19);
    
    	return 0;
    }

    Which produces the output
    Code:
    key 5 value 15
    key 6 value 16
    key 7 value 17
    key 105 value 115
    key 345 value 45
    key 55 not found
    key 205 not found
    key -8 value -78
    key -108 value 88
    key -99 not found
    key 19 not found
    For hash collison, the algorithm used simply finds the next free array slot (if there is one) and uses a linked chain. There are other methods that could be used. Errors are reported by simply returning true or false for the class methods. Exception handling would probably be employed 'for real' but I tried to keep this simple.

    Hope this helps.

    PS Like in all the good textbooks, I'll leave the implementation of deletekey to the reader!
    Last edited by 2kaud; June 14th, 2013 at 10:45 AM.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center