1

  1. Reading Algorithms book, need to grasp the concept of a hashtable. They write about hashing with separate chaining and hashing with linear probing. I guess Java's HashMap is a hashtable, therefore I'm wondering what mechanism does HashMap use (chaining or probing)?

  2. I need to implement simplest HashMap with get, put, remove. Could you point me at the good material to read that?

  3. When the unique keys used for the Map are custom objects, we need to implement hashCode() function inside the corresponding type. Did I get it right or when is hashCode() needed?

Unfortunately the book does not answer all questions, even though I understand that for many of you these questions are low level.

Improve this question
3
  • Technically, Java has a built in hashCode() method, but for most purposes, your assesment in #3 is correct. Commented May 20, 2014 at 13:55
  • Incidently; are you aware that Netbeans has the source code for HashMap available within it (as opposed to compiled byte code) so you can just go poking around within it (probably available on the internet as well but its much nicer to navigate code within an IDE) Commented May 20, 2014 at 13:58
  • Yes I can access java.util.HashMap code but I need a toy example like a Stack or Deque explained for 15 years old. Commented May 20, 2014 at 14:01

3 Answers 3

Reset to default
1

1: before java 1.8 HashMap uses separate chaining with linked lists to resolve collisions. There is a linked list for every bucket.

2: hmmmmmm maybe this one?

3: yes, you are right, hashCode() is used to calculate the hash of the Key. Then the hash code will be transformed to a number between 0 and number of buckets - 1.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Linked lists are only used for a small number of collisions. If the number of collisions is too big (and the keys are comparable) then a red-black tree is used.
Note that in Java 1.8 linked lists are no longer used to resolve collisions. A balanced tree is used instead, see: openjdk.java.net/jeps/180
@PhilippeMarschall that is only true in Java 1.8.
3. to be precise: between 0 and number of buckets - 1 :)
1

This is a Most Confusing Question for many of us in Interviews.But its not that complex.


We know

  • HashMap stores key-value pair in Map.Entry (we all know)

  • HashMap works on hashing algorithm and uses hashCode() and equals() method in put() and get() methods. (even we know this)

  • When we call put method by passing key-value pair, HashMap uses Key **hashCode()** with hashing to **find out the index** to store the key-value pair. (this is important)

  • The Entry is **stored in the LinkedList**, so if there are already existing entry, it uses **equals() method to check if the passed key already exists** (even this is important)

  • if yes it overwrites the value else it creates a new entry and store this key-value Entry.

  • When we call get method by passing Key, again it uses the hashCode() to find the index in the array and then use equals() method to find the correct Entry and return it’s value. (now this is obvious)

THIS IMAGE WILL HELP YOU UNDERSTAND:

enter image description here

Improve this answer

Comments

0

HashMap works on the principle of Hashing. Its working is two fold.

First, it maintains a Linked List to store objects of similar values, that means ones which are "equal".

Second it has a collection of these linked list whose headers are present in a array.

For more information refer blog Java Collection Internal Working

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.