Show the array that results from the following sequence of key insertions using a hashing system under the given conditions: 5, 205, 406, 5205, 8205, 307 (you can simply list the non-null array slots and their contents) a. array size is 100, linear probing used.
b. array size is 100, quadratic probing used.

a) Linear probing is one of the hashing technique in which we insert values into the hash table indexes based on hash value.

Hash value of key can be calculated as :

H(key) = key % size ;

Here H(key) is the index where the value of key is stored in hash table.

Given,

Keys to be inserted are : 5 , 205, 406,5205, 8205 ,307

and size of the array : 100.

First key to be inserted is : 5

So, H(5) = 5%100 = 5,

So, key 5 is inserted at 5th index of hash table.

Next key to inserted is : 205

So, H(205) = 205%100 = 5 (here collision happens)

Recompute hash value as follows:

H(key) =(key+i) % size here i= 1,2,3...

So, H(205) =( 205+1)%100 = 206%100 = 6

So, key 205 is inserted in the 6th index of the hash table.

Next Key to be inserted : 406

H(406) = 406%100 = 6(collision occurs)

H(406) =(406+1) %100 = 407%100 = 7

So, the value 406 is inserted in 7the index of the hash table.

Next key : 5205

H(5205) = 5205%100 = 5(collision)

So, H(5205) = (5205+1)%100 = 6( again collision)

So, H(5205) = 5205+2)%100 = 7(again collision)

So, H(5205) = (5205+3)%100 = 8 ( no collision)

So, value 5205 is inserted at 8th index of the hash table.

Similarly 8205 is inserted at 9th index of the hash table because , we have collisions from 5th to 8th indexes.

Next key value is : 307

H(307) = 307%100 = 7(collision)

So, (307+3)%100 = 310%100 = 10(no collision)  

So, 307 is inserted at 10th index of the hash table.

So, hash table will look like this:

Key       index

5         5

205         6

406         7

52058

82059

307         10

b) Quadratic probing:

Quadratic probing is also similar to linear probing but the difference is in collision resolution. In linear probing in case of collision we use : H(key) = (key+i)%size but here we use H(key) =( key+i^2)%size.

Applying Quadratic probing on above keys:.

First key to be inserted : 5.

5 will go to index 5 of the hash table.

Next key = 205 .

H(205) = 205%100 = 5(collision)

So. H(key)= (205+1^2)%100 = 6(no collision)

So, 205 is inserted into 6th index of the hash table.

Next key to be inserted 406:

So, 406 %100 = 6 (collision)

(406+1^2)%100 = 7(no collision)

So, 406 is moved to 7th index of the hash table.

Next key is : 5205

So, 5205%100 = 5 (collision)

So, (5205+1^2)%100 = 6 ( again collision)

So, (5205+2^2)%100 = 9 ( no collision)

So, 5205 inserted into 9th index of hash table.

Next key is 8205:

Here collision happens at 5the , 6the , 9th indexes,

So H(8205) = (8205+4^2)%100 = 8221%100 = 21

So, value 8205 is inserted in 21st index of hash table.

Next value is 307.

Here there is collision at 7the index.

So, H(307) = (307+1^2)%100 = 308%100= 8.

So, 307 is inserted at 8the index of the hash table.

Key          Index

5                  5

205                  6

406                  7

5205                9

8205               21

307                   8

we can all learn from our past mistakes because we all have different ways of learning different types of techniques. my way may or may not another classmate remember and have the repetition to acknowledge such standard. such as remembering acronyms. using abbreviations to us remember keep things in order in our memory. this us figure out what comes next in the sequence. if so, what we have is a sentence of just letters all in caps. we either know the meaning or have no idea what it stands for. most of the time we know the meaning and context. but most of us who don't know, should learn by having a quick glance at what needs to be remembered. such as repetition in the memory for acronyms. one way that me, is the fact that i'm always doing math and english assignments. so we have to remember specific meanings such as soapstone for documents, such as citing correctly. or pemdas for doing the equations correctly, even if it's the super long way. this works for everyone. you just have to find what works for you by practicing and repetition daily.