Jump to content
  • Advertisement


This topic is now archived and is closed to further replies.


What's a Hash Table?

This topic is 6916 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I know what a hashtable is. The matter is that i don''t speak english good enough to explain it

But anyway, let''s try!

A hashtable is a kind of array. However, when you want to store a new value, you calculate its index with a formula. Storing you values this way allows you to find them quickly (applying the formula). It''s useful if you want to seek for things you''ve stored.

You can easily find more complete informations about this in an algorithm book.

Share this post

Link to post
Share on other sites
Hash Tables in ''n'' words or less.

A hash table is way to sort data so that retreival can be done in constant time. To get this high speed performance however, you need lots of memory. Normally hash tables use twice as much memory as the data they''re actually storing.

So the hash table itsself is like a big array, and every item you want sorted is ''hashed'' or put into this array at an index that is somehow derived from its address space, or some other key unique to the data. The acutally hashing function is not rocket science, just something that grabs a few bits out of an address. So the hash function derives a psuedo-unique identifier from the data item and then the item is stored in the array at that index.
Since you''ve got way more array spaces than items, this normally works really well, but sometimes 2 data items will derive the same identifier (I said psuedo-unique you know) and then you run into problems where you''re trying to put 2 entries into the same place in an array. There are a couple of remedies for this, most commonly, the array is an array of linked lists, so that any 2 things hashed to the same place can simply be strung out, and all still belong to this same hash address.

Hash tables are for fast sorting when you''ve got memory to spare.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!