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? Hash our class first names into your new Hash table.

3. Given an empty “Open addressing with linear probing hash table”, Show the hash table after inserting the following numbers: 27, 36, 45, 14, 56, 22. What is a good table size?

4. If the expected data size is about 2000, what is a good size for the hash table?

5. Try both linear and quadratic probing in a table of size 10, use the numbers 11, 21, 71, 14, 51

Solutions

Expert Solution

b) If the table size will be 11 then it would be better. Because the total number of elements is only 9.

venereology answered 11 months ago

Next > < Previous

Related Solutions

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.

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.

Implement a Cuckoo hash table in which two separate tables are maintained. Each table should have...

Implement a Cuckoo hash table in which two separate tables are maintained. Each table should have a fixed size of 13. Use the hash function h1(x) = x mod 13 for the first table, and h2(x)= 11 – (x mod 11) for the second table. Your program should read an input file, input.txt, consisting of one input per line, insert the input to the table in order, and print out the final content of the hash table in the provided...

1.) Consider inserting values 15, 22 and 29 in the order given into a hash table...

1.) Consider inserting values 15, 22 and 29 in the order given into a hash table of size 7 with hash function h(x) = x mod 7. What will be the locations be the respective locations for 15, 22 and 29 in the hash table if quadratic probing is used to resolve colisions? a. 1, 2, 4 b. 1, 2, 3 c. 1, 2, 0 d. 1, 1, 1 2.) Consider the following sequences of addqs and removeqs, what order...

(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

C++ only please Description A hash table is a data structure that is used to store...

C++ only please Description A hash table is a data structure that is used to store keys/value pairs. It is perfect to use when you have a large amount of directory-type information and the operations you need to perform are to insert, delete, print, and search. I am giving you all a lot more freedom in this program in that the value held in your hash table can be a pointer to any object created from your own custom class....

Consider inserting values 15, 22 and 29 in the order given intoa hash table of...

Consider inserting values 15, 22 and 29 in the order given into a hash table of size 7 with hash function h(x) = x mod 7. What will be the locations be the respective locations for 15, 22 and 29 in the hash table if quadratic probing is used to resolve colisions?a.1, 2, 4b.1, 2, 3c.1, 2, 0d.1, 1, 1

Consider a hash table T with m=10 slots that uses open addressing with linear probing and...

Consider a hash table T with m=10 slots that uses open addressing with linear probing and the hash function h(k,i) = ((k mod m) + i) mod m, where i = 0,1,..., m-1 is the probe number. Show T after inserting keys <867,755,535,296,866,135,669,445,524>.

(Using Matlab)We are given data about a charity organization in table 1 Days 10 20 30...

(Using Matlab)We are given data about a charity organization in table 1 Days 10 20 30 40 50 60 70 80 90 100 Donation 23 45 60 82 111 140 167 198 200 220 Table 1: Donation collection by the charity organization Assume that x corresponds to the independent variable. Compute linear, quadratic and cubic fit for the data using regression techniques and plot them on three different graphs, all on the same figure. Use an appropriate small interval to...

Exercise 1. Defense and wins. The data in the table below shows the wining percentage and...

Exercise 1. Defense and wins. The data in the table below shows the wining percentage and the yards per game allowed in the 2014-15 season for a random sampling of teams. At α = 0.05, can you support the claim that there is a correlation between the winning percentage and the yards allowed? Team Winning percentage Total yards Baltimore Ravens 0.625 336.9 Cleveland Browns 0.438 366.1 Denver Broncos 0.750 305.2 Jacksonville Jaguars 0.188 370.8 New England Patriots 0.750 344.1 Oakland...

Subjects