Java Tutorial/Collections/Set

An IdentitySet that uses reference-equality instead of object-equality

/*
 * Copyright 2005 Ralf Joachim
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
/**
 * An IdentitySet that uses reference-equality instead of object-equality. According
 * to its special function it violates some design contracts of the <code>Set</code>
 * interface.
 * 
 * @author 
 * @version $Revision: 7491 $ $Date: 2006-04-13 10:49:49 -0600 (Thu, 13 Apr 2006) $
 * @since 0.9.9
 */
public final class IdentitySet implements Set {
    //--------------------------------------------------------------------------
    /** Default number of buckets. */
    private static final int    DEFAULT_CAPACITY = 17;
    
    /** Default load factor. */
    private static final float  DEFAULT_LOAD = 0.75f;
    
    /** Default number of entries. */
    private static final int    DEFAULT_ENTRIES = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD);
    
    /** Default factor to increment capacity. */
    private static final int    DEFAULT_INCREMENT = 2;
    
    /** First prime number to check is 3 as we prevent 2 by design. */
    private static final int    FIRST_PRIME_TO_CHECK = 3;
    
    //--------------------------------------------------------------------------
    /** Number of buckets. */
    private int                     _capacity;
    
    /** Maximum number of entries before rehashing. */
    private int                     _maximum;
    /** Buckets. */
    private Entry[]                 _buckets;
    /** Number of map entries. */
    private int                     _entries = 0;
    //--------------------------------------------------------------------------
    /**
     * Construct a set with default capacity.
     */
    public IdentitySet() {
        _capacity = DEFAULT_CAPACITY;
        _maximum = DEFAULT_ENTRIES;
        _buckets = new Entry[DEFAULT_CAPACITY];
    }
    
    /**
     * Construct a set with given capacity.
     * 
     * @param  capacity     The capacity of entries this set should be initialized with.
     */
    public IdentitySet(final int capacity) {
        _capacity = capacity;
        _maximum = (int) (capacity * DEFAULT_LOAD);
        _buckets = new Entry[capacity];
    }
    
    /**
     * {@inheritDoc}
     * @see java.util.Collection#clear()
     */
    public void clear() {
        _capacity = DEFAULT_CAPACITY;
        _maximum = DEFAULT_ENTRIES;
        _buckets = new Entry[DEFAULT_CAPACITY];
        _entries = 0;
    }
    /**
     * {@inheritDoc}
     * @see java.util.Collection#size()
     */
    public int size() { return _entries; }
    /**
     * {@inheritDoc}
     * @see java.util.Collection#isEmpty()
     */
    public boolean isEmpty() { return (_entries == 0); }
    /**
     * {@inheritDoc}
     * @see java.util.Collection#add(java.lang.Object)
     */
    public boolean add(final Object key) {
        int hash = System.identityHashCode(key);
        int index = hash % _capacity;
        if (index < 0) { index = -index; }
        Entry entry = _buckets[index];
        Entry prev = null;
        while (entry != null) {
            if (entry.getKey() == key) {
                // There is already a mapping for this key.
                return false;
            }
            prev = entry;
            entry = entry.getNext();
        }
        if (prev == null) {
            // There is no previous entry in this bucket.
            _buckets[index] = new Entry(key, hash);
        } else {
            // Next entry is empty so we have no mapping for this key.
            prev.setNext(new Entry(key, hash));
        }
        _entries++;
        if (_entries > _maximum) { rehash(); }
        return true;
    }
    /**
     * Rehash the map into a new array with increased capacity.
     */
    private void rehash() {
        long nextCapacity = _capacity * DEFAULT_INCREMENT;
        if (nextCapacity > Integer.MAX_VALUE) { return; }
        nextCapacity = nextPrime(nextCapacity);
        if (nextCapacity > Integer.MAX_VALUE) { return; }
        int newCapacity = (int) nextCapacity;
        Entry[] newBuckets = new Entry[newCapacity];
        Entry entry = null;
        Entry temp = null;
        Entry next = null;
        int newIndex = 0;
        for (int index = 0; index < _capacity; index++) {
            entry = _buckets[index];
            while (entry != null) {
                next = entry.getNext();
                newIndex = entry.getHash() % newCapacity;
                if (newIndex < 0) { newIndex = -newIndex; }
                temp = newBuckets[newIndex];
                if (temp == null) {
                    // First entry of the bucket.
                    entry.setNext(null);
                } else {
                    // Hook entry into beginning of the buckets chain.
                    entry.setNext(temp);
                }
                newBuckets[newIndex] = entry;
                entry = next;
            }
        }
        _capacity = newCapacity;
        _maximum = (int) (newCapacity * DEFAULT_LOAD);
        _buckets = newBuckets;
    }
    /**
     * Find next prime number greater than minimum.
     * 
     * @param  minimum  The minimum (exclusive) value of the next prime number.
     * @return The next prime number greater than minimum.
     */
    private long nextPrime(final long minimum) {
        long candidate = ((minimum + 1) / 2) * 2 + 1;
        while (!isPrime(candidate)) { candidate += 2; }
        return candidate;
    }
    /**
     * Check for prime number.
     * 
     * @param  candidate  Number to be checked for being a prime number.
     * @return <code>true</code> if the given number is a prime number
     *         <code>false</code> otherwise.
     */
    private boolean isPrime(final long candidate) {
        if ((candidate / 2) * 2 == candidate) { return false; }
        long stop = candidate / 2;
        for (long i = FIRST_PRIME_TO_CHECK; i < stop; i += 2) {
            if ((candidate / i) * i == candidate) { return false; }
        }
        return true;
    }
    /**
     * {@inheritDoc}
     * @see java.util.Collection#contains(java.lang.Object)
     */
    public boolean contains(final Object key) {
        int hash = System.identityHashCode(key);
        int index = hash % _capacity;
        if (index < 0) { index = -index; }
        Entry entry = _buckets[index];
        while (entry != null) {
            if (entry.getKey() == key) { return true; }
            entry = entry.getNext();
        }
        return false;
    }
    /**
     * {@inheritDoc}
     * @see java.util.Collection#remove(java.lang.Object)
     */
    public boolean remove(final Object key) {
        int hash = System.identityHashCode(key);
        int index = hash % _capacity;
        if (index < 0) { index = -index; }
        Entry entry = _buckets[index];
        Entry prev = null;
        while (entry != null) {
            if (entry.getKey() == key) {
                // Found the entry.
                if (prev == null) {
                    // First element in bucket matches.
                    _buckets[index] = entry.getNext();
                } else {
                    // Remove the entry from the chain.
                    prev.setNext(entry.getNext());
                }
                _entries--;
                return true;
            }
            prev = entry;
            entry = entry.getNext();
        }
        return false;
    }
    
    /**
     * {@inheritDoc}
     * @see java.util.Collection#iterator()
     */
    public Iterator iterator() {
        return new IdentityIterator();
    }
    
    /**
     * {@inheritDoc}
     * @see java.util.Collection#toArray()
     */
    public Object[] toArray() {
        Object[] result = new Object[_entries];
        int j = 0;
        for (int i = 0; i < _capacity; i++) {
            Entry entry = _buckets[i];
            while (entry != null) {
                result[j++] = entry.getKey();
                entry = entry.getNext();
            }
        }
        
        return result;
    }
    
    /**
     * {@inheritDoc}
     * @see java.util.Collection#toArray(java.lang.Object[])
     */
    public Object[] toArray(final Object[] a) {
        Object[] result = a;
        if (result.length < _entries) {
            result = (Object[]) java.lang.reflect.Array.newInstance(
                    result.getClass().getComponentType(), _entries);
        }
        
        int j = 0;
        for (int i = 0; i < _capacity; i++) {
            Entry entry = _buckets[i];
            while (entry != null) {
                result[j++] = entry.getKey();
                entry = entry.getNext();
            }
        }
        
        while (j < result.length) {
            result[j++] = null;
        }
        
        return result;
    }
    
    /**
     * In contrast with the design contract of the <code>Set</code> interface this method
     * has not been implemented and throws a <code>UnsupportedOperationException</code>.
     * 
     * {@inheritDoc}
     * @see java.util.Set#containsAll
     */
    public boolean containsAll(final Collection c) {
        throw new UnsupportedOperationException();
    }
    
    /**
     * This optional method has not been implemented for <code>IdentitySet</code> instead
     * it throws a <code>UnsupportedOperationException</code> as defined in the
     * <code>Set</code> interface.
     * 
     * {@inheritDoc}
     * @see java.util.Set#addAll
     */
    public boolean addAll(final Collection c) {
        throw new UnsupportedOperationException();
    }
    
    /**
     * This optional method has not been implemented for <code>IdentitySet</code> instead
     * it throws a <code>UnsupportedOperationException</code> as defined in the
     * <code>Set</code> interface.
     * 
     * {@inheritDoc}
     * @see java.util.Set#removeAll
     */
    public boolean removeAll(final Collection c) {
        throw new UnsupportedOperationException();
    }
    
    /**
     * This optional method has not been implemented for <code>IdentitySet</code> instead
     * it throws a <code>UnsupportedOperationException</code> as defined in the
     * <code>Set</code> interface.
     * 
     * {@inheritDoc}
     * @see java.util.Set#retainAll
     */
    public boolean retainAll(final Collection c) {
        throw new UnsupportedOperationException();
    }
    
    //--------------------------------------------------------------------------
    /**
     * An entry of the <code>IdentitySet</code>.
     */
    public final class Entry {
        /** Key of entry. */
        private Object  _key;
        
        /** Identity hashcode of key. */
        private int     _hash;
        
        /** Reference to next entry. */
        private Entry   _next = null;
        /**
         * Construct an entry.
         * 
         * @param key    Key of entry.
         * @param hash   Identity hashcode of key.
         */
        public Entry(final Object key, final int hash) {
            _key = key;
            _hash = hash;
        }
        /**
         * Get key of entry.
         *
         * @return Key of entry.
         */
        public Object getKey() { return _key; }
        /**
         * Get identity hashcode of key.
         *
         * @return Identity hashcode of key.
         */
        public int getHash() { return _hash; }
        /**
         * Set reference to next entry.
         *
         * @param  next     New reference to next entry.
         */
        public void setNext(final Entry next) { _next = next; }
        /**
         * Get reference to next entry.
         *
         * @return Reference to next entry.
         */
        public Entry getNext() { return _next; }
    }
    //--------------------------------------------------------------------------
    /**
     * An iterator over all entries of the <code>IdentitySet</code>.
     */
    private class IdentityIterator implements Iterator {
        /** Index of the current bucket. */
        private int     _index = 0; 
        
        /** The next entry to be returned. <code>null</code> when there is none. */
        private Entry   _next = _buckets[0];
        /**
         * Construct a iterator over all entries of the <code>IdentitySet</code>.
         */
        public IdentityIterator() {
            if (_entries > 0) {
                while ((_next == null) && (++_index < _capacity)) {
                    _next = _buckets[_index];
                }
            }
        }
        /**
         * {@inheritDoc}
         * @see java.util.Iterator#hasNext()
         */
        public boolean hasNext() {
            return (_next != null);
        }
        /**
         * {@inheritDoc}
         * @see java.util.Iterator#next()
         */
        public Object next() {
            Entry entry = _next;
            if (entry == null) { throw new NoSuchElementException(); }
            
            _next = entry.getNext();
            while ((_next == null) && (++_index < _capacity)) {
                _next = _buckets[_index];
            }
            
            return entry.getKey();
        }
        
        /**
         * This optional method is not implemented for <code>IdentityIterator</code>
         * instead it throws a <code>UnsupportedOperationException</code> as defined
         * in the <code>Iterator</code> interface.
         * 
         * @see java.util.Iterator#remove()
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    //--------------------------------------------------------------------------
}

A thin wrapper around a List transforming it into a modifiable Set.

import java.io.Serializable;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/**
 * A thin wrapper around a <code>List</code> transforming it into a modifiable
 * <code>Set</code>.
 * 
 * @version <tt>$Revision: 2800 $</tt>
 * @author 
 */
@SuppressWarnings("unchecked")
public class ListSet extends AbstractSet implements Set, Cloneable, Serializable {
  /** The serialVersionUID */
  private static final long serialVersionUID = 7333619218072079496L;
  /** The <tt>List</tt> which will be used for element storage. */
  protected final List list;
  /**
   * Construct a <tt>ListSet</tt>.
   * 
   * @param list
   *          The <tt>List</tt> which will be used for element storage.
   * 
   * @throws IllegalArgumentException
   *           List is <tt>null</tt> or contains duplicate entries.
   */
  public ListSet(final List list) {
    if (list == null)
      throw new RuntimeException("list");
    // make sure there are no duplicates
    int size = list.size();
    for (int i = 0; i < size; i++) {
      Object obj = list.get(i);
      if (list.indexOf(obj) != list.lastIndexOf(obj)) {
        throw new IllegalArgumentException("list contains duplicate entries");
      }
    }
    this.list = list;
  }
  /**
   * Construct a <tt>ListSet</tt> using an <tt>ArrayList</tt> for backing.
   */
  public ListSet() {
    this(new ArrayList());
  }
  /**
   * Construct a <tt>ListSet</tt> using an <tt>ArrayList</tt> for backing
   * and populated with the given elements.
   * 
   * @param elements
   *          The elements for the list.
   */
  public ListSet(final Collection elements) {
    this(new ArrayList(elements));
  }
  public List getList() {
    return list;
  }
  /**
   * Return the size of the set.
   * 
   * @return The size of the set.
   */
  public int size() {
    return list.size();
  }
  /**
   * Return an iteration over the elements in the set.
   * 
   * @return An iteration over the elements in the set.
   */
  public Iterator iterator() {
    return list.iterator();
  }
  /**
   * Add an element to the set.
   * 
   * @param obj
   *          Element to add to the set.
   * @return True if the element was added.
   */
  public boolean add(final Object obj) {
    boolean added = false;
    if (!list.contains(obj)) {
      added = list.add(obj);
    }
    return added;
  }
  /**
   * Returns <tt>true</tt> if this set contains no elements.
   * 
   * @return <tt>true</tt> if this set contains no elements.
   */
  public boolean isEmpty() {
    return list.isEmpty();
  }
  /**
   * Returns <tt>true</tt> if this set contains the specified element.
   * 
   * @param obj
   *          Element whose presence in this set is to be tested.
   * @return <tt>true</tt> if this set contains the specified element.
   */
  public boolean contains(final Object obj) {
    return list.contains(obj);
  }
  /**
   * Removes the given element from this set if it is present.
   * 
   * @param obj
   *          Object to be removed from this set, if present.
   * @return <tt>true</tt> if the set contained the specified element.
   */
  public boolean remove(final Object obj) {
    return list.remove(obj);
  }
  /**
   * Removes all of the elements from this set.
   */
  public void clear() {
    list.clear();
  }
  /**
   * Returns a shallow copy of this <tt>ListSet</tt> instance.
   * 
   * @return A shallow copy of this set.
   */
  public Object clone() {
    try {
      return super.clone();
    } catch (CloneNotSupportedException e) {
      throw new InternalError();
    }
  }
}

A weak HashSet: element stored in the WeakHashSet might be garbage collected

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software 
 * distributed under the License is distributed on an "AS IS" BASIS, 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
 * See the License for the specific language governing permissions and 
 * limitations under the License.
 */

import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.HashSet;
import java.util.Iterator;
/**
 * A weak HashSet. An element stored in the WeakHashSet might be
 * garbage collected, if there is no strong reference to this element.
 */
public class WeakHashSet extends HashSet {
    /**
     * Helps to detect garbage collected values.
     */
    ReferenceQueue queue = new ReferenceQueue();
    /**
     * Returns an iterator over the elements in this set.  The elements
     * are returned in no particular order.
     *
     * @return an Iterator over the elements in this set.
     */
    public Iterator iterator() {
        // remove garbage collected elements
        processQueue();
        // get an iterator of the superclass WeakHashSet
        final Iterator i = super.iterator();
        return new Iterator() {
            public boolean hasNext() {
                return i.hasNext();
            }
            public Object next() {
                // unwrap the element
                return getReferenceObject((WeakReference) i.next());
            }
            public void remove() {
                // remove the element from the HashSet
                i.remove();
            }
        };
    }
    /**
     * Returns <code>true</code> if this set contains the specified element.
     *
     * @param o element whose presence in this set is to be tested.
     * @return <code>true</code> if this set contains the specified element.
     */
    public boolean contains(Object o) {
        return super.contains(WeakElement.create(o));
    }
    /**
     * Adds the specified element to this set if it is not already
     * present.
     *
     * @param o element to be added to this set.
     * @return <code>true</code> if the set did not already contain the specified
     * element.
     */
    public boolean add(Object o) {
        processQueue();
        return super.add(WeakElement.create(o, this.queue));
    }
    /**
     * Removes the given element from this set if it is present.
     *
     * @param o object to be removed from this set, if present.
     * @return <code>true</code> if the set contained the specified element.
     */
    public boolean remove(Object o) {
        boolean ret = super.remove(WeakElement.create(o));
        processQueue();
        return ret;
    }
    /**
     * A convenience method to return the object held by the
     * weak reference or <code>null</code> if it does not exist.
     */
    private final Object getReferenceObject(WeakReference ref) {
        return (ref == null) ? null : ref.get();
    }
    /**
     * Removes all garbage collected values with their keys from the map.
     * Since we don"t know how much the ReferenceQueue.poll() operation
     * costs, we should call it only in the add() method.
     */
    private final void processQueue() {
        WeakElement wv = null;
        while ((wv = (WeakElement) this.queue.poll()) != null) {
            super.remove(wv);
        }
    }
    /**
     * A WeakHashSet stores objects of class WeakElement.
     * A WeakElement wraps the element that should be stored in the WeakHashSet.
     * WeakElement inherits from java.lang.ref.WeakReference.
     * It redefines equals and hashCode which delegate to the corresponding methods
     * of the wrapped element.
     */
    static private class WeakElement extends WeakReference {
        private int hash; /* Hashcode of key, stored here since the key
                               may be tossed by the GC */
        private WeakElement(Object o) {
            super(o);
            hash = o.hashCode();
        }
        private WeakElement(Object o, ReferenceQueue q) {
            super(o, q);
            hash = o.hashCode();
        }
        private static WeakElement create(Object o) {
            return (o == null) ? null : new WeakElement(o);
        }
        private static WeakElement create(Object o, ReferenceQueue q) {
            return (o == null) ? null : new WeakElement(o, q);
        }
        /* A WeakElement is equal to another WeakElement iff they both refer to objects
               that are, in turn, equal according to their own equals methods */
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof WeakElement))
                return false;
            Object t = this.get();
            Object u = ((WeakElement) o).get();
            if (t == u) 
                return true;
            if ((t == null) || (u == null))
                return false;
            return t.equals(u);
        }
        public int hashCode() {
            return hash;
        }
    }
}

Comparable with a sorted collection.

import java.util.Set;
import java.util.TreeSet;
class Product implements Comparable<Product> {
  String prodName;
  int prodID;
  Product(String str, int id) {
    prodName = str;
    prodID = id;
  }
  public int compareTo(Product p2) {
    return prodName.rupareToIgnoreCase(p2.prodName);
  }
  public boolean equals(Object p2) {
    return prodName.rupareToIgnoreCase(((Product) p2).prodName) == 0;
  }
}
public class Main {
  public static void main(String args[]) {
    Set<Product> prodList = new TreeSet<Product>();
    prodList.add(new Product("A", 1));
    prodList.add(new Product("B", 0));
    prodList.add(new Product("C", 2));
    prodList.add(new Product("D", 4));
    for (Product p : prodList)
      System.out.printf("%-14s ID: %d\n", p.prodName, p.prodID);
  }
}

Concurrent set

/*
 * Copyright Ben Meadowcroft 2006
 * Version: $Revision: 1.1 $
 * Date:    $Date: 2006/02/24 22:24:46 $
 */
//com.agnotion.util.concurrent;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
/**
 * @author Ben Meadowcroft
 */
public class ConcurrentSet<Q> implements Set<Q>
{
  /** Piggy back off a concurrent hash map to get "weekly consistent" iterators etc */
  private ConcurrentHashMap<Q, Object> map = new ConcurrentHashMap<Q, Object>();
  /**
   * 
   */
  public ConcurrentSet() {
    this.map = new ConcurrentHashMap<Q, Object>();
  }
  /* (non-Javadoc)
   * @see java.util.Set#add(E)
   */
  public boolean add(Q item) {
    boolean containsObj = map.containsKey(item);
    if (containsObj == false)
    {
      /* ConcurrentHashMap doesn"t allow null keys or values so we simply 
       * use the item added to the collection as the key and the Boolean 
       * TRUE object as the value. */
      map.put(item, Boolean.TRUE);
    }
    return !containsObj;
  }
  /* (non-Javadoc)
   * @see java.util.Set#addAll(java.util.Collection)
   */
  public boolean addAll(Collection<? extends Q> items) {
    boolean changed = false;
    for (Q item : items)
    {
      /* update flag determining whether set has changed or not */
      changed = add(item) || changed;
    }
    return changed;
  }
  /* (non-Javadoc)
   * @see java.util.Set#clear()
   */
  public void clear() {
    map.clear();
  }
  /* (non-Javadoc)
   * @see java.util.Set#contains(java.lang.Object)
   */
  public boolean contains(Object item) {
    return map.containsKey(item);
  }
  /* (non-Javadoc)
   * @see java.util.Set#containsAll(java.util.Collection)
   */
  public boolean containsAll(Collection<?> items) {
    return map.keySet().containsAll(items);
  }
  /* (non-Javadoc)
   * @see java.util.Set#isEmpty()
   */
  public boolean isEmpty() {
    return map.isEmpty();
  }
  /* (non-Javadoc)
   * @see java.util.Set#iterator()
   */
  public Iterator<Q> iterator() {
    return map.keySet().iterator();
  }
  /* (non-Javadoc)
   * @see java.util.Set#remove(java.lang.Object)
   */
  public boolean remove(Object item) {
    /* we double up argument as both key and value */
    return map.remove(item, Boolean.TRUE);
  }
  /* (non-Javadoc)
   * @see java.util.Set#removeAll(java.util.Collection)
   */
  public boolean removeAll(Collection<?> items) {
    return map.keySet().removeAll(items);
  }
  /* (non-Javadoc)
   * @see java.util.Set#retainAll(java.util.Collection)
   */
  public boolean retainAll(Collection<?> items) {
    return map.keySet().retainAll(items);
  }
  /* (non-Javadoc)
   * @see java.util.Set#size()
   */
  public int size() {
    return map.size();
  }
  /* (non-Javadoc)
   * @see java.util.Set#toArray()
   */
  public Object[] toArray() {
    return map.keySet().toArray();
  }
  /* (non-Javadoc)
   * @see java.util.Set#toArray(T[])
   */
  public <T> T[] toArray(T[] array) {
    return map.keySet().toArray(array);
  }

}

Convert a List to a Set

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
  public static void main(String[] args) {
    List<String> myList = new ArrayList<String>();
    myList.add("A");
    myList.add("B");
    myList.add("C");
    myList.add("D");
    Set<String> mySet = new HashSet<String>(myList);
    for (Object theFruit : mySet)
      System.out.println(theFruit);
  }
}
/*
D
A
B
C
*/

Convert an ArrayList to HashSet

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
  public static void main(String[] args) {
    List<String> myList = new ArrayList<String>();
    myList.add("A");
    myList.add("B");
    myList.add("C");
    myList.add("D");
    Set<String> mySet = new HashSet<String>(myList);
    for (Object theFruit : mySet)
      System.out.println(theFruit);
  }
}
/*
D
A
B
C
*/

Convert Set into array

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
  public static void main(String[] args) {
    Set<Object> set = new HashSet<Object>();
    set.add("A");
    set.add(new Long(10));
    set.add(new Date());
    List<Object> list = new ArrayList<Object>(set);
    Object[] objects = list.toArray();
    for (int i = 0; i < objects.length; i++) {
      Object object = objects[i];
      System.out.println("Object = " + object);
    }
  }
}

Convert Set into List

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
  public static void main(String[] args) {
    Set<Object> set = new HashSet<Object>();
    set.add("A");
    set.add(new Long(10));
    set.add(new Date());
    List<Object> list = new ArrayList<Object>(set);
    for (int i = 0; i < list.size(); i++) {
      Object o = list.get(i);
      System.out.println("Object = " + o);
    }
  }
}

Copy all the elements from set2 to set1 (set1 += set2), set1 becomes the union of set1 and set2

import java.util.HashSet;
import java.util.Set;
public class Main {
  public static void main(String[] argv) throws Exception {
    Set set1 = new HashSet();
    Set set2 = new HashSet();
    set1.addAll(set2);
  }
}

Create an array containing the elements in a set

import java.util.Arrays;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class Main {
  public static void main(String[] argv) {
    // Create the sorted set
    Set<String> set = new TreeSet<String>();
    set.add("b");
    set.add("c");
    set.add("a");
    Iterator it = set.iterator();
    while (it.hasNext()) {
      Object element = it.next();
      System.out.println(element);
    }
    // Create an array containing the elements in a set
    String[] array = (String[]) set.toArray(new String[set.size()]);
    Arrays.toString(array);
  }
}

Create new sets from Iterable, var argv

/**
 * Copyright (C) 2007 Google Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
/**
 * Helper methods related to {@link Set}s.
 *
 * @author maxr@google.ru (Max Ross)
 */
public class Sets {
  private Sets() {}
  /**
   * Construct a new {@link HashSet}, taking advantage of type inference to
   * avoid specifying the type on the rhs.
   */
  public static <E> HashSet<E> newHashSet() {
    return new HashSet<E>();
  }
  /**
   * Construct a new {@link HashSet} with the provided elements, taking advantage of type inference to
   * avoid specifying the type on the rhs.
   */
  public static <E> HashSet<E> newHashSet(E... elements) {
    HashSet<E> set = newHashSet();
    Collections.addAll(set, elements);
    return set;
  }
  /**
   * Construct a new {@link HashSet} with the contents of the provided {@link Iterable}, taking advantage of type inference to
   * avoid specifying the type on the rhs.
   */
  public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
    HashSet<E> set = newHashSet();
    for(E e : elements) {
      set.add(e);
    }
    return set;
  }
}

Creating a Set That Retains Order-of-Insertion

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class Main {
  public static void main(String[] argv) throws Exception {
    Set<String> set = new LinkedHashSet<String>();
    // Add some elements
    set.add("1");
    set.add("2");
    set.add("3");
    set.add("2");
    // List the elements
    for (Iterator it = set.iterator(); it.hasNext();) {
      Object o = it.next();
    }
  }
}

Creating a Sorted Set

import java.util.Arrays;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class Main {
  public static void main(String[] argv) {
    // Create the sorted set
    Set<String> set = new TreeSet<String>();
    set.add("b");
    set.add("c");
    set.add("a");
    Iterator it = set.iterator();
    while (it.hasNext()) {
      Object element = it.next();
      System.out.println(element);
    }
    // Create an array containing the elements in a set
    String[] array = (String[]) set.toArray(new String[set.size()]);
    Arrays.toString(array);
  }
}

Duplicate elements are discarded

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Main {
  public static void main(String[] argv) throws Exception {
    int[] array = new int[10];
    Set set = new HashSet(Arrays.asList(array));
  }
}

Get the intersection of set1 and set2, set1 becomes the intersection of set1 and set2

import java.util.HashSet;
import java.util.Set;
public class Main {
  public static void main(String[] argv) throws Exception {
    Set set1 = new HashSet();
    Set set2 = new HashSet();
    set1.retainAll(set2);
    // Remove all elements from a set
    set1.clear();
  }
}

Implements the Set interface, backed by a ConcurrentHashMap instance

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
import java.io.IOException;
import java.io.ObjectInputStream;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
/**
 * This class implements the <tt>Set</tt> interface, backed by a ConcurrentHashMap instance.
 * 
 * @author Matt Tucker
 * @param <E>
 */
public class ConcurrentHashSet<E> extends AbstractSet<E>
  implements
    Set<E>,
    Cloneable,
    java.io.Serializable
{
  /** */
  private static final long serialVersionUID = 1L;
  private transient ConcurrentHashMap<E, Object> map;
  // Dummy value to associate with an Object in the backing Map
  private static final Object PRESENT = new Object();
  /**
   * Constructs a new, empty set; the backing <tt>ConcurrentHashMap</tt> instance has default
   * initial capacity (16) and load factor (0.75).
   */
  public ConcurrentHashSet()
  {
    map = new ConcurrentHashMap<E, Object>();
  }
  /**
   * Constructs a new set containing the elements in the specified collection. The
   * <tt>ConcurrentHashMap</tt> is created with default load factor (0.75) and an initial capacity
   * sufficient to contain the elements in the specified collection.
   * 
   * @param c
   *            the collection whose elements are to be placed into this set.
   * @throws NullPointerException
   *             if the specified collection is null.
   */
  public ConcurrentHashSet(Collection<? extends E> c)
  {
    map = new ConcurrentHashMap<E, Object>(Math.max((int)(c.size() / .75f) + 1, 16));
    addAll(c);
  }
  /**
   * Constructs a new, empty set; the backing <tt>ConcurrentHashMap</tt> instance has the
   * specified initial capacity and the specified load factor.
   * 
   * @param initialCapacity
   *            the initial capacity of the hash map.
   * @param loadFactor
   *            the load factor of the hash map.
   * @throws IllegalArgumentException
   *             if the initial capacity is less than zero, or if the load factor is nonpositive.
   */
  public ConcurrentHashSet(int initialCapacity, float loadFactor)
  {
    map = new ConcurrentHashMap<E, Object>(initialCapacity, loadFactor, 16);
  }
  /**
   * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has the specified initial
   * capacity and default load factor, which is <tt>0.75</tt>.
   * 
   * @param initialCapacity
   *            the initial capacity of the hash table.
   * @throws IllegalArgumentException
   *             if the initial capacity is less than zero.
   */
  public ConcurrentHashSet(int initialCapacity)
  {
    map = new ConcurrentHashMap<E, Object>(initialCapacity);
  }
  /**
   * 
   * @see java.util.AbstractCollection#iterator()
   */
  @Override
  public Iterator<E> iterator()
  {
    return map.keySet().iterator();
  }
  /**
   * 
   * @see java.util.AbstractCollection#size()
   */
  @Override
  public int size()
  {
    return map.size();
  }
  /**
   * 
   * @see java.util.AbstractCollection#isEmpty()
   */
  @Override
  public boolean isEmpty()
  {
    return map.isEmpty();
  }
  /**
   * 
   * @see java.util.AbstractCollection#contains(java.lang.Object)
   */
  @Override
  public boolean contains(Object o)
  {
    return map.containsKey(o);
  }
  /**
   * 
   * @see java.util.AbstractCollection#add(java.lang.Object)
   */
  @Override
  public boolean add(E o)
  {
    return map.put(o, PRESENT) == null;
  }
  /**
   * 
   * @see java.util.AbstractCollection#remove(java.lang.Object)
   */
  @Override
  public boolean remove(Object o)
  {
    return map.remove(o) == PRESENT;
  }
  /**
   * 
   * @see java.util.AbstractCollection#clear()
   */
  @Override
  public void clear()
  {
    map.clear();
  }
  /**
   * 
   * @see java.lang.Object#clone()
   */
  @SuppressWarnings("unchecked")
  @Override
  public Object clone()
  {
    try
    {
      ConcurrentHashSet<E> newSet = (ConcurrentHashSet<E>)super.clone();
      newSet.map.putAll(map);
      return newSet;
    }
    catch (CloneNotSupportedException e)
    {
      throw new InternalError();
    }
  }
  /**
   * 
   * @param s
   * @throws java.io.IOException
   */
  private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
  {
    s.defaultWriteObject();
    s.writeInt(map.size());
    for (Iterator<E> i = map.keySet().iterator(); i.hasNext();)
    {
      s.writeObject(i.next());
    }
  }
  /**
   * Re-constitute the <tt>HashSet</tt> instance from a stream.
   * 
   * @param inputStream
   * @throws ClassNotFoundException
   * @throws IOException
   */
  private void readObject(ObjectInputStream inputStream) throws ClassNotFoundException,
    IOException
  {
    inputStream.defaultReadObject();
    map = new ConcurrentHashMap<E, Object>();
    int size = inputStream.readInt();
    for (int i = 0; i < size; i++)
    {
      E e = (E)inputStream.readObject();
      map.put(e, PRESENT);
    }
  }
}

List Set

/*
    GNU LESSER GENERAL PUBLIC LICENSE
    Copyright (C) 2006 The Lobo Project
    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.
    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.
    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
    Contact info: lobochief@users.sourceforge.net
*/
/*
 * Created on Sep 3, 2005
 */
import java.util.*;
public class ListSet implements List, Set {
  private final List list = new ArrayList();
  private final Set set = new HashSet();
  
  public ListSet() {
    super();
  }
  /* (non-Javadoc)
   * @see java.util.List#add(int, E)
   */
  public void add(int index, Object element) {
    if(this.set.add(element)) {
      list.add(index, element);
    }
  }
  /* (non-Javadoc)
   * @see java.util.List#add(E)
   */
  public boolean add(Object o) {
    if(this.set.add(o)) {
      return this.list.add(o);
    }
    else {
      return false;
    }
  }
  /* (non-Javadoc)
   * @see java.util.List#addAll(java.util.Collection)
   */
  public boolean addAll(Collection c) {
    boolean changed = false;
    Iterator i = c.iterator();
    while(i.hasNext()) {
      Object element = i.next();
      if(this.add(element)) {
        changed = true;
      }
    }
    return changed;
  }
  /* (non-Javadoc)
   * @see java.util.List#addAll(int, java.util.Collection)
   */
  public boolean addAll(int index, Collection c) {
    boolean changed = false;
    int insertIndex = index;
    Iterator i = c.iterator();
    while(i.hasNext()) {
      Object element = i.next();
      if(this.set.add(element)) {
        this.list.add(insertIndex++, element);
        changed = true;
      }
    }
    return changed;
  }
  /* (non-Javadoc)
   * @see java.util.List#clear()
   */
  public void clear() {
    this.set.clear();
    this.list.clear();
  }
  /* (non-Javadoc)
   * @see java.util.List#contains(java.lang.Object)
   */
  public boolean contains(Object o) {
    return this.set.contains(o);
  }
  /* (non-Javadoc)
   * @see java.util.List#containsAll(java.util.Collection)
   */
  public boolean containsAll(Collection c) {
    return this.set.containsAll(c);
  }
  /* (non-Javadoc)
   * @see java.util.List#get(int)
   */
  public Object get(int index) {
    return this.list.get(index);
  }
  /* (non-Javadoc)
   * @see java.util.List#indexOf(java.lang.Object)
   */
  public int indexOf(Object o) {
    return this.list.indexOf(o);
  }
  /* (non-Javadoc)
   * @see java.util.List#isEmpty()
   */
  public boolean isEmpty() {
    return this.set.isEmpty();
  }
  /* (non-Javadoc)
   * @see java.util.List#iterator()
   */
  public Iterator iterator() {
    return this.list.iterator();
  }
  /* (non-Javadoc)
   * @see java.util.List#lastIndexOf(java.lang.Object)
   */
  public int lastIndexOf(Object o) {
    return this.list.lastIndexOf(o);
  }
  /* (non-Javadoc)
   * @see java.util.List#listIterator()
   */
  public ListIterator listIterator() {
    return this.list.listIterator();
  }
  /* (non-Javadoc)
   * @see java.util.List#listIterator(int)
   */
  public ListIterator listIterator(int index) {
    return this.list.listIterator(index);
  }
  /* (non-Javadoc)
   * @see java.util.List#remove(int)
   */
  public Object remove(int index) {
    Object element = this.list.remove(index);
    if(element != null) {
      this.set.remove(element);
    }
    return element;
  }
  /* (non-Javadoc)
   * @see java.util.List#remove(java.lang.Object)
   */
  public boolean remove(Object o) {
    if(this.set.remove(o)) {
      this.list.remove(o);
      return true;
    }
    else {
      return false;
    }
  }
  /* (non-Javadoc)
   * @see java.util.List#removeAll(java.util.Collection)
   */
  public boolean removeAll(Collection c) {
    if(this.set.removeAll(c)) {
      this.list.removeAll(c);
      return true;
    }
    else {
      return false;
    }
  }
  /* (non-Javadoc)
   * @see java.util.List#retainAll(java.util.Collection)
   */
  public boolean retainAll(Collection c) {
    if(this.set.retainAll(c)) {
      this.list.retainAll(c);
      return true;
    }
    else {
      return false;
    }
  }
  /* (non-Javadoc)
   * @see java.util.List#set(int, E)
   */
  public Object set(int index, Object element) {
    this.set.add(element);
    return this.list.set(index, element);
  }
  /* (non-Javadoc)
   * @see java.util.List#size()
   */
  public int size() {
    return this.list.size();
  }
  /* (non-Javadoc)
   * @see java.util.List#subList(int, int)
   */
  public List subList(int fromIndex, int toIndex) {
    return this.list.subList(fromIndex, toIndex);
  }
  /* (non-Javadoc)
   * @see java.util.List#toArray()
   */
  public Object[] toArray() {
    return this.list.toArray();
  }
  /* (non-Javadoc)
   * @see java.util.List#toArray(T[])
   */
  public Object[] toArray(Object[] a) {
    return this.list.toArray(a);
  }
  
  public boolean equals(Object other) {
    return other instanceof ListSet && this.list.equals(((ListSet) other).list);
  }
  
  public int hashCode() {
    return this.list.hashCode();
  }
}

Remove all elements from a set

import java.util.HashSet;
import java.util.Set;
public class Main {
  public static void main(String[] argv) throws Exception {
    Set set1 = new HashSet();

    set1.clear();
  }
}

Remove all the elements in set1 from set2 (set1 -= set2), set1 becomes the asymmetric difference of set1 and set2

import java.util.HashSet;
import java.util.Set;
public class Main {
  public static void main(String[] argv) throws Exception {
    Set set1 = new HashSet();
    Set set2 = new HashSet();
    set1.removeAll(set2);
  }
}

Set implementation that use == instead of equals()

/*
 * Hibernate, Relational Persistence for Idiomatic Java
 *
 * Copyright (c) 2008, Red Hat Middleware LLC or third-party contributors as
 * indicated by the @author tags or express copyright attribution
 * statements applied by the authors.  All third-party contributions are
 * distributed under license by Red Hat Middleware LLC.
 *
 * This copyrighted material is made available to anyone wishing to use, modify,
 * copy, or redistribute it subject to the terms and conditions of the GNU
 * Lesser General Public License, as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 * for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this distribution; if not, write to:
 * Free Software Foundation, Inc.
 * 51 Franklin Street, Fifth Floor
 * Boston, MA  02110-1301  USA
 *
 */
import java.util.Collection;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Set;
/**
 * Set implementation that use == instead of equals() as its comparison
 * mechanism.  This is achieved by internally using an IdentityHashMap.
 *
 * @author Emmanuel Bernard
 */
public class IdentitySet implements Set {
  private static final Object DUMP_VALUE = new Object();
  private final IdentityHashMap map;
  /**
   * Create an IdentitySet with default sizing.
   */
  public IdentitySet() {
    this.map = new IdentityHashMap();
  }
  /**
   * Create an IdentitySet with the given sizing.
   *
   * @param sizing The sizing of the set to create.
   */
  public IdentitySet(int sizing) {
    this.map = new IdentityHashMap( sizing );
  }
  public int size() {
    return map.size();
  }
  public boolean isEmpty() {
    return map.isEmpty();
  }
  public boolean contains(Object o) {
    return map.get( o ) == DUMP_VALUE;
  }
  public Iterator iterator() {
    return map.entrySet().iterator();
  }
  public Object[] toArray() {
    return map.entrySet().toArray();
  }
  public Object[] toArray(Object[] a) {
    return map.entrySet().toArray( a );
  }
  public boolean add(Object o) {
    return map.put( o, DUMP_VALUE ) == null;
  }
  public boolean remove(Object o) {
    return map.remove( o ) == DUMP_VALUE;
  }
  public boolean containsAll(Collection c) {
    Iterator it = c.iterator();
    while ( it.hasNext() ) {
      if ( !map.containsKey( it.next() ) ) {
        return false;
      }
    }
    return true;
  }
  public boolean addAll(Collection c) {
    Iterator it = c.iterator();
    boolean changed = false;
    while ( it.hasNext() ) {
      if ( this.add( it.next() ) ) {
        changed = true;
      }
    }
    return changed;
  }
  public boolean retainAll(Collection c) {
    //doable if needed
    throw new UnsupportedOperationException();
  }
  public boolean removeAll(Collection c) {
    Iterator it = c.iterator();
    boolean changed = false;
    while ( it.hasNext() ) {
      if ( this.remove( it.next() ) ) {
        changed = true;
      }
    }
    return changed;
  }
  public void clear() {
    map.clear();
  }
}

Set operations: union, intersection, difference, symmetric difference, is subset, is superset

import java.util.Set;
import java.util.TreeSet;
public class Main {
  public static <T> Set<T> union(Set<T> setA, Set<T> setB) {
    Set<T> tmp = new TreeSet<T>(setA);
    tmp.addAll(setB);
    return tmp;
  }
  public static <T> Set<T> intersection(Set<T> setA, Set<T> setB) {
    Set<T> tmp = new TreeSet<T>();
    for (T x : setA)
      if (setB.contains(x))
        tmp.add(x);
    return tmp;
  }
  public static <T> Set<T> difference(Set<T> setA, Set<T> setB) {
    Set<T> tmp = new TreeSet<T>(setA);
    tmp.removeAll(setB);
    return tmp;
  }
  public static <T> Set<T> symDifference(Set<T> setA, Set<T> setB) {
    Set<T> tmpA;
    Set<T> tmpB;
    tmpA = union(setA, setB);
    tmpB = intersection(setA, setB);
    return difference(tmpA, tmpB);
  }
  public static <T> boolean isSubset(Set<T> setA, Set<T> setB) {
    return setB.containsAll(setA);
  }
  public static <T> boolean isSuperset(Set<T> setA, Set<T> setB) {
    return setA.containsAll(setB);
  }
  public static void main(String args[]) {
    TreeSet<Character> set1 = new TreeSet<Character>();
    TreeSet<Character> set2 = new TreeSet<Character>();
    set1.add("A");
    set1.add("B");
    set1.add("C");
    set1.add("D");
    set2.add("C");
    set2.add("D");
    set2.add("E");
    set2.add("F");
    System.out.println("set1: " + set1);
    System.out.println("set2: " + set2);
    System.out.println("Union: " + union(set1, set2));
    System.out.println("Intersection: " + intersection(set1, set2));
    System.out.println("Difference (set1 - set2): " + difference(set1, set2));
    System.out.println("Symmetric Difference: " + symDifference(set1, set2));
    TreeSet<Character> set3 = new TreeSet<Character>(set1);
    set3.remove("D");
    System.out.println("set3: " + set3);
    System.out.println("Is set1 a subset of set2? " + isSubset(set1, set3));
    System.out.println("Is set1 a superset of set2? " + isSuperset(set1, set3));
    System.out.println("Is set3 a subset of set1? " + isSubset(set3, set1));
    System.out.println("Is set3 a superset of set1? " + isSuperset(set3, set1));
  }
}

Set that compares object by identity rather than equality

// $Id: IdentitySet.java 16179 2009-03-18 11:08:10Z hardy.ferentschik $
/*
* JBoss, Home of Professional Open Source
* Copyright 2008, Red Hat Middleware LLC, and individual contributors
* by the @authors tag. See the copyright.txt in the distribution for a
* full listing of individual contributors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.Collection;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
 * Set that compares object by identity rather than equality. Wraps around a <code>IdentityHashMap</code>
 *
 * @author Emmanuel Bernard
 */
public class IdentitySet implements Set {
  private Map<Object, Object> map;
  private Object CONTAINS = new Object();
  public IdentitySet() {
    this( 10 );
  }
  public IdentitySet(int size) {
    this.map = new IdentityHashMap<Object, Object>( size );
  }
  public int size() {
    return map.size();
  }
  public boolean isEmpty() {
    return map.isEmpty();
  }
  public boolean contains(Object o) {
    return map.containsKey( o );
  }
  public Iterator iterator() {
    return map.keySet().iterator();
  }
  public Object[] toArray() {
    return map.keySet().toArray();
  }
  public boolean add(Object o) {
    return map.put( o, CONTAINS ) == null;
  }
  public boolean remove(Object o) {
    return map.remove( o ) == CONTAINS;
  }
  public boolean addAll(Collection c) {
    boolean doThing = false;
    for ( Object o : c ) {
      doThing = doThing || add( o );
    }
    return doThing;
  }
  public void clear() {
    map.clear();
  }
  public boolean removeAll(Collection c) {
    boolean remove = false;
    for ( Object o : c ) {
      remove = remove || remove( o );
    }
    return remove;
  }
  public boolean retainAll(Collection c) {
    throw new UnsupportedOperationException();
  }
  public boolean containsAll(Collection c) {
    for ( Object o : c ) {
      if ( !contains( o ) ) {
        return false;
      }
    }
    return true;
  }
  public Object[] toArray(Object[] a) {
    return map.keySet().toArray( a );
  }
  @Override
  public String toString() {
    return "IdentitySet{" +
        "map=" + map +
        "}";
  }
}

Set union and intersection

/* *****************************************************************************
 * SetUils.java
 * ****************************************************************************/
/* J_LZ_COPYRIGHT_BEGIN *******************************************************
* Copyright 2001-2004 Laszlo Systems, Inc.  All Rights Reserved.              *
* Use is subject to license terms.                                            *
* J_LZ_COPYRIGHT_END *********************************************************/
import java.util.*;
/**
 * A utility class containing set utility functions.
 *
 * @author Oliver Steele
 */
public abstract class SetUtils {
    public static boolean containsAny(Set a, Set b) {
        for (Iterator iter = b.iterator(); iter.hasNext(); ) {
            if (a.contains(iter.next())) {
                return true;
            }
        }
        return false;
    }
    public static Set intersection(Set a, Set b) {
        Set c = new HashSet();
        for (Iterator iter = b.iterator(); iter.hasNext(); ) {
            Object e = iter.next();
            if (a.contains(e)) {
                c.add(e);
            }
        }
        return c;
    }
}

Set with values iterated in insertion order.

/*
Copyright (c) 2007, Dennis M. Sosnoski
All rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
 * Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.
 * Neither the name of JiBX nor the names of its contributors may be used
   to endorse or promote products derived from this software without specific
   prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
 * Set with values iterated in insertion order. This is similar to the Java 1.4
 * java.util.LinkedHashSet class, but compatible with earlier JVM versions. This
 * implementation is for insert-only sets.
 */
public class InsertionOrderedSet implements Set
{
    private final Set m_baseMap;
    private final ArrayList m_insertList;
    
    public InsertionOrderedSet() {
        m_baseMap = new HashSet();
        m_insertList = new ArrayList();
    }
    
    /* (non-Javadoc)
     * @see java.util.Map#clear()
     */
    public void clear() {
        m_baseMap.clear();
        m_insertList.clear();
    }
    /* (non-Javadoc)
     * @see java.util.Set#isEmpty()
     */
    public boolean isEmpty() {
        return m_baseMap.isEmpty();
    }
    /* (non-Javadoc)
     * @see java.util.Set#size()
     */
    public int size() {
        return m_baseMap.size();
    }
    
    /* (non-Javadoc)
     * @see java.util.Set#add(java.lang.Object)
     */
    public boolean add(Object o) {
        if (m_baseMap.contains(o)) {
            return false;
        } else {
            m_baseMap.add(o);
            m_insertList.add(o);
            return true;
        }
    }
    /* (non-Javadoc)
     * @see java.util.Set#addAll(java.util.Collection)
     */
    public boolean addAll(Collection c) {
        boolean changed = false;
        for (Iterator iter = c.iterator(); iter.hasNext();) {
            Object item = (Object)iter.next();
            if (add(item)) {
                changed = true;
            }
        }
        return changed;
    }
    /* (non-Javadoc)
     * @see java.util.Set#contains(java.lang.Object)
     */
    public boolean contains(Object o) {
        return m_baseMap.contains(o);
    }
    /* (non-Javadoc)
     * @see java.util.Set#containsAll(java.util.Collection)
     */
    public boolean containsAll(Collection c) {
        return m_baseMap.containsAll(c);
    }
    /* (non-Javadoc)
     * @see java.util.Set#iterator()
     */
    public Iterator iterator() {
        return m_insertList.iterator();
    }
    /* (non-Javadoc)
     * @see java.util.Set#remove(java.lang.Object)
     */
    public boolean remove(Object o) {
        throw new UnsupportedOperationException("add-only set");
    }
    /* (non-Javadoc)
     * @see java.util.Set#removeAll(java.util.Collection)
     */
    public boolean removeAll(Collection c) {
        throw new UnsupportedOperationException("add-only set");
    }
    /* (non-Javadoc)
     * @see java.util.Set#retainAll(java.util.Collection)
     */
    public boolean retainAll(Collection c) {
        throw new UnsupportedOperationException("add-only set");
    }
    /* (non-Javadoc)
     * @see java.util.Set#toArray()
     */
    public Object[] toArray() {
        return m_insertList.toArray();
    }
    /* (non-Javadoc)
     * @see java.util.Set#toArray(T[])
     */
    public Object[] toArray(Object[] a) {
        return m_insertList.toArray(a);
    }
    
    /**
     * Convenience method to add every item in an array.
     *
     * @param objs
     */
    public void addAll(Object[] objs) {
        for (int i = 0; i < objs.length; i++) {
            add(objs[i]);
        }
    }
    /**
     * Get list of values in order added. The returned list is live, and will
     * grow as new items are added to the set.
     *
     * @return list
     */
    public ArrayList asList() {
        return m_insertList;
    }
}