Is HashMap in Java collision safe

Question

I am developing a parser that needs to put key value pairs in hashmap.

But a key can have multiple values which i can do in this way

HashMap<String,ArrayList<String>> .

But what happens if number of keys are very large and it start matching with other key's hashcode.

Will that rewrite previous key's value ?

Solution 1

If the hash of the key in the map collides with an existing key, the Map will re-arrange or keep the keys in a list under that hash. No keys will get overwritten by other keys that happen so be sorted in the same bucket.

If multiple threads are using the map concurrently, you might want to synchronize access to the map if it does not handle concurrent access. (Some standard Maps do, other don't. The Java Collections package does contain wrapper classes that add synchronisation.)

Solution 2

Firstly, take a look at Google Collections Multimap which would let you assign multiple values per key without having to manually maintain list of values.

Secondly, no - keys that have the same hashcode will not collide. Hash codes are not guaranteed or required to be unique; HashMap maintains a "bucket" of key/value pairs for each hash code internally.

Solution 3

HashMap is collision-safe: look at the sourcecode for put:

     /**
      * Associates the specified value with the specified key in this map.
      * If the map previously contained a mapping for the key, the old
      * value is replaced.
      *
      * @param key key with which the specified value is to be associated
      * @param value value to be associated with the specified key
      * @return the previous value associated with <tt>key</tt>, or
      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
      *         (A <tt>null</tt> return can also indicate that 
      *         previously associated <tt>null</tt> with <tt>key</tt>.)
      */
     public V put(K key, V value) {
         if (key == null)
             return putForNullKey(value);
         int hash = hash(key.hashCode());
         int i = indexFor(hash, table.length);
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }

         modCount++;
         addEntry(hash, key, value, i);
         return null;
     }

and

     /**
      * Adds a new entry with the specified key, value and hash code to
      * the specified bucket.  It is the responsibility of this
      * method to resize the table if appropriate.
      *
      * Subclass overrides this to alter the behavior of put method.
      */
     void addEntry(int hash, K key, V value, int bucketIndex) {
         Entry<K,V> e = table[bucketIndex];
         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
         if (size++ >= threshold)
             resize(2 * table.length);
     }

The entries of the table act like a linked list. When you put a new entry into the same bucket, it just adds to the linked list.

Solution 4

It will only overwrite the previous key's value if it is equal to the previous key. There are methods like linear probing, rehashing, buckets, etc., which are used in hash implementations to prevent hashcode collisions from overwriting unequal keys.

Solution 5

I would contribute that a collision is not the same as inserting an identical key. Collisions occur when separate keys hash to the same value. It is understood that anyone who implements the Map interface should be equipped to handle collisions. Thus, the answer to your question is that yes, HashMap in Java does safely handle collisions.

However, if an identical key is inserted, then the previous Value associated with that exact same key will be updated/overwritten. This is not considered a collision per se, but a direct clobbering of what is already there.

View more solutions