HashTable
Suppose you were tasked with finding a specific person you have never met from a group of people you’ve never seen; your only information given is the name of the person you are looking for. The only way to find this person would be to go to each and every individual person in the group and see if their name matches the name you are looking for. In a group of a few individuals, it would not take too long to find the correct person, but what if there were a million people in that group?
Now imagine the same scenario except now you give the name you have to a clerk. The clerk will then return a name and a number. This number will give you the exact location of the person without having to ask for a single person’s name. This method saves you time by knowing the location of the person.
What is a hashtable?
A hashtable, also known as a hashmap, is a type of data structure that maps keys to its value pairs.
#Declaring dictionary>>> D = {}#Adding elements to dictionary
>>> D['a']
>>> D['b']
>>> D['c']#Dictionary will now returnD = {'a': 1, 'b': 2, 'c': 3}
In hashing, large keys are converted into small keys by using hash functions. The values are then stored in a data structure called hashtable. The main idea of hashing is to distribute key/value pairs uniformly across an array. Each element is assigned a key
Collision
In most cases the key returned by the hash function is unique, however, there are certain cases where a key could be given two values. This is what is known as a collision. A collision can be solved with either of these methods: linear probing, chaining, and resize. Depending on the circumstance certain methods are better than others.
When a bucket is already full then the hash function will place the value and the next available node. This is known as Linear Probing.
If all the nodes in the list are full we cannot use the linear probing method, instead, we add a new node and place the value there. This method is known as chaining.
When the list is too full and no new nodes can be added we use the resizing method. Resize uses the load factor (a measurement) which is calculated by the number of entries divided by the number of buckets and then creates a new list. This new list will have enough space to add the new value
All of these methods help keep the time complexity 0(1) or constant time.
Time Complexity
In most cases, hashtables operate at constant time and have a time complexity of 0(1). However, if there are too many elements are hashed into the same key or passes the load balance, then the time complexity becomes of 0(n)
Applications
Hash tables allow you to store a large number of objects and still be able to quickly find and retrieve the specific object you need. Hash tables can be applied in a wide variety of applications. The most common applications include database indexing, caching, program compilation, and error checking.
