Comparing Set Implementations






Comparing Set Implementations

Figure shows the comparative performance of the different Set implementations. When you are choosing an implementation, of course, efficiency is only one of the factors you should take into account. Some of these implementations are specialized for specific situations; for example, EnumSet should always (and only) be used to represent sets of enum. Similarly, CopyOnWriteArraySet should only be used where set size will remain relatively small, read operations greatly outnumber writes, thread safety is required, and read-only iterators are acceptable.

Comparative performance of different Set implementations
 

add

contains

next

notes

HashSet

O(1)

O(1)

O(h/n)

h is the table capacity

LinkedHashSet

O(1)

O(1)

O(1)

 

CopyOnWriteArraySet

O(n)

O(n)

O(1)

 

EnumSet

O(1)

O(1)

O(1)

 

treeSet

O(log n)

O(log n)

O(log n)

 

ConcurrentSkipListSet

O(log n)

O(log n)

O(1)

 


That leaves the general-purpose implementations: HashSet, LinkedHashSet, TReeSet, and ConcurrentSkipListSet. The first three are not thread-safe, so can only be used in multi-threaded code either in conjunction with client-side locking, or wrapped in Collection.synchronizedSet (see Section 17.3.1). For single-threaded applications where there is no requirement for the set to be sorted, your choice is between HashSet and LinkedHashSet. If your application will be frequently iterating over the set, or if you require access ordering, LinkedHashSet is the implementation of choice.

Finally, if you require the set to sort its elements, the choice is between treeSet and ConcurrentSkipListSet. In a multi-threaded environment, ConcurrentSkipListSet is the only sensible choice. Even in single-threaded code ConcurrentSkipListSet may not show a significantly worse performance for small set sizes. For larger sets, however, or for applications in which there are frequent element deletions, treeSet will perform better if your application doesn't require thread safety.



 Python   SQL   Java   php   Perl 
 game development   web development   internet   *nix   graphics   hardware 
 telecommunications   C++ 
 Flash   Active Directory   Windows