hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/LightWeightHashSet.java - hadoop - Git at Google

 /**
  * 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.
  */
 package org.apache.hadoop.hdfs.util;

 import java.io.PrintStream;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.ConcurrentModificationException;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.NoSuchElementException;

 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;

 /**
  * A low memory linked hash set implementation, which uses an array for storing
  * the elements and linked lists for collision resolution. This class does not
  * support null element.
  *
  * This class is not thread safe.
  *
  */
 public class LightWeightHashSet<T> implements Collection<T> {
   /**
    * Elements of {@link LightWeightLinkedSet}.
    */
   static class LinkedElement<T> {
     protected final T element;

     // reference to the next entry within a bucket linked list
     protected LinkedElement<T> next;

     //hashCode of the element
     protected final int hashCode;

     public LinkedElement(T elem, int hash) {
       this.element = elem;
       this.next = null;
       this.hashCode = hash;
     }

     @Override
     public String toString() {
       return element.toString();
     }
   }

   protected static final float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
   protected static final float DEFAUT_MIN_LOAD_FACTOR = 0.2f;
   protected static final int MINIMUM_CAPACITY = 16;

   static final int MAXIMUM_CAPACITY = 1 << 30;
   private static final Log LOG = LogFactory.getLog(LightWeightHashSet.class);

   /**
    * An internal array of entries, which are the rows of the hash table. The
    * size must be a power of two.
    */
   protected LinkedElement<T>[] entries;
   /** Size of the entry table. */
   private int capacity;
   /** The size of the set (not the entry array). */
   protected int size = 0;
   /** Hashmask used for determining the bucket index **/
   private int hash_mask;
   /** Capacity at initialization time **/
   private final int initialCapacity;

   /**
    * Modification version for fail-fast.
    *
    * @see ConcurrentModificationException
    */
   protected int modification = 0;

   private float maxLoadFactor;
   private float minLoadFactor;
   private final int expandMultiplier = 2;

   private int expandThreshold;
   private int shrinkThreshold;

   /**
    * @param initCapacity
    *          Recommended size of the internal array.
    * @param maxLoadFactor
    *          used to determine when to expand the internal array
    * @param minLoadFactor
    *          used to determine when to shrink the internal array
    */
   @SuppressWarnings("unchecked")
   public LightWeightHashSet(int initCapacity, float maxLoadFactor,
       float minLoadFactor) {

     if (maxLoadFactor <= 0 || maxLoadFactor > 1.0f)
       throw new IllegalArgumentException("Illegal maxload factor: "
           + maxLoadFactor);

     if (minLoadFactor <= 0 || minLoadFactor > maxLoadFactor)
       throw new IllegalArgumentException("Illegal minload factor: "
           + minLoadFactor);

     this.initialCapacity = computeCapacity(initCapacity);
     this.capacity = this.initialCapacity;
     this.hash_mask = capacity - 1;

     this.maxLoadFactor = maxLoadFactor;
     this.expandThreshold = (int) (capacity * maxLoadFactor);
     this.minLoadFactor = minLoadFactor;
     this.shrinkThreshold = (int) (capacity * minLoadFactor);

     entries = new LinkedElement[capacity];
     if (LOG.isDebugEnabled()) {
       LOG.debug("initial capacity=" + initialCapacity + ", max load factor= "
           + maxLoadFactor + ", min load factor= " + minLoadFactor);
     }
   }

   public LightWeightHashSet() {
     this(MINIMUM_CAPACITY, DEFAULT_MAX_LOAD_FACTOR, DEFAUT_MIN_LOAD_FACTOR);
   }

   public LightWeightHashSet(int minCapacity) {
     this(minCapacity, DEFAULT_MAX_LOAD_FACTOR, DEFAUT_MIN_LOAD_FACTOR);
   }

   /**
    * Check if the set is empty.
    *
    * @return true is set empty, false otherwise
    */
   @Override
   public boolean isEmpty() {
     return size == 0;
   }

   /**
    * Return the current capacity (for testing).
    */
   public int getCapacity() {
     return capacity;
   }

   /**
    * Return the number of stored elements.
    */
   @Override
   public int size() {
     return size;
   }

   /**
    * Get index in the internal table for a given hash.
    */
   protected int getIndex(int hashCode) {
     return hashCode & hash_mask;
   }

   /**
    * Check if the set contains given element
    *
    * @return true if element present, false otherwise.
    */
   @SuppressWarnings("unchecked")
   @Override
   public boolean contains(final Object key) {
     return getElement((T)key) != null;
   }

   /**
    * Return the element in this set which is equal to
    * the given key, if such an element exists.
    * Otherwise returns null.
    */
   public T getElement(final T key) {
     // validate key
     if (key == null) {
       throw new IllegalArgumentException("Null element is not supported.");
     }
     // find element
     final int hashCode = key.hashCode();
     final int index = getIndex(hashCode);
     return getContainedElem(index, key, hashCode);
   }

   /**
    * Check if the set contains given element at given index. If it
    * does, return that element.
    *
    * @return the element, or null, if no element matches
    */
   protected T getContainedElem(int index, final T key, int hashCode) {
     for (LinkedElement<T> e = entries[index]; e != null; e = e.next) {
       // element found
       if (hashCode == e.hashCode && e.element.equals(key)) {
         return e.element;
       }
     }
     // element not found
     return null;
   }

   /**
    * All all elements in the collection. Expand if necessary.
    *
    * @param toAdd - elements to add.
    * @return true if the set has changed, false otherwise
    */
   @Override
   public boolean addAll(Collection<? extends T> toAdd) {
     boolean changed = false;
     for (T elem : toAdd) {
       changed |= addElem(elem);
     }
     expandIfNecessary();
     return changed;
   }

   /**
    * Add given element to the hash table. Expand table if necessary.
    *
    * @return true if the element was not present in the table, false otherwise
    */
   @Override
   public boolean add(final T element) {
     boolean added = addElem(element);
     expandIfNecessary();
     return added;
   }

   /**
    * Add given element to the hash table
    *
    * @return true if the element was not present in the table, false otherwise
    */
   protected boolean addElem(final T element) {
     // validate element
     if (element == null) {
       throw new IllegalArgumentException("Null element is not supported.");
     }
     // find hashCode & index
     final int hashCode = element.hashCode();
     final int index = getIndex(hashCode);
     // return false if already present
     if (getContainedElem(index, element, hashCode) != null) {
       return false;
     }

     modification++;
     size++;

     // update bucket linked list
     LinkedElement<T> le = new LinkedElement<T>(element, hashCode);
     le.next = entries[index];
     entries[index] = le;
     return true;
   }

   /**
    * Remove the element corresponding to the key.
    *
    * @return If such element exists, return true. Otherwise, return false.
    */
   @Override
   @SuppressWarnings("unchecked")
   public boolean remove(final Object key) {
     // validate key
     if (key == null) {
       throw new IllegalArgumentException("Null element is not supported.");
     }
     LinkedElement<T> removed = removeElem((T) key);
     shrinkIfNecessary();
     return removed == null ? false : true;
   }

   /**
    * Remove the element corresponding to the key, given key.hashCode() == index.
    *
    * @return If such element exists, return true. Otherwise, return false.
    */
   protected LinkedElement<T> removeElem(final T key) {
     LinkedElement<T> found = null;
     final int hashCode = key.hashCode();
     final int index = getIndex(hashCode);
     if (entries[index] == null) {
       return null;
     } else if (hashCode == entries[index].hashCode &&
             entries[index].element.equals(key)) {
       // remove the head of the bucket linked list
       modification++;
       size--;
       found = entries[index];
       entries[index] = found.next;
     } else {
       // head != null and key is not equal to head
       // search the element
       LinkedElement<T> prev = entries[index];
       for (found = prev.next; found != null;) {
         if (hashCode == found.hashCode &&
                 found.element.equals(key)) {
           // found the element, remove it
           modification++;
           size--;
           prev.next = found.next;
           found.next = null;
           break;
         } else {
           prev = found;
           found = found.next;
         }
       }
     }
     return found;
   }

   /**
    * Remove and return n elements from the hashtable.
    * The order in which entries are removed is unspecified, and
    * and may not correspond to the order in which they were inserted.
    *
    * @return first element
    */
   public List<T> pollN(int n) {
     if (n >= size) {
       return pollAll();
     }
     List<T> retList = new ArrayList<T>(n);
     if (n == 0) {
       return retList;
     }
     boolean done = false;
     int currentBucketIndex = 0;

     while (!done) {
       LinkedElement<T> current = entries[currentBucketIndex];
       while (current != null) {
         retList.add(current.element);
         current = current.next;
         entries[currentBucketIndex] = current;
         size--;
         modification++;
         if (--n == 0) {
           done = true;
           break;
         }
       }
       currentBucketIndex++;
     }
     shrinkIfNecessary();
     return retList;
   }

   /**
    * Remove all elements from the set and return them. Clear the entries.
    */
   public List<T> pollAll() {
     List<T> retList = new ArrayList<T>(size);
     for (int i = 0; i < entries.length; i++) {
       LinkedElement<T> current = entries[i];
       while (current != null) {
         retList.add(current.element);
         current = current.next;
       }
     }
     this.clear();
     return retList;
   }

   /**
    * Get array.length elements from the set, and put them into the array.
    */
   @SuppressWarnings("unchecked")
   public T[] pollToArray(T[] array) {
     int currentIndex = 0;
     LinkedElement<T> current = null;

     if (array.length == 0) {
       return array;
     }
     if (array.length > size) {
       array = (T[]) java.lang.reflect.Array.newInstance(array.getClass()
           .getComponentType(), size);
     }
     // do fast polling if the entire set needs to be fetched
     if (array.length == size) {
       for (int i = 0; i < entries.length; i++) {
         current = entries[i];
         while (current != null) {
           array[currentIndex++] = current.element;
           current = current.next;
         }
       }
       this.clear();
       return array;
     }

     boolean done = false;
     int currentBucketIndex = 0;

     while (!done) {
       current = entries[currentBucketIndex];
       while (current != null) {
         array[currentIndex++] = current.element;
         current = current.next;
         entries[currentBucketIndex] = current;
         size--;
         modification++;
         if (currentIndex == array.length) {
           done = true;
           break;
         }
       }
       currentBucketIndex++;
     }
     shrinkIfNecessary();
     return array;
   }

   /**
    * Compute capacity given initial capacity.
    *
    * @return final capacity, either MIN_CAPACITY, MAX_CAPACITY, or power of 2
    *         closest to the requested capacity.
    */
   private int computeCapacity(int initial) {
     if (initial < MINIMUM_CAPACITY) {
       return MINIMUM_CAPACITY;
     }
     if (initial > MAXIMUM_CAPACITY) {
       return MAXIMUM_CAPACITY;
     }
     int capacity = 1;
     while (capacity < initial) {
       capacity <<= 1;
     }
     return capacity;
   }

   /**
    * Resize the internal table to given capacity.
    */
   @SuppressWarnings("unchecked")
   private void resize(int cap) {
     int newCapacity = computeCapacity(cap);
     if (newCapacity == this.capacity) {
       return;
     }
     this.capacity = newCapacity;
     this.expandThreshold = (int) (capacity * maxLoadFactor);
     this.shrinkThreshold = (int) (capacity * minLoadFactor);
     this.hash_mask = capacity - 1;
     LinkedElement<T>[] temp = entries;
     entries = new LinkedElement[capacity];
     for (int i = 0; i < temp.length; i++) {
       LinkedElement<T> curr = temp[i];
       while (curr != null) {
         LinkedElement<T> next = curr.next;
         int index = getIndex(curr.hashCode);
         curr.next = entries[index];
         entries[index] = curr;
         curr = next;
       }
     }
   }

   /**
    * Checks if we need to shrink, and shrinks if necessary.
    */
   protected void shrinkIfNecessary() {
     if (size < this.shrinkThreshold && capacity > initialCapacity) {
       resize(capacity / expandMultiplier);
     }
   }

   /**
    * Checks if we need to expand, and expands if necessary.
    */
   protected void expandIfNecessary() {
     if (size > this.expandThreshold && capacity < MAXIMUM_CAPACITY) {
       resize(capacity * expandMultiplier);
     }
   }

   @Override
   public Iterator<T> iterator() {
     return new LinkedSetIterator();
   }

   @Override
   public String toString() {
     final StringBuilder b = new StringBuilder(getClass().getSimpleName());
     b.append("(size=").append(size).append(", modification=")
         .append(modification).append(", entries.length=")
         .append(entries.length).append(")");
     return b.toString();
   }

   /** Print detailed information of this object. */
   public void printDetails(final PrintStream out) {
     out.print(this + ", entries = [");
     for (int i = 0; i < entries.length; i++) {
       if (entries[i] != null) {
         LinkedElement<T> e = entries[i];
         out.print("\n  " + i + ": " + e);
         for (e = e.next; e != null; e = e.next) {
           out.print(" -> " + e);
         }
       }
     }
     out.println("\n]");
   }

   private class LinkedSetIterator implements Iterator<T> {
     /** The current modification epoch. */
     private int expectedModification = modification;
     /** The current index of the entry array. */
     private int index = -1;
     /** The next element to return. */
     private LinkedElement<T> next = nextNonemptyEntry();
     private LinkedElement<T> current;

     private LinkedElement<T> nextNonemptyEntry() {
       for (index++; index < entries.length && entries[index] == null; index++);
       return index < entries.length ? entries[index] : null;
     }

     @Override
     public boolean hasNext() {
       return next != null;
     }

     @Override
     public T next() {
       if (modification != expectedModification) {
         throw new ConcurrentModificationException("modification="
             + modification + " != expectedModification = " + expectedModification);
       }
       if (next == null) {
         throw new NoSuchElementException();
       }
       current = next;
       final T e = next.element;
       // find the next element
       final LinkedElement<T> n = next.next;
       next = n != null ? n : nextNonemptyEntry();
       return e;
     }

     @Override
     public void remove() {
       if (current == null) {
         throw new NoSuchElementException();
       }
       if (modification != expectedModification) {
         throw new ConcurrentModificationException("modification="
             + modification + " != expectedModification = " + expectedModification);
       }
       LightWeightHashSet.this.removeElem(current.element);
       current = null;
       expectedModification = modification;
     }
   }

   /**
    * Clear the set. Resize it to the original capacity.
    */
   @Override
   @SuppressWarnings("unchecked")
   public void clear() {
     this.capacity = this.initialCapacity;
     this.hash_mask = capacity - 1;

     this.expandThreshold = (int) (capacity * maxLoadFactor);
     this.shrinkThreshold = (int) (capacity * minLoadFactor);

     entries = new LinkedElement[capacity];
     size = 0;
     modification++;
   }

   @Override
   public Object[] toArray() {
     Object[] result = new Object[size];
     return toArray(result);
   }

   @Override
   @SuppressWarnings("unchecked")
   public <U> U[] toArray(U[] a) {
     if (a == null) {
       throw new NullPointerException("Input array can not be null");
     }
     if (a.length < size) {
       a = (U[]) java.lang.reflect.Array.newInstance(a.getClass()
           .getComponentType(), size);
     }
     int currentIndex = 0;
     for (int i = 0; i < entries.length; i++) {
       LinkedElement<T> current = entries[i];
       while (current != null) {
         a[currentIndex++] = (U) current.element;
         current = current.next;
       }
     }
     return a;
   }

   @Override
   public boolean containsAll(Collection<?> c) {
     Iterator<?> iter = c.iterator();
     while (iter.hasNext()) {
       if (!contains(iter.next())) {
         return false;
       }
     }
     return true;
   }

   @Override
   public boolean removeAll(Collection<?> c) {
     boolean changed = false;
     Iterator<?> iter = c.iterator();
     while (iter.hasNext()) {
       changed |= remove(iter.next());
     }
     return changed;
   }

   @Override
   public boolean retainAll(Collection<?> c) {
     throw new UnsupportedOperationException("retainAll is not supported.");
   }
 }
	/**
	* 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.
	*/
	package org.apache.hadoop.hdfs.util;

	import java.io.PrintStream;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.ConcurrentModificationException;
	import java.util.Iterator;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.NoSuchElementException;

	import org.apache.commons.logging.Log;
	import org.apache.commons.logging.LogFactory;

	/**
	* A low memory linked hash set implementation, which uses an array for storing
	* the elements and linked lists for collision resolution. This class does not
	* support null element.
	*
	* This class is not thread safe.
	*
	*/
	public class LightWeightHashSet<T> implements Collection<T> {
	/**
	* Elements of {@link LightWeightLinkedSet}.
	*/
	static class LinkedElement<T> {
	protected final T element;

	// reference to the next entry within a bucket linked list
	protected LinkedElement<T> next;

	//hashCode of the element
	protected final int hashCode;

	public LinkedElement(T elem, int hash) {
	this.element = elem;
	this.next = null;
	this.hashCode = hash;
	}

	@Override
	public String toString() {
	return element.toString();
	}
	}

	protected static final float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
	protected static final float DEFAUT_MIN_LOAD_FACTOR = 0.2f;
	protected static final int MINIMUM_CAPACITY = 16;

	static final int MAXIMUM_CAPACITY = 1 << 30;
	private static final Log LOG = LogFactory.getLog(LightWeightHashSet.class);

	/**
	* An internal array of entries, which are the rows of the hash table. The
	* size must be a power of two.
	*/
	protected LinkedElement<T>[] entries;
	/** Size of the entry table. */
	private int capacity;
	/** The size of the set (not the entry array). */
	protected int size = 0;
	/ Hashmask used for determining the bucket index /
	private int hash_mask;
	/ Capacity at initialization time /
	private final int initialCapacity;

	/**
	* Modification version for fail-fast.
	*
	* @see ConcurrentModificationException
	*/
	protected int modification = 0;

	private float maxLoadFactor;
	private float minLoadFactor;
	private final int expandMultiplier = 2;

	private int expandThreshold;
	private int shrinkThreshold;

	/**
	* @param initCapacity
	* Recommended size of the internal array.
	* @param maxLoadFactor
	* used to determine when to expand the internal array
	* @param minLoadFactor
	* used to determine when to shrink the internal array
	*/
	@SuppressWarnings("unchecked")
	public LightWeightHashSet(int initCapacity, float maxLoadFactor,
	float minLoadFactor) {

	if (maxLoadFactor <= 0 \|\| maxLoadFactor > 1.0f)
	throw new IllegalArgumentException("Illegal maxload factor: "
	+ maxLoadFactor);

	if (minLoadFactor <= 0 \|\| minLoadFactor > maxLoadFactor)
	throw new IllegalArgumentException("Illegal minload factor: "
	+ minLoadFactor);

	this.initialCapacity = computeCapacity(initCapacity);
	this.capacity = this.initialCapacity;
	this.hash_mask = capacity - 1;

	this.maxLoadFactor = maxLoadFactor;
	this.expandThreshold = (int) (capacity * maxLoadFactor);
	this.minLoadFactor = minLoadFactor;
	this.shrinkThreshold = (int) (capacity * minLoadFactor);

	entries = new LinkedElement[capacity];
	if (LOG.isDebugEnabled()) {
	LOG.debug("initial capacity=" + initialCapacity + ", max load factor= "
	+ maxLoadFactor + ", min load factor= " + minLoadFactor);
	}
	}

	public LightWeightHashSet() {
	this(MINIMUM_CAPACITY, DEFAULT_MAX_LOAD_FACTOR, DEFAUT_MIN_LOAD_FACTOR);
	}

	public LightWeightHashSet(int minCapacity) {
	this(minCapacity, DEFAULT_MAX_LOAD_FACTOR, DEFAUT_MIN_LOAD_FACTOR);
	}

	/**
	* Check if the set is empty.
	*
	* @return true is set empty, false otherwise
	*/
	@Override
	public boolean isEmpty() {
	return size == 0;
	}

	/**
	* Return the current capacity (for testing).
	*/
	public int getCapacity() {
	return capacity;
	}

	/**
	* Return the number of stored elements.
	*/
	@Override
	public int size() {
	return size;
	}

	/**
	* Get index in the internal table for a given hash.
	*/
	protected int getIndex(int hashCode) {
	return hashCode & hash_mask;
	}

	/**
	* Check if the set contains given element
	*
	* @return true if element present, false otherwise.
	*/
	@SuppressWarnings("unchecked")
	@Override
	public boolean contains(final Object key) {
	return getElement((T)key) != null;
	}

	/**
	* Return the element in this set which is equal to
	* the given key, if such an element exists.
	* Otherwise returns null.
	*/
	public T getElement(final T key) {
	// validate key
	if (key == null) {
	throw new IllegalArgumentException("Null element is not supported.");
	}
	// find element
	final int hashCode = key.hashCode();
	final int index = getIndex(hashCode);
	return getContainedElem(index, key, hashCode);
	}

	/**
	* Check if the set contains given element at given index. If it
	* does, return that element.
	*
	* @return the element, or null, if no element matches
	*/
	protected T getContainedElem(int index, final T key, int hashCode) {
	for (LinkedElement<T> e = entries[index]; e != null; e = e.next) {
	// element found
	if (hashCode == e.hashCode && e.element.equals(key)) {
	return e.element;
	}
	}
	// element not found
	return null;
	}

	/**
	* All all elements in the collection. Expand if necessary.
	*
	* @param toAdd - elements to add.
	* @return true if the set has changed, false otherwise
	*/
	@Override
	public boolean addAll(Collection<? extends T> toAdd) {
	boolean changed = false;
	for (T elem : toAdd) {
	changed \|= addElem(elem);
	}
	expandIfNecessary();
	return changed;
	}

	/**
	* Add given element to the hash table. Expand table if necessary.
	*
	* @return true if the element was not present in the table, false otherwise
	*/
	@Override
	public boolean add(final T element) {
	boolean added = addElem(element);
	expandIfNecessary();
	return added;
	}

	/**
	* Add given element to the hash table
	*
	* @return true if the element was not present in the table, false otherwise
	*/
	protected boolean addElem(final T element) {
	// validate element
	if (element == null) {
	throw new IllegalArgumentException("Null element is not supported.");
	}
	// find hashCode & index
	final int hashCode = element.hashCode();
	final int index = getIndex(hashCode);
	// return false if already present
	if (getContainedElem(index, element, hashCode) != null) {
	return false;
	}

	modification++;
	size++;

	// update bucket linked list
	LinkedElement<T> le = new LinkedElement<T>(element, hashCode);
	le.next = entries[index];
	entries[index] = le;
	return true;
	}

	/**
	* Remove the element corresponding to the key.
	*
	* @return If such element exists, return true. Otherwise, return false.
	*/
	@Override
	@SuppressWarnings("unchecked")
	public boolean remove(final Object key) {
	// validate key
	if (key == null) {
	throw new IllegalArgumentException("Null element is not supported.");
	}
	LinkedElement<T> removed = removeElem((T) key);
	shrinkIfNecessary();
	return removed == null ? false : true;
	}

	/**
	* Remove the element corresponding to the key, given key.hashCode() == index.
	*
	* @return If such element exists, return true. Otherwise, return false.
	*/
	protected LinkedElement<T> removeElem(final T key) {
	LinkedElement<T> found = null;
	final int hashCode = key.hashCode();
	final int index = getIndex(hashCode);
	if (entries[index] == null) {
	return null;
	} else if (hashCode == entries[index].hashCode &&
	entries[index].element.equals(key)) {
	// remove the head of the bucket linked list
	modification++;
	size--;
	found = entries[index];
	entries[index] = found.next;
	} else {
	// head != null and key is not equal to head
	// search the element
	LinkedElement<T> prev = entries[index];
	for (found = prev.next; found != null;) {
	if (hashCode == found.hashCode &&
	found.element.equals(key)) {
	// found the element, remove it
	modification++;
	size--;
	prev.next = found.next;
	found.next = null;
	break;
	} else {
	prev = found;
	found = found.next;
	}
	}
	}
	return found;
	}

	/**
	* Remove and return n elements from the hashtable.
	* The order in which entries are removed is unspecified, and
	* and may not correspond to the order in which they were inserted.
	*
	* @return first element
	*/
	public List<T> pollN(int n) {
	if (n >= size) {
	return pollAll();
	}
	List<T> retList = new ArrayList<T>(n);
	if (n == 0) {
	return retList;
	}
	boolean done = false;
	int currentBucketIndex = 0;

	while (!done) {
	LinkedElement<T> current = entries[currentBucketIndex];
	while (current != null) {
	retList.add(current.element);
	current = current.next;
	entries[currentBucketIndex] = current;
	size--;
	modification++;
	if (--n == 0) {
	done = true;
	break;
	}
	}
	currentBucketIndex++;
	}
	shrinkIfNecessary();
	return retList;
	}

	/**
	* Remove all elements from the set and return them. Clear the entries.
	*/
	public List<T> pollAll() {
	List<T> retList = new ArrayList<T>(size);
	for (int i = 0; i < entries.length; i++) {
	LinkedElement<T> current = entries[i];
	while (current != null) {
	retList.add(current.element);
	current = current.next;
	}
	}
	this.clear();
	return retList;
	}

	/**
	* Get array.length elements from the set, and put them into the array.
	*/
	@SuppressWarnings("unchecked")
	public T[] pollToArray(T[] array) {
	int currentIndex = 0;
	LinkedElement<T> current = null;

	if (array.length == 0) {
	return array;
	}
	if (array.length > size) {
	array = (T[]) java.lang.reflect.Array.newInstance(array.getClass()
	.getComponentType(), size);
	}
	// do fast polling if the entire set needs to be fetched
	if (array.length == size) {
	for (int i = 0; i < entries.length; i++) {
	current = entries[i];
	while (current != null) {
	array[currentIndex++] = current.element;
	current = current.next;
	}
	}
	this.clear();
	return array;
	}

	boolean done = false;
	int currentBucketIndex = 0;

	while (!done) {
	current = entries[currentBucketIndex];
	while (current != null) {
	array[currentIndex++] = current.element;
	current = current.next;
	entries[currentBucketIndex] = current;
	size--;
	modification++;
	if (currentIndex == array.length) {
	done = true;
	break;
	}
	}
	currentBucketIndex++;
	}
	shrinkIfNecessary();
	return array;
	}

	/**
	* Compute capacity given initial capacity.
	*
	* @return final capacity, either MIN_CAPACITY, MAX_CAPACITY, or power of 2
	* closest to the requested capacity.
	*/
	private int computeCapacity(int initial) {
	if (initial < MINIMUM_CAPACITY) {
	return MINIMUM_CAPACITY;
	}
	if (initial > MAXIMUM_CAPACITY) {
	return MAXIMUM_CAPACITY;
	}
	int capacity = 1;
	while (capacity < initial) {
	capacity <<= 1;
	}
	return capacity;
	}

	/**
	* Resize the internal table to given capacity.
	*/
	@SuppressWarnings("unchecked")
	private void resize(int cap) {
	int newCapacity = computeCapacity(cap);
	if (newCapacity == this.capacity) {
	return;
	}
	this.capacity = newCapacity;
	this.expandThreshold = (int) (capacity * maxLoadFactor);
	this.shrinkThreshold = (int) (capacity * minLoadFactor);
	this.hash_mask = capacity - 1;
	LinkedElement<T>[] temp = entries;
	entries = new LinkedElement[capacity];
	for (int i = 0; i < temp.length; i++) {
	LinkedElement<T> curr = temp[i];
	while (curr != null) {
	LinkedElement<T> next = curr.next;
	int index = getIndex(curr.hashCode);
	curr.next = entries[index];
	entries[index] = curr;
	curr = next;
	}
	}
	}

	/**
	* Checks if we need to shrink, and shrinks if necessary.
	*/
	protected void shrinkIfNecessary() {
	if (size < this.shrinkThreshold && capacity > initialCapacity) {
	resize(capacity / expandMultiplier);
	}
	}

	/**
	* Checks if we need to expand, and expands if necessary.
	*/
	protected void expandIfNecessary() {
	if (size > this.expandThreshold && capacity < MAXIMUM_CAPACITY) {
	resize(capacity * expandMultiplier);
	}
	}

	@Override
	public Iterator<T> iterator() {
	return new LinkedSetIterator();
	}

	@Override
	public String toString() {
	final StringBuilder b = new StringBuilder(getClass().getSimpleName());
	b.append("(size=").append(size).append(", modification=")
	.append(modification).append(", entries.length=")
	.append(entries.length).append(")");
	return b.toString();
	}

	/** Print detailed information of this object. */
	public void printDetails(final PrintStream out) {
	out.print(this + ", entries = [");
	for (int i = 0; i < entries.length; i++) {
	if (entries[i] != null) {
	LinkedElement<T> e = entries[i];
	out.print("\n " + i + ": " + e);
	for (e = e.next; e != null; e = e.next) {
	out.print(" -> " + e);
	}
	}
	}
	out.println("\n]");
	}

	private class LinkedSetIterator implements Iterator<T> {
	/** The current modification epoch. */
	private int expectedModification = modification;
	/** The current index of the entry array. */
	private int index = -1;
	/** The next element to return. */
	private LinkedElement<T> next = nextNonemptyEntry();
	private LinkedElement<T> current;

	private LinkedElement<T> nextNonemptyEntry() {
	for (index++; index < entries.length && entries[index] == null; index++);
	return index < entries.length ? entries[index] : null;
	}

	@Override
	public boolean hasNext() {
	return next != null;
	}

	@Override
	public T next() {
	if (modification != expectedModification) {
	throw new ConcurrentModificationException("modification="
	+ modification + " != expectedModification = " + expectedModification);
	}
	if (next == null) {
	throw new NoSuchElementException();
	}
	current = next;
	final T e = next.element;
	// find the next element
	final LinkedElement<T> n = next.next;
	next = n != null ? n : nextNonemptyEntry();
	return e;
	}

	@Override
	public void remove() {
	if (current == null) {
	throw new NoSuchElementException();
	}
	if (modification != expectedModification) {
	throw new ConcurrentModificationException("modification="
	+ modification + " != expectedModification = " + expectedModification);
	}
	LightWeightHashSet.this.removeElem(current.element);
	current = null;
	expectedModification = modification;
	}
	}

	/**
	* Clear the set. Resize it to the original capacity.
	*/
	@Override
	@SuppressWarnings("unchecked")
	public void clear() {
	this.capacity = this.initialCapacity;
	this.hash_mask = capacity - 1;

	this.expandThreshold = (int) (capacity * maxLoadFactor);
	this.shrinkThreshold = (int) (capacity * minLoadFactor);

	entries = new LinkedElement[capacity];
	size = 0;
	modification++;
	}

	@Override
	public Object[] toArray() {
	Object[] result = new Object[size];
	return toArray(result);
	}

	@Override
	@SuppressWarnings("unchecked")
	public <U> U[] toArray(U[] a) {
	if (a == null) {
	throw new NullPointerException("Input array can not be null");
	}
	if (a.length < size) {
	a = (U[]) java.lang.reflect.Array.newInstance(a.getClass()
	.getComponentType(), size);
	}
	int currentIndex = 0;
	for (int i = 0; i < entries.length; i++) {
	LinkedElement<T> current = entries[i];
	while (current != null) {
	a[currentIndex++] = (U) current.element;
	current = current.next;
	}
	}
	return a;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
	Iterator<?> iter = c.iterator();
	while (iter.hasNext()) {
	if (!contains(iter.next())) {
	return false;
	}
	}
	return true;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
	boolean changed = false;
	Iterator<?> iter = c.iterator();
	while (iter.hasNext()) {
	changed \|= remove(iter.next());
	}
	return changed;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
	throw new UnsupportedOperationException("retainAll is not supported.");
	}
	}