We want to store the following sequence of keys in a hash table: 407, 801, 815,

Question

We want to store the following sequence of keys in a hash table: 407, 801, 815, 704, 814, 721, 935. Draw the result of inserting these keys for each of the following tables: Hash function: Select the last two digits then use division by 7: h(k) = (k%100)%7. Collision resolution strategy: Linear rehashing with c = 2 (Show the number of probes). Hash function: Folding on a single digit then use division by 7. Collision resolution strategy: External chaining. Hash function: h(k) = (3x(k%100))%7. Collision resolution strategy: coalesced chaining with a cellar size of 2 (Show clearly the links and the final location of peal).

Explanation / Answer

Value: 407, 801, 815, 704, 814, 721, 935

(1) h(k) = (K%100)%7

   h(407) = (407%100)%7 = (7)%7 = 0
   h(801) = (801%100)%7 = (1)%7 = 1
   h(815) = (815%100)%7 = (15)%7 = 1
   h(704) = (704%100)%7 = (4)%7 = 4
   h(814) = (814%100)%7 = (14)%7 = 0
   h(721) = (721%100)%7 = (21)%7 = 3
   h(935) = (935%100)%7 = (35)%7 = 0

   The linear probing hash table is a fairly simple structure where data items are stored directly inside the hash element array. If the cell is already occupied then we check next cell to it util we find empty cell.

   In this question there is linear probing with c=2 i.e if the cell is already occupied then we increase the value of key by 2 and will chech that cell util we find empty cell we will repeat the process by increasing key by 2.

   key       value
   0   ->   407
   1   ->   801
   2   ->   814       //key 0 is already occupied by 407 so we increase the key value of 814 by c that is equal to 2
   3   ->    815       //key 1 is already occupied by 801 so we increase the key value of 815 by c that is equal to 2
   4   ->    704
   5   ->   721
   6    ->   935       //key 0 is already occupied by 407 so we increase the key value of 815 by c but 2 is already occupied                    by 814 so we again increase key value by 2

   Remember once we reach the end of array we will start from 0 for example let h(k) = 6 but it is already filled then we will check key 1 in this case.

(2) for single digit take mod with 10

   h(k) = (k%10)%7

   h(407) = (407%100)%7 = (7)%7 = 0
   h(801) = (801%100)%7 = (1)%7 = 1
   h(815) = (815%100)%7 = (5)%7 = 5
   h(704) = (704%100)%7 = (4)%7 = 4
   h(814) = (814%100)%7 = (4)%7 = 4
   h(721) = (721%100)%7 = (1)%7 = 1
   h(935) = (935%100)%7 = (5)%7 = 5

   Separte or External Chaining work like this (we use array of array)

   key       value
   0   ->    407
   1   ->   801, 721
   2  
   3
   4   ->   704, 814
   5   ->    815, 935
   6

(3) h(k) = (3*(k%100))%7
  
   h(407) = (3*(407%100))%7 = (3*7)%7 = 21%7 = 0
   h(801) = (3*(801%100))%7 = (3*1)%7 = 3%7 = 3
   h(815) = (3*(815%100))%7 = (3*15)%7 = 45%7 = 3
   h(704) = (3*(704%100))%7 = (3*4)%7 = 12%7 = 5
   h(814) = (3*(814%100))%7 = (3*14)%7 = 52%7 = 3
   h(721) = (3*(721%100))%7 = (3*21)%7 = 63%7 = 0
   h(935) = (3*(935%100))%7 = (3*35)%7 = 105%7 = 0

   Collision resolution strategy: coalesced chaining is one of the toughest hash. This strategy don't use rehash. If that cell is occupied already we will check empty cell from bottom and once we got we will instert that value

   key       Value
   0   ->   407
   1   ->   935
   2   ->   721
   3   ->    801
   4   ->   814
   5   ->    704
   6   ->   815

   If the cell is filled we will start searching for empty cell from bottom

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.