Understanding hash tables
Here's what I understand from the definition of a hash table. A hash table is essentially an array that contains items (objects). These objects could have multiple member fields and one of those member fields is considered to be the "key". The "key" is then hashed/mapped onto numbers that range from 0 to size_of_hash_table - 1. If I have got the definition right, then we actually have two arrays: one of them the actual hash table and the other one where keys get mapped onto. Furthermore, what is that point of mapping "keys" onto numbers?
Hash maps are usefull when you want to index data by a key. For example, suppose you want to access a student information from his name. You could have a map.
A map would be a table, with each line for a student. The first column, the key, would be the student name
So when you want to access a student info, you would search his name in the first column. That would involve string comparison.
The hash_map brings a first gain here. It's hash function will convert names to a number. As numbers are faster than compare than strings, a student search would be faster.
A good hash function is very important, it brings an other benefit. A "perfect " hash function could convert N student names into N consecutive numbers. So the hash function could convert the student names directly into a position to read in a table. One read in an array is again faster than searhcing a number in each line of an array.
Now, perfect hash function are hard to find. That's why sometimes there will be two different student numbers hashed in the same number.That's why a key must be able to have multiple members
A map would be a table, with each line for a student. The first column, the key, would be the student name
So when you want to access a student info, you would search his name in the first column. That would involve string comparison.
The hash_map brings a first gain here. It's hash function will convert names to a number. As numbers are faster than compare than strings, a student search would be faster.
A good hash function is very important, it brings an other benefit. A "perfect " hash function could convert N student names into N consecutive numbers. So the hash function could convert the student names directly into a position to read in a table. One read in an array is again faster than searhcing a number in each line of an array.
Now, perfect hash function are hard to find. That's why sometimes there will be two different student numbers hashed in the same number.That's why a key must be able to have multiple members
Topic archived. No new replies allowed.