Loyc.Collections.Impl.KeylessHashtable< T > Class Template Reference

A fairly obscure space-saving hashtable that offers no built-in way to store keys, only values. Because there are no keys, the hashtable cannot be rehashed when it is full, and searching for a given key finds all values in the same bucket, some of which may be unrelated. More...

---

Source file:

• /Core/Loyc.Collections/Other/KeylessHashtable.cs

Inheritance diagram for Loyc.Collections.Impl.KeylessHashtable< T >:

Remarks

A fairly obscure space-saving hashtable that offers no built-in way to store keys, only values. Because there are no keys, the hashtable cannot be rehashed when it is full, and searching for a given key finds all values in the same bucket, some of which may be unrelated.

My primary primary motivation for this data structure is compactness. It's comparable to a "counting bloom filter", in that searching for a key can find false positives, but not false negatives, but it offers the additional feature that one or more values can be associated with each key.

The size per entry dependends on the size of the hashtable. This data structure is the most compact when its size is limited to 65536 entries and buckets; its overhead doubles when you exceed this limit, since "shorts" become "ints".

The Count is allowed to exceed the Capacity, but it is not allowed to cross a size threshold (255 or 65535). Capacity returns the number of buckets, so if Count exceeds Capacity, it simply means there are more items than buckets, so there will be a larger-than-normal amount of "false positives" (multiple items will typically be returned from a search).

The size requirement per entry is 2 bytes (plus sizeof(T)) for a table of size 255 or less, 4 bytes (plus sizeof(T)) for a table of size 65535 or less, and 8 bytes (plus sizeof(T)) for larger tables. Prime number sizes are generally preferred for best performance.

The memory for buckets (1-4 bytes) is allocated up-front, but other memory is allocated on-demand. For example, if you create a new hashtable with capacity 251 and add 50 items, 251 bytes are allocated up-front, but less than 100 * (1+sizeof(T)) additional bytes are allocated.

By its very nature, KeylessHashtable allows multiple values to be associated with a single key.

A normal hashtable could theoretically be built on top of this one by storing the key and value together in type T.

Properties
int	Count [get]
abstract int	Capacity [get]

Public Member Functions
void	Add< K > (K key, T value)
bool	Remove< K > (K key, T value)
IEnumerator< T >	Find< K > (K key)
abstract void	Add (uint hashCode, T value)
abstract bool	Remove (uint hashCode, T value)
abstract int	Remove (uint hashCode, Predicate< T > shouldRemove, int maxToRemove)
abstract void	Clear ()
abstract IEnumerator< T >	GetEnumerator ()
abstract IEnumerator< T >	Find (uint hashCode)

Static Public Member Functions
static KeylessHashtable< T >	New (int numBuckets)
static KeylessHashtable< T >	New (int numBuckets, int maxCount)

Protected fields
T[]	_values
int	_firstUnused = -1
int	_count