public class QuadraticProbeHashTable
2: import java.util.Arrays;
4: /**
5: * A class implementing a hash table using open addressing. The open addressing
6: * scheme is quadratic probing -- try the locations 1, 4, 9, 16, ... positions
7: * after the original location.
8: *
9: * @author Mark Young (A00000000)
10: */
11: public class QuadraticProbeHashTable {
12:
13: private static final int DEFAULT_SIZE = 13;
14: private static final double MAX_LOAD = 0.75;
15:
16: private Integer[] contents;
17: private int numInTable;
18:
19: /**
20: * Create an empty hash table.
21: */
22: public QuadraticProbeHashTable() {
23: contents = new Integer[DEFAULT_SIZE];
24: numInTable = 0;
25: }
26:
27: /**
28: * Add the given item to this HT.
29: *
30: * @param anItem the item to add.
31: * @return true if {@code anItem} was added; false otherwise.
32: */
33: public boolean insert(int anItem) {
34: int posn, step;
35:
36: // check for overload
37: if ((numInTable + 1)/MAX_LOAD > contents.length) {
38: if (!resize()) {
39: return false;
40: }
41: }
42:
43: // insert the item (or fail if it's found)
44: step = 0;
45: do {
46: posn = (anItem + step*step) % contents.length;
47: if (contents[posn] == null) {
48: contents[posn] = anItem;
49: ++numInTable;
50: return true;
51: }
52: if (contents[posn].equals(anItem)) {
53: return false;
54: }
55: ++step;
56: } while (true);
57: }
58:
59: /**
60: * Remove the given item from this HT.STUB!
61: *
62: *
63: * @param anItem the item to remove.
64: * @return true if {@code anItem} was deleted; false otherwise.
65: */
66: public boolean delete(int anItem) {
67: throw new UnsupportedOperationException();
68: }
69:
70: /**
71: * Check whether this HT contains the given value.
72: *
73: * @param anItem the item to check for.
74: * @return true if anItem is in this HT; false otherwise.
75: */
76: public boolean contains(int anItem) {
77: int posn, step;
78:
79: // look for the item
80: step = 0;
81: do {
82: posn = (anItem + step*step) % contents.length;
83: if (contents[posn] == null) {
84: return false;
85: }
86: if (contents[posn].equals(anItem)) {
87: return true;
88: }
89: ++step;
90: } while (true);
91: }
92:
93: /**
94: * Make a String representation of this HT.
95: *
96: * @return a String representing the array of this HT's contents.
97: */
98: @Override
99: public String toString() {
100: return Arrays.toString(contents);
101: }
102:
103: /**
104: * Make this HT larger.
105: *
106: * STUB!
107: *
108: * @return true if this HT was enlarged; false otherwise.
109: */
110: private boolean resize() {
111: return false;
112: }
114: }