I know little of hash tables, but I thought they might help me out. I have two integers (the hash keys?) and I want to return an integer. How would I convert this to a hash table? I was thinking of using a 2D array, like int table[4][4], where I could just enter the values like a typical array and return the data, but the two integers being used as the hash keys might be huge, and that would be a lot of wasted memory.

Input two integers, output one integer.

Is having a large array, but only using a couple entries
called a dispersed array?

Where can I find more info about this?

I think it''s actually called a sparse array. I could be wrong though.

There should be plenty of explanation of hashing out there on the web if you use Google. The idea is that you take a value with a large range and convert it to a smaller range so that you are effectively storing a lot of values in a smaller space. The way you do this is called the hashing function. Except in certain specialised areas, you will often find yourself trying to put 2 values in the same space, so you also need a way of deciding what to do when this happens: this is your method for resolving collisions.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

quote:Original post by Kylotan
I think it's actually called a sparse array. I could be wrong though.

No, you're absolutely right.

quote:The idea is that you take a value with a large range and convert it to a smaller range so that you are effectively storing a lot of values in a smaller space.

Ergo, a simple hash function would be modulo a convenient radix - 10, for example:

int hash(int x){  return x % 10;}  

quote:Except in certain specialised areas, you will often find yourself trying to put 2 values in the same space, so you also need a way of deciding what to do when this happens: this is your method for resolving collisions.

One of the simpler methods is to move to the next free space in your hash table, but it eventually breeds complications during retrieval. Another is to make each entry actually be a linked list, so any collisions are appended to the list.

(That Kylotan guy's pretty good, eh?)

[Edit:] An application to your scenario.

So we have to numbers and wish to store just a single value. We could hash the numbers and use them as array indices into the sparse matrix (which is better implemented as a std::map). We're done. As for reversing the procedure, well, I'm trying to drink some soup right now so my brain's a little fuzzy...

[ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ]
Thanks to Kylotan for the idea!

Edited by - Oluseyi on January 12, 2002 10:32:10 PM

That''s it. Sparse arrays. I don''t think I need to use hash
functions if I can use this.

So if I had a sparse array, each entry would be a linked list
which would look something like this:

typedef struct NODE {

INT row;
INT col;
INT value;

struct NODE *next_row;
struct NODE *next_col;

} NODE;


And there would be two head pointers:

struct NODE *first_row;
struct NODE *first_col;

To find an entry, I can probably pick the row or col head pointer
(it shouldn''t matter). If I picked the row header pointer, I would
traverse the linked list until I found a row match. Then I would
start traversing the col linked list until I find a col match.
That should give me the value I want.

Any suggestions?