Compact HashMap

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

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

Download compactmap

Filename	Size
compactmap-2.0.pom
compactmap-2.0.jar	23 KB
compactmap-2.0-sources.jar	13 KB
compactmap-2.0-javadoc.jar	31 KB

How to add to project

Apache Maven

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

Gradle Groovy

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

Gradle Kotlin

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

Apache Buildr

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

Apache Ivy

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

Groovy Grape

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

Scala SBT

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

Leiningen

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

Dependencies

compile (1)

Group / Artifact	Type	Version
com.github.andrewoma.dexx : dexx-collections	jar	0.2

test (3)

Group / Artifact	Type	Version
org.junit.jupiter : junit-jupiter	jar	5.4.2
org.junit.vintage : junit-vintage-engine	jar	5.4.2
com.google.guava : guava-testlib	jar	27.1-jre

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