CODEWITHSUNDEEP
javaarrayshashtablesuperclass
Patrick
Patrick

Reputation: 637

Arrays of Hash Table storing two types of references

My question is about the bucket array of Hash Table(called A,for example). Since sometimes there will be collision in a hash map, it's common to use the simple chaining solution. That is to say, making each bucket pointing to a linked-list containing entries, and if collision happens, just adding the new entry with same key to the this list.

But according to the data structure book, when a bucket A[i] is empty, it stores null, and if A[i] stores just a single entry (key, value), we can simply have A[i] point directly to the entry (key, value) rather than to a list-based map holding only the one entry. Therefore I think the hash table will be holding two different kinds of objects(Entry Objects and List Objects).

I have had trouble implementing this method.I choose to declare a new abstract class(Called "super" for example) which is inherited by both List class and Entry class.And there is nothing in this new class. As a result, the hash table now hold only one type Object "super" which can point to both types of objects I need. However, I have to use "instanceof" to know what exactly the bucket A[i] is pointing to so as to do operations like adding a new entry. I've heard that using instanceof too much is not appropriate. And there will be many places requiring a "cast". So should I copy the code in the class Entry and List into the "super" class so as to not using so many "cast"s ?

Upvotes: 1

Views: 254

Answers (1)

Eran
Eran

Reputation: 394156

There is nothing wrong in storing a single entry as a linked list having just a single link. After all, the difference between an entry (that contains just the key and the value) and a link of a linked list that contains an entry (the contains the key, the value and a reference to the next link) is a single reference to the next link. That's what the JDK implementation of HashMap does for buckets having a small number of entries.

This way you don't have to worry about storing different types of objects in your table.

On the other hand, the implementation of HashMap in Java 8 uses two entry implementations to store the entries of a bucket - a Node (linked list) and a TreeNode (a node of a tree). If you look at the implementation, you'll see they use e instanceof TreeNode to check the specific type of a given node. So as you can see, even the JDK use "instanceof" to know what exactly the bucket A[i] is pointing to.

Upvotes: 1

Related Questions