Package xfast provides access to a sorted tree that treats integers as if they were words of m bits, where m can be 8, 16, 32, or 64. The advantage to storing integers as a trie of words is that operations can be performed in constant time depending on the size of the universe and not on the number of items in the trie.

The time complexity is as follows: Space: O(n log M) Insert: O(log M) Delete: O(log M) Search: O(log log M) Get: O(1)

where n is the number of items in the trie and M is the size of the universe, ie, 2^63-1 for 64 bit ints.

As you can see, for 64 bit ints, inserts and deletes can be performed in O(64), constant time which provides very predictable behavior in the best case.

A get by key can be performed in O(1) time and searches can be performed in O(6) time for 64 bit integers.

While x-tries have relatively slow insert, deletions, and consume a large amount of space, they form the top half of a y-fast trie which can insert and delete in O(log log M) time and consumes O(n) space.

xfast is referenced in 1 repository