Printable View
I was reading Game Coding Complete 2nd (page 75 if you have it) and noticed he mentioned "If you traverse a large number of free and available blocks very frequently, choose a hash table or tree based structure".
OK, tree structure I understand, but hash table? Not that I want to write one of these myself, but where would you use a hash table in a memory management solution?
Just curious.
I suppose you could use the block addresses as key and the free flag as value, but it doesn't sound very efficient to me.
Theoretically, a hash can have an O(1) search algorithm, though the amount of memory you'd be using for your hash table would be the same amount you were actually maintaining. Still, it would be faster than say a flat array or linked list when searching for memory chunks.
To decide between a hash or a tree...I'd use a hash if I was able to ( or forced to ) keep memory fragmentation low, or keep certain pools for each system. That would keep an even distribution among hash buckets if you were to key them by address like CornedBeef suggested. Or you can hash based on system. IE => bucket 1 = graphics memory; bucket 2 = physics memory; etc.
I have not messed with hash tables and Prelude has some excellent material on her site concerning them, but I'm still a bit fuzzy on them. They sound very useful to me but I must say I don't truly understand how to implement one.
Perhaps skorman00 could give us some help here.
Hey eternallyconfuzzled has had a makeover. Nice.
I've found this to be helpful as well as the wikipedia pages on hash tables.
Hashs are pretty simple, and extremely useful. I'm sure you guys can find tons of ways to use them for optimizations in your code.
Think of a hash table as an array of linked lists. Each item in the list has something about it that says "I go in the list at index [x]." That something is usually an integer % the size of the array. So when you're searching for an item, you have a narrower search set, since you know which linked list it will be in.
Actually a traditionaly hash table would just be an array, and if there is a collision you walk forward (by a constant offset) until you reach a free spot. Having a list at each position in the array is more like double hasing, you hash to the first index, then to the secondary one in the list.
As you've probably gathered, hash functions/tables are basically just for fast searching of large amounts of data, not really for 'memory management' as you seem to think. Hash tables are actually typically space inefficient, but potentially fast (as was mentioned, can take just a single lookup to find a value in the table). What perspective is referring to is when you are building your hash table, using the hash function that you've come up with, and there is something already taking up that spot (if you examine some of the examples of hash functions you'll see how this happens). You then need to determine a way to walk forward/backward in the list (doesn't have to be a constant offset, you can use a linear search, binary search, etc) until you find an empty spot (and, you'd ideally like to make it so that this new one won't likely occupy the space of another in the hash table).Quote:
but where would you use a hash table in a memory management solution?
It can be, but there's no reason for most applications for the hash table to be nothing more than an array.Quote:
Think of a hash table as an array of linked lists
Even though you don't have to impliment it with an array of linked lists, you can still think of it as such. I find that to be the best way to describe how a hash speeds up searching without worrying about the implimentation details. Much like you can think of a heap as a tree, though is most often implimented with an array.