Geek Answers Handbook

Java: memory structure data

Does anyone have a list of rough large-size estimates for various data structures? eg.

  • Arrays
  • Lists
  • Hashmaps
  • LinkedLists

I remember how some of these grades were cast in different places, but I can’t find them right now.

I know this is really incredibly difficult, especially for things like HashMaps, but I'm looking for something really rude, like this:

Memory(HashMap) = fixedOverhead + variableOverhead * tableSize + A*numKeys + B*numValues + Memory(allKeys) + Memory(allValues)

Of course, this will change a lot depending on this and that, but even a rough estimate of intra-factor-2 will be very useful.

+5
source share
5 answers

, . , , , Java.

dataType -

Array: (length n)
    n*sizeOf(dataType)

LinkedList:
    n*(sizeOf(dataType)+sizeOf(pointer))+sizeOf(pointer[head pointer])

List: 
    Array-backed=SpaceEfficiency(Array)
    LinkedList-backed=SpaceEfficiency(LinkedList)

HashMap: with v values, k keys
    v*sizeOf(valueDataType)

Tree: k-way tree with n nodes
    n*(sizeOf(nodeDataType)+(k*sizeOf(pointer)))+sizeOf(pointer[head pointer])

Graph: e edges, v vertices
    AdjacencyList:
        at most: v*((v*sizeOf(vertexDataType))+(e*sizeOf(pointer))) fully connected graph
        at least: v*sizeOf(vertexDataType) disconnected graph
    AdjacencyMatrix:
        v^2*sizeOf(int)
0

, :

import java.util.*;
/**
    RamInit (c) GPLv3

    @author Stefan Wagner
    @date Do 22. Mär 08:40:40 CET 2012

*/
public class RamInit
{
    private java.lang.Object consumer; 

    public RamInit (char type, int size)
    {
        switch (type) 
        {
            case 'a': Integer [] ai = new Integer [size]; 
                for (int i = 0; i < size; ++i) 
                    ai[i] = i; 
                consumer = ai; 
                break;
            case 'l': List<Integer> li = new ArrayList<Integer> (); 
                for (int i = 0; i < size; ++i) 
                    li.add (i); 
                consumer = li;
                break;
            case 'h': HashMap <Integer, Integer> hm = new HashMap <Integer, Integer> (); 
                for (int i = 0; i < size; ++i) 
                    hm.put (i, size - i); 
                consumer = hm;
                break;
            case 'L': LinkedList <Integer> ll = new LinkedList <Integer> (); 
                for (int i = 0; i < size; ++i) 
                    ll.add (i);     
                consumer = ll;          
                break;
            default: System.err.println ("invalid: " + type);
        }
    }

    public static void main (String args[])
    {
        char type = 'a';
        int size = 1000000; // 1M
        if (args.length == 2)
        {
            type = args[0].charAt (0);
            size = Integer.parseInt (args[1]);
        }
        try {
            new RamInit (type, size);
        }
        catch (OutOfMemoryError oome)
        {
            System.exit (1);
        }
    }
}

script, :

#!/bin/bash

iterProg () {
ram=$1
maxram=$2 
typ=$3
size=$4
# echo java -Xmx${ram}M RamInit $typ $((size*1000*1000)) 
echo -n "." 
java -Xmx${ram}M RamInit $typ $((size*1000*1000)) && echo -en "\n"$typ $size ${ram}M || { 
    if (($ram==$maxram))
    then
        # echo "fail" 
        return 
    else 
        iterProg $((ram+1)) $maxram $typ $size 
    fi
    }
}

# try from 16 MB to 256
for typ in {a,l,h,L}; do 
  for size in {1,2,4}; do 
    iterProg $((size*17+1)) 256 $typ $size 
  done
done

- - , 37MB RamInit Collection a 1M, 2M .

, , 20M , 128, (20 + 128)/2, avg , .

HashMap 2 , List/Array/Vector. - , :

bash iterRamFind.sh 
..
a 1 19M.....
a 2 39M...............
a 4 83M..
l 1 19M.......
l 2 41M.......................
l 4 91M..............................................
h 1 63M.............................................................................................
h 2 127M...........................................................................................................................................................................................
h 4 255M......................
L 1 39M.................................................
L 2 83M...............................................................................................
L 4 163

17 . , .

, Longs, - , 2.

0

Infoq, infoq-11-nov-jvmperformance.mp3 twitter: Pdf-, : mp3 .

It talks a lot about collections and other details about the size of objects in the JVM.

0
source

More articles:


All Articles