Problem 2: In class we saw that resolving collisions by chaining would result in

Question

Problem 2: In class we saw that resolving collisions by chaining would result in a constant-time insertion e can consider an alternative way to store elements on a hash table which we call jumping around. In this system there are no collisions, because when we insert/delete/search an element we "jump around" the procedure, but potentially long deletion and search queries. table looking for it. it is not free we check h(a, 1) and so on. So is stored in location h(a, i) where i is the first counter Search: Similarly to search for a we compute h(r, i) in order until either we find a or we find an empty 1. Argue that Insertion and Search run in expected constant time if you assume simple uniform hashing More specifically: we define a hash function that takes as input an element r and a counter i Insertion: When we insert into the hash table we compute h(r0) and check if that slot is free. which yields a free slot. slot (which tells us that a is not in the table). 2. How you would implement deletion in this table? What can go wrong if you delete element z from the table and restore the slot as a "free" one in the table? What else can you do?

Explanation / Answer

You should be having some background about chaining technique before we actually move on to jumping around. Let me give a quick overview of it. Whenever a new element has to be inserted, deleted or searched from the hashtable, it computes the hash and goes to that particular bucket but if multiple items give the same hash, this results in collision. One of the ways to resolve it is to use chaining method. Where, once an item's bucket is found, it is appended to the chain within that bucket. Bigger the chain of a bucket, worst will be performance. Since it will eventually become like a list and search will be sequential within that.

Now coming to jumping around technique, the text says that once a hash is computed, and the bucket with that value is located, the item will be inserted in the bucket if it is empty. If the bucket is already occupied, it will move on to next bucket (even though the next bucket's hash value is different). Similarly, it will move on till it finds an empty bucket.

1. Now, given that it is uniform hashing, which means the hashtable buckets and the hash function will be in such a way that (most of the times) each element will be getting a unique value when needed to perform any hash table operation. Hence insertion and searching will take constant time.

2. However, deletion would be little challenging with this method. Reason being the jumping over logic. According to the logic, all hash operations will sequentially be going to next buckets until it finds an empty bucket. Especially search, if it finds an empty bucket, it means that the item is not in the hashtable.

Solution to this is straightforward, whenever an item is deleted, all the items below that should travel one bucket level up. This will prevent empty buckets.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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