Skip to content

Archives

Links for 2012-10-12

  • ElementCostInDataStructures

    “The cost per element in major data structures offered by Java and Guava (r11)].” A very useful reference!

    Ever wondered what’s the cost of adding each entry to a HashMap? Or one new element in a TreeSet? Here are the answers: the cost per-entry for each well-known structure in Java and Guava. You can use this to estimate the cost of a structure, like this: if the per-entry cost of a structure is 32 bytes, and your structure contains 1024 elements, the structure’s footprint will be around 32 kilobytes. Note that non-tree mutable structures are amortized (adding an element might trigger a resize, and be expensive, otherwise it would be cheap), making the measurement of the “average per element cost” measurement hard, but you can expect that the real answers are close to what is reported below.

    (tags: java coding guava reference memory cost performance data-structures)