1  import java.util.*;
  2  
  3  public class MyHashSet<E> implements Collection<E> {
  4    // Define the default hash table size. Must be a power of 2
  5    private final static int DEFAULT_INITIAL_CAPACITY = 4;
  6    
  7    // Define the maximum hash table size. 1 << 30 is same as 2^30
  8    private final static int MAXIMUM_CAPACITY = 1 << 30; 
  9    
 10    // Current hash table capacity. Capacity is a power of 2
 11    private int capacity;
 12    
 13    // Define default load factor
 14    private final static float DEFAULT_MAX_LOAD_FACTOR = 0.75f; 
 15  
 16    // Specify a load factor threshold used in the hash table
 17    private float loadFactorThreshold; 
 18    
 19    // The number of elements in the set
 20    private int size = 0; 
 21    
 22    // Hash table is an array with each cell that is a linked list
 23    private LinkedList<E>[] table;
 24  
 25    /** Construct a set with the default capacity and load factor */
 26    public MyHashSet() {  
 27      this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);    
 28    }
 29    
 30    /** Construct a set with the specified initial capacity and 
 31     * default load factor */
 32    public MyHashSet(int initialCapacity) { 
 33      this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);    
 34    }
 35    
 36    /** Construct a set with the specified initial capacity 
 37     * and load factor */
 38    public MyHashSet(int initialCapacity, float loadFactorThreshold) { 
 39      if (initialCapacity > MAXIMUM_CAPACITY)
 40        this.capacity = MAXIMUM_CAPACITY;
 41      else
 42        this.capacity = trimToPowerOf2(initialCapacity);
 43      
 44      this.loadFactorThreshold = loadFactorThreshold;    
 45      table = new LinkedList[capacity];
 46    }
 47    
 48    @Override /** Remove all elements from this set */ 
 49    public void clear() {
 50      size = 0;
 51      removeElements();
 52    }
 53  
 54    @Override /** Return true if the element is in the set */
 55    public boolean contains(Object e) {
 56      int bucketIndex = hash(e.hashCode());
 57      if (table[bucketIndex] != null) {
 58        LinkedList<E> bucket = table[bucketIndex]; 
 59        return bucket.contains(e);
 60      }
 61      
 62      return false;
 63    }
 64    
 65    @Override /** Add an element to the set */
 66    public boolean add(E e) {
 67      if (contains(e)) // Duplicate element not stored
 68        return false;
 69      
 70      if (size + 1 > capacity * loadFactorThreshold) {
 71        if (capacity == MAXIMUM_CAPACITY)
 72          throw new RuntimeException("Exceeding maximum capacity");
 73      
 74        rehash();
 75      }
 76      
 77      int bucketIndex = hash(e.hashCode());
 78      
 79      // Create a linked list for the bucket if it is not created
 80      if (table[bucketIndex] == null) {
 81        table[bucketIndex] = new LinkedList<E>();
 82      }
 83  
 84      // Add e to hashTable[index]
 85      table[bucketIndex].add(e);
 86  
 87      size++; // Increase size
 88      
 89      return true;
 90    }
 91  
 92    @Override /** Remove the element from the set */
 93    public boolean remove(Object e) {
 94      if (!contains(e))
 95        return false;
 96      
 97      int bucketIndex = hash(e.hashCode());
 98      
 99      // Create a linked list for the bucket if it is not created
100      if (table[bucketIndex] != null) {
101        LinkedList<E> bucket = table[bucketIndex]; 
102        bucket.remove(e);
103      }
104  
105      size--; // Decrease size
106      
107      return true;
108    }
109  
110    @Override /** Return true if the set contains no elements */
111    public boolean isEmpty() {
112      return size == 0;
113    }
114  
115    @Override /** Return the number of elements in the set */
116    public int size() {
117      return size;
118    }
119  
120    @Override /** Return an iterator for the elements in this set */
121    public java.util.Iterator<E> iterator() {
122      return new MyHashSetIterator(this);
123    }
124    
125    /** Inner class for iterator */
126    private class MyHashSetIterator implements java.util.Iterator<E> {
127      // Store the elements in a list
128      private java.util.ArrayList<E> list;
129      private int current = 0; // Point to the current element in list
130      private MyHashSet<E> set;
131      
132      /** Create a list from the set */
133      public MyHashSetIterator(MyHashSet<E> set) {
134        this.set = set;
135        list = setToList();
136      }
137  
138      @Override /** Next element for traversing? */
139      public boolean hasNext() {
140        return current < list.size();
141      }
142  
143      @Override /** Get current element and move cursor to the next */
144      public E next() {
145        return list.get(current++);
146      }
147  
148      @Override /** Remove the element returned by the last next() */
149      public void remove() {
150        // Left as an exercise
151        // You need to remove the element from the set
152        // You also need to remove it from the list
153      }
154    }  
155    
156    /** Hash function */
157    private int hash(int hashCode) {
158      return hashCode & (capacity - 1);
159    }
160  
161    /** Return a power of 2 for initialCapacity */
162    private int trimToPowerOf2(int initialCapacity) {
163      int capacity = 1;
164      while (capacity < initialCapacity) {
165        capacity <<= 1;
166      }
167      
168      return capacity;
169    }
170    
171    /** Remove all e from each bucket */
172    private void removeElements() {
173      for (int i = 0; i < capacity; i++) {
174        if (table[i] != null) {
175          table[i].clear();
176        }
177      }
178    }
179    
180    /** Rehash the set */
181    private void rehash() {
182      java.util.ArrayList<E> list = setToList(); // Copy to a list
183      capacity <<= 1; // Double capacity      
184      table = new LinkedList[capacity]; // Create a new hash table
185      size = 0; // Reset size 
186      
187      for (E element: list) {
188        add(element); // Add from the old table to the new table
189      }
190    }
191  
192    /** Copy elements in the hash set to an array list */
193    private java.util.ArrayList<E> setToList() {
194      java.util.ArrayList<E> list = new java.util.ArrayList<>();
195      
196      for (int i = 0; i < capacity; i++) {
197        if (table[i] != null) {
198          for (E e: table[i]) {
199            list.add(e);
200          }
201        }
202      }  
203      
204      return list;
205    }
206  
207    @Override
208    public String toString() {
209      java.util.ArrayList<E> list = setToList();
210      StringBuilder builder = new StringBuilder("[");
211      
212      // Add the elements except the last one to the string builder
213      for (int i = 0; i < list.size() - 1; i++) {
214        builder.append(list.get(i) + ", ");
215      }
216      
217      // Add the last element in the list to the string builder
218      if (list.size() == 0)
219        builder.append("]");
220      else
221        builder.append(list.get(list.size() - 1) + "]");
222      
223      return builder.toString();
224    }
225  
226    @Override
227    public boolean addAll(Collection<? extends E> arg0) {
228      // Left as an exercise
229      return false;
230    }
231  
232    @Override
233    public boolean containsAll(Collection<?> arg0) {
234      // Left as an exercise
235      return false;
236    }
237  
238    @Override
239    public boolean removeAll(Collection<?> arg0) {
240      // Left as an exercise
241      return false;
242    }
243  
244    @Override
245    public boolean retainAll(Collection<?> arg0) {
246      // Left as an exercise
247      return false;
248    }
249  
250    @Override
251    public Object[] toArray() {
252      // Left as an exercise
253      return null;
254    }
255  
256    @Override
257    public <T> T[] toArray(T[] arg0) {
258      // Left as an exercise
259      return null;
260    }
261  }