Hash tables

The Hash Table is a Data Structure in an "associative" way, that is, it has to associate a key with a value to perform its operations.

The key is associated with the value thanks to the hash function. This function is used to calculate the index that corresponds to the value of the key that we have passed to it.

This structure also has the particularity that it is one of the most efficient and fastest Data Structures, this is because its execution time is constant in the average case. The complexity of hash tables is:

The hash function

The hash function is the most important part of the hash table since it determines the cost of this data structure.

The hash function what it does with the key is to convert it so to speak into a code. This code what this function does is that when we pass the key this key is going to be passed by the function and this function is going to transform it into a reference to the memory.

The hash function inside is a set of mathematical operations that unwraps the key until it can not be understood for example if we give the values "hola" or "Hola" it will give us:

As we can see this will give a totally different value although the only difference between the 2 words is the capitalization, and these values are unique, "hola" and "Hola" will always take these values.

The hash functions will almost always take a predetermined length, for example "a" and "how are you doing bro" when passed through the hash function will have the same length so there will be collisions.

A characteristic of hash tables is that a computer does not take time to make it but it is very difficult to undo it so much so that.

The hash table stores the elements in the slots or buckets.

collision

We know that most hashes have a fixed length size, this means that it can happen the situation that 2 different inputs (keys) passing through the hash function can result in the same value.

It is mathematically impossible that a collision does not occur, but we can say that collisions mostly occur in bad algorithms, if an algorithm has collisions then the algorithmic complexity will vary. Let's see an example:

Suppose that the hash function goes to a single reference in memory, this will gather several values let's say in an array or the a linked list so read or modify will have the algorithmic complexity of one of them.

It is possible to create a collision free algorithm, this is done by being careful with the length and the amount of keys we have or the hash algorithm we are using (MD5 or some SHA algorithm).

Example

In Python, the Dictionary data types represent the implementation of hash tables. Let's see an example

dict = {'Name': 'Enrique',     
        'Age':18,              
        'Gender':'male',       
        'Idiom': 'en',
        'second idiom': 'es'   
        }

dict['second idiom'] # es

implement

althouh in some languages it works a little differently, we can implement a hash table in this way

class hash_table():            
    def __init__(self,size):   
        self.size = size       
        self.data = [None]*self.size    
    def __str__(self):
        return str(self.__dict__)       
    def _hash(self, key):
        hash = 0               
        for i in range(len(key)):       
            hash = (hash + ord(key[i])*i) % self.size
        return hash            
  
    def set(self, key, value): 
        hash = self._hash(key) 
        if not self.data[hash]:         
            self.data[hash] = [[key,value]] 
        else:
            self.data[hash].append([key, value])

    def get(self,key):
        hash = self._hash(key)
        if self.data[hash]:
            for i in range(len(self.data[hash])): 
                if self.data[hash][i][0] == key: 
                    return self.data[hash][i][1]    
        return None


    def keys(self): 
        keys_array = [] 
        for i in range(self.size):      
            if self.data[i]:
                if len(self.data[i]) > 1:       
                    for j in range(len(self.data[i])):  
                        keys_array.append(self.data[i][j][0])
                else:
                    keys_array.append(self.data[i][0][0])
        return keys_array

    def values(self): 
        values_array = []
        for i in range(self.size):      
            if self.data[i]:
                for j in range(len(self.data[i])):
                    values_array.append(self.data[i][j][1])
        return values_array

Pros and Cons:

Pros

• Fast: the most important advantage over hash tables is that it is fast in accessing, deleting and saving data. For this reason it is widely used in databases.
• Use: is very easy to use and understand

Cons

• Collisions: the collisions can become inefficient when there are many keys in the hash tables
• values: hash tables do not allow for all types of values (eg. NULL)
• memory: if space is reserved for all possible elements it may require more memory than needed

Example

we can see a great example with a Google Interview Question: Given an array, return the first recurring character

Example1 : array = [2,5,6,2,6,5,1,4]

It should return 2

def sl(array):
    dictionary = dict()
    for item in array:
        if item in dictionary:
            return item
        else:
            dictionary[item] = True