HashMap

Overview

Table-based implementation of a map with support for user-defined hash functions and nil values.

On a call to HashMap:add(key,val), HashMap checks for the existence of getmetatable(key).__hash. If it exists, key:__hash() is called and the result is used to select a bucket for the entry (key=val). If it does not exist, the default Lua hashing function is used to determine the bucket for the entry.

For instance, The Tuple class overrides __hash and __eq, so HashMap can be used as a multi-key map by making the keys tuples:

> h = HashMap:new()
> tuple = sano.makers.tuple
> h:add(tuple(1,1,2), tuple(3,4))
...
> print( h:get(tuple(1,1,2)) )
(3, 4)

If h were a regular Lua table, the two instances of tuple(1,1,2) would not be recognized as being equivalent:

> h = {}
> h[tuple(1,1,2)] = tuple(3,4)
...
> print( h[tuple(1,1,2)] )
nil

If the __hash metamethod hashes distinct keys to the same bucket, then all keys which are different according to '==' are retained in the HashMap. If Tuple used a bad hash function and by chance tuple(1,2,3) and tuple(3,2,1) hashed to the same value, both would still be retained as keys since tuple(1,2,3) ~= tuple(3,2,1).

Mutable objects should not be changed when they are being used as keys in a HashMap, as HashMap has no way of knowing when keys change and will not know to rehash the changed key.

More examples of usage:

> h = HashMap:new(); h:add("Jones","Phil"); print(h)
{Jones="Phil"}
> print(h:get("Jones"))
Phil
> h:add("Smith","Andrea"); h:add("Doe","John")
> for k,v in h:iter() do print(k,v) end
Smith   Andrea
Jones   Phil
Doe     John
> for k,v in h:orderedIter() do print(k,v) end -- entries sorted by key
Doe     John
Jones   Phil
Smith   Andrea
> print(h:add("Jones","Frankie")) -- override previous value
Phil
> print(h)
{Smith="Andrea", Jones="Frankie", Doe="John"}
> print(h:size()) -- prints the number of entries in the map
3

Summary

newCreates and returns a new, empty HashMap.
makeCreates and returns a new Map, containing the mappings supplied.
getReturns the value stored against key, or nil if no no such value exists.
__eqReturns true if both maps have the same size and contain the same mappings.
addAdds the key-value pair to this HashMap and returns the previous value stored against key (possibly nil) value may be nil, but key must be non-nil.
containsReturns true if this map contains a mapping (possibly nil) for the given key.
getReturns the value stored against key, or nil if no no such value exists.
iterReturns an iteration over all key-value pairs in this map.
orderedIterReturns an iteration over the entries in this HashMap, ordered by key.
removeRemoves the entry with key == key from this HashMap and returns the value associated with key.
sizeReturns the number of key-value pairs in this HashMap.
testUnit test.
toStringReturns a string representation of map.
addMappingsAdds mappings to this Map and returns Map to allow chaining.
containsAllReturns true iff collection:contains(e) for e in iter(iterable).
removeAllEquivalent to calling set:remove(e) for e in iter(elements).
valIterEquivalent to Map:iter() except that iteration steps return elements in the order val,key instead of key,val.

Detail

HashMap:new()

Creates and returns a new, empty HashMap.

Map:make(mappings [, vals])

Creates and returns a new Map, containing the mappings supplied.

input can be one of several types:

  1. A single Lua table {a=1,b=2,c=3,d=4,e=5}
  2. A single iteration which returns two values per iteration step: iter.zip("abcde",iter.count())
  3. Two iterables which both return one value per iteration step - this is a shorthand for 2.
  4. Any table with an iter method which, when called, returns an iteration satisfying 2.

So, the following are all equivalent:
Map:make{a=1,b=2,c=3,d=4,e=5} 
  == Map:make(iter.zip("abcde",iter.count()))
  == Map:make("abcde",iter.count())
  == Map:make(Map:make{a=1,b=2,c=3,d=4,e=5})

HashMap:get(key)

Returns the value stored against key, or nil if no no such value exists.

If the value of nil is explicitly stored against key, then get(key) will return nil and contains(key) will return true.

synonym: __call So, m:get("h") == m("h")

HashMap:__eq(other)

Returns true if both maps have the same size and contain the same mappings.

HashMap:add(key,value)

Adds the key-value pair to this HashMap and returns the previous value stored against key (possibly nil)

value may be nil, but key must be non-nil.

Example:

> h = hashmap {a=1,b=2}; print(h:add("a",19))
1

HashMap:contains(key)

Returns true if this map contains a mapping (possibly nil) for the given key.

HashMap:get(key)

Returns the value stored against key, or nil if no no such value exists.

If the value of nil is explicitly stored against key, then get(key) will return nil and contains(key) will return true.

synonym: __call So, m:get("h") == m("h")

HashMap:iter()

Returns an iteration over all key-value pairs in this map.

Each iteration step returns two values; the first is the key for the current entry, the second is the value for the entry.

HashMap:orderedIter(orderFn)

Returns an iteration over the entries in this HashMap, ordered by key.

orderFn determines how the keys are ordered; default is natural increasing order. This method internally makes a copy of the key set of this map and sorts it.

HashMap:remove(key)

Removes the entry with key == key from this HashMap and returns the value associated with key.

Example:

> h = HashMap:make {a=1,b=2}; print(h:remove("a"))
1
> print(h)
{b=2}

HashMap:size()

Returns the number of key-value pairs in this HashMap.

key-value pairs with a nil value are included in the count.

HashMap:test()

Unit test.

maps.toString(map)

Returns a string representation of map.

Example:

> x = HashMap:make{a=1,b=2,c=3,d=4}
> print(x)
{a=1, d=4, c=3, b=2}

Map:addMappings(mappings, vals)

Adds mappings to this Map and returns Map to allow chaining.

input can be one of several types:

  1. A single Lua table {a=1,b=2,c=3,d=4,e=5}
  2. A single iteration which returns two values per iteration step: iter.zip("abcde",iter.count())
  3. Two iterables which both return one value per iteration step - this is a shorthand for 2.
  4. Any table with an iter method which, when called, returns an iteration satisfying 2.

So, the following are all equivalent:
Map:addMappings{a=1,b=2,c=3,d=4,e=5} 
  == Map:addMappings(iter.zip("abcde",iter.count()))
  == Map:addMappings("abcde",iter.count())
  == Map:addMappings(Map:addMappings{a=1,b=2,c=3,d=4,e=5})

collections.containsAll(collection, elements)

Returns true iff collection:contains(e) for e in iter(iterable).

sets.removeAll(set, elements)

Equivalent to calling set:remove(e) for e in iter(elements).

Map:valIter()

Equivalent to Map:iter() except that iteration steps return elements in the order val,key instead of key,val.