Is HashMap in Java collision safe

Question

Hi

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 ?

thanks

-devSunday

Answer 1

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.

Answer 2

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.)

Answer 3

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.

Answer 4

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.

Answer 5

I have a small question...I have been searching since past couple of days.I want a alternative to the nested declaration of the following type in java

ArrayList>> attributeValuesArrayList = new ArrayList>>();

Is there something that is simpler and has the same usability. I am a newbee to JAVA.

Thanks in advance.