Intro into #Hashing ?

Chaining:

1.Chaining without Replacement:

The hash address of an identifier X is computed. 

1. If this position is vacant, it is placed there.
2. It its position is occupied by another identifier Y, the identifier X is put in the next vacant position and a chain is formed to the new position i.e. from Y to X.

Example:    Identifier is 11, 32, 41, 54, 33.

Hash function:    f(x) = X mod 10 and Table size = 10

1. Identifier 11 and 32 get hashed into positions 1 and 2 respectively. 
2. The hash address of 41 is 1 but its position is occupied, hence it is put at position 3 and a chain is formed.    
3. 54 stored at position 4
4. The hash address of 33 is 3 but it is occupied.  So 3 is placed at position 5 and a chain is formed from position 3 to 5 as shown. 

Advantage:

1. Since identifiers are chained, we have to only use the chains to locate an identifier.
2. It is more efficient as compared to the previous methods.

Disadvantage: 

1. The main idea is to chain all identifiers having same hash address (synonyms). However, when an overflow occurs,  an identifier occupies the position of another identifier. Hence, even non-synonyms get chained together thereby increasing complexity. 

2.Chaining with Replacement:

This is an improvement over the above method. As we saw above, even non synonyms get chained. To avoid this from happening, if we find that another identifier Y which is a non-synonym, is occupying the position of an identifier X, X replaces Y and then Y is relocated to a new position. 

It will not make a difference to Y since Y was anyway not in its own bucket. But by placing X in its own bucket, we are improving the efficiency. 

Let us consider the same example as earlier.  Here, 11, 32, 41 and 54 get placed in the same way as before. 

However, when 33 has to be placed, its position is occupied by 41. Thus, 33 replaces 41 and 41 is now put into the next empty slot i.e 5 and the chain from element 11 at position 1 is modified. 

1. 11,41===1
2. 33===3
3. We will swap 41 & 33

Advantages: 

1. Most of the identifiers occupy their valid positions. 
2. Searching becomes easier since only the synonyms are chained. 

Disadvantages: 

1. Insertions and deletions take more time. 

3.Chaining using linked lists:

All of the above methods suffer from a variety of problems. 

1. Limited amount of space, due to which the table can become full.
2.  The complexity of chaining which results in poor efficiency. 

Obviously the best method would be to have unlimited amount of space for each bucket so that we could put in as many identifiers as we want without any overflow taking place.

Advantages 

1. Most efficient method to resolve collision. 
2. There is no limit on the number of identifiers. 
3. Searching, Insertion and Deletions are done efficiently. 
4. The hash table will never be ‘full’. 

Disadvantages

1. If many identifiers are put into a single list, searching time within a bucket will increase.
2. Handling of the pointer array and linked lists is more complex as compared to simple arrays.  

EXTENDIBLE HASHING

Reason for Extendible hashing :

1.  Most records have to be stored in disk
2. Disk read/write operations much more expensive than operations in main memory
3. Regular hash tables need to examine several disk blocks when collisions occur
4. We want to limit number of disk accesses for find/insert operations

Concept :

1. Retrieval to be performed in two disk accesses and Insertion also in  few accesses. 
2. This can be achieved by using a tree structure. 
3. The tree is an M-ary tree (degree M) which allows M-way branching. 
4. This means that as the branching increases, depth of the tree decreases. 
5. A complete Binary tree has height (log₂N) whereas a complete M-ary tree  has height of (log _M/2 N). As M increases, the depth decreases. 

Procedure:

1. Hash the key of each record into a reasonably long integer to avoid collision
2. Adding 0’s to the left so they have the same length
3. Build a directory
4. The directory is stored in the primary memory
5. Each entry in the directory points to a leaf 
6. Directory is extensible
7. Each leaf contains M records, 
8. Stored in one disk block  
9. Share the same D number of leading digits

For more information on hashing,

1. http://cse.uaa.alaska.edu/~afkjm/csce311/fall2018/handouts/hashing-drozdek.pdf
2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec08.pdf

1. GitHub Repository for code: https://github.com/kakabisht/Data-structures
2. Blog on Encryption and Decryption:https://programmerprodigy.code.blog/2020/04/10/encryption-and-decryption/