tango.util.container.HashMap

License:

BSD style: see license.txt

Version:

Apr 2008: Initial release

Authors:

Kris

Since:

0.99.7

Based upon Doug Lea's Java collection package

class HashMap(K, V, alias Hash = Container.hash, alias Reap = Container.reap, alias Heap = Container.DefaultCollect) : IContainer!(V) ¶#

Hash table implementation of a Map

Iterator iterator ()
int opApply (int delegate(ref V value) dg)
int opApply (int delegate(ref K key, ref V value) dg)

bool get (K key, ref V element)
bool keyOf (V value, ref K key)
bool contains (V element)
bool containsPair (K key, V element)

bool removeKey (K key)
bool take (ref V element)
bool take (K key, ref V element)
size_t remove (V element, bool all)
size_t remove (IContainer!(V) e, bool all)
size_t replace (V oldElement, V newElement, bool all)
bool replacePair (K key, V oldElement, V newElement)

bool add (K key, V element)
bool opIndexAssign (V element, K key)
V    opIndex (K key)
V*   opIn_r (K key)

size_t size ()
bool isEmpty ()
V[] toArray (V[] dst)
HashMap dup ()
HashMap clear ()
HashMap reset ()
size_t buckets ()
float threshold ()
void buckets (size_t cap)
void threshold (float desired)

this(float f = Container.defaultLoadFactor) ¶#

Construct a HashMap instance

~this() ¶#

Clean up when deleted

Iterator iterator() [final] ¶#

Return a generic iterator for contained elements

int opApply(int delegate(ref K key, ref V value) dg) [final] ¶#

int opApply(int delegate(ref V value) dg) [final] ¶#

size_t size() [final] ¶#

Return the number of elements contained

bool add(K key, V element) [final] ¶#

Add a new element to the set. Does not add if there is an equivalent already present. Returns true where an element is added, false where it already exists (and was possibly updated). Time complexity: O(1) average; O(n) worst.

bool add(K key, V element, K function(K) retain) [final] ¶#

Add a new element to the set. Does not add if there is an equivalent already present. Returns true where an element is added, false where it already exists (and was possibly updated). This variation invokes the given retain function when the key does not already exist. You would typically use that to duplicate a char[], or whatever is required. Time complexity: O(1) average; O(n) worst.

bool get(K key, ref V element) [final] ¶#

Return the element associated with key

param:

a key

param:

a value reference (where returned value will reside)

Returns:

whether the key is contained or not

V* opIn_r(K key) [final] ¶#

Return the element associated with key

param:

a key

Returns:

a pointer to the located value, or null if not found

bool contains(V element) [final] ¶#

Does this set contain the given element? Time complexity: O(1) average; O(n) worst

bool keyOf(V value, ref K key) [final] ¶#

Time complexity: O(n).

bool containsKey(K key) [final] ¶#

Time complexity: O(1) average; O(n) worst.

bool containsPair(K key, V element) [final] ¶#

Time complexity: O(1) average; O(n) worst.

HashMap dup() [final] ¶#

Make an independent copy of the container. Does not clone elements Time complexity: O(n)

bool removeKey(K key) [final] ¶#

Time complexity: O(1) average; O(n) worst.

bool replaceKey(K key, K replace) [final] ¶#

Time complexity: O(1) average; O(n) worst.

bool replacePair(K key, V oldElement, V newElement) [final] ¶#

Time complexity: O(1) average; O(n) worst.

bool take(ref V element) [final] ¶#

Remove and expose the first element. Returns false when no more elements are contained Time complexity: O(n)

bool take(K key, ref V value) [final] ¶#

Remove and expose the element associated with key

param:

a key

param:

a value reference (where returned value will reside)

Returns:

whether the key is contained or not Time complexity: O(1) average, O(n) worst

bool opIndexAssign(V element, K key) [final] ¶#

Operator shortcut for assignment

V opIndex(K key) [final] ¶#

Operator retreival function

Throws NoSuchElementException where key is missing

size_t remove(IContainer!(V) e, bool all = false) [final] ¶#

Remove a set of values

size_t remove(V element, bool all = false) [final] ¶#

Removes element instances, and returns the number of elements removed Time complexity: O(1) average; O(n) worst

size_t replace(V oldElement, V newElement, bool all = false) [final] ¶#

Replace instances of oldElement with newElement, and returns the number of replacements

Time complexity: O(n).

HashMap clear() [final] ¶#

Clears the HashMap contents. Various attributes are retained, such as the internal table itself. Invoke reset() to drop everything.

Time complexity: O(n)

HashMap reset() [final] ¶#

Reset the HashMap contents. This releases more memory than clear() does

Time complexity: O(n)

size_t buckets() [final] ¶#

Return the number of buckets

Time complexity: O(1)

HashMap buckets(size_t cap) [final] ¶#

Set the desired number of buckets in the hash table. Any value greater than or equal to one is OK.

If different than current buckets, causes a version change Time complexity: O(n)

HashMap buckets(size_t cap, float threshold) [final] ¶#

Set the number of buckets for the given threshold and resize as required Time complexity: O(n)

HashMap cache(size_t chunk, size_t count = 0) [final] ¶#

Configure the assigned allocator with the size of each allocation block (number of nodes allocated at one time) and the number of nodes to pre-populate the cache with. Time complexity: O(n)

float threshold() [final] ¶#

Return the current load factor threshold

The Hash table occasionally checka against the load factor resizes itself if it has gone past it.

Time complexity: O(1)

void threshold(float desired) [final] ¶#

Set the resize threshold, and resize as required Set the current desired load factor. Any value greater than 0 is OK. The current load is checked against it, possibly causing a resize. Time complexity: O(n)

V[] toArray(V[] dst = null) [final] ¶#

Copy and return the contained set of values in an array, using the optional dst as a recipient (which is resized as necessary).

Returns a slice of dst representing the container values. Time complexity: O(n)

bool isEmpty() [final] ¶#

Is this container empty? Time complexity: O(1)

HashMap check() [final] ¶#

Sanity check

size_t instances(V element) [private] ¶#

Count the element instances in the set (there can only be 0 or 1 instances in a Set). Time complexity: O(n)

HashMap checkLoad() [private] ¶#

Check to see if we are past load factor threshold. If so, resize so that we are at half of the desired threshold.

void resize(size_t newCap) [private] ¶#

resize table to new capacity, rehashing all elements

bool removeNode(Ref node, Ref* list) [private] ¶#

Remove the indicated node. We need to traverse buckets for this, since we're singly-linked only. Better to save the per-node memory than to gain a little on each remove

Used by iterators only

HashMap clear(bool all) [private, final] ¶#

Clears the HashMap contents. Various attributes are retained, such as the internal table itself. Invoke reset() to drop everything.

Time complexity: O(n)

void increment() [private] ¶#

new element was added

void decrement(Ref p) [private] ¶#

element was removed

void mutate() [private] ¶#

set was changed

struct Iterator [private] ¶#

Iterator with no filtering

bool valid() ¶#: Did the container change underneath us?
bool next(ref K k, ref V v) ¶#: Accesses the next value, and returns false when there are no further values to traverse
V* next(ref K k) ¶#: Return a pointer to the next value, or null when there are no further values to traverse
int opApply(int delegate(ref K key, ref V value) dg) ¶#: Foreach support
bool remove() ¶#: Remove value at the current iterator location