Hashing and Hash Table

    Hashing is method that is usually used to store and retrieve strings that are transformed to shorter length values or keys to represent them. These shortened strings act as indexes or addresses in the hash table for the original string. This method id used as it is easier to find shorter length items than their original length.

    A hash table is where we store the string in an array format. The index of the table/array is the hashed key while the value of the index is the original string.

    Hash function are functions to hash a string.
   
    Types of hash functions:

     - Mid-square
        The string is squared and the a specified number of bits from the middle part is taken to get the hash key. If the key is a string, it is converted into a number.
       

       

     - Division
        Get the added up ascii of the string and modulo it by a specified number (usually the table size).

     - Folding
        Divide the value into equal digit parts, except for the last part which can contain less or more digits. Add all the parts together and ignore the last carry. The result is the hashed value.

     - Digit Extraction
        Obtain a predefined digit from the original value and the hashed value is obtained.

     - Rotating Hash
        Use another hash method then reverse the obtained value to obtain the hashed value.

    If we continuously use the same hash method for many strings, some of the hash values might be the same.This is called a collision.

    There are two way to handle a collision:
        - Linear Probing
            Look for the next available slot in the table and put the value there instead.

           This method though makes it harder to find a specific string as when you calculate the hash key of a string, the hash key might not be where it is stored in the table, causing you to have to loop through the table until you find the wanted value. This makes it very ineffective if there are many collisions.

        - Chaining
            Make a link list in the slot where collisions occur.

            When a collision happens a link list is used to store the next value with same hash key. This is so that when we want a specified string and it experiences collision, we only need to iterate through the link list in the slot, not the entire table.

    In blockchain use in cryptocurrency, hashing is used to encrypt transactions so that the item, when hashed, will produce an output of a fixed length. The output will always be the specified length no matter how long the original input is. This makes it keep track of the transactions as you can recall/trace the hash.