Chaining in HashMap

Question

Code:

public static void main(String[] args) {
    Map<String,String> map= new HashMap<String,String>();
    map.put("a", "s");
    map.put("a", "v");

    System.out.println(map.get("a"));

}

Now, as per my understanding, since the key values in both the put case is the same i.e. a, collision is bound to happen, and hence chaining occurs. [Correct me if I am wrong].

Now if I want to retrieve the list of all the values mapped to key value a, how do i get it?

Right now my println prints v only.

Answer 1

This has nothing to do with collision or chaining: you're replacing the old value of a with a new value.

A map keeps unique keys. collision/chaining will occur in a hash data structure when two distinct keys happen to get the same hash value based on the particular hash function. Or in java, you can explicitly create an object that returns the same value for hashCode().

If you want mapping with multiple values for a key, then you'll need to use a different data structure/class.

Answer 2

Like other people already suggested, there is no such thing as Collision for your case.

It's simply because Hashmap only accepts an unique key.

However you can have an alternative if you want the key to be not unique, for example Google Guava Multimap or Apache Multimap

Example using Google lib:

public class MutliMapTest {
public static void main(String... args) {
Multimap<String, String> myMultimap = ArrayListMultimap.create();

// Adding some key/value
myMultimap.put("Fruits", "Bannana");
myMultimap.put("Fruits", "Apple");
myMultimap.put("Fruits", "Pear");
myMultimap.put("Vegetables", "Carrot");

// Getting the size
int size = myMultimap.size();
System.out.println(size);  // 4

// Getting values
Collection<string> fruits = myMultimap.get("Fruits");
System.out.println(fruits); // [Bannana, Apple, Pear]

Collection<string> vegetables = myMultimap.get("Vegetables");
System.out.println(vegetables); // [Carrot]

// Iterating over entire Mutlimap
for(String value : myMultimap.values()) {
 System.out.println(value);
}

// Removing a single value
myMultimap.remove("Fruits","Pear");
System.out.println(myMultimap.get("Fruits")); // [Bannana, Pear]

// Remove all values for a key
myMultimap.removeAll("Fruits");
System.out.println(myMultimap.get("Fruits")); // [] (Empty Collection!)
}
}

Answer 3

See the java doc for put

Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)

The collision happens when two different keys comes up with the same hashcode and not when two same keys.

class StringKey {
String text;

public StringKey() {
    text = "";
}

public StringKey(String text) {
    this.text = text;
}

public String getText() {
    return text;
}

public void setText(String text) {
    this.text = text;
}

@Override
public int hashCode() {
    if (text != null) {
        text.substring(0, 1).hashCode();
    }
    return 0;
}

@Override
public boolean equals(Object o) {
    if (o instanceof StringKey) {
        return ((StringKey) o).getText().equals(this.getText());
    }
    return false;
}

public static void main(String[] args) {
    Map<StringKey, String> map = new HashMap<StringKey, String>();
    StringKey key1 = new StringKey("a");
    StringKey key2 = new StringKey("b");

    map.put(key1, "s");
    map.put(key2, "v");

    System.out.println(map.get(key1));
    System.out.println(key1.hashCode() + " " + key2.hashCode() + " " + key1.equals(key2));
}
}

The output is

s
0 0 false

now this will cause a collision; but you can not interpret this from the output of map keys and values.

Answer 4

The second put() simply overwrites what the first put() wrote. There is no chaining.

Answer 5

Second put replaces first put, so you will have only one value with key "a" in Hashmap.

So your map just contains

map.put("a", "v");

Answer 6

Now,as per my understanding, since the key values in both the put case is the same i.e. a, collision is bound to happen, and hence chaining occurs. [Correct me if i am wrong].

You're wrong. Thats not how a Map works. Consider using a MultiMap from Google's Guava library.

You can always roll your own:

Map<String, ArrayList<String>>();

Answer 7

You will have to make your HashMap as follows

public static void main(String[] args) {
    HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
    if ( map.get("a") == null ){
        map.put("a", new ArrayList<String>());
    }

    ArrayList<String> innerList = map.get("a");
    innerList.add("s");
    innerList.add("v");

    map.put("a",innerList);

    System.out.println(map.get("a"));
}

Answer 8

Hashing algorithm used in HashMaps are pretty vague in the first go. Internally a HashMap is nothing but an array with indices. The index here is usually referred to as 'hashValue'. As the hashValue is the index of an element in the array, it has to be less than the size of the HashMap itself.The HashMap's hashing algorithm converts the key's hashcode into the hashValue. This is where the Map stores the Entry (key-value pair).

When an element is put into a Map, it generates the hashValue from the element key's hashcode, and stores the Entry into the array at this index, which is nothing but the hashValue. Now, hashing algorithm can be efficient to a certain extent only, that is we can never assure that the hashValue generated for two different keys are always different. It could be same under two conditions: 1) The keys are same (as in your case) 2) The Keys are different, but the hashValue generated for both the keys are same.

We simply cannot replace the value of the Entry at the hashValue position in the array, as this will violate the second condition, which is very valid. This is where the equals() comes into picture. Now, the HashMap checks for the equality between the new key and the key that exists in that index's Entry. If both the keys are same it means replacement, else it's collision and the HashMap uses the appropriate collision technique.

Now, if you want the list of all the values that you put for a particular key, consider using a composite map HashMap<String, List<String>>.

Answer 9

Both the keys you tried to put in the HashMap has the same HashCode. Thus the first value gets overwritten an you will end up having only one value in the HashMap.

You can put Two similar objects in the same HashMap by overriding thier hashCode() Method.

Answer 10

Further notes on when Chaining actually takes place when a HashMap is used:

The Java implementation for HashMap will either override a key or chain an object to it depending on the following:

1. You put an object foo as key, with hash code X into the map
2. You put another object bar (as key..) that has the same hash code X into the map

3. Since the hashes are the same, the algorithm would need to put the object bar on the same index where foo is already stored. It would then consult the equals method of foo, to determine whether it should chain bar to foo (i.e foo.next() will become bar) or override foo with bar:

   3.1.If equals returns true, foo & bar are either the same object, or they are semantically the same, and overriding will take place rather than chaining.

   3.2. If equals returns false, foo & bar are treated as two distinct entities and chaining will take place. If you then print your HashMap, you'll be seeing both foo and bar.