Skip to content

vlsi/compactmap

Folders and files

NameName
Last commit message
Last commit date
Feb 14, 2024
Dec 13, 2023
Dec 13, 2023
Mar 14, 2015
Apr 28, 2019
Mar 30, 2020
Mar 30, 2020
Feb 14, 2024
Dec 13, 2023

Repository files navigation

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 Apache 2.0 License, see https://raw.githubusercontent.com/vlsi/compactmap/master/LICENSE

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 sitnikov.vladimir@gmail.com

About

Memory efficient java.util.Map implementation modelled after http://code.google.com/apis/v8/design.html

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages