Data Structures with C++ Using STL”, William Ford and William Topp, 2002, Prenti

Question

Data Structures with C++ Using STL”, William Ford and William Topp, 2002, Prentice Hall, 0-13-085850-1

CH12
Question 15. page 718
Use the hash function hf(x)=x, m=11 to map an integer value to a hash table index. insert the data 1,13,12,53,77,29,31,22 into the has table.
a. construct the hash table by using linear probe addressing
b. construct the hash table by using chaining with separate lists.
c. for both techniques, determine the load factor, the average number of probes needed to locate
a value in the table, and the average number of probes needed to determine that a value is not in the table. For linears
probe addressing, when counting the number of probes needed to locate a value that is not in the table, count the discovery
of an empty slot as a probe. for chaining with separate lists, record an encounter with the end of a list as a probe.

Explanation / Answer

Example Let the hash table be an 11-element array. If k is the key of a data record, let H(k) represent the hash function, where H(k) = k mod 11. Insert the keys 83, 14, 29, 70, 10, 55, 72:

0 1 2 3 4 5 6 7 8 9 10

Goals of Hashing An insert without a collision takes O(1) time. A search also takes O(1) time, if the record is stored in its proper location (without a collision). The hash function can take many forms: - If the key k is an integer: k % tablesize - If key k is a String (or any Object): k.hashCode() % tablesize - Any function that maps k to a table position! The table size should be a prime number.

Linear Probing During insert of key k to position p: If position p contains a different key, then examine positions p+1, p+2, etc.* until an empty position is found and insert k there. During a search for key k at position p: If position p contains a different key, then examine positions p+1, p+2, etc.* until either the key is found or an unused position is encountered. *wrap around to beginning of array if p+i > tablesize

Linear Probing Example Example: Insert additional keys 72, 36, 65, 48 using H(k) = k mod 11 and linear probing. 0 1 2 3 4 5 6 7 8 9 10

Special consideration If we remove a key from the hash table, can we get into problems?

0 1 2 3 4 5 6 7 8 9 10

Remove 83. Now search for 48. We can’t find 48 due to the gap in position 6! How can we solve this problem? .

Efficiency using Linear Probing Insert & Search for a hash table with n elements: Expected (Average) Time: O(____) Worst Case time O(____)

Chained Hashing The maximum number of elements that can be stored in a hash table implemented using an array is the table size. We can store more elements than the table size by using chained hashing. Each array position in the hash table is a head reference to a linked list of keys (a "bucket"). All colliding keys that hash to an array position are inserted to that bucket. HashMap and HashSet use chained hashing.

Chaining

0 1 2 3 4 5 6 7 8 9 10

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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