实现HashMap的例子，关键字为long类型，来自jive2.5
package com.cache;
public final class LongHashMap {
protected long table[];
protected Object values[];
protected byte state[];
protected int freeEntries;
//The number of distinct associations in the map; its "size()".
protected int distinct;
protected int lowWaterMark;
protected int highWaterMark;
//The minimum load factor for the hashtable.
protected double minLoadFactor;
//The maximum load factor for the hashtable.
protected double maxLoadFactor;
protected static final int DEFAULT_CAPACITY = 277;
protected static final double DEFAULT_MIN_LOAD_FACTOR = 0.2;
protected static final double DEFAULT_MAX_LOAD_FACTOR = 0.6;
</td></tr>
</table>
protected static final byte FREE = 0;
protected static final byte FULL = 1;
protected static final byte REMOVED = 2;
/**
* Constructs an empty map with default capacity and default load factors.
*/
public LongHashMap() {
this(DEFAULT_CAPACITY);
}
/**
* Constructs an empty map with the specified initial capacity and default
* load factors.
*
* @param initialCapacity the initial capacity of the map.
* @throws IllegalArgumentException if the initial capacity is less
* than zero.
*/
public LongHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR);
}
public LongHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
setUp(initialCapacity,minLoadFactor,maxLoadFactor);
}
public void clear() {
for (int i=0; i< state.length; i++) {
state[i] = FREE;
}
for (int i=0; i< values.length-1; i++) {
values[i] = null;
}
this.distinct = 0;
this.freeEntries = table.length; // delta
trimToSize();
}
public boolean containsKey(long key) {
return indexOfKey(key) >= 0;
}
public boolean containsValue(Object value) {
return indexOfValue(value) >= 0;
}
public void ensureCapacity(int minCapacity) {
if (table.length < minCapacity) {
int newCapacity = nextPrime(minCapacity);
rehash(newCapacity);
}
}
public final Object get(long key) {
int i = indexOfKey(key);
//If not in the map return null
if (i<0) {
return null;
}
else {
return values[i];
}
}
private final int indexOfInsertion(long key) {
final long tab[] = table;
final byte stat[] = state;
final int length = tab.length;
final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF;
int i = hash % length;
// double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
int decrement = (hash) % (length-2);
//OLD CODE: int decrement = (hash / length) % length;
if (decrement == 0) decrement = 1;
// stop if we find a removed or free slot, or if we find the key itself
// do NOT skip over removed slots (yes, open addressing is like that...)
while (stat[i] == FULL && tab[i] != key) {
i -= decrement;
//hashCollisions++;
if (i<0) i+=length;
}
if (stat[i] == REMOVED) {
// stop if we find a free slot, or if we find the key itself.
// do skip over removed slots (yes, open addressing is like that...)
// assertion: there is at least one FREE slot.
int j = i;
while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
i -= decrement;
//hashCollisions++;
if (i< 0) i+=length;
}
if (stat[i] == FREE) i = j;
}
if (stat[i] == FULL) {
// key already contained at slot i.
// return a negative number identifying the slot.
return -i-1;
}
// not already contained, should be inserted at slot i.
// return a number >= 0 identifying the slot.
return i;
}
private final int indexOfKey(long key) {
final long tab[] = table;
final byte stat[] = state;
final int length = tab.length;
final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF;
int i = hash % length;
// double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
int decrement = (hash) % (length-2);
//OLD CODE: int decrement = (hash / length) % length;
if (decrement == 0) decrement = 1;
// stop if we find a free slot, or if we find the key itself.
// do skip over removed slots (yes, open addressing is like that...)
while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
i -= decrement;
//hashCollisions++;
if (i<0) i+=length;
}
if (stat[i] == FREE) return -1; // not found
return i; //found, return index where key is contained
}
/**
* @param value the value to be searched in the receiver.
* @return the index where the value is contained in the receiver,
* returns -1 if the value was not found.
*/
protected int indexOfValue(Object value) {
final Object val[] = values;
final byte stat[] = state;
for (int i=stat.length; --i >= 0;) {
if (stat[i]==FULL && val[i]==value) return i;
}
return -1; // not found
}
/**
* Returns the first key the given value is associated with.
*
* @param value the value to search for.
* @return the first key for which holds get(key) == value;
* returns Long.MIN_VALUE if no such key exists.
*/
public long keyOf(Object value) {
//returns the first key found; there may be more matching keys, however.
int i = indexOfValue(value);
if (i<0) return Long.MIN_VALUE;
return table[i];
}
/**
* Returns all the keys in the map.
*/
public long[] keys() {
long[] elements = new long[distinct];
long[] tab = table;
byte[] stat = state;
int j=0;
for (int i = tab.length ; i-- > 0 ;) {
if (stat[i]==FULL) {
elements[j++]=tab[i];
}
}
return elements;
}
public boolean put(long key, Object value) {
int i = indexOfInsertion(key);
if (i<0) { //already contained
i = -i -1;
this.values[i]=value;
return false;
}
if (this.distinct > this.highWaterMark) {
int newCapacity = chooseGrowCapacity(
this.distinct+1,
this.minLoadFactor,
this.maxLoadFactor
);
rehash(newCapacity);
return put(key, value);
}
this.table[i]=key;
this.values[i]=value;
if (this.state[i]==FREE) this.freeEntries--;
this.state[i]=FULL;
this.distinct++;
if (this.freeEntries < 1) { //delta
int newCapacity = chooseGrowCapacity(
this.distinct+1,
this.minLoadFactor,
this.maxLoadFactor
);
rehash(newCapacity);
}
return true;
}
/**
* Returns the number of (key,value) associations currently contained.
*
* @return the number of (key,value) associations currently contained.
*/
public int size() {
return distinct;
}
/**
* Returns true if the receiver contains no (key,value) associations.
*
* @return true if the receiver contains no (key,value) associations.
*/
public boolean isEmpty() {
return distinct == 0;
}
protected void rehash(int newCapacity) {
int oldCapacity = table.length;
//if (oldCapacity == newCapacity) return;
long oldTable[] = table;
Object oldValues[] = values;
byte oldState[] = state;
long newTable[] = new long[newCapacity];
Object newValues[] = new Object[newCapacity];
byte newState[] = new byte[newCapacity];
this.lowWaterMark = chooseLowWaterMark(newCapacity,this.minLoadFactor);
this.highWaterMark = chooseHighWaterMark(newCapacity,this.maxLoadFactor);
this.table = newTable;
this.values = newValues;
this.state = newState;
this.freeEntries = newCapacity-this.distinct; // delta
for (int i = oldCapacity ; i-- > 0 ;) {
if (oldState[i]==FULL) {
long element = oldTable[i];
int index = indexOfInsertion(element);
newTable[index]=element;
newValues[index]=oldValues[i];
newState[index]=FULL;
}
}
}
public boolean removeKey(long key) {
int i = indexOfKey(key);
if (i<0) return false; // key not contained
this.state[i]=REMOVED;
this.values[i]=null; // delta
this.distinct--;
if (this.distinct < this.lowWaterMark) {
int newCapacity = chooseShrinkCapacity(
this.distinct,
this.minLoadFactor,
this.maxLoadFactor
);
rehash(newCapacity);
}
return true;
}
protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
if (initialCapacity < 0) {
throw new IllegalArgumentException(
"Initial Capacity must not be less than zero: "+ initialCapacity
);
}
if (minLoadFactor < 0.0 || minLoadFactor >= 1.0) {
throw new IllegalArgumentException(
"Illegal minLoadFactor: "+ minLoadFactor
);
}
if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) {
throw new IllegalArgumentException(
"Illegal maxLoadFactor: "+ maxLoadFactor
);
}
if (minLoadFactor >= maxLoadFactor) {
throw new IllegalArgumentException(
"Illegal minLoadFactor: " + minLoadFactor +
" and maxLoadFactor: " + maxLoadFactor
);
}
int capacity = initialCapacity;
capacity = nextPrime(capacity);
// open addressing needs at least one FREE slot at any time.
if (capacity==0) {
capacity=1;
}
this.table = new long[capacity];
this.values = new Object[capacity];
this.state = new byte[capacity];
//memory will be exhausted long before this pathological case happens, anyway.
this.minLoadFactor = minLoadFactor;
if (capacity == LARGEST_PRIME) this.maxLoadFactor = 1.0;
else this.maxLoadFactor = maxLoadFactor;
this.distinct = 0;
this.freeEntries = capacity; // delta
/**
* lowWaterMark will be established upon first expansion. Establishing
* it now (upon instance construction) would immediately make the table
* shrink upon first put(...). After all the idea of an
* "initialCapacity" implies violating lowWaterMarks when an object is
* young. See ensureCapacity(...)
*/
this.lowWaterMark = 0;
this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
}
/**
* Trims the capacity of the receiver to be the receiver's current size.
* Releases any superfluous internal memory. An application can use this
* operation to minimize the storage of the receiver.
*/
public void trimToSize() {
//*1.2 because open addressing's performance exponentially degrades
//beyond that point so that even rehashing the table can take very long
int newCapacity = nextPrime((int)(1 + 1.2*size()));
if (table.length > newCapacity) {
rehash(newCapacity);
}
}
/**
* Returns an array of all the values in the Map.
*/
public Object[] values() {
Object[] elements = new Object[distinct];
Object[] val = values;
byte[] stat = state;
int j=0;
for (int i = stat.length ; i-- > 0 ;) {
if (stat[i]==FULL) {
elements[j++]=val[i];
}
}
return elements;
}
/**
* Chooses a new prime table capacity optimized for growing that
* (approximately) satisfies the invariant
* c * minLoadFactor <= size <= c * maxLoadFactor
* and has at least one FREE slot for the given size.
*/
private int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
return nextPrime(Math.max(size+1, (int) ((4*size / (3*minLoad+maxLoad)))));
}
/**
* Returns new high water mark threshold based on current capacity and
* maxLoadFactor.
*
* @return int the new threshold.
*/
private int chooseHighWaterMark(int capacity, double maxLoad) {
//makes sure there is always at least one FREE slot
return Math.min(capacity-2, (int) (capacity * maxLoad));
}
/**
* Returns new low water mark threshold based on current capacity and minLoadFactor.
* @return int the new threshold.
*/
protected int chooseLowWaterMark(int capacity, double minLoad) {
return (int) (capacity * minLoad);
}
/**
* Chooses a new prime table capacity neither favoring shrinking nor growing,
* that (approximately) satisfies the invariant
* c * minLoadFactor <= size <= c * maxLoadFactor
* and has at least one FREE slot for the given size.
*/
protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) {
return nextPrime(Math.max(size+1, (int) ((2*size / (minLoad+maxLoad)))));
}
protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
return nextPrime(Math.max(size+1, (int) ((4*size / (minLoad+3*maxLoad)))));
}
protected int nextPrime(int desiredCapacity) {
int i = java.util.Arrays.binarySearch(primeCapacities, desiredCapacity);
if (i<0) {
//desired capacity not found, choose next prime greater than desired
//capacity
i = -i -1; // remember the semantics of binarySearch...
}
return primeCapacities[i];
}
/**
* The largest prime this class can generate; currently equal to Integer.MAX_VALUE.
*/
public static final int LARGEST_PRIME = Integer.MAX_VALUE; //yes, it is prime.
private static final int[] primeCapacities = {
//chunk #0
LARGEST_PRIME,
//chunk #1
5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
210719881,421439783,842879579,1685759167,
//chunk #2
433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107,
3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699,
1854585413,
//chunk #3
953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341,
7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963,
2004663929,
//chunk #4
1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963,
8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463,
//chunk #5
31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953,
1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013,
587742049,1175484103,
//chunk #6
599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729,
4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683,
//chunk #7
311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867,
2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673,
1344393353,
//chunk #8
3,7,17,37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899,
701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
359339171,718678369,1437356741,
//chunk #9
43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337,
1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741,
759155483,1518310967,
//chunk #10
379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611,
3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929,
1600153859
};
static { //initializer
// The above prime numbers are formatted for human readability.
// To find numbers fast, we sort them once and for all.
java.util.Arrays.sort(primeCapacities);
}
}