Compact HashMap layout/size tests

Hash table implementation modelled after memory efficient V8's Fast Property Access

License	Apache-2.0
GroupId	com.github.vlsi.compactmap
ArtifactId	jol
Last Version	2.0
Release Date	Mar 30, 2020
Type	jar
Description	Compact HashMap layout/size tests Hash table implementation modelled after memory efficient V8's Fast Property Access

Download jol

Filename	Size
jol-2.0.pom
jol-2.0.jar	1 KB

How to add to project

Apache Maven

<!-- https://jarcasting.com/artifacts/com.github.vlsi.compactmap/jol/ -->
<dependency>
    <groupId>com.github.vlsi.compactmap</groupId>
    <artifactId>jol</artifactId>
    <version>2.0</version>
</dependency>

Gradle Groovy

// https://jarcasting.com/artifacts/com.github.vlsi.compactmap/jol/
implementation 'com.github.vlsi.compactmap:jol:2.0'

Gradle Kotlin

// https://jarcasting.com/artifacts/com.github.vlsi.compactmap/jol/
implementation ("com.github.vlsi.compactmap:jol:2.0")

Apache Buildr

'com.github.vlsi.compactmap:jol:jar:2.0'

Apache Ivy

<dependency org="com.github.vlsi.compactmap" name="jol" rev="2.0">
  <artifact name="jol" type="jar" />
</dependency>

Groovy Grape

@Grapes(
@Grab(group='com.github.vlsi.compactmap', module='jol', version='2.0')
)

Scala SBT

libraryDependencies += "com.github.vlsi.compactmap" % "jol" % "2.0"

Leiningen

[com.github.vlsi.compactmap/jol "2.0"]

Dependencies

compile (1)

Group / Artifact	Type	Version
com.github.vlsi.compactmap : compactmap	jar	2.0

test (4)

Group / Artifact	Type	Version
org.openjdk.jol : jol-core	jar	0.9
org.junit.jupiter : junit-jupiter	jar	5.4.2
org.pcollections : pcollections	jar	3.0.3
com.github.krukow : clj-ds	jar	0.0.4

Project Modules

There are no modules declared in this project.

CompactHashMap

Usage

Add Maven dependency:

<dependency>
    <groupId>com.github.vlsi.compactmap</groupId>
    <artifactId>compactmap</artifactId>
    <version>1.3.0</version>
</dependency>

Gradle:

compile("com.github.vlsi.compactmap:compactmap:1.3.0")

About

This is a memory efficient alternative to HashMap. Main design goal is taken from "Fast Property Access" http://code.google.com/apis/v8/design.html#prop_access.

This implementation however can store specific key-value pairs out of the map, so they do not consume memory when repeated in different maps.

The expected memory consumption (8u40, 64 bit, compressed references) is as follows:

# of elements  CompactHashMap  HashMap (with 1.0 fillFactor)
            0              32       48
            1              32      104
            2              32      136
            3              32      176
            4              64      208
            5              64      256
            6              64      288
            7              72      320
            8              72      352

In other words, the first three non default values consume the same 32 bytes, then map grows as 32 + 16 + 4 * (n-2) == 40 + 4 * n. Regular HashMap grows as 64 + 36 * n.

The runtime of put and get is constant. The expected runtime is as follows (measured in hashmap and array accesses):

             best case        worst case
get    1 hashmap + 1 array    2 hashmap
put    1 hashmap + 1 array    6 hashmap

Sample

	// Mark height->auto a default mapping entry, so it would not consume memory in CompactHashMaps
	CompactHashMapDefaultValues.add("height", "auto");

	// Mark all values of width as default, so they would not consume memory in real maps
	CompactHashMapDefaultValues.add("width");

	CompactHashMap<String, String> map = new CompactHashMap<String, String>();
	map.put("height", "auto");      // does not consume memory in map
	map.put("width", "100%");       // does not consume memory in map either
	map.put("id", "myFirstButton"); // consumes some memory

	map.get("height"); // => "auto"
	map.get("width");  // => "100%"
	map.get("id");     // => "myFirstButton"

	map.put("height", "50px"); // consumes some memory (switches from default to custom)

	map.get("height"); // => "50px"

License

This library is distibuted under terms of GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

Change log

v2.0:

• Change license: LGPL 2.0 -> Apache-2.0

v1.3.0

• Improvement: implement null keys
• Improvement: Map#toString
• Improvement: Map#hashCode + equals
• Improvement: Map.Entry#hashCode + equals
• Improvement: Map.Entry#toString
• Improvement: Map#containsValue (it is slow but it works)
• Test: use guava-testlib for Map implementation testing

v1.2.1

• Improvement: release to Maven Central
• Improvement: fix EntrySet.remove method

v1.2.0

• Improvement: reduce size of hidden classes by using persistent dexx-collections.
• Improvement: mavenize build
• Switch to semantic versioning

v1.1

• Fix: #1 containKey returns true on non existing key
• Fix: #2 size should account removed keys
• Improvement: #3 Default values should be serialized as map

Author

Vladimir Sitnikov [email protected]

Versions

Version
2.0 Mar 30, 2020
1.3.0 Apr 28, 2019
1.2.1 Mar 19, 2015