How to maintain uniqueness of key in hashmap internally

Question

Everyone know hashmap contain unique key. But i want know how it maintain uniqueness?

Suppose we inserted 100 data into the hashmap, After that we insert duplicate key and value in the same hashmap. I know it will override the value. But i want to know it will check all the previous keys which is already stored inside the hashmap then will override new key.

Or if it check previous all keys everytime then it will take more time . So please tell me the correct answer.

Google "how do hashmaps work internally", e.g. how bucketing works. — luk2302, Aug 10 '21 at 15:07
It doesn't check all the keys. It calculates the new key's hash code, and then checks (at worst) all the keys for equality in the bucket to which that hash code would be mapped. — Andy Turner, Aug 10 '21 at 15:08
I know it calculate new hashcode then store but if we try insert same key which already stored then it checks all previous keys — Jatin Bansal, Aug 10 '21 at 15:21

score 1 · Answer 1 · answered Aug 10 '21 at 15:30

You need to know the internal representation of the HashMap.

Actually it is an array of list of key value items, graphically we can represent it as you can see below:

  bucket 
  position
  --------
  0         NULL
  1         --> (K1, V1) --> (K47, V47)
  2         NULL
  3         NULL
  ...
  54        --> (K89, V89)
  ...

When you perform a put operation put(key, value) first the code retrieve the hashCode of the key. This value with a module operation is needed to search on the list on the specific bucket. Then it performs a search element by element on that list performing an equals method to check if the key is already present or not. If the key is present it replace only the value, if not it will add a new couple key, value at the end of the list.

The pseudo code of the HashMap is similar to the following:

public HashMap {
    private List<List<KeyValue<K, V>>> keyValuesBuckets;

    public void put(K key, V value) {
       int hash = key.hashCode();
       int bucketPosition = hash % keyValuesBuckets.size();
       for (KeyValue kv : keyValuesBuckets.get(bucketPosition)) {
          if (kv.getKey().equals(key)) {
             // Key is present change the value and exit
             kv.setValue(value);
             return;
          }
       }
       // Key is not present
      keyValuesBuckets.get(bucketPosition).add(new KeyValue(key, value));
}

Note that the code is not the real code. There is no check on the null values for example, but it gives you the idea on how the equality is checked using both hashCode and equals methods.

To have a more in depth details on how it works start from the definition of [hashCode][1]:

Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by HashMap.

and [equals][2]

In the javadoc you can find the contract that equals and hashCode must supply so that a class can be used as a key in a HashMap:

The general contract of hashCode is: Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application. If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables. [1]: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode-- [2]: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-java.lang.Object-

score 0 · Answer 2 · answered Aug 10 '21 at 15:14

Take a look at the following image taken from here (https://www.bigocheatsheet.com/)

Hash collections have a O(1) insertion complexity meaning that the operation does not depend on how many data points are already present in the data structure. As the name suggests keys are hashed into buckets. If you want to look up a values for key a the key is taken and a hash function employed mapping the value to a specific memory location. There is no need to look up any other value.

The exception are hash collisions which are bound to happen due to dimensionality reduction. After employing the has function, different keys max resolve to the same hash and thus land in the same bucket. In this case other means of checks have to take place (this is the reason why you always have to overwrite hashcode and equals) Further information about this can be found here: https://stackoverflow.com/a/19691998/3244464

How to maintain uniqueness of key in hashmap internally

2 Answers2