Java TreeMap, TreeSet, and PriorityQueue have something in common, they all maintain some kind of ordering.

HashSet is implemented using a HashMap, TreeSet is implemented using a TreeMap. The TreeMap itself is implemented using a red-black tree which is a self-balancing binary search tree.
On the other hand, a HashMap has an average time complexity of O(1) for put(), contains() and remove() operations. The worst-case time complexity for those operations is O(log n) since Java 8, and O(n) before that.
Big O complexities are as follows.

### PriorityQueue

log(n) operations: offer(), poll(), remove(), add()

O(1) opearations: peek(), size()

O(n) operations: remove(object), contains(object)

O(1) opearations: peek(), size()

O(n) operations: remove(object), contains(object)

### HashMap

log(n) operations: get(), put(), contains(), remove()

O(n) operations: clone(), equals(), hashCode(), toArray(), toString()

O(1) opearations: clear(), isEMpty(), size()

O(n) operations: clone(), equals(), hashCode(), toArray(), toString()

O(1) opearations: clear(), isEMpty(), size()

### TreeMap

log(n) operations: get(), put(), containsKey() and remove()

O(n) operations: clone(), equals(), hashCode(), toArray(), toString(), containsValue()

O(1) opearations: clear(), isEMpty(), size()

O(n) operations: clone(), equals(), hashCode(), toArray(), toString(), containsValue()

O(1) opearations: clear(), isEMpty(), size()

### TreeSet

log(n) operations: add(), contains(), remove()

O(1) opearations: clear(), first(), isEMpty(), size(), last(), pollFirst(), pollLast()

O(n) operations: clone(), equals(), hashCode(), toArray() and toString()

O(1) opearations: clear(), first(), isEMpty(), size(), last(), pollFirst(), pollLast()

O(n) operations: clone(), equals(), hashCode(), toArray() and toString()

This comment has been removed by a blog administrator.

ReplyDelete