1 import java.util.*;
2
3 public class MyHashSet<E> implements Collection<E> {
4
5 private final static int DEFAULT_INITIAL_CAPACITY = 4;
6
7
8 private final static int MAXIMUM_CAPACITY = 1 << 30;
9
10
11 private int capacity;
12
13
14 private final static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
15
16
17 private float loadFactorThreshold;
18
19
20 private int size = 0;
21
22
23 private LinkedList<E>[] table;
24
25
26 public MyHashSet() {
27 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
28 }
29
30
32 public MyHashSet(int initialCapacity) {
33 this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
34 }
35
36
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
49 public void clear() {
50 size = 0;
51 removeElements();
52 }
53
54 @Override
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
66 public boolean add(E e) {
67 if (contains(e))
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
80 if (table[bucketIndex] == null) {
81 table[bucketIndex] = new LinkedList<E>();
82 }
83
84
85 table[bucketIndex].add(e);
86
87 size++;
88
89 return true;
90 }
91
92 @Override
93 public boolean remove(Object e) {
94 if (!contains(e))
95 return false;
96
97 int bucketIndex = hash(e.hashCode());
98
99
100 if (table[bucketIndex] != null) {
101 LinkedList<E> bucket = table[bucketIndex];
102 bucket.remove(e);
103 }
104
105 size--;
106
107 return true;
108 }
109
110 @Override
111 public boolean isEmpty() {
112 return size == 0;
113 }
114
115 @Override
116 public int size() {
117 return size;
118 }
119
120 @Override
121 public java.util.Iterator<E> iterator() {
122 return new MyHashSetIterator(this);
123 }
124
125
126 private class MyHashSetIterator implements java.util.Iterator<E> {
127
128 private java.util.ArrayList<E> list;
129 private int current = 0;
130 private MyHashSet<E> set;
131
132
133 public MyHashSetIterator(MyHashSet<E> set) {
134 this.set = set;
135 list = setToList();
136 }
137
138 @Override
139 public boolean hasNext() {
140 return current < list.size();
141 }
142
143 @Override
144 public E next() {
145 return list.get(current++);
146 }
147
148 @Override
149 public void remove() {
150
151
152
153 }
154 }
155
156
157 private int hash(int hashCode) {
158 return hashCode & (capacity - 1);
159 }
160
161
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
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
181 private void rehash() {
182 java.util.ArrayList<E> list = setToList();
183 capacity <<= 1;
184 table = new LinkedList[capacity];
185 size = 0;
186
187 for (E element: list) {
188 add(element);
189 }
190 }
191
192
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
213 for (int i = 0; i < list.size() - 1; i++) {
214 builder.append(list.get(i) + ", ");
215 }
216
217
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
229 return false;
230 }
231
232 @Override
233 public boolean containsAll(Collection<?> arg0) {
234
235 return false;
236 }
237
238 @Override
239 public boolean removeAll(Collection<?> arg0) {
240
241 return false;
242 }
243
244 @Override
245 public boolean retainAll(Collection<?> arg0) {
246
247 return false;
248 }
249
250 @Override
251 public Object[] toArray() {
252
253 return null;
254 }
255
256 @Override
257 public <T> T[] toArray(T[] arg0) {
258
259 return null;
260 }
261 }