Class LinearMap<K,V>

java.lang.Object
io.lacuna.bifurcan.IMap.Mixin<K,V>
io.lacuna.bifurcan.LinearMap<K,V>
All Implemented Interfaces:
ICollection<IMap<K,V>,IEntry<K,V>>, IMap<K,V>, Iterable<IEntry<K,V>>, Function<K,V>
public class LinearMap<K,V> extends IMap.Mixin<K,V>
A hash-map implementation which uses Robin Hood hashing for placement, and allows for customized hashing and equality semantics. Performance is equivalent to HashMap for lookups and construction, and superior in the case of poor hash distribution. Because entries are stored contiguously, performance of clone() and iteration is significantly better than HashMap. Unlike Map, it can only hold Integer.MAX_VALUE elements.

The IMap.entries() method is O(1) and allows random access, returning an IList that proxies through to an underlying array. Partitioning this list is the most efficient way to process the collection in parallel.

However, LinearMap also exposes O(N) split(int) and merge(IMap, BinaryOperator) methods, which despite their asymptotic complexity can be quite fast in practice. The appropriate way to split this collection will depend on the use case.

  • Field Details

  • Constructor Details

    • LinearMap

      public LinearMap()

    • LinearMap

      public LinearMap(int initialCapacity)
      Parameters:
      initialCapacity - the initial capacity of the map

    • LinearMap

      public LinearMap(ToLongFunction<K> hashFn, BiPredicate<K,K> equalsFn)
      Parameters:
      hashFn - a function which yields the hash value of keys
      equalsFn - a function which checks equality of keys

    • LinearMap

      public LinearMap(int initialCapacity, ToLongFunction<K> hashFn, BiPredicate<K,K> equalsFn)
      Parameters:
      initialCapacity - the initial capacity of the map
      hashFn - a function which yields the hash value of keys
      equalsFn - a function which checks equality of keys

  • Method Details

    • from

      public static <K, V> LinearMap<K,V> from(Map<K,V> map)
      Returns:
      a copy of map

    • from

      public static <K, V> LinearMap<K,V> from(IMap<K,V> map)
      Returns:
      a copy of map, with the same equality semantics

    • from

      public static <K, V> LinearMap<K,V> from(Iterator<IEntry<K,V>> iterator)
      Returns:
      a map representing all remaining entries in iterator

    • from

      public static <K, V> LinearMap<K,V> from(Collection<Map.Entry<K,V>> collection)
      Returns:
      a map representing the entries in collection

    • keyHash

      public ToLongFunction<K> keyHash()
      Accessors
      Returns:
      the hash function used by the map

    • keyEquality

      public BiPredicate<K,K> keyEquality()
      Returns:
      the key equality semantics used by the map

    • put

      public LinearMap<K,V> put(K key, V value)
      Returns:
      an updated map with value stored under key

    • put

      public LinearMap<K,V> put(K key, V value, BinaryOperator<V> merge)
      Parameters:
      merge - a function which will be invoked if there is a pre-existing value under key, with the current value as the first argument and new value as the second, to determine the combined result
      Returns:
      an updated map with value under key

    • remove

      public LinearMap<K,V> remove(K key)
      Returns:
      an updated map that does not contain key

    • clear

      public LinearMap<K,V> clear()

    • mapValues

      public <U> LinearMap<K,U> mapValues(BiFunction<K,V,U> f)
      Type Parameters:
      U - the new type of the values
      Parameters:
      f - a function which transforms the values
      Returns:
      a transformed map which shares the same equality semantics

    • get

      public V get(K key, V defaultValue)
      Returns:
      the value under key, or defaultValue if there is no such key

    • update

      public LinearMap<K,V> update(K key, UnaryOperator<V> update)
      Parameters:
      update - a function which takes the existing value, or null if none exists, and returns an updated value.
      Returns:
      an updated map with update(value) under key.

    • keys

      public ISet<K> keys()
      Returns:
      a set representing all keys in the map

    • indexOf

      public OptionalLong indexOf(K key)
      Returns:
      the index of key within the collection, if it's present

    • nth

      public IEntry<K,V> nth(long index)
      Returns:
      the element at idx

    • size

      public long size()
      Returns:
      the number of elements in the collection

    • isLinear

      public boolean isLinear()
      Returns:
      true, if the collection is linear

    • forked

      public IMap<K,V> forked()
      Description copied from interface: ICollection
      This returns a data structure which is forked, which is equivalent to Clojure's persistent data structures, also sometimes called functional or immutable. This is called "forked" because it means that multiple functions can make divergent changes to the data structure without affecting each other.

      If only a single function or scope uses the data structure, it can be left as a linear data structure, which can have significant performance benefits.

      If the data structure is already forked, it will simply return itself.

      Returns:
      a forked form of the data structure

    • linear

      public IMap<K,V> linear()
      Description copied from interface: ICollection
      This returns a data structure which is linear, or temporarily mutable. The term "linear", as used here, does not completely align with the formal definition of linear types as used in type theory. It is meant to describe the linear dataflow of the method calls, and as a converse to "forked" data structures.

      If ICollection.forked() is called on a linear collection, all references to that linear collection should be discarded.

      If the data structure is already linear, it will simply return itself.

      Returns:
      a linear form of this data structure

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class IMap.Mixin<K,V>

    • clone

      public LinearMap<K,V> clone()
      Specified by:
      clone in interface ICollection<K,V>
      Overrides:
      clone in class IMap.Mixin<K,V>
      Returns:
      a cloned copy of the collection

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class IMap.Mixin<K,V>

    • split

      public List<LinearMap<K,V>> split(int parts)
      Description copied from interface: ICollection
      Splits the collection into roughly even pieces, for parallel processing. Depending on the size and contents of the collection, this function may not return exactly parts subsets.
      Parameters:
      parts - the target number of pieces
      Returns:
      a list containing subsets of the collection.

    • union

      public LinearMap<K,V> union(IMap<K,V> m)
      Returns:
      a combined map, with the values from m shadowing those in this amp

    • merge

      public LinearMap<K,V> merge(IMap<K,V> m, BinaryOperator<V> mergeFn)
      Parameters:
      m - another map
      mergeFn - a function which, in the case of key collisions, takes two values and returns the merged result
      Returns:
      a new map representing the merger of the two maps

    • difference

      public LinearMap<K,V> difference(IMap<K,?> m)
      Returns:
      a new map representing the current map, less the keys in m

    • difference

      public IMap<K,V> difference(ISet<K> keys)
      Returns:
      a new map representing the current map, less the keys in keys

    • intersection

      public LinearMap<K,V> intersection(IMap<K,?> m)
      Returns:
      a new map representing the current map, but only with the keys in m

    • intersection

      public LinearMap<K,V> intersection(ISet<K> keys)
      Returns:
      a new map representing the current map, but only with the keys in keys

    • containsAll

      public boolean containsAll(ISet<K> set)
      Returns:
      true if this map contains all elements in set

    • containsAll

      public boolean containsAll(IMap<K,?> map)
      Returns:
      true if this map contains all keys in map

    • containsAny

      public boolean containsAny(ISet<K> set)
      Returns:
      true if this map contains any element in set

    • containsAny

      public boolean containsAny(IMap<K,?> map)
      Returns:
      true if this map contains any element in map