-
June 12th, 2013, 01:02 PM
#1
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.
-
June 12th, 2013, 02:56 PM
#2
Re: A question regarding hashtable
Originally Posted by LarryChen
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
-
June 13th, 2013, 04:10 AM
#3
Re: A question regarding hashtable
Originally Posted by LarryChen
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. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
June 13th, 2013, 08:34 AM
#4
Re: A question regarding hashtable
Originally Posted by 2kaud
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.
-
June 13th, 2013, 10:30 AM
#5
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. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
June 13th, 2013, 02:01 PM
#6
Re: A question regarding hashtable
Originally Posted by 2kaud
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.
-
June 13th, 2013, 02:30 PM
#7
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. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
June 14th, 2013, 06:22 AM
#8
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. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|