| Line 67... |
Line 67... |
| 67 |
|
67 |
|
| 68 |
System.out.print(key); //print out the key
|
68 |
System.out.print(key); //print out the key
|
| 69 |
|
69 |
|
| 70 |
int h=hash(key); //hash the key
|
70 |
int h=hash(key); //hash the key
|
| 71 |
|
71 |
|
| - |
|
72 |
//run once for each position in the Table
|
| 72 |
for (int i=0; i<entries.length; i++) { //run once for each place in the Table
|
73 |
for (int i=0; i<entries.length; i++) {
|
| 73 |
int j = nextProbe(h,i); //get the [first, next] place to try putting the value
|
74 |
//get the [first, next] place to try putting the value
|
| - |
|
75 |
int j = nextProbe(h,i);
|
| 74 |
Entry entry=entries[j]; //get the Entry at j (where we want to put value)
|
76 |
//get the Entry at j (where we want to put value)
|
| - |
|
77 |
Entry entry=entries[j];
|
| 75 |
|
78 |
|
| 76 |
System.out.print(" -> " + j); //print the location we tried to place the value
|
79 |
//print the location we tried to place the value
|
| - |
|
80 |
System.out.print(" -> " + j);
|
| 77 |
|
81 |
|
| 78 |
//if entry[j] == null then we have found a good place to put value!
|
82 |
//if entry[j] == null then we have found a good place to put value!
|
| 79 |
if (entry==null) {
|
83 |
if (entry==null) {
|
| 80 |
|
84 |
|
| 81 |
System.out.println(); //terminate the line
|
85 |
System.out.println(); //terminate the line
|
| Line 106... |
Line 110... |
| 106 |
} //end for loop
|
110 |
} //end for loop
|
| 107 |
|
111 |
|
| 108 |
return null; // failure: table overflow
|
112 |
return null; // failure: table overflow
|
| 109 |
} //end put()
|
113 |
} //end put()
|
| 110 |
|
114 |
|
| 111 |
//Method to remove a key/value pair from the table. This will leave a NIL behind
|
115 |
//Method to remove a key/value pair from the table.
|
| - |
|
116 |
//This will leave a NIL behind
|
| 112 |
//Precondition: key != null
|
117 |
//Precondition: key != null
|
| 113 |
//Postcondition: return the old value if the key was found, then put a NIL in it's place
|
118 |
//Postcondition: return the old value if the key was found, then
|
| - |
|
119 |
// put a NIL in it's place. return null if the key
|
| 114 |
// return null if the key was not found in the table.
|
120 |
// was not found in the table.
|
| 115 |
public Object remove(Object key) {
|
121 |
public Object remove(Object key) {
|
| 116 |
int h=hash(key); //hash the key
|
122 |
int h=hash(key); //hash the key
|
| - |
|
123 |
//run once for every place in the table
|
| 117 |
for (int i=0; i<entries.length; i++) { //run once for every place in the table
|
124 |
for (int i=0; i<entries.length; i++) {
|
| 118 |
int j = nextProbe(h,i); //find the [first, next] place to put the value
|
125 |
//find the [first, next] place to put the value
|
| - |
|
126 |
int j = nextProbe(h,i);
|
| 119 |
Entry entry=entries[j];
|
127 |
Entry entry=entries[j];
|
| 120 |
|
128 |
|
| 121 |
if (entry==null) break; //break out of the loop, since the key was not found
|
129 |
//break out of the loop, since the key was not found
|
| - |
|
130 |
if (entry==null) break;
|
| 122 |
if (entry==NIL) continue; //keep going, since we found a NIL
|
131 |
if (entry==NIL) continue; //keep going, since we found a NIL
|
| 123 |
if (entry.key.equals(key)) { //we found the key we are looking for...
|
132 |
if (entry.key.equals(key)) { //we found the key we are looking for...
|
| 124 |
Object oldValue=entry.value; //save value to return
|
133 |
Object oldValue=entry.value; //save value to return
|
| 125 |
entries[j] = NIL; //replace the value with a NIL
|
134 |
entries[j] = NIL; //replace the value with a NIL
|
| 126 |
--size; //decrement size
|
135 |
--size; //decrement size
|
| Line 156... |
Line 165... |
| 156 |
//
|
165 |
//
|
| 157 |
//Precondition: 0 <= newValue <= 6
|
166 |
//Precondition: 0 <= newValue <= 6
|
| 158 |
//Postcondition: probeType will be changed
|
167 |
//Postcondition: probeType will be changed
|
| 159 |
//WARNING: Please do NOT change probeType while in a test run
|
168 |
//WARNING: Please do NOT change probeType while in a test run
|
| 160 |
public void setProbeType( int newValue ) {
|
169 |
public void setProbeType( int newValue ) {
|
| - |
|
170 |
//put in for safety, just in case
|
| 161 |
if( newValue < 0 || newValue > 6 ) { newValue = 0; } //put in for safety, just in case
|
171 |
if( newValue < 0 || newValue > 6 ) { newValue = 0; }
|
| 162 |
probeType = newValue;
|
172 |
probeType = newValue;
|
| 163 |
}
|
173 |
}
|
| 164 |
|
174 |
|
| 165 |
//A private class which will hold a key/value pair
|
175 |
//A private class which will hold a key/value pair
|
| 166 |
private class Entry {
|
176 |
private class Entry {
|