Compact HashMap

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

License

License

GroupId

GroupId

com.github.vlsi.compactmap
ArtifactId

ArtifactId

compactmap
Last Version

Last Version

2.0
Release Date

Release Date

Type

Type

jar
Description

Description

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

Download compactmap

How to add to project

<!-- https://jarcasting.com/artifacts/com.github.vlsi.compactmap/compactmap/ -->
<dependency>
    <groupId>com.github.vlsi.compactmap</groupId>
    <artifactId>compactmap</artifactId>
    <version>2.0</version>
</dependency>
// https://jarcasting.com/artifacts/com.github.vlsi.compactmap/compactmap/
implementation 'com.github.vlsi.compactmap:compactmap:2.0'
// https://jarcasting.com/artifacts/com.github.vlsi.compactmap/compactmap/
implementation ("com.github.vlsi.compactmap:compactmap:2.0")
'com.github.vlsi.compactmap:compactmap:jar:2.0'
<dependency org="com.github.vlsi.compactmap" name="compactmap" rev="2.0">
  <artifact name="compactmap" type="jar" />
</dependency>
@Grapes(
@Grab(group='com.github.vlsi.compactmap', module='compactmap', version='2.0')
)
libraryDependencies += "com.github.vlsi.compactmap" % "compactmap" % "2.0"
[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.

Build Status Maven Central

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
1.3.0
1.2.1