Java/Collections Data Structure/HashSet
Содержание
- 1 Add values to HashSet<String>
- 2 A memory-efficient hash set.
- 3 Check if a particular element exists in Java HashSet
- 4 Convert an ArrayList to HashSet
- 5 Convert array to Set
- 6 Convert Set into array
- 7 Copy all elements of Java HashSet to an Object Array
- 8 Create an array containing the elements in a set
- 9 Duplicate elements are discarded
- 10 Find maximum element of Java HashSet
- 11 Find Minimum element of Java HashSet
- 12 Generic collection conversion: HashSet and ArrayList
- 13 Get Enumeration over Java HashSet
- 14 Get Size of Java HashSet
- 15 Get Synchronized Set from Java HashSet
- 16 HashSet implementation of set
- 17 Implements a HashSet where the objects given are stored in weak references
- 18 Integer value set
- 19 Iterate through elements of Java HashSet
- 20 Listing the Elements of a Collection(iterate over the elements of set or list)
- 21 Remove all elements from Java HashSet
- 22 Remove element from HashSet
- 23 Remove one set from another set
- 24 Remove specified element from Java HashSet
Add values to HashSet<String>
<source lang="java">
import java.util.HashSet; class HashSetDemo {
public static void main(String args[]) { HashSet<String> hs = new HashSet<String>(); hs.add("B"); hs.add("A"); hs.add("D"); hs.add("E"); hs.add("C"); hs.add("F"); System.out.println(hs); }
}
</source>
A memory-efficient hash set.
<source lang="java">
/*
* Copyright 2009 Google Inc. * * 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.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.lang.reflect.Array; import java.util.AbstractSet; import java.util.Collection; import java.util.Iterator; import java.util.NoSuchElementException; /**
* A memory-efficient hash set. * * @param <E> the element type */
public class HashSet<E> extends AbstractSet<E> implements Serializable {
private class SetIterator implements Iterator<E> { private int index = 0; private int last = -1; public SetIterator() { advanceToItem(); } public boolean hasNext() { return index < table.length; } @SuppressWarnings("unchecked") public E next() { if (!hasNext()) { throw new NoSuchElementException(); } last = index; E toReturn = (E) unmaskNull(table[index++]); advanceToItem(); return toReturn; } public void remove() { if (last < 0) { throw new IllegalStateException(); } internalRemove(last); if (table[last] != null) { index = last; } last = -1; } private void advanceToItem() { for (; index < table.length; ++index) { if (table[index] != null) { return; } } } } /** * In the interest of memory-savings, we start with the smallest feasible * power-of-two table size that can hold three items without rehashing. If we * started with a size of 2, we"d have to expand as soon as the second item * was added. */ private static final int INITIAL_TABLE_SIZE = 4; private static final Object NULL_ITEM = new Serializable() { Object readResolve() { return NULL_ITEM; } }; static Object maskNull(Object o) { return (o == null) ? NULL_ITEM : o; } static Object unmaskNull(Object o) { return (o == NULL_ITEM) ? null : o; } /** * Number of objects in this set; transient due to custom serialization. * Default access to avoid synthetic accessors from inner classes. */ transient int size = 0; /** * Backing store for all the objects; transient due to custom serialization. * Default access to avoid synthetic accessors from inner classes. */ transient Object[] table; public HashSet() { table = new Object[INITIAL_TABLE_SIZE]; } public HashSet(Collection<? extends E> c) { int newCapacity = INITIAL_TABLE_SIZE; int expectedSize = c.size(); while (newCapacity * 3 < expectedSize * 4) { newCapacity <<= 1; } table = new Object[newCapacity]; super.addAll(c); } @Override public boolean add(E e) { ensureSizeFor(size + 1); int index = findOrEmpty(e); if (table[index] == null) { ++size; table[index] = maskNull(e); return true; } return false; } @Override public boolean addAll(Collection<? extends E> c) { ensureSizeFor(size + c.size()); return super.addAll(c); } @Override public void clear() { table = new Object[INITIAL_TABLE_SIZE]; size = 0; } @Override public boolean contains(Object o) { return find(o) >= 0; } @Override public Iterator<E> iterator() { return new SetIterator(); } @Override public boolean remove(Object o) { int index = find(o); if (index < 0) { return false; } internalRemove(index); return true; } @Override public int size() { return size; } @Override public Object[] toArray() { return toArray(new Object[size]); } @SuppressWarnings("unchecked") @Override public <T> T[] toArray(T[] a) { if (a.length < size) { a = (T[]) Array.newInstance(a.getClass().getComponentType(), size); } int index = 0; for (int i = 0; i < table.length; ++i) { Object e = table[i]; if (e != null) { a[index++] = (T) unmaskNull(e); } } while (index < a.length) { a[index++] = null; } return a; } /** * Adapted from {@link org.apache.rumons.collections.map.AbstractHashedMap}. */ @SuppressWarnings("unchecked") protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException { table = new Object[in.readInt()]; int items = in.readInt(); for (int i = 0; i < items; i++) { add((E) in.readObject()); } } /** * Adapted from {@link org.apache.rumons.collections.map.AbstractHashedMap}. */ protected void doWriteObject(ObjectOutputStream out) throws IOException { out.writeInt(table.length); out.writeInt(size); for (int i = 0; i < table.length; ++i) { Object e = table[i]; if (e != null) { out.writeObject(unmaskNull(e)); } } } /** * Returns whether two items are equal for the purposes of this set. */ protected boolean itemEquals(Object a, Object b) { return (a == null) ? (b == null) : a.equals(b); } /** * Return the hashCode for an item. */ protected int itemHashCode(Object o) { return (o == null) ? 0 : o.hashCode(); } /** * Works just like {@link #addAll(Collection)}, but for arrays. Used to avoid * having to synthesize a collection in {@link Sets}. */ void addAll(E[] elements) { ensureSizeFor(size + elements.length); for (E e : elements) { int index = findOrEmpty(e); if (table[index] == null) { ++size; table[index] = maskNull(e); } } } /** * Removes the item at the specified index, and performs internal management * to make sure we don"t wind up with a hole in the table. Default access to * avoid synthetic accessors from inner classes. */ void internalRemove(int index) { table[index] = null; --size; plugHole(index); } /** * Ensures the set is large enough to contain the specified number of entries. */ private void ensureSizeFor(int expectedSize) { if (table.length * 3 >= expectedSize * 4) { return; } int newCapacity = table.length << 1; while (newCapacity * 3 < expectedSize * 4) { newCapacity <<= 1; } Object[] oldTable = table; table = new Object[newCapacity]; for (Object o : oldTable) { if (o != null) { int newIndex = getIndex(unmaskNull(o)); while (table[newIndex] != null) { if (++newIndex == table.length) { newIndex = 0; } } table[newIndex] = o; } } } /** * Returns the index in the table at which a particular item resides, or -1 if * the item is not in the table. */ private int find(Object o) { int index = getIndex(o); while (true) { Object existing = table[index]; if (existing == null) { return -1; } if (itemEquals(o, unmaskNull(existing))) { return index; } if (++index == table.length) { index = 0; } } } /** * Returns the index in the table at which a particular item resides, or the * index of an empty slot in the table where this item should be inserted if * it is not already in the table. */ private int findOrEmpty(Object o) { int index = getIndex(o); while (true) { Object existing = table[index]; if (existing == null) { return index; } if (itemEquals(o, unmaskNull(existing))) { return index; } if (++index == table.length) { index = 0; } } } private int getIndex(Object o) { int h = itemHashCode(o); // Copied from Apache"s AbstractHashedMap; prevents power-of-two collisions. h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); // Power of two trick. return h & (table.length - 1); } /** * Tricky, we left a hole in the map, which we have to fill. The only way to * do this is to search forwards through the map shuffling back values that * match this index until we hit a null. */ private void plugHole(int hole) { int index = hole + 1; if (index == table.length) { index = 0; } while (table[index] != null) { int targetIndex = getIndex(unmaskNull(table[index])); if (hole < index) { /* * "Normal" case, the index is past the hole and the "bad range" is from * hole (exclusive) to index (inclusive). */ if (!(hole < targetIndex && targetIndex <= index)) { // Plug it! table[hole] = table[index]; table[index] = null; hole = index; } } else { /* * "Wrapped" case, the index is before the hole (we"ve wrapped) and the * "good range" is from index (exclusive) to hole (inclusive). */ if (index < targetIndex && targetIndex <= hole) { // Plug it! table[hole] = table[index]; table[index] = null; hole = index; } } if (++index == table.length) { index = 0; } } } private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { in.defaultReadObject(); doReadObject(in); } private void writeObject(ObjectOutputStream out) throws IOException { out.defaultWriteObject(); doWriteObject(out); }
}
</source>
Check if a particular element exists in Java HashSet
<source lang="java">
import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Integer> hSet = new HashSet<Integer>(); hSet.add(new Integer("1")); hSet.add(new Integer("2")); hSet.add(new Integer("3")); System.out.println(hSet.contains(new Integer("3"))); }
}
</source>
Convert an ArrayList to HashSet
<source lang="java">
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
- /
</source>
Convert array to Set
<source lang="java">
import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Set; public class Main {
public static void main(String[] args) { Integer[] numbers = { 7, 7, 8, 9, 10, 8, 8, 9, 6, 5, 4 }; List<Integer> list = Arrays.asList(numbers); Set<Integer> set = new HashSet<Integer>(list); for (Iterator iterator = set.iterator(); iterator.hasNext();) { Object o = iterator.next(); System.out.print(o + ", "); } }
}
</source>
Convert Set into array
<source lang="java">
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); } }
}
</source>
Copy all elements of Java HashSet to an Object Array
<source lang="java">
import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Integer> hSet = new HashSet<Integer>(); hSet.add(new Integer("1")); hSet.add(new Integer("2")); hSet.add(new Integer("3")); Object[] objArray = hSet.toArray(); for (Object obj : objArray) System.out.println(obj); }
}
</source>
Create an array containing the elements in a set
<source lang="java">
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); }
}
</source>
Duplicate elements are discarded
<source lang="java">
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)); }
}
</source>
Find maximum element of Java HashSet
<source lang="java">
import java.util.Collections; import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Long> hashSet = new HashSet<Long>(); hashSet.add(new Long("1111111111")); hashSet.add(new Long("2222222222")); hashSet.add(new Long("3333333333")); hashSet.add(new Long("4444444444")); hashSet.add(new Long("5555555555")); Object obj = Collections.max(hashSet); System.out.println(obj); }
}
</source>
Find Minimum element of Java HashSet
<source lang="java">
import java.util.Collections; import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Long> hashSet = new HashSet<Long>(); hashSet.add(new Long("9")); hashSet.add(new Long("4")); hashSet.add(new Long("2")); hashSet.add(new Long("2")); hashSet.add(new Long("3")); Object obj = Collections.min(hashSet); System.out.println("Minimum Element of Java HashSet is : " + obj); }
}
</source>
Generic collection conversion: HashSet and ArrayList
<source lang="java">
import java.util.ArrayList; import java.util.Date; import java.util.HashSet; import java.util.List; import java.util.Set; public class Capture {
static <T> Set<T> listToSet(List<T> list) { Set<T> set = new HashSet<T>(); set.addAll(list); return set; } public static void main(String[] args) { List<?> list = new ArrayList<Date>(); Set<?> set = listToSet(list); }
}
</source>
Get Enumeration over Java HashSet
<source lang="java">
import java.util.Collections; import java.util.Enumeration; import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<String> hashSet = new HashSet<String>(); hashSet.add("A"); hashSet.add("B"); hashSet.add("D"); hashSet.add("E"); hashSet.add("F"); Enumeration e = Collections.enumeration(hashSet); while (e.hasMoreElements()) System.out.println(e.nextElement()); }
}
</source>
Get Size of Java HashSet
<source lang="java">
import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Integer> hSet = new HashSet<Integer>(); System.out.println("Size of HashSet : " + hSet.size()); hSet.add(new Integer("1")); hSet.add(new Integer("2")); hSet.add(new Integer("3")); System.out.println(hSet.size()); hSet.remove(new Integer("1")); System.out.println(hSet.size()); }
} /* Size of HashSet : 0 3 2
- /
</source>
Get Synchronized Set from Java HashSet
<source lang="java">
import java.util.Collections; import java.util.HashSet; import java.util.Set; public class Main {
public static void main(String[] args) { HashSet hashSet = new HashSet(); Set set = Collections.synchronizedSet(hashSet); }
}
</source>
HashSet implementation of set
<source lang="java">
import java.util.HashSet; import java.util.Set; public class FindDups {
public static void main(String[] args) { Set<String> s = new HashSet<String>(); for (String a : args) if (!s.add(a)) System.out.println("Duplicate detected: " + a); System.out.println(s.size() + " distinct words: " + s); }
}
</source>
Implements a HashSet where the objects given are stored in weak references
<source lang="java">
/*
* file: WeakHashSet.java * package: oreilly.hcj.references * * This software is granted under the terms of the Common Public License, * CPL, which may be found at the following URL: * http://www-124.ibm.ru/developerworks/oss/CPLv1.0.htm * * Copyright(c) 2003-2005 by the authors indicated in the @author tags. * All Rights are Reserved by the various authors. *
- DO NOT EDIT ABOVE THIS LINE ########## */
import java.util.AbstractSet; import java.util.Collection; import java.util.Iterator; import java.util.Set; import java.util.WeakHashMap; /**
* Implements a HashSet where the objects given are stored in weak references. **
* Uses the WeakHashMap class as a backing store to implement a set of objects that are * stored as weak references. All information concerning using keys in the WeakHashMap * class pertain to this class and it is reccomended that the user of this class review * that material before using the class. *
**
* Because this set contains only weak references, it is not serializable. If one tried * to serialize a weak reference, the results would be highly unpredictable as the * object could likely vanish from memory before the proces was even completed. Users of * this class must use transient when the containing class uses this set. *
**
* Because of the semantics of the weak references, the value null is not allowed in this * set. *
**
* This collection is not identity based but equality based. This can cause some * confusion as you cannot put in two objects whose equals() methods return * true. It also means that an object being held is not necessarily the same one that * the user is holding. For example, you could have a String with the value "fred" at * memory location X and ther could be another String with the value "fred" at memory * location Y. The first instance is in the set but the second isn"t. *
* * @author * @version $Revision: 1.8 $ * * @see java.lang.util.WeakHashMap * @see java.lang.ref.WeakReference */
public class WeakHashSet extends AbstractSet implements Set {
/** Dummy value used as a value object. */ private static final Object DUMMY = new String("DUMMY"); //$NON-NLS-1$ /** Holds the backing store. */ WeakHashMap backingStore = new WeakHashMap(); /** * Constructs a new empty WeakHashSet with default values passed the the backing * store. * * @see java.util.WeakHashMap#WeakHashMap() */ public WeakHashSet() { backingStore = new WeakHashMap(); } /** * Constructs a new WeakHashSet with default values passed the the backing store and * fills it with the given collection. Note that duplicates in the collection will * merely be overwritten * * @see java.util.WeakHashMap#WeakHashMap(Collection) */ public WeakHashSet(final Collection c) { backingStore = new WeakHashMap(Math.max((int)(c.size() / .75f) + 1, 16)); addAll(c); } /** * Constructs a new WeakHashSet with the values given passed the the backing store. * * @see java.util.WeakHashMap#WeakHashMap(int, float) */ public WeakHashSet(final int initialCapacity, final float loadFactor) { backingStore = new WeakHashMap(initialCapacity, loadFactor); } /** * Constructs a new WeakHashSet with the values given passed the the backing store. * * @see java.util.WeakHashMap#WeakHashMap(int) */ public WeakHashSet(final int initialCapacity) { backingStore = new WeakHashMap(initialCapacity); } /** * {@inheritDoc} */ public boolean isEmpty() { return backingStore.keySet() .isEmpty(); } /** * {@inheritDoc} * * @throws NullPointerException If the user tries to add null to the set. */ public boolean add(final Object o) { if (o == null) { throw new NullPointerException(); } return backingStore.put(o, DUMMY) == null; } /** * {@inheritDoc} * * @see #add(Object) */ public boolean addAll(final Collection c) { boolean changed = false; Iterator iter = c.iterator(); while (iter.hasNext()) { changed = (changed | (backingStore.put(iter.next(), DUMMY) != DUMMY)); } return changed; } /** * {@inheritDoc} */ public void clear() { backingStore.clear(); } /** * {@inheritDoc} */ public boolean contains(final Object o) { return backingStore.containsKey(o); } /** * {@inheritDoc} */ public boolean containsAll(final Collection c) { return backingStore.keySet() .containsAll(c); } /** * {@inheritDoc} */ public boolean equals(final Object o) { return backingStore.equals(o); } /** * Returns the hash code value for this set. **
* Gives back the hashCode for the backing store key set. The user should be aware, * however, that this hash code can change without user intervention as the objects * in the collection can easily be collected microseconds after completetion of the * method. It is not reccomended that the user rely on this hash code for * consistency *
* * @return The hashcode for this object. */ public int hashCode() { return backingStore.keySet() .hashCode(); } /** * Returns an iterator over the elements contained in this collection. **
* Note that this iterator is extremely volatile because the user may iterate over an * element in the set and find seconds later that it has been removed. This is * because of the semantics of weak references which act like a second thread is * silently modifying the collection. For this reason, it is advisable that if the * user wants to do something with the set that they maintain a strong reference to * the object and not rely on it being in the collection for them. *
**
* This iterator is fail fast and WeakReference transparrent. By this we mean that * the iterator simply ignores objects pending in the reference queue for cleanup. *
* * @return The iterator. */ public Iterator iterator() { return backingStore.keySet() .iterator(); } /** * {@inheritDoc} */ public boolean remove(final Object o) { return backingStore.keySet() .remove(o); } /** * {@inheritDoc} */ public boolean removeAll(final Collection c) { return backingStore.keySet() .removeAll(c); } /** * {@inheritDoc} */ public boolean retainAll(final Collection c) { return backingStore.keySet() .retainAll(c); } /** * {@inheritDoc} */ public int size() { return backingStore.keySet() .size(); } /** * {@inheritDoc} */ public Object[] toArray() { return backingStore.keySet() .toArray(); } /** * {@inheritDoc} */ public Object[] toArray(final Object[] a) { return backingStore.keySet() .toArray(a); } /** * {@inheritDoc} */ public String toString() { return backingStore.keySet() .toString(); } /** * {@inheritDoc} */ protected Object clone() throws CloneNotSupportedException { throw new CloneNotSupportedException(); }
} /* ########## End of File ########## */
</source>
Integer value set
<source lang="java">
import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Integer> hSet = new HashSet<Integer>(); hSet.add(new Integer("1")); hSet.add(new Integer("2")); hSet.add(new Integer("3")); System.out.println("HashSet contains.." + hSet); }
} //HashSet contains..[1, 2, 3]
</source>
Iterate through elements of Java HashSet
<source lang="java">
import java.util.HashSet; import java.util.Iterator; public class Main {
public static void main(String[] args) { HashSet<Integer> hSet = new HashSet<Integer>(); hSet.add(new Integer("1")); hSet.add(new Integer("2")); hSet.add(new Integer("3")); Iterator itr = hSet.iterator(); while (itr.hasNext()) System.out.println(itr.next()); }
}
</source>
Listing the Elements of a Collection(iterate over the elements of set or list)
<source lang="java">
import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class Main {
public static void main(String[] argv) throws Exception { Set collection = new HashSet(); // For a set or list for (Iterator it = collection.iterator(); it.hasNext();) { Object element = it.next(); } }
}
</source>
Remove all elements from Java HashSet
<source lang="java">
import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Integer> hSet = new HashSet<Integer>(); hSet.add(new Integer("1")); hSet.add(new Integer("2")); hSet.add(new Integer("3")); System.out.println(hSet); hSet.clear(); System.out.println(hSet); System.out.println(hSet.isEmpty()); }
} /* [1, 2, 3] [] true
- /
</source>
Remove element from HashSet
<source lang="java">
import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class HashSetExample {
public static void main(String[] args) { Set<Integer> set = new HashSet<Integer>(); set.add(new Integer(1)); set.add(new Integer(2)); set.add(new Integer(3)); set.add(new Integer(4)); set.add(new Integer(5)); set.add(new Integer(6)); set.add(new Integer(7)); set.add(new Integer(8)); set.add(new Integer(9)); set.add(new Integer(10)); // Use iterator to display the vsetes System.out.println("HashSet Before: "); for (Iterator i = set.iterator(); i.hasNext();) { Integer integer = (Integer) i.next(); System.out.println(integer); } // Remove the integer 6 System.out.println("\nRemove integer 6"); set.remove(new Integer(6)); // Use iterator to display the vsetes System.out.println("\nHashSet After: "); for (Iterator i = set.iterator(); i.hasNext();) { Integer integer = (Integer) i.next(); System.out.println(integer); } }
}
</source>
Remove one set from another set
<source lang="java">
import java.util.HashSet; import java.util.Set; public class FindDups2 {
public static void main(String[] args) { Set<String> uniques = new HashSet<String>(); Set<String> dups = new HashSet<String>(); for (String a : args) if (!uniques.add(a)) dups.add(a); uniques.removeAll(dups); System.out.println("Unique words: " + uniques); System.out.println("Duplicate words: " + dups); }
}
</source>
Remove specified element from Java HashSet
<source lang="java">
import java.util.HashSet; public class Main {
public static void main(String[] args) { HashSet<Integer> hSet = new HashSet<Integer>(); hSet.add(new Integer("1")); hSet.add(new Integer("2")); hSet.add(new Integer("3")); System.out.println(hSet); boolean blnRemoved = hSet.remove(new Integer("2")); System.out.println(blnRemoved); System.out.println(hSet); }
} /* [1, 2, 3] true [1, 3]
- /
</source>