Subversion Repositories programming

Rev

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

Rev 9 Rev 10
Line 10... Line 10...
10 
    //used is the total number of elements, NOT INCLUDING NIL
 10 
    //used is the total number of elements, NOT INCLUDING NIL
11 
    private int size, used;
 11 
    private int size, used;
12 
    private float loadFactor;
 12 
    private float loadFactor;
13 
    private final Entry NIL = new Entry(null,null);  // dummy
 13 
    private final Entry NIL = new Entry(null,null);  // dummy
14
14
- 
 
 15 
    private int probeType; //holds the type of probing to use
- 
 
 16
15 
    //variable to hold total number of collisions this run.
 17 
    //variable to hold total number of collisions this run.
16 
    //Definition: collision - the number of times we must jump to
 18 
    //Definition: collision - the number of times we must jump to
17 
    //                        get to the next null space in the table
 19 
    //                        get to the next null space in the table
18 
    //                        This includes jumping NIL's
 20 
    //                        This includes jumping NIL's
19 
    //
 21 
    //
Line 130... Line 132...
130 
    //Postcondition: return collisions
 132 
    //Postcondition: return collisions
131 
    public int collisions() {
 133 
    public int collisions() {
132 
    	return collisions;
 134 
    	return collisions;
133 
    }
 135 
    }
134 
 
 136 
 
- 
 
 137 
    //Method to set the probeType variable
- 
 
 138 
    //
- 
 
 139 
    //0 == Linear Probing (step size 1) DEFAULT
- 
 
 140 
    //1 == Prime  Probing (step size 3)
- 
 
 141 
    //2 == Prime  Probing (step size 5)
- 
 
 142 
    //3 == Prime  Probing (step size 7)
- 
 
 143 
    //4 == Prime  Probing (step size 11)
- 
 
 144 
    //5 == Quadratic Probing
- 
 
 145 
    //6 == Double Hashing
- 
 
 146 
    //
- 
 
 147 
    //Precondition: 0 <= newValue <= 6
- 
 
 148 
    //Postcondition: probeType will be changed
- 
 
 149 
    //WARNING: Please do NOT change probeType while in a test run
- 
 
 150 
    public void setProbeType( int newValue ) {
- 
 
 151 
    	if( newValue < 0 || newValue > 6 ) { newValue = 0; } //put in for safety, just in case
- 
 
 152 
	probeType = newValue;
- 
 
 153 
    }
- 
 
 154 
 
135 
    //A private class which will hold a key/value pair
 155 
    //A private class which will hold a key/value pair
136 
    private class Entry {
 156 
    private class Entry {
137 
        Object key, value;
 157 
        Object key, value;
138 
        Entry(Object k, Object v) { key=k; value=v; }
 158 
        Entry(Object k, Object v) { key=k; value=v; }
139 
    }
 159 
    }
Line 150... Line 170...
150
170
151 
    //Method to implement linear probing
 171 
    //Method to implement linear probing
152 
    //Precondition: h != null; i != null
 172 
    //Precondition: h != null; i != null
153 
    //Postcondition: return the next place to try and put the value
 173 
    //Postcondition: return the next place to try and put the value
154 
    private int nextProbe(int h, int i) {
 174 
    private int nextProbe(int h, int i) {
- 
 
 175
155 
        return (h + i)%entries.length;      // Linear Probing
 176 
	int returnVal = 0; //set to zero to stop compiler error
156
177
- 
 
 178 
	switch( probeType ) {
- 
 
 179 
		case 0: { //linear probing
- 
 
 180 
			returnVal = (h + i)%entries.length;
- 
 
 181 
			break;
- 
 
 182 
		}
- 
 
 183
- 
 
 184 
		case 1: { //Prime Probing ( p=3  )
157 
    	//return (h + (i * 3 ))%entries.length; //Prime Probing ( p=3  )
 185 
			returnVal = (h + (i * 3 ))%entries.length;
- 
 
 186 
			break;
- 
 
 187 
		}
- 
 
 188
- 
 
 189 
		case 2: { //Prime Probing ( p=5  )
158 
	//return (h + (i * 5 ))%entries.length; //Prime Probing ( p=5  )
 190 
			returnVal = (h + (i * 5 ))%entries.length;
- 
 
 191 
			break;
- 
 
 192 
		}
- 
 
 193
- 
 
 194 
		case 3: {  //Prime Probing ( p=7  )
159 
	//return (h + (i * 7 ))%entries.length; //Prime Probing ( p=7  )
 195 
			returnVal = (h + (i * 7 ))%entries.length;
- 
 
 196 
			break;
- 
 
 197 
		}
- 
 
 198
- 
 
 199 
		case 4: { //Prime Probing ( p=11 )
160 
	//return (h + (i * 11))%entries.length; //Prime Probing ( p=11 )
200 
			returnVal = (h + (i * 11))%entries.length;
- 
 
 201 
			break;
161
202 
		}
- 
 
 203
- 
 
 204 
    		case 5: { //Quadratic Probing
162 
        //return (h + (i * i ))%entries.length; //Quadratic Probing
 205 
			returnVal = (h + (i * i ))%entries.length;
- 
 
 206 
			break;
- 
 
 207 
		}
163 
 
 208 
 
- 
 
 209 
		//I am aware that my implementation of Double Hashing (which follows) is
- 
 
 210 
		//wasteful in terms of computation time (we must create the array "step"
- 
 
 211 
		//each and every time this code is run.  I did it this way to abstract the
- 
 
 212 
		//method used to find the nextProbe() location from the put method.
- 
 
 213 
		case 6: { //Double Hashing
- 
 
 214 
			int[] step = { 2,3,5,7,11 };
- 
 
 215 
			int stepSize = step[h%4];
164 
	// STILL NEED TO ADD DOUBLE HASHING IMPLEMENTATION HERE
 216 
			returnVal = (h + (i * stepSize))%entries.length;
- 
 
 217 
			break;
- 
 
 218 
		}
- 
 
 219 
	}
- 
 
 220 
	//return the final value
- 
 
 221 
	return returnVal;
165
222
166 
    }
 223 
    }
167 
 
 224 
 
168 
    //Method to rehash the entire table.  This will get rid of NIL's
 225 
    //Method to rehash the entire table.  This will get rid of NIL's
169 
    //Precondition: none
 226 
    //Precondition: none