Home » » Ullman set -- A clever data struture

Ullman set -- A clever data struture

This structure can be used as hashmap, but there're some things that hashmap can not do.
1) reset, or rather batch deleting all its members 2) iterating over its members only take O(n) time.
Disadvantage of Ullman set: can only process Integer smaller than N, if we can't know the upperbound of its members, Ullman set can do nothing about this, which in contrast is the advantage of hashmap.


Sent to you by jeffye via Google Reader:


via Research on Search by Dell Zhang on 2/23/09

The Ullman set is a clever data structure for a set of n integers densely distributed over a range, say from 0 to N-1. It uses O(N) space, and supports construction, destruction, adding, deleting, membership-test as well as cardinality operations in O(1) time. Moreover iterating over its members only takes O(n) time.


Things you can do from here:



Popular Posts