Why does a hash table degenerate into a Linked List when the hashcode () implementation returns a constant value?

Question

// The worst possible legal hash function - never use! @Override public int hashCode() { return 42; } 

Its validity, as it guarantees that equal objects have the same hash code. Its atrocious because it guarantees that every object has the same hash code. Therefore, each hash of objects in the same bucket, and hash tables degenerate into linked lists. Programs that must be run in linear mode are executed in quadratic time.

I am trying to understand the above (quote from page 47, paragraph 9, Joshua Bloch Effective Java).

As I see it, it looks like this (consider the following code):

 Map<String, String> h = new HashMap<String,String>(); h.put("key1", "value1"); h.put("key1", "value2"); 

What happens to the second h.put("key1",...) command h.put("key1",...) : 1. Get the hash code of key1 2. Go to the bucket representing the above hash code 3. Inside this bucket for each object, call the equals method to find whether an identical object exists.

It is rather faster, because first you discover a "group" (bucket) of objects, and then the actual object.

Now that the hashcode implementation is such that it returns the same integer (for example, 42 above) for ALL objects, then there is only one bucket, and the equals method should be called one after the other on each object as a whole hashmap / hashtable. This is as bad as a linked list, because if the objects that are in the linked list, you also need to go through them one by one, comparing (calling equal) each object.

That's why it has been said that hash tables degenerate into a linked list?

(I apologize for the verbosity of the above text. I am not clear enough in my concepts to say this more briefly)

Answer 1

HashTable is an array with a display function (hashCode). When pasting into an array, you calculate the position and insert the element there.

BUT, hashCode does not guarantee that each element will have a different position, so some objects may collide (have the same address), and hashTable should solve it. How to do this, there are two general approaches.

Single chain

In a separate chain (used in Java), each array index contains a linked list, so each bucket (position) has infinite capacity. Therefore, if your hashCode returns only one value, you only use one list => hashTable - this is a linked list.

Linear research

The second approach is linear sensing. In linear sensing, an internal array is really a normal array of elements. When you find out that the position is already taken, you iterate over the array and put the new element in the first empty position.

So, I use hashCode for expression for each element, you only generate collisions, so you try to put all elements in the same index and because it is always busy, you iterate over all the squared elements and place a new element at the end of this structure . If you read what you are doing again, you should see that you are using only another (you can say implicitly) implementation of the linked list.

Why not do it

You really shouldn't return constant values, because hashtables are built to provide O(1) expected complexity of the search and insert operations (due to a hash function that returns a different address for (almost) every other object). If you return only one value, the implementation will change the linked list with O(n) for both operations.

Answer 2

Yes, your understanding seems accurate. However, this is not like a linked list. The actual internal implementation of records with a common bucket is a simple old linked list. The bucket contains Map.Entry at the top of the list, and each entry has a pointer forward to the next occupant of its bucket. (For implementing a HashMap built into Java, of course.)

Answer 3

Hash tables - when used correctly - offer constant time searches on average. In terms of time complexity, constant time is as good as it gets.

Linked lists offer linear time search. Linear time (that is, looking at each element in turn) is just as bad as it gets.

When a hash table is misused by the method described by Bloch, its search behavior degenerates into the behavior of a linked list, simply because it effectively becomes a linked list.

Similar things can be said about other operations.