CODEWITHSUNDEEP
java
mkurz
mkurz

Reputation: 2826

LinkedHashSet vs HashSet memory consumption

In Java how much more memory (bytes) is a LinkedHashSet consuming compared to a "normal" HashSet? I know LinkedHashSet is slightly slower for certain operations, but what about memory usage?

Upvotes: 0

Views: 1593

Answers (2)

PiotrK
PiotrK

Reputation: 1552

As the name suggests and the docs state explicitly, LinkedHashSet, apart from the core HashSet, needs to maintain a linked list. I think it's safe to assume here that the upper bound of memory consumption can be approximated as if you'd have just two separate data structures: a hash set and a linked list. How much they consume memory, is a separate question.

However, if you need hard data on the number of bytes of memory used, you can always perform some tests on your own. It shouldn't be too hard to test, or google for a while - I'm sure there are already some test results available on the Internet.

@edit, after Louis' answer

It seemed interesting for me why the difference is smaller. Here's a simple benchmark I wrote:

package com.company;

import com.javamex.classmexer.MemoryUtil;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Creating data structures under test -------
        HashSet<Integer> hashSet = new HashSet<>();

        Random random = new Random();
        for (int i=0; i<1000000; i++)
        {
            hashSet.add(random.nextInt());
        }

        LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(hashSet);

        // Measuring memory usage --------------------
        long sizeOfHashSet = MemoryUtil.deepMemoryUsageOf(hashSet);
        long sizeOfLinkedHashSet = MemoryUtil.deepMemoryUsageOf(linkedHashSet);
        System.out.println("Size of HashSet:\n" + sizeOfHashSet + " B");
        System.out.println("Size of LinkedHashSet:\n" + sizeOfLinkedHashSet + " B");
        System.out.println("LinkedHashSet is bigger from HashSet by " + (sizeOfLinkedHashSet*100/sizeOfHashSet - 100) + "%");

        System.out.println("\n");

        long numberOfElements = hashSet.size();
        System.out.println("Number of elements in the test HashSet: " + numberOfElements);

        System.out.println("Average size of a single element in HashSet: " + sizeOfHashSet/numberOfElements + " B");
        System.out.println("Average size of a single element in LinkedHashSet: " + sizeOfLinkedHashSet/numberOfElements + " B");
    }
}

After it running it several times I noticed it prints out fairy stable results (object sizes differ by +/- 2 KiB) which I present below:

Size of HashSet:
56347616 B
Size of LinkedHashSet:
64348040 B
LinkedHashSet is bigger from HashSet by 14%

Number of elements in the test HashSet: 999876
Average size of a single element in HashSet: 56 B
Average size of a single element in LinkedHashSet: 64 B

What's interesting, it doesn't align with values given by Louis. However, the difference in bytes per element is the same as Louis wrote (8 B). Could someone explain the discrepancy in values? Am I measuring object size in a wrong way?

Upvotes: 2

Louis Wasserman
Louis Wasserman

Reputation: 198014

https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt

A HashSet is ~32 bytes/element; a LinkedHashSet is ~40 bytes/element.

Upvotes: 3

Related Questions