edit: double post.
No problem Dampe. Basically, a hashtable is an associative array where you can store a "key,data" pair. So, if you wanted to store say a character (and by character I mean a player object or something, not a letter :P) by name, you'd make his name the "key" and then the character object itself would be the data. This facilitates fast lookup of random data that is best indexed with a string or some other "weird" key value. If you knew you had 10 characters and you knew exactly who you'd have up front, it'd of course be much more logical (and faster) to use an array. Hashtables are best when the dynamic is data and you want to be able to look it up based on a unique key (sorry for being redundant but just trying to be clear.)
Basically, what the hash table does is it converts the string you provide to it as a key to a number. This is called "hashing" and the algorithm to generate that # is the hashing algorithm. So, let's just say our hashing algorithm just adds up the ASCII values of each letter of the string provided as key, for illustrative purposes.
So, let's use the following pseudo-code
myObject:someobject
myObject.name = "Test"
'the first parameter to insertEntry is the key
'the second parameter is the object we want to store
'under that key value
hashtable.insertEntry( myObject.name , myObject )
So the code above is inserting an entry into the hashtable with the key "myObject.name", which evaluates to "Test".
So summing the ASCII value for Test we get
T......e........s..........t
84 + 101 + 115 + 116
or 416.
Now, what good does that # do us, and how does the hashtable use that as an index?
Well, the hashtable itself is just an "array of lists" of some size. That size is up to you when you create the hashtable - in the code in the post above I call THashtable.constructor( array.length ) - so the hashtable will have the same # of array elements as the length of the array.
For example purposes though, let's pretend we have a hashtable of size 5...0-4. So the hashtable itself is a 5 element array of Tlists.
So how do we use our generated # above, 416 (the hash value) to index this array? Well, the hashtable does this internally by doing a mod operation that conceptually looks like:
hash-value mod size-of-hash-table
This will always return a result from 0 to size-of-hash-table (well, actually it'll be from 0 to the size of the hashtable minus 1, which will then work perfectly as an index to the hashtables internal array)
so if we insert the #'s we get
416 mod 5
which = 1. (if you need to know how a mod operation works, just ask)
So the key "Test" generates a hash value of 1, which is the index where the hashtable will store the object.
So now we've stored "MyObject" with the key "Test". We can do a lookup like so
hashtable.getEntry( "Test" )
The only parameter is the key value to lookup. Now the hashtable does the same thing - it hashes the key - which will again = 416 which will then have the mod operation performed on it to produce the index of "1", and then the hash-table will return the value of the object stored at index 1.
Internally it's a bit more complex than this b/c of the possibility of "hash collisions" which are the result of 2 different keys producing the same result index. For example, using the hashing algorithm above (which is a very bad one, but it's good for demonstrative purposes) the key "Tets" would also = 416, and so would "steT" or any other arrangement of those same 4 letters. So now we've got multiple keys returning the same hash value? What happens here?
Well, internally the hashtable doesn't just store the object at the index that was generated. It stores a container object (this is the gHashEntry I've talked about in the above posts). This container object stores the "key" AND the "object". This way, multiple objects can be stored at the same index even if they have different keys, since the hash-table only returns the object whose key matches the one provided.
Hopefully this example will make it clearer. Lets say we have 3 objects, and all of the keys produce the same hash value, so they are all going to be stored internally at the same index of the hashtable (remember too that the hashtable is an array of Lists - so each time a hash collision results the object is simply added to the end of the list of the hash table)
So here's some more pseudo-code
object1:someobjecttype
object2:someobjecttype
object3:someobjecttype
'here we make a 3 element hashtable (0-2)
hash:thashtable = Thashtable.constructor( 3 )
object1.name = "Test"
object2.name = "tseT"
object3.name = "Tets"
hash.insertEntry( object1.name, object1 )
hash.insertEntry( object2.name, object2 )
hash.insertEntry( object3.name, object3 )
After this code runs, the hash table will have 3 entries. But since "Test", "tseT" and "Tets" all evaluate to the same value (1) the hashtable internally looks like this
[0] -> points to an empty list
[1] -> gHashEntry -> gHashEntry -> gHashEntry
[2] -> points to an empty list
those 3 gHashEntrys are the container objects I mentioned. The first one, which holds the first entry (object1) will look like this
ghashEntry.name "Test"
gHashEntry.obj = Object1
the 2nd one would be
gHashEntry.name = "tseT"
gHashEntry.obj = Object2
and I'm sure you can guess what the 3rd one would look like.
So now, even though all of the objects are stored in the same element of the hash table, we can still do a lookup and get the proper result with a call like so
hash.getEntry( "tseT" )
This works because when the hashtable is looking for the result it compares the key provided ("tseT") to the key of each entry in the list at the index of the hash value of that key.
So first it will reach the first entry ("Test") and compare it's stored key against "tseT"...nope, not the right object...then it goes to the next object in the list - and that one's key (or name) does match "tseT", and so it returns the associated object. It will return Object2.
Ack...this is a long post and I"m not sure if I made it real clear how this works. I have trouble illustrating concepts in any sort of brief manner, so I apologize :). Anyways, hope this helps a bit.