Subversion Repositories programming

Rev

Rev 11 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 11 Rev 16
Line 63... Line 63...
63 
    //               return null if the table overflows (should never happen,
 63 
    //               return null if the table overflows (should never happen,
64 
    //               but it is there just in case)
 64 
    //               but it is there just in case)
65 
    public Object put(Object key, Object value) {
 65 
    public Object put(Object key, Object value) {
66 
        if (used>loadFactor*entries.length) rehash();
 66 
        if (used>loadFactor*entries.length) rehash();
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 
	for (int i=0; i<entries.length; i++) { //run once for each place in the Table
 72 
        for (int i=0; i<entries.length; i++) { //run once for each place in the Table
73 
            int j = nextProbe(h,i); //get the [first, next] place to try putting the value
 73 
            int j = nextProbe(h,i); //get the [first, next] place to try putting the value
74 
            Entry entry=entries[j]; //get the Entry at j (where we want to put value)
 74 
            Entry entry=entries[j]; //get the Entry at j (where we want to put value)
75
75
76 
	    System.out.print(" -> " + j); //print the location we tried to place the value
 76 
            System.out.print(" -> " + j); //print the location we tried to place the value
77
77
78 
	    //if entry[j] == null then we have found a good place to put value!
 78 
            //if entry[j] == null then we have found a good place to put value!
79 
	    if (entry==null) {
 79 
            if (entry==null) {
80 
 
 80
81 
                System.out.println(); //terminate the line
 81 
                System.out.println(); //terminate the line
82
82
83 
                entries[j] = new Entry(key,value);
 83 
                entries[j] = new Entry(key,value);
84 
                ++size;
 84 
                ++size;
85 
                ++used;
 85 
                ++used;
86 
                return null;  // insertion success
 86 
                return null;  // insertion success
87 
            }
 87 
            }
88
88
89 
	    //if entry[j] == NIL then we must continue to probe for a new place,
 89 
            //if entry[j] == NIL then we must continue to probe for a new place,
90 
	    //otherwise we will confuse the remove() and get() methods
 90 
            //otherwise we will confuse the remove() and get() methods
91 
            if (entry==NIL) { collisions++; continue; }
 91 
            if (entry==NIL) { collisions++; continue; }
92 
 
 92 
 
93 
	    //if entry[j].key == key then we need to update the record
 93 
            //if entry[j].key == key then we need to update the record
94 
            if (entry.key.equals(key)) {
 94 
            if (entry.key.equals(key)) {
95 
                Object oldValue=entry.value;
 95 
                Object oldValue=entry.value;
96 
                entries[j].value = value;
 96 
                entries[j].value = value;
97 
                return oldValue;  // update success
 97 
                return oldValue;  // update success
98 
            }
 98 
            }
99 
 
 99 
 
100 
	    //if we get here, we have had a collision that is not a NIL,
 100 
            //if we get here, we have had a collision that is not a NIL,
101 
	    //and is not an Entry that needs updating, therefore it is something
 101 
            //and is not an Entry that needs updating, therefore it is something
102 
	    //else that hashes to the same value.  Therefore we must increment the
 102 
            //else that hashes to the same value.  Therefore we must increment the
103 
	    //collision counter
 103 
            //collision counter
104 
	    collisions++;
 104 
            collisions++;
105
105
- 
 
 106 
        } //end for loop
106 
	}
 107
107 
        return null;  // failure: table overflow
 108 
    return null;  // failure: table overflow
108 
    }
 109 
    } //end put()
109 
 
 110 
 
110 
    //Method to remove a key/value pair from the table.  This will leave a NIL behind
 111 
    //Method to remove a key/value pair from the table.  This will leave a NIL behind
111 
    //Precondition: key != null
 112 
    //Precondition: key != null
112 
    //Postcondition: return the old value if the key was found, then put a NIL in it's place
 113 
    //Postcondition: return the old value if the key was found, then put a NIL in it's place
113 
    //               return null if the key was not found in the table.
 114 
    //               return null if the key was not found in the table.
Line 138... Line 139...
138 
 
 139 
 
139 
    //Method to access private variable collisions
 140 
    //Method to access private variable collisions
140 
    //Precondition: none
 141 
    //Precondition: none
141 
    //Postcondition: return collisions
 142 
    //Postcondition: return collisions
142 
    public int collisions() {
 143 
    public int collisions() {
143 
    	return collisions;
 144 
        return collisions;
144 
    }
 145 
    }
145 
 
 146 
 
146 
    //Method to set the probeType variable
 147 
    //Method to set the probeType variable
147 
    //
 148 
    //
148 
    //0 == Linear Probing (step size 1) DEFAULT
 149 
    //0 == Linear Probing (step size 1) DEFAULT
Line 155... Line 156...
155 
    //
 156 
    //
156 
    //Precondition: 0 <= newValue <= 6
 157 
    //Precondition: 0 <= newValue <= 6
157 
    //Postcondition: probeType will be changed
 158 
    //Postcondition: probeType will be changed
158 
    //WARNING: Please do NOT change probeType while in a test run
 159 
    //WARNING: Please do NOT change probeType while in a test run
159 
    public void setProbeType( int newValue ) {
 160 
    public void setProbeType( int newValue ) {
160 
    	if( newValue < 0 || newValue > 6 ) { newValue = 0; } //put in for safety, just in case
 161 
        if( newValue < 0 || newValue > 6 ) { newValue = 0; } //put in for safety, just in case
161 
	probeType = newValue;
 162 
        probeType = newValue;
162 
    }
 163 
    }
163 
 
 164 
 
164 
    //A private class which will hold a key/value pair
 165 
    //A private class which will hold a key/value pair
165 
    private class Entry {
 166 
    private class Entry {
166 
        Object key, value;
 167 
        Object key, value;
Line 180... Line 181...
180 
    //Method to implement linear probing
 181 
    //Method to implement linear probing
181 
    //Precondition: h != null; i != null
 182 
    //Precondition: h != null; i != null
182 
    //Postcondition: return the next place to try and put the value
 183 
    //Postcondition: return the next place to try and put the value
183 
    private int nextProbe(int h, int i) {
 184 
    private int nextProbe(int h, int i) {
184
185
185 
	int returnVal = 0; //set to zero to stop compiler error
 186 
    int returnVal = 0; //set to zero to stop compiler error
186
187 
 
187 
	switch( probeType ) {
 188 
    switch( probeType ) {
188 
		case 0: { //linear probing
 189 
        case 0: { //linear probing
189 
			returnVal = (h + i)%entries.length;
 190 
            returnVal = (h + i)%entries.length;
190 
			break;
 191 
            break;
191 
		}
 192 
        }
192
193 
 
193 
		case 1: { //Prime Probing ( p=3  )
 194 
        case 1: { //Prime Probing ( p=3  )
194 
			returnVal = (h + (i * 3 ))%entries.length;
195 
            returnVal = (h + (i * 3 ))%entries.length;
195 
			break;
 196 
            break;
196 
		}
 197 
        }
197
198 
 
198 
		case 2: { //Prime Probing ( p=5  )
 199 
        case 2: { //Prime Probing ( p=5  )
199 
			returnVal = (h + (i * 5 ))%entries.length;
 200 
            returnVal = (h + (i * 5 ))%entries.length;
200 
			break;
 201 
            break;
201 
		}
 202 
        }
202
203 
 
203 
		case 3: {  //Prime Probing ( p=7  )
 204 
        case 3: {  //Prime Probing ( p=7  )
204 
			returnVal = (h + (i * 7 ))%entries.length;
 205 
            returnVal = (h + (i * 7 ))%entries.length;
205 
			break;
 206 
            break;
206 
		}
 207 
        }
207
208 
 
208 
		case 4: { //Prime Probing ( p=11 )
 209 
        case 4: { //Prime Probing ( p=11 )
209 
			returnVal = (h + (i * 11))%entries.length;
 210 
            returnVal = (h + (i * 11))%entries.length;
210 
			break;
 211 
            break;
211 
		}
 212 
        }
212
213 
 
213 
    		case 5: { //Quadratic Probing
 214 
        case 5: { //Quadratic Probing
214 
			returnVal = (h + (i * i ))%entries.length;
 215 
            returnVal = (h + (i * i ))%entries.length;
215 
			break;
 216 
            break;
216 
		}
 217 
        }
217 
 
 218 
 
218 
		//I am aware that my implementation of Double Hashing (which follows) is
 219 
        //I am aware that my implementation of Double Hashing (which follows) is
219 
		//wasteful in terms of computation time (we must create the array "step"
 220 
        //wasteful in terms of computation time (we must create the array "step"
220 
		//each and every time this code is run.  I did it this way to abstract the
 221 
        //each and every time this code is run.  I did it this way to abstract the
221 
		//method used to find the nextProbe() location from the put method.
 222 
        //method used to find the nextProbe() location from the put method.
222 
		case 6: { //Double Hashing
 223 
        case 6: { //Double Hashing
223 
			int[] step = { 2,3,5,7,11 };
 224 
            int[] step = { 2,3,5,7,11 };
224 
			int stepSize = step[h%4];
 225 
            int stepSize = step[h%4];
225 
			returnVal = (h + (i * stepSize))%entries.length;
 226 
            returnVal = (h + (i * stepSize))%entries.length;
226 
			break;
 227 
            break;
227 
		}
 228 
        }
228 
	}
 229 
    }
229 
	//return the final value
 230 
    //return the final value
230 
	return returnVal;
 231 
    return returnVal;
231
232
232 
    }
 233 
    }
233 
 
 234 
 
234 
    //Method to rehash the entire table.  This will get rid of NIL's
 235 
    //Method to rehash the entire table.  This will get rid of NIL's
235 
    //Precondition: none
 236 
    //Precondition: none