What standard containers allow you to find an element in them by its value for O (log (n))?

  • one
    HashSet has O (1) asymptotics, so it does not fit. SortedSet should come up. - VladD
  • one
    You see log (n) - think immediately about the tree (s) - Andrew Bystrov

1 answer 1

HashSet / HashMap has O (1) asymptotics at best, in case of collisions, either a list or a tree works there (if there are more than 8 values ​​in one node, if I'm not mistaken), and in this case, O (log (n)) may well turn out at worst.

If you need a collection that, on average, yields O (log (n)), then the TreeSet / TreeMap is built on a tree, therefore most likely we are talking about them. Or do you need all possible containers in Java with access time in O (log (n))? Interested in collections from all sorts of guava and Apache (all sorts of PatriciaTrie and TreeList) or is it just JDK?

If you are interested in more about the collection, see this my article .