-1

Everyone knows HashSet stores elements in buckets based on the size of the hashtable and the elements' hash code values.

But how does CopyOnWriteArraySet store elements? I thought it makes a snapshot of those buckets and copies them. Looks like it doesn't. Does it store them in 'normal' array 1 by 1 and checks equals()? Does it even use hashing principle?

khelwood
  • 55,782
  • 14
  • 81
  • 108
Ana Maria
  • 475
  • 2
  • 11
  • [Looks like](http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java) it's just a wrapper for `CopyOnWriteArrayList` which uses plain array storage. – khelwood Aug 22 '20 at 12:28

1 Answers1

1

CopyOnWriteArraySet is a Set-wrapper for CopyOnWriteArrayList, which stores its elements in an array, so it does not use hashing. That's why it doesn't have the O(1) lookup benefit of a HashSet.

The docs say it is only suitable for small sets.

khelwood
  • 55,782
  • 14
  • 81
  • 108
  • Thanks a lot! Do you know why they sticked with CopyOnWriteArrayList implementation? Couldn't they make something like a copy on HashSet for modifications? In that case we would have lookup benefit as well as elements would be copied into hashtable snapshot. Am I missing something? – Ana Maria Aug 22 '20 at 12:45
  • I don't know why anyone made any particular decision, but have a look at [this question](https://stackoverflow.com/questions/6720396/different-types-of-thread-safe-sets-in-java) and [this one](https://stackoverflow.com/q/29249714/3890632) discussing when CopyOnWriteArraySet is useful. – khelwood Aug 22 '20 at 12:49
  • Thanks, yeah I know when to use it. I am curious of why store its snapshot in plain array instead of buckets.. – Ana Maria Aug 22 '20 at 12:50
  • 1
    If "when to use it" specifies "only when really small sets are involved", that would be the reason that it is practical to use plain array storage instead of a hashtable. – khelwood Aug 22 '20 at 13:53
  • True, makes sense. Looking on memory perspective, it would also take less space, right? Because if it had used CopyOnWriteHashSet, it would need to store entire hashtable + linkedList on each bucket, am I right? – Ana Maria Aug 22 '20 at 16:40
  • It would need to store a more complex structure, and there would be more overhead if the whole structure is supposed to be copied each time an element is added. – khelwood Aug 22 '20 at 16:44