HashSet.java.html

  1  import java.util.Iterator;
  2  import java.util.NoSuchElementException;
  3  
  4  /**
  5     This class implements a hash set using separate chaining.
  6  */
  7  public class HashSet
  8  {
  9     private Node[] buckets;
 10     private int currentSize;
 11  
 12     /**
 13        Constructs a hash table.
 14        @param bucketsLength the length of the buckets array
 15     */
 16     public HashSet(int bucketsLength)
 17     {
 18        buckets = new Node[bucketsLength];
 19        currentSize = 0;
 20     }
 21  
 22     /**
 23        Tests for set membership.
 24        @param x an object
 25        @return true if x is an element of this set
 26     */
 27     public boolean contains(Object x)
 28     {
 29        int h = x.hashCode();
 30        if (h < 0) { h = -h; }
 31        h = h % buckets.length;
 32        
 33        Node current = buckets[h];
 34        while (current != null)
 35        {
 36           if (current.data.equals(x)) { return true; }
 37           current = current.next;
 38        }
 39        return false;
 40     }
 41  
 42     /**
 43        Adds an element to this set.
 44        @param x an object
 45        @return true if x is a new object, false if x was
 46        already in the set
 47     */
 48     public boolean add(Object x)
 49     {
 50        int h = x.hashCode();
 51        if (h < 0) { h = -h; }
 52        h = h % buckets.length;
 53        
 54        Node current = buckets[h];
 55        while (current != null)
 56        {
 57           if (current.data.equals(x)) { return false; }
 58              // Already in the set
 59           current = current.next;
 60        }
 61        Node newNode = new Node();
 62        newNode.data = x;
 63        newNode.next = buckets[h];
 64        buckets[h] = newNode;
 65        currentSize++;
 66        return true;
 67     }
 68  
 69     /**
 70        Removes an object from this set.
 71        @param x an object
 72        @return true if x was removed from this set, false
 73        if x was not an element of this set
 74     */
 75     public boolean remove(Object x)
 76     {
 77        int h = x.hashCode();
 78        if (h < 0) { h = -h; }
 79        h = h % buckets.length;
 80        
 81        Node current = buckets[h];
 82        Node previous = null;
 83        while (current != null)
 84        {
 85           if (current.data.equals(x)) 
 86           {
 87              if (previous == null) { buckets[h] = current.next; }
 88              else { previous.next = current.next; }
 89              currentSize--;
 90              return true;
 91           }
 92           previous = current;
 93           current = current.next;
 94        }
 95        return false;
 96     }
 97  
 98     /**
 99        Returns an iterator that traverses the elements of this set.
100        @return a hash set iterator
101     */
102     public Iterator iterator()
103     {
104        return new HashSetIterator();
105     }
106  
107     /**
108        Gets the number of elements in this set.
109        @return the number of elements
110     */
111     public int size()
112     {
113        return currentSize;
114     }
115  
116     class Node
117     {
118        public Object data;
119        public Node next;
120     }
121  
122     class HashSetIterator implements Iterator
123     {
124        private int bucketIndex;
125        private Node current;
126  
127        /**
128           Constructs a hash set iterator that points to the
129           first element of the hash set.
130        */
131        public HashSetIterator()
132        {
133           current = null;
134           bucketIndex = -1;
135        }
136        
137        public boolean hasNext()
138        {
139           if (current != null && current.next != null) { return true; }
140           for (int b = bucketIndex + 1; b < buckets.length; b++)
141           {
142              if (buckets[b] != null) { return true; }
143           }
144           return false;
145        }
146         
147        public Object next()
148        {
149           if (current != null && current.next != null) 
150           {            
151              current = current.next; // Move to next element in bucket
152           }
153           else // Move to next bucket
154           {            
155              do
156              {
157                 bucketIndex++;
158                 if (bucketIndex == buckets.length) 
159                 {
160                    throw new NoSuchElementException();
161                 }
162                 current = buckets[bucketIndex];
163              }
164              while (current == null);            
165           }
166           return current.data;
167        }
168  
169        public void remove()
170        {
171           throw new UnsupportedOperationException();
172        }
173     }
174  }