rgba

Hey,

I'm looking for an efficient way to store memory addresses and lookup for an arbitrary memory address must be very fast.

I'm thinking along the lines of a hash table, but the range of possible memory addresses is so big that building a suitable hash table that uses the memory addresses as a key would be impossible.

Basically, I need to be able to locate an arbitrary memory address with minimal lookup time, i.e. a hash table.

Does anyone have any suggestions to this problem?

Thanks

Narue

>hash table, but the range of possible memory addresses is so big
You're confusing a basic lookup table with a hash table. A hash table is designed so that you don't need to provide slots for the entire range of keys. A hash function takes a key and turns it into a suitable index into the table, so the size of the table is only related to the number of expected keys, not the expected range of keys.

>Does anyone have any suggestions to this problem?
I'd say go with a hash table unless there are other restrictions that you haven't mentioned.

__________________
Even if the voices aren't real, they have some pretty good ideas.

rgba

Hey Narue,

Thanks for the reply. Actually, the question I wanted to ask was how to generate a function that finds the correct item in the hash table from the memory address???

Sorry for the confusion!

Thanks

Narue

The address is your key, right? Just hash it with one of these. You'll need a collision strategy as well, but all in all it's pretty straightforward.

__________________
Even if the voices aren't real, they have some pretty good ideas.

rgba

Thanks Narue, will have a look at the links!

rhish.franks

Hey the thing is very simple. When you will get a key i.e. address for search, it will go to the hash function. Now hash fn will give you the possible address for that, now next will be dependant on what collision handling tech you have used. i.e. either linear probing or buckets method etc., so when your hash fn returns the virtual address value, it will be passed to other fn which will search for real address by kipping in mind collision detection technic.

rgba

Hey rhish.franks,

Yeah, I do understand the concept of the hash function, I'm just not quite sure yet how to create a function based on the memory addresses...

rhish.franks

Hey Rgba, i would suggest you to create your hash function by considering what is done in main memory management. i.e. in paging and also in demand paging. There total work is done on the basis of memory addresses only. So you can also use like that virtual address. Just consider throughly those methods, am sure you will get something useful from that.

rgba

Hey rhish.franks,

Thanks, I will be looking into that when I get some free time...