An array hash table for storing integer key/value pairs
- The hash table can store duplicate keys, and multiple keys can map the same value. If duplicate keys exist, the order is FIFO.
- The hash table is open: in the case of a "hash collision", a single slot stores multiple entries, which are searched sequentially.
- The hash table is dynamic: the capacity is automatically increased and decreased.
- The hash table is never rehashed automatically, because this operation is time-consuming. Instead the user can decide if rehashing is necessary by checking the load factor.
- The value 0x80000000 is reserved and cannot be associated with a key.
Example:
var o = new polygonal.ds.IntIntHashTable(16);
for (i in 0...4) o.set(i, i);
trace(o); //outputs:
[ IntIntHashTable size=4 capacity=16 load=0.25
0 -> 0
1 -> 1
2 -> 2
3 -> 3
]
Constructor
new (slotCount:Int, initialCapacity:Int = -1)
Parameters:
slotCount | the total number of slots into which the hashed keys are distributed.
This defines the space-time trade off of this hash table.
A high |
|---|---|
capacity | the initial physical space for storing the elements at the time this hash table is initialized.
This also defines the minimum allowed size.
If omitted, the initial |
Variables
read onlycapacity:Int
The size of the allocated storage space for the elements.
If more space is required to accommodate new elements, capacity grows according to this.growthRate.
The capacity never falls below the initial size defined in the constructor and is usually a bit larger than this.size (mild overallocation).
read onlykey:Int = HashKey.next()
A unique identifier for this object.
A hash table transforms this key into an index of an array element by using a hash function.
read onlyloadFactor:Float
The load factor measure the "denseness" of a hash table and is proportional to the time cost to look up an entry.
E.g. assuming that the keys are perfectly distributed, a load factor of 4.0 indicates that each slot stores 4 keys, which have to be sequentially searched in order to find a value.
A high load factor thus indicates poor performance.
If the load factor gets too high, additional slots can be allocated by calling this.rehash().
reuseIterator:Bool = false
If true, reuses the iterator object instead of allocating a new one when calling this.iterator().
The default is false.
If this value is true, nested iterations will fail as only one iteration is allowed at a time.
Methods
clone (byRef:Bool = true, ?copier:Int ‑> Int):Collection<Int>
Duplicates this hash set by creating a deep copy (byRef and copier are ignored).
inlineextract (key:Int):Int
Removes the first occurrence of key and returns the value mapped to it.
Returns:
the value mapped to key or IntIntHashTable.KEY_ABSENT if key does not exist.
free ():Void
Destroys this object by explicitly nullifying all key/values.
If compiled with -D alchemy , always call this method when the life cycle of this object ends to prevent a memory leak.
inlineget (key:Int):Int
Returns the first value that is mapped to key or IntIntHashTable.KEY_ABSENT if key does not exist.
getAll (key:Int, out:Array<Int>):Int
Stores all values that are mapped to key in out or returns 0 if key does not exist.
Returns:
the total number of values mapped to key.
getCollisionCount ():Int
Counts the total number of collisions.
A collision occurs when two distinct keys are hashed into the same slot.
inlinegetFront (key:Int):Int
Returns the value that is mapped to key or IntIntHashTable.KEY_ABSENT if key does not exist.
Uses move-to-front-on-access which reduces access time when similar keys are frequently queried.
iterator ():Itr<Int>
Returns a new IntIntHashTableValIterator object to iterate over all values contained in this hash table.
The values are visited in a random order.
See:
keys ():Itr<Int>
Returns a new IntIntHashTableKeyIterator object to iterate over all keys stored in this map.
The keys are visited in a random order.
See:
pack ():IntIntHashTable
Free up resources by reducing the capacity of the internal container to the initial capacity.
rehash (slotCount:Int):IntIntHashTable
Redistributes all keys over slotCount.
This is an expensive operations as the hash table is rebuild from scratch.
inlineremap (key:Int, val:Int):Bool
Remaps the first occurrence of key to a new value val.
Returns:
true if val was successfully remapped to key.
remove (val:Int):Bool
Removes all occurrences of the value val.
Returns:
true if val was removed, false if val does not exist.
inlineset (key:Int, val:Int):Bool
Maps the value val to key.
The method allows duplicate keys.
To ensure unique keys either use this.hasKey() before this.set() or this.setIfAbsent().
Returns:
true if key was added for the first time, false if another instance of key was inserted.
inlinesetIfAbsent (key:Int, val:Int):Bool
Maps val to key in this map, but only if key does not exist yet.
Returns:
true if key was mapped to val for the first time.
inlineunset (key:Int):Bool
Removes the first occurrence of key.
Returns:
true if key is successfully removed.
unsetPair (key:Int, val:Int):Bool
Removes the first mapping from key to val.
Returns:
true if key is successfully removed.