Topic 8 – Hashing Techniques

Concept of Hashing

Hashing in computer science (not to be confused with the running/drinking group of the same name) – refers to sorting items into bins or buckets. The concept is simple and commonly practiced in real life to aid in searching for items. For example you probably organize your clothes using a hashing technique – putting underwear in one drawer, socks in another, shorts in another, etc… You simply use one identifying technique of your data to separate the data into buckets – and then when you need to find something – you only need to search that bucket (or drawer, or bin, or whatever).

Video – The Hash Function

Link – https://www.youtube.com/watch?time_continue=1&v=oLdbdErnj_I

Hash Tables

A hash table (also called hash map) is a data structure used to implement an associative array, a structure that can map keys to values. Each key is typically assigned its own bucket, but multiple keys can be assigned to a common bucket. This goes back to sorting your clothes, in this case your clothes will each have a key; underwear, socks, shirts, shorts, etc… and the bucket will be the hash table (only in computer science you need to create this structure). Hash tables are discussed in depth in this article – http://en.wikipedia.org/wiki/Hash_table

Hash Functions

You will need a way to decide which bucket a data item goes into based on some algorithm. This algorithm is called a Hash Function. If you look at your contacts list on your phone – you might see an alphabet list. Each letter in the alphabet list represents a bucket – and is the first letter of the name of a contact. In this case the Hash Algorithm for sorting your contacts in buckets is to use the first initial of the persons name. There are lots of different hash function, and your ability to write a good hash function may be important. A perfect Hash function is said to be one that assigns each data element a unique bucket, though this is a very rare case – you should fully read http://en.wikipedia.org/wiki/Hash_function to understand hash function concepts.

Security and Hash Functions

A common use of hash functions is in security. For security purposes it is often a bad practice to store user passwords. Of course this would make it difficult to create a user login system – so we can turn to hash functions. A good hash function can take the user password

Hashed Password = f(User Password)

Instead of storing the user password, you instead store the hashed password. When the user logs in and gives their password – you apply the hash function to the entered password, compare it against the stored hash password – and if they are the same – the user logs in. Notice this never requires you to store the user password in your system. If the hash function is strong enough then it is impossible to convert it back to the original password – thus protecting your users. Information about cryptographic hash passwords is at http://en.wikipedia.org/wiki/Cryptographic_hash_function Collisions are one of the problems that can easily be faced with using hash functions and hashing for cryptography and authentication protection.