HashTable

Hash table is a data structure that stores pairs of keys and values without any particular order.

This $(D_PSYMBOL HashTable) is implemented using closed hashing. Hash collisions are resolved with linear probing.

Key should be hashable with hasher. hasher is a callable that accepts an argument of type Key and returns a hash value for it ($(D_KEYWORD size_t)).

struct HashTable (

Key

Value

alias hasher = hash

) if (

isHashFunction!(hasher, Key)

) {

alias KeyValue = HashArray.Bucket.KV;

alias Range = .Range!HashArray;

alias ConstRange = .Range!(const HashArray);

alias ByKey = .ByKey!(const HashArray);

alias ByValue = .ByValue!HashArray;

alias ConstByValue = .ByValue!(const HashArray);

this(size_t n, Allocator allocator);

this(Allocator allocator);

this(S init, Allocator allocator);

this(R range, Allocator allocator);

this(KeyValue[n] array, Allocator allocator);

typeof(this) opAssign(S that);

shared(Allocator) allocator [@property getter];

size_t capacity [@property getter];

size_t length [@property getter];

bool empty [@property getter];

void clear();

size_t bucketCount [@property getter];

enum size_t maxBucketCount;

Value opIndexAssign(Value value, Key key);

size_t insert(KeyValue keyValue);

size_t insert(R range);

Value opIndex(T key);

size_t remove(Key key);

bool opBinaryRight(T key);

void rehash(size_t n);

Range opIndex();

ConstRange opIndex();

ByKey byKey();

ByValue byValue();

ConstByValue byValue();

}

Constructors

this this(size_t n, Allocator allocator)
this(Allocator allocator): Constructor.
this this(S init, Allocator allocator): Initializes this HashTable from another one.
this this(R range, Allocator allocator): Constructs the hash table from a forward range.
this this(KeyValue[n] array, Allocator allocator): Initializes the hash table from a static array.

Members

Aliases

ByKey alias ByKey = .ByKey!(const HashArray)
ByValue alias ByValue = .ByValue!HashArray
ConstByValue alias ConstByValue = .ByValue!(const HashArray)
ConstRange alias ConstRange = .Range!(const HashArray): The range types for $(D_PSYMBOL HashTable).
KeyValue alias KeyValue = HashArray.Bucket.KV: Type of the key-value pair stored in the hash table.
Range alias Range = .Range!HashArray: The range types for $(D_PSYMBOL HashTable).

Functions

byKey ByKey byKey(): Returns a bidirectional range that iterats over the keys of this $(D_PSYMBOL HashTable).
byValue ByValue byValue()
ConstByValue byValue(): Returns a bidirectional range that iterats over the values of this $(D_PSYMBOL HashTable).
clear void clear(): Removes all elements.
insert size_t insert(KeyValue keyValue): Inserts a new element in the hash table.
insert size_t insert(R range): Inserts a forward range of key/value pairs into the hash table.
opAssign typeof(this) opAssign(S that): Assigns another hash table.
opBinaryRight bool opBinaryRight(T key): Looks for key in this hash table.
opIndex Value opIndex(T key): Find the element with the key key.
opIndex Range opIndex()
ConstRange opIndex(): Returns a bidirectional range whose element type is a tuple of a key and the respective value.
opIndexAssign Value opIndexAssign(Value value, Key key): Inserts a new value at key or reassigns the element if key already exists in the hash table.
rehash void rehash(size_t n): Sets the number of buckets in the container to at least n and rearranges all the elements according to their hash values.
remove size_t remove(Key key): Removes the element with the key key.

Properties

allocator shared(Allocator) allocator [@property getter]
bucketCount size_t bucketCount [@property getter]: Returns current bucket count in the container.
capacity size_t capacity [@property getter]: Maximum amount of elements this $(D_PSYMBOL HashTable) can hold without resizing and rehashing. Note that it doesn't mean that the $(D_PSYMBOL Set) will hold exactly $(D_PSYMBOL capacity) elements. $(D_PSYMBOL capacity) tells the size of the container under a best-case distribution of elements.
empty bool empty [@property getter]: Tells whether the container contains any elements.
length size_t length [@property getter]: Returns the number of elements in the container.

Variables

maxBucketCount enum size_t maxBucketCount;: The maximum number of buckets the container can have.

Parameters

Key: Key type.
Value: Value type.
hasher: Hash function for Key.