An array hash set for storing Hashable objects
Example:
class Element extends polygonal.ds.HashableItem {
var val:String;
public function new(val:String) {
super();
this.val = val;
}
public function toString():String {
return val;
}
}
...
var o = new polygonal.ds.HashSet<Element>(16);
var a = new Element("a");
var b = new Element("b");
var c = new Element("c");
o.set(a);
o.set(a);
o.set(b);
o.set(c);
o.set(c);
trace(o); //outputs:
[ HashSet size=3 capacity=16 load=0.19
a
b
c
]
Constructor
new (slotCount:Int, initialCapacity:Int = -1)
Parameters:
slotCount | the total number of slots into which the hashed values are distributed.
This defines the space-time trade off of this set.
A high |
---|---|
capacity | the initial physical space for storing the elements at the time this set 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 set and is proportional to the time cost to look up an entry.
E.g. assuming that the elements are perfectly distributed, a load factor of 4.0 indicates that each slot stores 4 elements, which have to be sequentially searched in order to find an element.
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:T ‑> T):Collection<T>
Creates and returns a shallow copy (structure only - default) or deep copy (structure & elements) of this set.
If byRef
is true, primitive elements are copied by value whereas objects are copied by reference.
If byRef
is false, the copier
function is used for copying elements. If omitted, clone()
is called on each element assuming all elements implement Cloneable
.
free ():Void
Destroys this object by explicitly nullifying all elements.
Improves GC efficiency/performance (optional).
getCollisionCount ():Int
Counts the total number of collisions.
A collision occurs when two distinct elements are hashed into the same slot.
inlinehasFront (val:T):Bool
Returns true if this set contains val
.
Uses move-to-front-on-access which reduces access time when similar elements are frequently queried.
iterator ():Itr<T>
Returns a new HashSetIterator object to iterate over all elements contained in this hash set.
The elements are visited in a random order.
See:
pack ():HashSet<T>
Free up resources by reducing the capacity of the internal container to the initial capacity.
rehash (slotCount:Int):HashSet<T>
Redistributes all elements over slotCount
.
This is an expensive operations as the set is rebuild from scratch.
remove (val:T):Bool
Removes val
.
Returns:
true if val
was successfully removed, false if val
does not exist.
inlineset (val:T):Bool
Adds val
to this set if possible.
Returns:
true if val
was added to this set, false if val
already exists.
inlineunset (val:T):Bool
Removes val
from this set if possible.
Returns:
true if val
was removed from this set, false if val
does not exist.