Asked  6 Months ago    Answers:  5   Viewed   39 times

Is it bad practice to use mutable objects as Hashmap keys? What happens when you try to retrieve a value from a Hashmap using a key that has been modified enough to change its hashcode?

For example, given

class Key
{
    int a; //mutable field
    int b; //mutable field

    public int hashcode()
        return foo(a, b);
    // setters setA and setB omitted for brevity
}

with code

HashMap<Key, Value> map = new HashMap<Key, Value>();

Key key1 = new Key(0, 0);
map.put(key1, value1); // value1 is an instance of Value

key1.setA(5);
key1.setB(10);

What happens if we now call map.get(key1)? Is this safe or advisable? Or is the behavior dependent on the language?

 Answers

11

It has been noted by many well respected developers such as Brian Goetz and Josh Bloch that :

If an object’s hashCode() value can change based on its state, then we must be careful when using such objects as keys in hash-based collections to ensure that we don’t allow their state to change when they are being used as hash keys. All hash-based collections assume that an object’s hash value does not change while it is in use as a key in the collection. If a key’s hash code were to change while it was in a collection, some unpredictable and confusing consequences could follow. This is usually not a problem in practice — it is not common practice to use a mutable object like a List as a key in a HashMap.

Tuesday, June 1, 2021
 
Smandoli
answered 6 Months ago
64

HashMap does not call hashcode when null is passed as key and null Key is handled as special case.

Put Method

HashMap puts null key in bucket 0 and maps null as key to passed value. HashMap does it by linked list data structure. HashMap uses linked list data structure internally.

Linked list data structure used by HashMap (a static class in HashMap.java)

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
}

In Entry class the K is set to null and value mapped to value passed in put method.

Get Method

While in Hashmap get method the checks if key is passed as null. Search Value for null key in bucket 0.

Hence there can only be one null key in one hashmap object.

Monday, August 2, 2021
 
insomiac
answered 4 Months ago
44

In particular, is there a difference between the hashing algorithm they use? What is the formula used to hash in these two classes?

The primary hash function used when you use an object as a hash table key is the object's hashCode() method. It is up the to the key class to implement a decent hash function.

The Hashtable and HashMap classes take the key's hashcode value and convert it to an index in the primary hashtable array-of-chains. However, there are differences in how this happens between Hashtable and HashMap.

  • For Hashtable (Java 8) the code is this:

     hash = key.hashCode();
     index = (hash & 0x7FFFFFFF) % tab.length;
    
  • For HashMap (Java 8) the code is (effectively) this:

     // (I have restructured the code for ease of comparison.)
     int h;
     hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     index = (tab.length - 1) & hash;
    

As you can see, HashMap is scrambling the hashcode value returned by the key's hashcode function. This is explained in the source code as follows:

[This method] computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

Notes:

  1. The & versus % difference is because in Hashtable the hash array size is a prime number, but in HashMap (Java 8) the size is a power of 2.

  2. In Java 8 HashMap, the implementation will turn a long hash chain into a binary tree if the key class implements Comparable.

  3. HashMap handles null keys, but Hashtable doesn't.


However, all of this extra complexity in HashMap only comes into play if your key class has a poorly designed / implemented hashCode() method ... or if someone is deliberately trying to engineer hash collisions.

In other words, if your key class is well designed, the differences should not matter.

Monday, October 4, 2021
 
AWeim
answered 2 Months ago
44

The statement

hm(42) += 1234

will create the default value (an empty HashSet), then update it by adding 1234 to it, then throw it away.


If you want to update the HashMap itself, then remove the withDefault part from the definition, and use getOrElseUpdate instead:

hm.getOrElseUpdate(42, HashSet.empty[Int]) += 1234

Alternatively, you can leave the withDefault as-is, but update your hash map as follows:

hm(42) = (hm(42) += 1234)
Wednesday, October 27, 2021
 
Owen
answered 1 Month ago
97
  1. HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.

  2. LinkedHashMap will iterate in the order in which the entries were put into the map

Source

Saturday, November 20, 2021
 
David Hodgson
answered 1 Week ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share