Hashing Arrays ( h_array )

Definition

An instance A of the parameterized data type h_array<I,E> (hashing array) is an injective mapping from a hashed data type I , called the index type of A, to the set of variables of arbitrary type E, called the element type of A. We use A(i) to denote the variable indexed by i and we use dom(A) to denote the set of ``used indices''. This set is empty at the time of creation and is modified by array accesses. Each hashing array has an associated default value xdef. The variable A(i) has value xdef for all i $\notin$dom(A). If I is a user-defined type, you have to provide a Hash function (see Section User Defined Parameter Types).

Related data types are d_arrays, maps, and dictionaries.

#include < LEDA/core/h_array.h >

Creation

h_array<I,E>	A	creates an injective function a from I to the set of unused variables of type E, sets xdef to the default value of type E (if E has no default value then xdef stays undefined) and dom(A) to the empty set, and initializes A with a.
h_array<I,E>	A(E x)	creates an injective function a from I to the set of unused variables of type E, sets xdef to x and dom(A) to the empty set, and initializes A with a.
h_array<I,E>	A(E x, int table_sz)	as above, but uses an initial table size of table_sz instead of the default size 1.

Operations

E&	A[const I& i]	returns the variable A(i).
bool	A.defined(const I& i)	returns true if i $\in$ dom(A) and false otherwise.
void	A.undefine(const I& i)	removes i from dom(A) and sets A(i) to xdef.
void	A.clear()	makes dom(A) empty.
void	A.clear(const E& x)	makes dom(A) empty and sets xdef to x.
int	A.size()	returns | dom(A)|.
bool	A.empty()	returns true if A is empty, false otherwise.
void	A.set_default_value(const E& x)
		sets xdef to x.

Iteration

forall_defined(i, A) { ``the elements from dom(A) are successively assigned to i'' }
Remark: the current element may not be deleted resp. declared undefined during execution of the loop.

forall(x, A) { ``for all i $\in$ dom(A) the entries A[i] are successively assigned to x'' }.

Implementation

Hashing arrays are implemented by hashing with chaining. Access operations take expected time O(1). In many cases, hashing arrays are more efficient than dictionary arrays (cf. Dictionary Arrays).