A mutable, growable collection of key => value associations with O(1) key lookup/update and amortized O(1) insertion of new keys. Iteration order corresponds to the order in which keys were first added to the Map (ie updating the value of an existing key does not affect iteration order).
This uses a "Robin Hood hashing" open-addressed linear-probed hash table. Each slot knows its own hash, where its slot index comes from the high bits, which makes Robin Hood distance comparisons trivial -- just subtract. Empty slots use a hash value that looks like a "perfect" (distance 0) fit from the Robin Hood perspective, which makes them look like good candidates for "displacing" without an additional check in the inner loop.
- Make generation_PRIVATE private to the module (once that is supported in the language).
- Either use a different scheme for invalidating iterators in order to allow more than 2**32 entries, or exploit this size limit and use UInt32 for sz, used, and shift ( and possibly store just the high 32 bits of the hash after finalization).
Creating a Mapstatic fun sourcemcreate(capacity: Int): mutable this
Creates a new hash table. If specified, "size" is how many values can be added to the hash table without rehashing.
Creates a mutable, minimally-sized clone of this table. The optional 'reserveCapacity' parameter is the number of additional values that can be added after cloning without forcing a rehash.
NOTE: Making capacity observable on frozen values prevents optimizations such as shrinking to fit on freeze. By making it mutable we preserve option value to add such optimizations in the future.
Like get(), but returns both the key and the value.
Like maybeGet(), but returns both the key and the value.
Get the first item in the Map, throws if the container is empty.
Get the first item in the Map as Some() if non-empty, or None() if empty.
Get the last item in the Map, throws if the container is empty.
Get the last item in the Map as Some() if non-empty, or None() if empty.
If k exists in this map, returns its value. Else, runs f() to get a new value, inserts it, and returns that new value.
Returns true if the Map has a value associated with the given key, else false.
Modifying Itemsmutable fun sourceset(k: K, v: V): Void
Associate key with value in this Map:
- If the key already exists in this Map, associates it to the new value.
- Else add the key/value association.
Like mset(), but throws a Duplicate() exception if the key already exists.
If the key does not already exist, inserts it and returns true. Else returns false.
Adds all of the key/value associations from the second Map to this one, replacing values for keys already present and adding key/value associations for keys not yet in this Map.
Remove the given key from this Map:
- If the key is present remove it and return true.
- Otherwise do nothing and return false.
Internal helper for iteration guarding against concurrent modifiction.