Hashing

/*
Hashing
1) linear search
    - specific arrangement of elements
    O(n)
2) binary search
    - elements need to be sorted
        - search time: log n
    - if not sorted
        - nlogn (best time complexity for sorting)
        - better to use linear search then, O(n)
3) Hashing
    - searching in constant time, everytime!
    - elements stored in hashtable
    - hash function: maps the keys to the resultant of hash function
        - most basic hash function: H(x) = x
        - But still inefficient
    - change the hash function
        1. h(x) = x % size (size of hashtable)
        2. multiplication method
            s1. choose constant A such that constant 0 <A < 1'
            s2. multiply the key by A
            s3. extract the fractional part of A
            s4. multiply the result of step 3 by hashtable size
            s5. hashFunction h(k) = floor(m(kA mod 1))
                fractional part of A = (kA mod 1)
                recommended to use A as 0.618 (phi - 1 (Golden ratio))
        3. folding method
            s1. divide the key value into a number of parts . that is divide k into parts k1 k2,.. kn 
            where each part has the same number of digits except the last part which may have
            less digits than the other parts
            s2. add the individual parts. that is obtain the sum of k1 + k2 + ... + kn. that hash value
            is produced by ignoring the last carry if any
            (sum mod sizeOfHashTable )
        
    - collision
        - open hashing (chaining)
            - use linked list
            - on collision, add another node add to the respect index
        - closed
            - linear probing
                - h'(x) = (h(x) + f(i)) % size; f(i) = i
                    h(x) = x % size
                if on calculation of h'(x), there is a collision, then calculate h'x again
                but this time, *increment i*
                - disadvantage: the elements should be as scattered as possible to avoid multiple collisions
                    this method leads to "clustering" of elements
            - quadratic probing
                - f(i) = i^2
                
            
*/

#include <stdio.h>

int main() {
    printf("Hello world!\n");
    return 0;
}