hash table with negative number

[LarryChen]

Here when I talk about hash table, I mean it is simply an array and it has nothing to do with STL hash map. For example, there is an array, int a[] = {3, 5,6, 7, 11}. The key for hash table could be the elements of array a. What if there is negative item in the array, for example, int a[] = {3, -1, 5, 7, -6}? How'd I build a hash table based on this array? Thanks.

[S_M_A]

Assuming int is 32 bits, how would you build a hash table for unsigned int a[] = {3, 4294967295, 5, 7, 4294967290}?

[LarryChen]

Actually, my question is how to build a hash table for negative integer. Any idea? Thanks.

Assuming int is 32 bits, how would you build a hash table for unsigned int a[] = {3, 4294967295, 5, 7, 4294967290}?

[S_M_A]

Well a negative number is just a positive number interpreted as being negative. I.e. a 32 bit signed integer set to -1 will have the same content as an unsigned int set to 4294967295 (0xFFFFFFFF). That's why I asked you how you would handle those numbers instead.

[LarryChen]

Obviously it is not good to handle a negative numbge with a 2's complement because it will use too much space to build a hashtable. Basically I need a way to map a key as a negative number to a value in such a hash table.

Well a negative number is just a positive number interpreted as being negative. I.e. a 32 bit signed integer set to -1 will have the same content as an unsigned int set to 4294967295 (0xFFFFFFFF). That's why I asked you how you would handle those numbers instead.

[laserlight]

Obviously it is not good to handle a negative numbge with a 2's complement because it will use too much space to build a hashtable. Basically I need a way to map a key as a negative number to a value in such a hash table.

You just need to construct an appropriate hash function. I don't see what is the problem.

[LarryChen]

How does hash function work with an array since my hash table is implemented on an array?

You just need to construct an appropriate hash function. I don't see what is the problem.

[laserlight]

How does hash function work with an array since my hash table is implemented on an array?

Same idea as when you want to compute a hash value given a string.

[LarryChen]

Would you please tell me how to compute a hash value given a string? Here hash table is implemented as an array and it has nothing to do with stl hash map. Thanks.

Same idea as when you want to compute a hash value given a string.

[MrViggy]

Hash function examples. Scroll to the bottom.

Viggy

[LarryChen]

I know hash function. Which data structure would you use to store the keys and values? Thanks.

Hash function examples. Scroll to the bottom.

Viggy

[MrViggy]

One method is to use an array of lists.

Viggy

[LarryChen]

What is array of lists? Would you mind giving me a simple example? Thanks.

One method is to use an array of lists.

Viggy

[MrViggy]

An array, who's data type is a list:

std::vector <std::list<foo> >

Viggy

[LarryChen]

Can you use hash function without using any of STL? I repeat my original quesiton. There is an array, int a[] = {3, -1, 5, 7, -6}. How'd I build a hash table based on this array without using any of STL? Thanks.

An array, who's data type is a list:

std::vector <std::list<foo> >

Viggy