IBM developerWorks: The wonders of GLib, Part 2 - Hash tables, the iterator, the GScanner, & tokensJun 18, 2000, 19:30 (2 Talkback[s])
(Other stories by George Lebl)
"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."
0 Talkback[s] (click to add your comment)