Training

JAM - Just Another Map

Maps revisited

Our very own Map type

  • Ongoing example that visits many topics of Java
  • Interfaces, Abstract Classes, Generics, Packages
  • Naming, Method Design, Extending, Reuse
  • JUnit, Benchmarking, Documentation
  • Lambdas
  • Concurrency
  • Maps are interesting data structures
  • Fast but space inefficient
  • Unsorted by default
  • No random access
  • Unique keys only

Basic Capabilities

What are the minimum Map requirements?

A map is a data structure and it is mainly used for fast look ups. It stores data in the form of key and value pairs where every key is unique. Each key here maps to a value and hence the name map.

The idea is to use a mathematical functional to derive a numeric value (the hash value) from the key and use it to map the key to a storage position.

  • Key-Value storage
  • Unique keys but values can be anything
  • Value look up by key
  • Any pair of data structures usable per map aka one defined set per map
  • Fast lookup
  • Basic operations, add, get, remove, remove all, size, get all (?)

Hash Codes

A short computer science detour.

A hash function is any function that can be used to map data of arbitrary size to data of fixed size. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes.

  • Same key, same hash
  • Different key, most likely different hash
  • Collisions should be rare
  • Calculation should be fast

Java HashCode

Java delivers by default hashes for every non-primitive data type.

  • int hashCode() is part of Object which is the base for every non-primitive data type
  • Every object inherits it (inheritance - we get to that later)
  • Free to implement your own version aka override it
  • Default hashCode() is basic and context-less
  • Two invocations during runtime must yield the same result when the underlying object was not modified.
  • No need to remain consistent from one execution of an application to another.
  • If two objects are equal according to the equals(Object) method, then the hash code must be identical as well.
  • Objects that are not equal can produce the same hash code but programmers should be aware of the possible negative consequences.

Java HashCodes

Two examples

/**
 * Returns a hash code for this string. The hash code for a
 * {@code String} object is computed as
 * 
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * 
* using {@code int} arithmetic, where {@code s[i]} is the * ith character of the string, {@code n} is the length of * the string, and {@code ^} indicates exponentiation. * (The hash value of the empty string is zero.) * * @return a hash code value for this object. */ public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }
/**
 * Returns a hash code for a {@code boolean} value; compatible with
 * {@code Boolean.hashCode()}.
 *
 * @param value the value to hash
 * @return a hash code value for a {@code boolean} value.
 * @since 1.8
 */
public static int hashCode(boolean value) {
    return value ? 1231 : 1237;
}

JAM - Naming

All stuff needs names first

  • Interface - SimpleMap<K, V>
  • First implementation - BasicHashMap<K, V>
  • Methods
    • V get(K)
    • V put(K, V)
    • void putAll(SimpleMap<K, V>)
    • int size()
    • void clear()
    • V remove(K)
    • boolean contains(K)

JAM - Interface

public interface SimpleMap<K, V>
{
    public V get(K);
    public V put(K, V);
    public void putAll(SimpleMap<K, V>);
    public V remove(K);
    public int size();
    public void clear();
    public boolean contains(K)
}
/**
 * Interface for map-like data structures that behave similarly
 * to known implementations such as HashMap.
 * <p>
 * This interface is not to be confused with java.util.Map despite being
 * similar it is not fully comparable due to the lack of method coverage.
 *
 * @author René Schwietzke
 */
public interface SimpleMap<K, V>
{
    /**
     * Returns the stored value of a key if it exists, null otherwise
     *
     * @param key the key to look for
     * @returns the found value or null if not found
     */
    public V get(K key);
}