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 }