What happens if multiple put operations are performed on linkedhashmap in parallel?-CodePudding

I have sample code:

Map<Integer, String> hs = new LinkedHashMap<>();
IntStream.range(0,1000).parallel().forEach(value -> hs.put(value, "value"));
System.out.println(hs.size());

This is never returning size as 1000 as I understand linkedhashmap is not thread safe and when I use Collections.synchronizedMap(new LinkedHashMap<>()); the size is always 1000 as it is thread safe.

I want to understand what happens in the case of linkedhashmap put operation when multiple threads try to put data in it? How does it have less entries?

CodePudding user response：

Ask yourself how a linked hashmap works.

As the name implies: by "linking" objects into some sort of "chain", with a data structure that keeps track of the "next" element.

Now imagine the chain ends in object X, and 2 different threads come in and add a new entry that should go after X. Both these threads update that data structure, and the second one overwrites what the first thread did.

In other words: two new elements should be added as HashMap key, but only one of the two actually makes it, the other one is simply lost.

It is like two people throwing bricks into a garbage bin. If they don't pay attention, they might throw bricks at the same time, the bricks "collide", and not both of them end up in the garbage bin.

CodePudding user response：

    hs.put(0, "0");
    hs.put(1, "1");
    hs.put(2, "2");
    // hs should be "0 -> 1 -> 2"

    hs.put(0, "0");
    hs.put(1, "1");
    // so sometimes it should be `0.next = 1`
    // because it is not thread safe
    // `2` should be behind 1, but it cut the queue
    // become 0.next = 1; 0.next = 2; `0.next` is assigned twice
    // so the `1` is lost!
    hs.put(2, "2");

    // hs will be "0 -> 2"