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.
Printable View
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.
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.
It might be easier if you posted the code you are currently using.
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
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.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
Hope this helps.:)
PS Like in all the good textbooks, I'll leave the implementation of deletekey to the reader!:D