Exercise 4 - Collision resolution • Given a hash table with m=11 entries and the following hash function h, and step function h₂: ● . h₁(key) = key mod m h₂(key)= (key mod (m-1)} + 1 Implement the necessary functions to insert the keys {22, 1, 13, 11, 24, 33, 18, 42, 31} in the given order (from left to right) into the hash table using each of the following hash methods: Linear-Probing with h(k,i) = (h₁(k)+i) mod m Double-Hashing with h, as the hash function and h₂ as the step function h(k,i) = (h₁(k)+ ih₂(k)) mod m Chaining with h(k)= h,(k) 0 Linear Double Chaining Probing Hashing 22 22 1 1 2 13 3 11 4 24 5 33 6 7 8 9 42 10 31 18 1 13 11 18 31 24 33 42 33 11 → 22 1 2413 18 3142

Exercise 4 - Collision resolution • Given a hash table with m=11 entries and the following hash function h, and step function h₂: ● . h₁(key) = key mod m h₂(key)= (key mod (m-1)} + 1 Implement the necessary functions to insert the keys {22, 1, 13, 11, 24, 33, 18, 42, 31} in the given order (from left to right) into the hash table using each of the following hash methods: Linear-Probing with h(k,i) = (h₁(k)+i) mod m Double-Hashing with h, as the hash function and h₂ as the step function h(k,i) = (h₁(k)+ ih₂(k)) mod m Chaining with h(k)= h,(k) 0 Linear Double Chaining Probing Hashing 22 22 1 1 2 13 3 11 4 24 5 33 6 7 8 9 42 10 31 18 1 13 11 18 31 24 33 42 33 11 → 22 1 2413 18 3142

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

A hash map of size 15 has been constructed with Double-Hashing by applying h; (k;) = [ h(k;)+jd(k;)] mod 15. The primary hashing function is h(k;) = k; mod 15. The secondary hashing function is d;(k;) = k; mod 7. In one sentence, describe why the secondary hashing function is poorly chosen.
Explain how a hash table with linear probing collision handling works internally. Illustrate by showing a hash table containing the numbers 3, 11, 16, 22, with 7 hash buckets. (Assume that we just use the numbers themselves as hash values, i.e., our hash function for integers is hashCode(x) = x.)
Assume that linear probing is used for hash-tables. To improve the time complexity of the operations performed on the table, a special AVAILABLE object is used to mark a location when an item is removed from the location. Assuming that all keys are positive integers, the following two techniques were suggested instead of marking the location as AVAILABLE: i) When an entry is removed, instead of marking its location in the table as AVAILABLE, indicate the key in the location as the negative value of the removed key (e.g., if the removed key was 16, indicate the key as -16). Searching for an entry with the removed key would then terminate once a negative value of the key is found (instead of continuing to search if AVAILABLE is used). ii) Instead of using AVAILABLE, find a key in the table that should have been placed in the location of the removed entry, then place that key (the entire entry of course) in that location (instead of setting the location as AVAILABLE). The motive is to…
Implement a commonly used hash table in a program that handles collision using linear probing. Using (K mod 13) as the hash function, store the following elements in the table: {1, 5, 21, 26, 39, 14, 15, 16, 17, 18, 19, 20, 111, 145, 146}.
Insert the following sequence of keys in the hash table.Keys = {4, 2, 1, 3, 5, 6, 8}Use linear probing technique for collision resolution: h(k, i) = [h(k) + i] mod mHash function, h(k) = 3k + 1Table size, M = 10 Draw the hash table, compute the index where the hashvalue will be inserted for each key, and show how you would use the technique when a collisionoccurs.
Suppose you have a hash table with seven entries (indexed 0 through 6). This table uses open addressing with the hash function that maps each letter to its alphabet code (a = A = 0, etc.) modulo 7. Rehashing is accomplished using linear-probing with a jump of 1. Describe the state of the table after each of the letters D, a, d, H, a, and h are added to the table.
What is the worst-case performance of a lookup operation in a hashmap and why? Group of answer choices A- O(1), hashmap always has a constant time lookup, and that is why we like using this associative data structure. B- O(lg(n)) hashmap has a log(n) lookup because we are able to perform a binary search on the keys because our hashmap always maintains a sorted order of entries added. C- O(n) because we can have a bad hash function that puts all of our items in the same bucket, thus we would have to iterate through all n items.
Given the following Java functions, transcribe it into a Python 3 program. /*** Removes the mapping for this key from this hash table if present.*/public Object remove(Object key) {Entry e = removeEntryForKey(key);return (e == null ? e : e.value);}
1) Suppose hashing is being done by using open addressing with linear probing. The hash function tobe used for an element with key k is h(k) = k mod 11. Show the contents of the hash table afterinserting the following keys in order into the hash table:27 40 22 15 31 18 36 19 20
A linear probing hash table of length 10 uses the hash function h(x) = x mod 10 + 1. mod is the reminder operator. For example the h(42) = 42 mod 10 + 1 = 2 + 1 = 3 so we insert 42 in the position 3 in the array. After inserting 6 integer keys into an initially empty hash table, the array of keys is…
Given a hash table of size M=10 and a linear probing method, following are the contents of the hash table: [-1, 41, 71, -1, 64, 75, 84, -1, 88, 9]. -1 indicates slot is empty. Use the standard hash function: h(x)=x%M Match the index on the left with the value on the right for the hash table after the following operations are carried out in the given order: delete(88) delete(41) delete(44) insert(108) insert(71)