Hashing is a way to map 'keys' (data of any type) to slots in a table of a set length. The key is put through a hash function to return a value, known as the hash value, hash code, hash sum, checksum or simply hash which is what is actually stored, instead of the data itself. The nature of a secure hashing function should be such that it is near impossible to work backwards from the hash value to find the original data value - this makes hashing ideal for storing passwords without storing the actual plaintext password. Another common use is shortening data since the output of a hash function must is of a fixed length. Cryptography also makes use of hashing as it's difficult to fake a hash value in order to hide malicious data. That is the whole idea behind the Pretty Good Privacy data validation algorithm. There are many other uses of hashing in real-world computer science too, so it is an important area to understand.
In a hash table, the has function outputs are stored associatively. This means the rows can be searched in constant time, and then that row's value used as a reference to point back to the key that holds the information you actually need. Since following the reference is also doable in constant time, this makes for a much faster search than iterating through a list, or many types of tree. A good hash function is referentially transparent. An obstacle to this fast searching is if two data values hash to the same slot in the hash table - called a collision. To deal with this, many programming languages have a way to override hash functions for an object.
In any deterministic hasing function, there will be a set of keys that hashes to the same slot, causing collisions that degrade the usefulness of the table. To avoid this, one can use universal hashing which is when you select a hashing function from a family of such functions at random each time. Individually, they have the same limits as a deterministic function, but when picked at random from their family, you can evade most collisions and deny any attackers hoping to use that feature of a poorly-designed hashing table against you.
© BrainMass Inc. brainmass.com March 19, 2024, 3:26 am ad1c9bdddf