<><><><><><><><><><><> HashSet.java <><><><><><><><><><><><> 18.1 Hashing 1077 [

Question

<><><><><><><><><><><> HashSet.java <><><><><><><><><><><><>

18.1 Hashing 1077 [0 [1 [2 [3 [4] [51 6 [7 [8 [9] lementData size7 1 91 45 71 Figure 18.6 Hash collisions resolved by separate chaining

Explanation / Answer

import java.util.Arrays; public class HashSet implements Set { private static final double MAX_LOAD = 0.75; // load factor on which to rehash private Node[] elements; private int size; // Constructs a new empty set of integers. @SuppressWarnings("unchecked") public HashSet() { elements = (Node[]) new HashSet.Node[10]; size = 0; } // Adds the given value to this set, // if it was not already contained in the set. public void add(E value) { // linear probing to find proper index if (!contains(value)) { int h = hash(value); Node newNode = new Node(value); newNode.next = elements[h]; elements[h] = newNode; size++; } // resize if necessary if (loadFactor() > MAX_LOAD) { rehash(); } } // Returns whether the given value is found in this set. public boolean contains(E value) { // linear probing to find proper index int h = hash(value); Node current = elements[h]; while (current != null) { if (current.data.equals(value)) { return true; } current = current.next; } return false; } // Returns true if there are no elements in this set. public boolean isEmpty() { return size == 0; } // Returns the hash table's "load factor", its ratio of size to capacity. public double loadFactor() { return (double) size / elements.length; } // Removes the given element value from this set, // if it was found in the set. public void remove(E value) { // linear probing to find proper index int h = hash(value); if (elements[h] != null) { // front case if (elements[h].data.equals(value)) { elements[h] = elements[h].next; } else { // non-front case Node current = elements[h]; while (current.next != null && !current.next.data.equals(value)) { current = current.next; } // current.next == null // || current.next.data == value if (current.next != null) { current.next = current.next.next; } } } } // Returns the number of elements in this set. public int size() { return size; } // Returns a text representation of this set. // TODO: finish (this is not a proper toString; it shows the internal array) public String toString() { return Arrays.toString(elements); } // Debugging helper that prints the inner hash table. public void debug() { System.out.println("debug() output:"); System.out.printf("index data "); for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.