Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java 8 Hashmap Internals

Tags:

java

hashmap

I have gone through the implementation of Java 8 Hashmap and arrived with below doubts. Please help me to clarify them:

  1. I read in an article which says that, nodes with the same hashcode will be added in same bucket as a linked list. It says that the new node to this linked list will be added in head insteadof tail to avoid tail traversal. But when I see the source code, new node is getting added in tail. Is that correct?
  2. I didn't completely understand this variable MIN_TREEIFY_CAPACITY. Is it like after this much count, entire map will be converted to tree(from array to tree)?
like image 532
Antony Vimal Raj Avatar asked Mar 06 '23 01:03

Antony Vimal Raj


1 Answers

But when I see the source code, new node is getting added in tail. Is that correct?

It is added to the head, in older versions. However, many changes were made in Java 8 which does.

class A {
    static class SameHash {
        final int n;

        SameHash(int n) {
            this.n = n;
        }

        @Override
        public int hashCode() {
            return 1;
        }

        @Override
        public String toString() {
            return "SameHash{" +
                    "n=" + n +
                    '}';
        }
    }

    public static void main(String[] args) {
        HashSet<SameHash> set = new HashSet<>();
        for (int i = 1; i <= 4; i++)
            set.add(new SameHash(i));
        System.out.println(set);
    }
}

prints

[SameHash{n=1}, SameHash{n=2}, SameHash{n=3}, SameHash{n=4}]

NOTE: Keys can have different hashCodes but can end up in the same bucket.

I didn't completely understand this variable MIN_TREEIFY_CAPACITY. Is it like after this much count, entire map will be converted to tree(from array to tree)?

After this count, the bucket is converted to a tree provided the key is Comparable

like image 178
Peter Lawrey Avatar answered Mar 11 '23 20:03

Peter Lawrey