Subversion Repositories programming

Rev

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

Rev 8 Rev 9
Line 9... Line 9...
9 
    //size is the total number of elements, including NIL
 9 
    //size is the total number of elements, including NIL
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
- 
 
 15 
    //variable to hold total number of collisions this run.
- 
 
 16 
    //Definition: collision - the number of times we must jump to
- 
 
 17 
    //                        get to the next null space in the table
- 
 
 18 
    //                        This includes jumping NIL's
- 
 
 19 
    //
- 
 
 20 
    //NOTE: will only be counted on inserting values
14 
    private int collisions; //initialized to 0 by default
 21 
    private int collisions; //initialized to 0 by default
15 
 
 22 
 
16 
    //create a HashTable with a certain capacity (maximum items)
 23 
    //create a HashTable with a certain capacity (maximum items)
17 
    //and a maximum load factor (if we exceed this we will rehash)
 24 
    //and a maximum load factor (if we exceed this we will rehash)
18 
    public HashTable(int capacity, float loadFactor) {
 25 
    public HashTable(int capacity, float loadFactor) {
Line 68... Line 75...
68 
                return null;  // insertion success
 75 
                return null;  // insertion success
69 
            }
 76 
            }
70
77
71 
	    //if entry[j] == NIL then we must continue to probe for a new place,
 78 
	    //if entry[j] == NIL then we must continue to probe for a new place,
72 
	    //otherwise we will confuse the remove() and get() methods
 79 
	    //otherwise we will confuse the remove() and get() methods
73 
            if (entry==NIL) continue;
 80 
            if (entry==NIL) { collisions++; continue; }
74 
 
 81 
 
75 
	    //if entry[j].key == key then we need to update the record
 82 
	    //if entry[j].key == key then we need to update the record
76 
            if (entry.key.equals(key)) {
 83 
            if (entry.key.equals(key)) {
77 
                Object oldValue=entry.value;
 84 
                Object oldValue=entry.value;
78 
                entries[j].value = value;
 85 
                entries[j].value = value;
79 
                return oldValue;  // update success
 86 
                return oldValue;  // update success
80 
            }
 87 
            }
- 
 
 88 
 
- 
 
 89 
	    //if we get here, we have had a collision that is not a NIL,
- 
 
 90 
	    //and is not an Entry that needs updating, therefore it is something
- 
 
 91 
	    //else that hashes to the same value.  Therefore we must increment the
- 
 
 92 
	    //collision counter
81 
        }
 93 
	    collisions++;
- 
 
 94
- 
 
 95 
	}
82 
        return null;  // failure: table overflow
 96 
        return null;  // failure: table overflow
83 
    }
 97 
    }
84 
 
 98 
 
85 
    //Method to remove a key/value pair from the table.  This will leave a NIL behind
 99 
    //Method to remove a key/value pair from the table.  This will leave a NIL behind
86 
    //Precondition: key != null
 100 
    //Precondition: key != null
Line 109... Line 123...
109 
    //Postcondition: return size
 123 
    //Postcondition: return size
110 
    public int size() {
 124 
    public int size() {
111 
        return size;
 125 
        return size;
112 
    }
 126 
    }
113 
 
 127 
 
- 
 
 128 
    //Method to access private variable collisions
- 
 
 129 
    //Precondition: none
- 
 
 130 
    //Postcondition: return collisions
- 
 
 131 
    public int collisions() {
- 
 
 132 
    	return collisions;
- 
 
 133 
    }
- 
 
 134 
 
114 
    //A private class which will hold a key/value pair
 135 
    //A private class which will hold a key/value pair
115 
    private class Entry {
 136 
    private class Entry {
116 
        Object key, value;
 137 
        Object key, value;
117 
        Entry(Object k, Object v) { key=k; value=v; }
 138 
        Entry(Object k, Object v) { key=k; value=v; }
118 
    }
 139 
    }