Understanding the Set interface in Java

Question

I've been struggling to understand the whole abstract idea behind a custom implementation of a Set interface in Java. In our lectures we've implemented functional sets and even flag sets, both of which appear to be inherently recursive lists with functionalities built precisely for a set implementation.

At the end of the day, objects in the set are simply called from the set with a simple for-each loop even though some custom implementations do not remove objects from the list.

For example, in this functional set mentioned, {1,2,3} is represented as Add 3, Add 2, Add 1, Empty while a remove(2) method called directly after would look like Remove 2, Add 3, Add 2, Add 1, Empty. On what basis does Java then decide if the element is part of the set? Does it work solely on the add() and remove() methods to decide if the object still exists in the set?

I hope I'm being coherent enough.

"I hope I'm being coherent enough." - Not really ... I can't figure out what your 2nd question is really asking. — Stephen C
– Stephen C, Commented Dec 17, 2012 at 23:01

Stephen C · Accepted Answer · 2012-12-18 00:53:01Z

In our lectures we've implemented functional sets and even flag sets, both of which appear to be inherently recursive lists with functionalities built precisely for a set implementation.

Those implementions are not likely to be particularly instructive for Java Sets. Java sets are mutable ... not functional. Anyway, the general specification of the Java Set API is given by the javadoc for the java.util.Set interface.

On what basis does Java then decide if the element is part of the set?

The Set / Collection "contract" requires that it use equals(Object) to determine this. For example, the Collection.contains(Object) method is specified as follows:

"Returns true if this collection contains the specified element [o]. More formally, returns true if and only if this collection contains at least one element e such that (o==null ? e==null : o.equals(e))."

Different set implementations augment or replace this with the Comparable / Comparator APIs or Object.hashCode(). The details are in the respective implementation class javadocs.

However, there is no guarantee that a custom Set implementation will obey the contract.

Does it work solely on the add() and remove() methods to decide if the object still exists in the set?

Other Set methods (such as contains()) also need to know if an object is a set member ... if that is what you were asking.

I'm guessing for the case of custom implemented sets like the functional set mentioned, I kinda have to differentiate between my conceptual Set and the recursive list that I'm using as a basis to build and define my Set. Because elements in the Set are eventually just called out with a standard for-each loop iterating through the set (at least that's how the provided test module does it), does that mean the interface implicitly "looks through" the logs of add() and remove() (somewhat mentioned by @william.berg few answers below) to determine if the element should be contained in the Set?

Adel Boutros · Accepted Answer · 2012-12-17 22:46:44Z

Did you check the java source code provided by Oracle? It's a good place to start. Checking the methods in class Set would answer your question.

The main difference between set and list is that set do not respect the order. So if you add the items in a certain order, you are not garanteed to get them back in the same order. This is because Set optimizes the order to acheive the fastest access time possible. Therefore Set are fasert in most case.

Louis Wasserman · Accepted Answer · 2012-12-17 22:48:05Z

On what basis does Java then decide if the element is part of the set?

On whatever basis was programmed by the author of the functional set implementation. There's no such implementation built into Java, so we have no way of knowing if there's source code for you to check.

Alex MDC · Accepted Answer · 2012-12-17 22:51:29Z

Start at the right (from the Empty) and work to the left. What you end up with is the state of set at that point.

What your code is doing is creating a new immutable set from an existing set (starting with the Empty set) and a single change (either Add or Remove an element). This is how you would write a set in a functional language as everything is immutable.

william.berg · Accepted Answer · 2012-12-17 22:52:00Z

You're asking whether removing items that don't exist, or have been added twice, act in a way inconsistent with a theoretical set? Then no, Set learns and forgets members by add() and remove().

Collectives™ on Stack Overflow

Understanding the Set interface in Java

5 Answers 5

1 Comment

1 Comment

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

1 Comment

Comments

Comments

Comments

Related