Exotic data structures in Java
Exotic data structures in Java!
The project is collection of less known data structures. The focus has been made
on balancing performance with simplicity and ease
of understanding. I tried to document all major
parts in implementation.
Currently there are:
Skip lists in performance are much like binary trees,
but they offer better locality of data. They are frequently
used as substitute for binary trees when it comes to concurrency.
They are randomized datastructures.
Implementation is different from typical skip list as
each node has some number of level nodes and they point to
nodes some hops ahead. This way some space requirements has been
reduced. It is a multiset holding sorted values, implementing
java Collection interface and resembling closely interface of
TreeSet.
| Operation | Performance |
|---|---|
| Insert | O(logN) |
| Delete | O(logN) |
| Search | O(logN) |
BTrees are frequently used to implement functional
data structures because they strike good balance between
tree (which is immutable) and array (which is mutable).
They are also a good way to sort large arrays. You can
find benchmarks here.
What is really interesting that similar to TimSort they are
adaptive (make use of natural order in data) so inserting ordered
values is much faster than average.
Implementation is multiset implementing Collection java interface,
and resembling SortedSet interface. The branching factor is configurable.
I found that branches=64 is optimal for ~4 000 000 elements.
Further optimization is exponential search rather than plain binary
search for intra-node searches, which makes it more robust for partially
sorted data (for which leaves are hot on borders)
| Operation | Performance |
|---|---|
| Insert | O(logN) |
| Delete | O(logN) |
| Search | O(logN) |
Immutable data structure that is more performant than
CopyOnWriteArray. It’s very similar to BTree except that
data is not sorted. Constant operations in table are in fact
always limited by O(depth*branching factor).
Performance is depending on branching factor. For small
branching modifications are fast at expense of reads. For big
branching factors modifications are slow.
| Operation | Performance |
|---|---|
| Insert | ~O(1) |
| Delete | ~O(1) |
| Search | O(N) |
| Index | ~O(1) |
