CMSC204-Lab 6- Hashing Lab Solved

Given the following key values, show what the data structures would look like after inserting the following

              15 54 13 10 135 114 49 174 27 24

  (no preprocessing necessary:  pk = key)

 

Complete various hashing calculations as specified in the subsequent slides

Feel free to complete this assignment using Excel, Word or other tools

Submit your work and a small write-up highlighting your lessons learned

Check out the following video out

https://www.youtube.com/watch?v=4YiQITXu_iM&t

Parts 2 – 4 as well

•Array of 10 elements using open addressing with linear probing
 

N = 13

•Array of 10 elements using open addressing with quadratic probing
 

N = 13

•Linear array of 10 elements using open addressing (division hashing)
and the linear-quotient collision path algorithm

N = 13, 4k+3 prime = 19

LQHashing:

1. ip = pk % N

2. q=pk/N

    if (q%N != 0)

        offset = q

    else

        offset = 4k+3 prime

3. While collisions:

         ip’ = (ip + offset) % N

4. Set Array[ip]=key

•Bucket hashing of 10 elements (N=10) ip = (pk) % N