an efficient way to store/lookup memory addresses?
 

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

Re: an efficient way to store/lookup memory addresses?
 

>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.

Re: an efficient way to store/lookup memory addresses?
 

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

Re: an efficient way to store/lookup memory addresses?
 

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.

Re: an efficient way to store/lookup memory addresses?
 

Thanks Narue, will have a look at the links!

Re: an efficient way to store/lookup memory addresses?
 

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.

Re: an efficient way to store/lookup memory addresses?
 

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...

Re: an efficient way to store/lookup memory addresses?
 

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.

Re: an efficient way to store/lookup memory addresses?
 

Hey rhish.franks,

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