envzn
0.8 · beta · not released

Which dictionary?

Every dictionary has the same interface, Dictionary[K, V, H]: a key type, a value type and a hasher. What differs is how each one stores its keys, and so how fast it is. Choose by your keys, and start at the top of the table.

Your keys Use Why
Integers IntKeyedDictionary The fast choice for integer keys: it uses the integer itself as the hash and keeps keys and values in flat arrays.
Strings or bytes StringKeyedDictionary The fast choice for text keys: keys are kept as bytes in one flat pool. You convert a String key to bytes once, then look it up as bytes.
Any other type ChainedHashDictionary The general choice when neither fast dictionary fits your key.

These three are the ones to use. They are the dictionaries that have been tuned for speed. The others exist for one need each, have not been optimized yet, and may be much slower. Use one only when you need what it adds:

  • ProHashDictionary, for keys that come from outside (users, files, the network). It hashes with a secret key, so nobody can choose keys that all land in one slot and slow every lookup down.
  • RedBlackTreeDictionary, for keys you need in sorted order. It walks its keys in order, and every lookup, insert and remove is O(log n).
  • ShallowDictionary, for integer keys you do not control, which might cluster.

Hold the interface, create the implementation. The implementations are hidden: you name one only in CREATE, and every variable, field and parameter has the type Dictionary[K, V, H]. Changing your mind later is a one-line change.

The hasher is the third type. InlineIntHasher pairs with IntKeyedDictionary, and DefaultHasher suits the rest. SipHasher is the keyed hash behind ProHashDictionary.

The byte-keyed dictionaries take two type parameters, not three. In StringKeyedDictionary (and ProHashDictionary) the key is always a BinaryWord: a borrowed window over bytes you already hold. Convert the String once with INTO ByteBuffer, copy out its bytes, and keep them alive for as long as the dictionary uses the key.

Reading a value can fail, and says so. lookup returns the value or a failure, and you test it in an IF: there is no "missing key" value to forget to check.

CLASS Main IMPLEMENTS TaskStarter {
    METHOD start() RETURNS STATUS {
        // Integer keys: IntKeyedDictionary, with the hasher passed in.
        Dictionary[int32, int64, InlineIntHasher[int32]] stockById := CREATE IntKeyedDictionary[int32, int64, InlineIntHasher[int32]](CREATE InlineIntHasher[int32]())
        $? := stockById->insert(1001, 12)
        int32 wantedId = 1001
        IF stockById->lookup(wantedId) THEN {
            int64 count = $RETURNED
            printline(("item $1 has $2 in stock")->format(wantedId, count))
        }

        // Text keys: StringKeyedDictionary. The key is the String's bytes, converted once.
        Dictionary[BinaryWord, int64, DefaultHasher[BinaryWord]] stockByName := CREATE StringKeyedDictionary[int64, DefaultHasher[BinaryWord]]()
        ByteBuffer pears := "pears" INTO ByteBuffer
        binary[] pearsBytes := DUPLICATE pears->data()
        BinaryWord pearsKey = CREATE BinaryWord(pearsBytes, 0, pearsBytes.length)
        $? := stockByName->insert(pearsKey, 7)
        IF stockByName->lookup(pearsKey) THEN {
            int64 count = $RETURNED
            printline(("pears: $1")->format(count))
        }
        ELSE {
            printline("no pears")
        }
        RETURN (SUCCESS)
    }
}

A set is a dictionary with only keys: Set[V, H] wraps a ChainedHashDictionary, takes the same hashers, and is created directly.