“In his second installment on GLib, George Lebl gets into a
little more detail. He gives us the rundown on hash tables, and
walks us through creating a table, inserting and looking up data,
and using the iterator through entries. He also provides code and
setup examples of how to use tokens and the GScanner….”
“For those that don’t know how hash tables work, here’s a quick
rundown. A hash table is for associating data with a key. You want
to be able to find the data again quickly when given the key. It’s
a very time-consuming task to look through every possible option,
so hash tables figure out a number from the key called the hash or
the hash number. The hash table is just an array from 0 to the
maximum hash number possible. Each entry in the array has a list of
entries which have this hash number. So when the hash table wants
to look something up, it takes the key, figures out its hash
number, and then looks for the entry in the given location in the
array. The reason this is so quick is that most of the time the
array is larger then the number of elements. And each location in
the array is not likely to have more than a few entries. Thus the
time spent searching for an element is not dependent on the number
of entries you put into the hash table.”
“When most people think of hash tables, they think of
associating a piece of data with a string key and then retrieving
the data quickly using that string key. GLib takes this concept
further. There is no reason for keys to be only strings. The
keys in GHashTable, the GLib type for a hash table, are simple void
pointers. The keys can be any sort of data. Each hash table then
needs to be able to give a hash number to a key. It also needs to
be able to compare two keys to see if they are equal. This means
that each hash table stores pointers for two functions: one that
gives back an unsigned integer with the hash of the key, and one
that compares two keys for equality and returns a boolean
value.”