Demonstrate the insertion of the keys 5,28,19,15,20,33,12,17,10 into a hash tabl

Question

Demonstrate the insertion of the keys 5,28,19,15,20,33,12,17,10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k) =k mod 9, (10') Suppose we wish to search a linked list of length n, where each element contains a key k along with a hash value h(k). Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key? (10') Consider inserting the keys 10,22,3 1,4,15,28,17,88,59 into a hash table of length m addressing with the auxiliary hash function h'(k)=k mod m. Illustrate (which means you should write down the result with your explanation) the result of the inserting these keys using linear probing, using quadratic probing with c and c,-3 and using double hashing with h2(k)=1+(k mod(m-1)) (10') 4. 5. 6. 11 using open

Explanation / Answer

Solution to question 4

Keys to be inserted -> 5,28,19,15,20,33,12,17,10

1. Insert 5
Position = 5mod9 = 5
Hash Table at position 5 is empty , so 5 will be inserted at position 5
Hash Table -> 5 : 5

2. Insert 28
Position = 28mod9 = 1
Hash Table at position 1 is empty , so 28 will be inserted at position 1
Hash Table ->
1 : 28
5 : 5

3. Insert 19
Position = 19mod9 = 1
Hash Table at position 1 is not empty , so 19 will be inserted at position 1 after 28
Hash Table ->
1 : 28 -> 19
5 : 5

4. Insert 15
Position = 15mod9 = 6
Hash Table at position 6 is empty , so 15 will be inserted at position 6
Hash Table ->
1 : 28 -> 19
5 : 5
6 : 15

5. Insert 20
Position = 20mod9 = 2
Hash Table at position 2 is empty , so 20 will be inserted at position 2
Hash Table ->
1 : 28 -> 19
2 : 20
5 : 5
6 : 15

6. Insert 33
Position = 33mod9 = 6
Hash Table at position 6 is not empty , so 33 will be inserted at position 6 after 15
Hash Table ->
1 : 28 -> 19
2 : 20
5 : 5
6 : 15 -> 33

7. Insert 12
Position = 12mod9 = 3
Hash Table at position 3 is empty , so 12 will be inserted at position 3
Hash Table ->
1 : 28 -> 19
2 : 20
3 : 12
5 : 5
6 : 15 -> 33

8. Insert 17
Position = 17mod9 = 8
Hash Table at position 8 is empty , so 17 will be inserted at position 8
Hash Table ->
1 : 28 -> 19
2 : 20
3 : 12
5 : 5
6 : 15 -> 33
8 : 17

9. Insert 10
Position = 10mod9 = 1
Hash Table at position 1 is not empty , so 10 will be inserted at position 1 after 19
Hash Table ->
1 : 28 -> 19 -> 10
2 : 20
3 : 12
5 : 5
6 : 15 -> 33
8 : 17

Solution to question 5 :

- Every element has a key and hash value associated with it
- Key is a long character string , so comparing two keys can take some time
- To reduce the comparison time , we can compare strings while searching only when they both have same hash key (Because if two strings are equal then their hash keys will also be equal)

**If you have any query , please feel free to comment with details.
**Happy leaning :)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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