This project contains implementations of various data structures in C# plus some benchmarking applications and tests.

All structures in this library implement ordered dictionaries, that means System.Collections.Generic.IDictionary<int,T> and few additional functions: Higher(int x), Lower(int x), First(), Last(). Library contains following data structures:

• van Emde Boas Tree
• x-fast trie (with standard hashing or dynamic perfect hashing)
• y-fast trie (with standard hashing or dynamic perfect hashing)

Some data structures required red-black tree. Implementation comes from Mono. Also it is used as a point of reference in benchmarking.

Performance results of all important functions. All benchmarks were run on structures of size from 100 000 elements to 1 000 000 elements containing randomly picked elements. In case of find 100 000, search operation was performed 100 000 times. Time is in milliseconds, memory usage is in megabytes.