hash table with negative number

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.

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

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

Quote:

---

Originally Posted by S_M_A

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

---

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.

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.

Quote:

---

Originally Posted by 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.

---

Quote:

---

Originally Posted by 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.

---

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

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

Quote:

---

Originally Posted by laserlight

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

---

Quote:

---

Originally Posted by LarryChen

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.

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.

Quote:

---

Originally Posted by laserlight

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

---

Hash function examples. Scroll to the bottom.

Viggy

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

Quote:

---

Originally Posted by MrViggy

Hash function examples. Scroll to the bottom.

Viggy

---

One method is to use an array of lists.

Viggy

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

Quote:

---

Originally Posted by MrViggy

One method is to use an array of lists.

Viggy

---

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

Code:

---

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

---

Viggy

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.

Quote:

---

Originally Posted by MrViggy

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

Code:

---

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

---

Viggy

---

Quote:

---

Originally Posted by LarryChen

Can you use hash function without using any of STL?

---

Obviously :)

Quote:

---

Originally Posted by LarryChen

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?

---

Why not start by taking MrViggy's suggestion of using an array of lists? There is no requirement to use any existing library in that suggestion. It makes sense to use an existing library where it is applicable (and it does not have to be the STL part of the C++ standard library: it could be a library component from whatever programming language that is in use), but if you insist otherwise, just implement what you need.

That is, if you want the functionality of a std::vector<std::list<foo> >, but you insist on not using these containers, then start by implementing your own version of std::vector and std::list.