Question

In: Computer Science

3. Assume a hash table with 7 locations and the hashing function h(i) = i%7. Show...

3. Assume a hash table with 7 locations and the hashing function h(i) = i%7. Show the hash table that results when the integers are inserted in the order given. (10 points each. Total 30)

• 5, 11, 18, 23, 28, 13, 25, with collisions resolved using linear probing

• 5, 11, 18, 23, 28, 13, 25, with collisions resolved using quadratic probing

• 5, 11, 18, 23, 28, 13, 25, with collisions resolved using chaining.

Solutions

Expert Solution

Linear probing:

For 5, 5%7=5, so for 5, it is inserted in 6th row(for value 0, it is 1st row, for value 2 it is 2nd row and so on).

11%7=4, it is inserted in 5th row.

18%7=4, so for 4, it should be inserted in 5th row, but already value 11 is present in that slot, hence as per linear probing if there is a collision, the key value should be inserted into next free slot. Therefore value 18 is inserted in 7th row which is the next free slot.

23%7=2, it is inserted in 3rd row.

28%7=0, it is inserted in 1st row.

13%7=6, it should be inserted in 7th row. But there is a collision, hence the next available free slot is in 2nd row.

25%7=4, it should be inserted in 5th row. But there is a collision, hence the next available free slot is in 4th row.

Quadratic probing:

For 5, 5%7=5, so for 5, it is inserted in 6th row(for value 0, it is 1st row, for value 2 it is 2nd row and so on).

11%7=4, it is inserted in 5th row.

18%7=4, so for 4, it should be inserted in 5th row, but already value 11 is present in that slot. As per quadratic probing if there is a collision, then (key + 1*1)%7 hash function is used to find the next free slot.

Therefore ( 18+1)%7 =5, it should be inserted in 6th row. But already value 5 is present in that slot. Hence the next hash function used to compute the next slot is (key + 2*2)%7= (18+4)%7=1. Therefore 18 is inserted in 2nd row.

23%7=2, it is inserted in 3rd row.

28%7=0, it is inserted in first row.

13%7=6, it is inserted in 7th row.

25%7=4, it should be inserted in 5th row, but that slot is already occupied, hence (25+1*1)%7=5 , 6th row is the next slot to be inserted, but it also occupied. (25+2*2)%7= 1, 2nd row is occupied. (25+3*3)%7=34%7= 6, it is also occupied. (25+4*4)%7=41%7= 6, (25+5*5)%7= 1, it is occupied, (25+6*6)%7=61%7= 5, it is also occupied, (25+7*7)%7=74%7=4, it is occupied. (25+8*8)%7=89%7= 5, it is already occupied. (25+9*9)%7=106%7=1, it is already occupied. (25+10*10)%7=125%7=6, it is already occupied.

Hence it goes on and it can't find an empty slot for 25 in quadratic probing.

chaining:

Each slot is made to point to linked list of records that have same hash value in the chaining method.

18%7=4, 5th row is already occupied, hence a separate chain for the value 18 is made so that value 11 which is already occupied in that slot is made to point that new value 18.

When 25 also has to be inserted in 5th row, value 18 is made to point to this new value 25. Hence a

linked list of values that maps to same hash value is formed.

venereology answered 10 months ago

Next > < Previous

Related Solutions

SHOW WORK Draw the hash table that results using the hash function: h(k)=kmod7 to hash the...

SHOW WORK Draw the hash table that results using the hash function: h(k)=kmod7 to hash the keys 41, 16, 40, 47, 10, 55. Assuming collisions are handled by Double hashing. SHOW WORK

Which memory locations are assigned by the hashing function h(k) = k mod 97 to the...

Which memory locations are assigned by the hashing function h(k) = k mod 97 to the records of insurance company customers with these Social Security numbers? (a) 034-56-7981 (b) 220-19-5744 (c) 183-21-1232

Use double hashing and the following hash functions: hash(key) = (key % table size) and hash2(key)...

Use double hashing and the following hash functions: hash(key) = (key % table size) and hash2(key) = (16 - (key % 10)) + 1 to insert the following numbers into a dictionary's hash table: 1, 12, 14, 3, 5 and 17. The table size is 11. Show the table and where each value is inserted. No coding required for this problem.

Data Structures: Hashing Exercise: 1. a) Given an empty “separate chaining hash table” of size 10,...

Data Structures: Hashing Exercise: 1. a) Given an empty “separate chaining hash table” of size 10, with hash function Location = Number modulus 10 Show the hash table after inserting the following numbers: 21, 18, 27 , 31 , 48, 51 , 37, 98, 17 b) What table size would be better? 11? 12? 20? 2. We want to hash name strings into a chaining hash table of size 10, how would you divide the alphabet into 10 groups?...

How do I graph this step function? f(t) = -3(2t-3)H(t-2) + (2t-1)H(t-1) Please show step by...

How do I graph this step function? f(t) = -3(2t-3)H(t-2) + (2t-1)H(t-1) Please show step by step. How is it the same graph as f(t) = H(t-1)-3H(t-2)+H(t-1)*2(t-1)-H(t-2)*6(t-2)? Please show why as well.

In C++ Use vectors instead of linked lists Create a Hash table program using H(key) =...

In C++ Use vectors instead of linked lists Create a Hash table program using H(key) = key%tablesize with Chaining and Linear probing for a text file that has a list of 50 numbers Ask the user to enter the file name, what the table size is, and which of the two options they want to use between chaining and linear probing

(10 pts) Draw the result of hashing 11, 22, 3, and 43 into a table using...

(10 pts) Draw the result of hashing 11, 22, 3, and 43 into a table using the following hash function, using separate chaining: h(x) = x % 4 0 1 2 3 (10 pts) Draw the result of hashing 11, 22, 3, and 43 into a table using the following hash function, using open addressing with linear probing: h(x) = x % 4 0 1 2 3

7. Show that the dual space H' of a Hilbert space H is a Hilbert space...

7. Show that the dual space H' of a Hilbert space H is a Hilbert space with inner product (', ')1 defined by (f .. fV)1 = (z, v)= (v, z), where f.(x) = (x, z), etc.

Assume the health production function is h = 365 − 1/H, where h is the number...

Assume the health production function is h = 365 − 1/H, where h is the number of healthy days a person has in each year and H is the person’s health capital. Assume this person earns a wage of $100/day, and the marginal cost of health investment π = 25 and is constant over time. The annual interest rate is 5 percent, and health capital depreciates at a rate of 35 percent per annum. Find the optimal level of health...

Consider G = (Z12, +). Let H = {0, 3, 6, 9}. a. Show that H...

Consider G = (Z12, +). Let H = {0, 3, 6, 9}. a. Show that H is a subgroup of G. b. Find all the cosets of H in G and denote this set by G/H. [Note: If x ∈ G then H +12 [x]12 = {[h + x]12?? | [h]12 ∈ H} is the coset generated by x.] c. For H +12 [x]12, H +12 [y]12 ∈ G/H define (H+12[x]12)⊕(H+12[y]12) by(H+12 [x]12)⊕(H+12 [y]12)=H+12 [x+y]12. d. Show that ⊕ is...

Subjects