Hashmap and how this works behind the scene [duplicate]

Question

quick question to be sure I understood well how HashMap in java works.

Here is an example of code:

//String key = new String("key");
//String val = new String("value");
String key = "key";
String val = "value";

HashMap map = new HashMap();
map.put(key, val);

System.out.println("hashmap object created. Its key hashcode = "+key.hashCode());
// the hashcode is 106079
System.out.println("hashmap object value for key = "+map.get(key));

// Let's store using a key with same hashcode
Integer intkey = new Integer(106079);
val = "value2";
map.put(intkey, val);
System.out.println("hashmap object created. Its intkey hashcode = "+intkey.hashCode());
// this returns 106079 once again. So both key and intkey have the same hashcode

// Let's get the values
System.out.println("hashmap object value for intkey = "+map.get(intkey));
System.out.println("hashmap object value for key = "+map.get(key));

the returned values are as expected. I read that behind the scene, HashMap works as follows:

1. get the key/value.
2. make a hashcode from the key.
3. store in bucket the key and value objects (in my case bucket number 106079)

same again for the second one.

4. stores it within the same bucket but as this is at this point a LinkedList, I suppose store it at "next available allocation".

To get it:

1. pick up the key, get hashcode,
2. look at the bucket,
3. then look at the key from the first element in the LinkedList,
4. then check if key passed and key from element match, if not then continue to the next, and so on until value can be retrieved.

Am I understanding this concept correctly?

Many thanks!

EDIT:

many thanks, so to complete: - How does Java HashMap store entries internally - How does a Java HashMap handle different objects with the same hash code?

And:

• There shouldn't be that many "buckets"
• A bucket is not the same as an entry. A bucket is a logical collection of all entries sharing the same bucket# (which in the Java case is a function of the key's hashCode()). As stated in other answers, bucket overflow could be implemented several ways, not necessarily in a List.
• There are other existing collision resolutions: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution
• it uses Object's equals method to compare and retrieve objects from the same bucket.

Answer 1

Please also note, there are several ways HashMap can implement hash codes collision resolution, not only utilizing linked list as you mentioned

Java's HashMap implementation does not only use LinkedList strategy to handle key-values with same key.hashCode() values.

Also, you may want to read this article

Answer 2

Yes, your understanding is correct. Just note that a single bucket is assigned many hashcodes: in a fresh HashMap there are altogether 16 buckets, each assigned a total of 2³²/16 = 2²⁸ hashcodes.