News: 11 March 2016 - Forum Rules
Current Moderators - DarkSol, KingMike, MathOnNapkins, Azkadellia, Danke

Author Topic: What is a hash table?  (Read 2232 times)

Pikachumanson

  • Hero Member
  • *****
  • Posts: 607
    • View Profile
What is a hash table?
« on: December 09, 2012, 12:49:00 am »
Does the nes or tg 16 use it?

Ryusui

  • Hero Member
  • *****
  • Posts: 4989
  • It's the greatest day.
    • View Profile
    • Tumblr
Re: What is a hash table?
« Reply #1 on: December 09, 2012, 03:25:10 am »
http://en.wikipedia.org/wiki/Hash_table

Considering how much memory they can require, there's probably no benefit to using them on platforms where memory is limited. Why do you ask?
In the event of a firestorm, the salad bar will remain open.

Pikachumanson

  • Hero Member
  • *****
  • Posts: 607
    • View Profile
Re: What is a hash table?
« Reply #2 on: December 09, 2012, 03:29:08 am »
Just for future reference. I saw mention of them on this and the only thing I know about hash is this #. What are they used for? The higher end newer systems?

Gideon Zhi

  • Discord Staff
  • Hero Member
  • *****
  • Posts: 3532
    • View Profile
    • Aeon Genesis
Re: What is a hash table?
« Reply #3 on: December 09, 2012, 08:19:21 am »
They're a way to store and access data in roughly constant time. The idea is that you crunch your data point through some equation that you determine will a reasonably large number of unique differences when run against your data set, then you use that as an index to an array. This way, if you're looking for one particular element, instead of sorting the array or having to seek through every element of the array you can simply re-crunch your hashing equation to determine exactly (not quite, but good enough for introductory explanatory purposes) where the data would be in the array, and jump straight to that index.

You won't find hash tables implemented in games prior to the PS1 era, possibly the PS2 era. They require a lot of memory and are really only useful if your data set is either gignormously large or constantly changing. For anything else you can simply either directly index based on known indices and max values or pre-sort your list and do a binary search in log(n) time.

Pikachumanson

  • Hero Member
  • *****
  • Posts: 607
    • View Profile
Re: What is a hash table?
« Reply #4 on: December 09, 2012, 01:51:41 pm »
Thanx for the explanation!

Zoinkity

  • Hero Member
  • *****
  • Posts: 565
    • View Profile
Re: What is a hash table?
« Reply #5 on: December 09, 2012, 06:54:25 pm »
Want a good example?  StarCraft64 on the N64 (PC too actually, but different circumstances). 
Instead of storing string names it generates 32bit hashes.  That means that file lookup only requires you to take the original string, convert it into a hash, then search for 32bit values instead of using something like strncmp a billion times.  With 2850-some-odd files, that matters a lot.

Another really handy side effect is that instead of having to compare data of various sides all your hashes are the same length, and when doing standard int comparisons it takes more code to grab individual entries than comparing the values.  It's radically faster.

To be fair though, they use a lousy implementation of it ;*)

Certain modern PC games will generate a hash based on a filename and use it as a decryption key.  Unless they have a filelist, you'd basically have to brute-force files out of them--something that could take, no joke, millions of years in the worst case.