Enhanced C#
Language of your choice: library documentation

Documentation moved to ecsharp.net

GitHub doesn't support HTTP redirects, so you'll be redirected in 3 seconds.

 All Classes Namespaces Functions Variables Enumerations Enumerator Properties Events Pages
Properties | Public Member Functions | Static Public Member Functions | Protected fields | List of all members
Loyc.Collections.Impl.KeylessHashtable< T > Class Template Referenceabstract

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:
Inheritance diagram for Loyc.Collections.Impl.KeylessHashtable< T >:
Loyc.Collections.Impl.KeylessHashtable< T, Int, Math >

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