For this assignment, you will create hash set using linear probing to handle collissions. Our hash set implements the "CiscCollection" interface.
| CiscHashSet< E > implements CiscCollection< E > |
| - f_MAX_LOAD_FACTOR: double = 0.75 - elementDate: Object[] - size: int - numRemoved: int - f_REMOVED: Object = new Object(); |
| + CiscHashSet() + size(): int + isEmpty(): boolean + clear(): void + contains(value: Object): boolean + iterator(): Iterator E + toArray(): Object[] + add(value: E): void + remove(value: Object): void + toString(): String + hashFunction(value: Object): int + rehash(): void |
| CiscHashSetIterator implements Iterator< E > |
| - nextIndex: int |
| + CiscHashSetIterator() + hasNext(): boolean + next(): E |
MAX_LOAD_FACTOR: double
This static final constant indicates the maximum load factor before rehashing is required.
elementData: Object[]
The underlying circular array buffer used as a hash table. Its initial capacity should be 11.
size: int
The number of elements in the CiscHashSet.
numRemoved: int
The number of REMOVED placeholders in the CiscHashSet.
REMOVED : Object
This static final constant refers to an "empty" Object used to indicate hash table indices that had values removed.
CiscHashSet() Constructs
a CiscHashSet instance, and creates elementData with an initial capacity of 11.
size() : int
The size method should return the number of elements in the set.
isEmpty() : boolean
The isEmtpy method should return true if set is empty, false otherwise.
clear() : void
This method should effectively empty the set of all elements.
contains(value : Object) : boolean
This method should return true if the provided value is present in the set, false otherwise. Your implementation should not evaluate more hash table indices than necessary.
iterator() : Iterator< E >
This method should create and return an instance of CiscHashSetIterator.
toArray() : Object[]
This method returns an array containing all the elements in the set, as stored in the underlying array. The length of the returned array is equal to the number of elements in the set.
add(value : E) : void
This method should add the provided value to the set. If the value is already present, it should have no effect. Before adding a new element, this method should call the rehash method if the maximum load factor (which should take into account both size and numRemoved) has been reached (but only after it has determined that a new element will be added). Your implementation should not evaluate more hash table indices than necessary, and it should not call the contains method.
remove(value : Object) : void
This method should remove the provided value from the set. If the value is not present, it should have no effect. Your implementation should not evaluate more hash table indices than necessary, and it should not call the contains method.
toString() : String
This method should return a string representation of the set containing only actual values in the set, in the order in which they are present in the set, using the format: "[10, 8, 9, 5, 3, 7, 2]" for a non-empty set or "[]" for an empty set.
hashFunction(value : Object) : int
This private method should return the index to which the provided value hashes in the underlying hash table. It should compute this index by taking the absolute value of the value's hashCode and modding it with the capacity of the hash table.
rehash() : void
This private method should replace elementData with a new array having a capacity equal to the twice the old capacity plus 1. It should repeatedly call the add method to re-add all previously added elements in the set.
This class should be private and non-static.
nextIndex : int
This instance variable should keep track of the index in the hash table containing the next element value to return.
CiscHashSetIterator()
Constructs a CiscHashSetIterator to iterate over a CiscHashMap instance. Ensures that the initial value of nextIndex is appropriate (possibly by calling a helper method)
hasNext() : boolean
Returns true if the iterator has yet to return all entries in the set.
next() : E
Returns the next element in the set, determined by the order of the elements in the hash table. Updates the value of nextIndex (possibly by calling a helper method).