[Memory management] Hash table?

This is a discussion on [Memory management] Hash table? within the Game Programming forums, part of the General Programming Boards category; I was reading Game Coding Complete 2nd (page 75 if you have it) and noticed he mentioned "If you traverse ...

  1. #1
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709

    [Memory management] Hash table?

    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.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

  4. #4
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    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.

  5. #5
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Hey eternallyconfuzzled has had a makeover. Nice.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,761
    I've found this to be helpful as well as the wikipedia pages on hash tables.

  7. #7
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  9. #9

    Join Date
    May 2005
    Posts
    1,041
    but where would you use a hash table in a memory management solution?
    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).

    Think of a hash table as an array of linked lists
    It can be, but there's no reason for most applications for the hash table to be nothing more than an array.
    I'm not immature, I'm refined in the opposite direction.

  10. #10
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 10:23 PM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 06:06 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-25-2007, 12:36 AM
  4. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 07:54 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 10:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21