Section 13.3. Comparing Set Implementations


13.3. Comparing Set Implementations

Table 13.1 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.

Table 13.1. 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.




Java Generics and Collections
Java Generics and Collections
ISBN: 0596527756
EAN: 2147483647
Year: 2006
Pages: 136

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net