Package com.github.andrewoma.dexx.collection

Class DerivedKeyHashMap<K,V>

java.lang.Object

com.github.andrewoma.dexx.collection.internal.base.AbstractTraversable<E>

com.github.andrewoma.dexx.collection.internal.base.AbstractIterable<Pair<K,V>>

com.github.andrewoma.dexx.collection.internal.base.AbstractMap<K,V>

com.github.andrewoma.dexx.collection.DerivedKeyHashMap<K,V>

All Implemented Interfaces:

Iterable<Pair<K,V>>, Map<K,V>, Traversable<Pair<K,V>>, java.lang.Iterable<Pair<K,V>>

public class DerivedKeyHashMap<K,V>
extends AbstractMap<K,V>

DerivedKeyHashMap is a HashMap variant where the key for the Map is derived from the value stored.

By deriving the key it is possible to reduce the memory overhead per node in the map (assuming the key is a primitive field in the value object). e.g.

 
 static class Value {
     int key;
     int value;
 }

 DerivedKeyHashMap<Integer, Value> map = new DerivedKeyHashMap<Integer, Value>(
     new KeyFunction<Integer, Value>() {
         public Integer key(Value value) {
             return value.key;
         }
 });

 Value value = new Value();
 value.key = 1;
 value.value = 100;
 map = map.put(value.key, value);
 

The underlying implementation is a port of Scala's HashMap which is an implementation of a hash array mapped trie.

It uses significantly less memory than Scala's implementation as the leaf nodes are the values themselves (not objects containing keys, values and hashes).

As the key is derived from the value, DerivedKeyHashMap does not support null values.

Field Summary

Fields

Modifier and Type	Field	Description
private CompactHashMap<K,V>	compactHashMap
private KeyFunction<K,V>	keyFunction

Constructor Summary

Constructors

Modifier	Constructor	Description
	DerivedKeyHashMap(@NotNull KeyFunction<K,V> keyFunction)
private	DerivedKeyHashMap(KeyFunction<K,V> keyFunction, CompactHashMap<K,V> compactHashMap)

Method Summary

Modifier and Type	Method	Description
boolean	containsKey(K key)	Returns true if this map contains the specified key.
static <K,V> @NotNull BuilderFactory<Pair<K,V>,DerivedKeyHashMap<K,V>>	factory(KeyFunction<K,V> keyFunction)
<U> void	forEach(@NotNull Function<Pair<K,V>,U> f)	All collection methods can be built upon this forEach definition.
V	get(K key)	Returns the value associated with the key or null if the no value exists with the key specified.
@NotNull java.util.Iterator<Pair<K,V>>	iterator()
@NotNull DerivedKeyHashMap<K,V>	put(K key, V value)	Returns a map with the value specified associated to the key specified.
@NotNull DerivedKeyHashMap<K,V>	remove(K key)	Returns a map with the value associated with the key removed if it exists.
int	size()	Returns the size of the collection.

Methods inherited from class com.github.andrewoma.dexx.collection.internal.base.AbstractMap

asMap, equals, hashCode, keys, values

Methods inherited from class com.github.andrewoma.dexx.collection.internal.base.AbstractTraversable

isEmpty, makeString, makeString, to, toArray, toArray, toIndexedList, toSet, toSortedSet, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface com.github.andrewoma.dexx.collection.Traversable

isEmpty, makeString, makeString, to, toArray, toArray, toIndexedList, toSet, toSortedSet

Field Detail

keyFunction

private final KeyFunction<K,V> keyFunction

compactHashMap

private final CompactHashMap<K,V> compactHashMap

Constructor Detail

DerivedKeyHashMap

public DerivedKeyHashMap(@NotNull
                         @NotNull KeyFunction<K,V> keyFunction)

DerivedKeyHashMap

private DerivedKeyHashMap(KeyFunction<K,V> keyFunction,
                          CompactHashMap<K,V> compactHashMap)

Method Detail

factory

@NotNull
public static <K,V> @NotNull BuilderFactory<Pair<K,V>,DerivedKeyHashMap<K,V>> factory(KeyFunction<K,V> keyFunction)

containsKey

public boolean containsKey(@NotNull
                           K key)

Description copied from interface: Map

Returns true if this map contains the specified key.

put

@NotNull
public @NotNull DerivedKeyHashMap<K,V> put(@NotNull
                                                 K key,
                                                 V value)

Description copied from interface: Map

Returns a map with the value specified associated to the key specified.

If value already exists for the key, it will be replaced.

get

@Nullable
public V get(@NotNull
             K key)

Description copied from interface: Map

Returns the value associated with the key or null if the no value exists with the key specified.

remove

@NotNull
public @NotNull DerivedKeyHashMap<K,V> remove(@NotNull
                                                    K key)

Description copied from interface: Map

Returns a map with the value associated with the key removed if it exists.

size

public int size()

Description copied from interface: Traversable

Returns the size of the collection.

Warning: infinite collections are possible, as are collections that require traversal to calculate the size.

Specified by:

size in interface Traversable<K>

Overrides:

size in class AbstractTraversable<Pair<K,V>>

forEach

public <U> void forEach(@NotNull
                        @NotNull Function<Pair<K,V>,U> f)

Description copied from interface: Traversable

All collection methods can be built upon this forEach definition.

Specified by:

forEach in interface Traversable<K>

Overrides:

forEach in class AbstractIterable<Pair<K,V>>

iterator

@NotNull
public @NotNull java.util.Iterator<Pair<K,V>> iterator()