深入Java基础(四)--哈希表(1)HashMap应用及源码详解
publicclass HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {privatestaticfinallongserialVersionUID =
362498820763181265L;
staticfinalintDEFAULT_INITIAL_CAPACITY =
1<<
4;
staticfinalintMAXIMUM_CAPACITY =
1<<
30;
staticfinalfloat DEFAULT_LOAD_FACTOR =
0.75f;
staticfinalintTREEIFY_THRESHOLD =
8;
staticfinalintUNTREEIFY_THRESHOLD =
6;
staticclass Node<K,V> implements Map.Entry<K,V> {finalinthash;
finalNode
V value;
K key;
next;Node(inthash, K key, V value, Node next) {this.hash = hash;this.key = key;this.value = value;this.next = next;
}publicfinalK getKey() {returnkey; }publicfinalV getValue() {returnvalue; }publicfinalString toString() {returnkey +"="+ value; }publicfinalinthashCode() {returnObjects.hashCode(key) ^ Objects.hashCode(value);
}publicfinalV setValue(V newValue) {
V oldValue = value;
value = newValue;returnoldValue;
}publicfinalbooleanequals(Object o) {if(o ==this)returntrue;if(o instanceof Map.Entry) {
Map.Entry e = (Map.Entry)o;if(Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))returntrue;
}returnfalse;
}
}transient Node[] table;transient Set> entrySet;transientintsize;transientintmodCount;intthreshold;finalfloat loadFactor;publicHashMap(intinitialCapacity, float loadFactor) {if(initialCapacity <0)thrownewIllegalArgumentException("Illegal initial capacity: "+
initialCapacity);if(initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;if(loadFactor <=0|| Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegal load factor: "+
loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}staticfinalinttableSizeFor(intcap) {intn = cap -1;
n |= n >>>1;
n |= n >>>2;
n |= n >>>4;
n |= n >>>8;
n |= n >>>16;return(n <0) ?1: (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n +1;
}publicHashMap(intinitialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}publicHashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;
}publicHashMap(Map m) {this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m,false);
}publicV get(Object key) {
Node e;return(e = getNode(hash(key), key)) ==null?null: e.value;
}finalNode getNode(inthash, Object key) {
Node[] tab;
Node first, e;intn;
K k;if((tab = table) !=null&& (n = tab.length) >0&&
(first = tab[(n -1) & hash]) !=null) {if(first.hash == hash &&((k = first.key) == key || (key !=null&& key.equals(k))))returnfirst;if((e = first.next) !=null) {if(first instanceof TreeNode)return((TreeNode)first).getTreeNode(hash, key);do {if(e.hash == hash &&
((k = e.key) == key || (key !=null&& key.equals(k))))returne;
}while((e = e.next) !=null);
}
}returnnull;
}finalTreeNode getTreeNode(inth, Object k) {return((parent !=null) ? root() :this).find(h, k,null);
}finalTreeNode root() {for(TreeNode r =this, p;;) {if((p = r.parent) ==null)returnr;
r = p;
}
}finalTreeNode find(inth, Object k, Class kc) {
TreeNode p =this;do {intph, dir; K pk;
TreeNode pl = p.left, pr = p.right, q;if((ph = p.hash) > h)p = pl;elseif(ph < h)p = pr;elseif((pk = p.key) == k || (k !=null&& k.equals(pk)))returnp;elseif(pl ==null)p = pr;elseif(pr ==null)p = pl;elseif((kc !=null||
(kc = comparableClassFor(k)) !=null) &&
(dir = compareComparables(kc, k, pk)) !=0)p = (dir <0) ? pl : pr;elseif((q = pr.find(h, k, kc)) !=null)returnq;elsep = pl;}while(p !=null);returnnull;
}publicbooleancontainsKey(Object key) {returngetNode(hash(key), key) !=null;
}publicV put(K key, V value) {returnputVal(hash(key), key, value,false,true);
}finalV putVal(inthash, K key, V value,booleanonlyIfAbsent,booleanevict) {
Node[] tab;
Node p;intn, i;if((tab = table) ==null|| (n = tab.length) ==0)
n = (tab = resize()).length;if((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value,null);else{Node e; K k;if(p.hash == hash &&
((k = p.key) == key || (key !=null&& key.equals(k))))
e = p;elseif(p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);else{for(intbinCount =0; ; ++binCount) {if((e = p.next) ==null) {
p.next = newNode(hash, key, value,null);if(binCount >= TREEIFY_THRESHOLD -1)treeifyBin(tab, hash);break;
}if(e.hash == hash &&
((k = e.key) == key || (key !=null&& key.equals(k))))break;
p = e;
}
}if(e !=null) {V oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);returnoldValue;
}
}
++modCount;if(++size > threshold)
resize();
afterNodeInsertion(evict);returnnull;
}finalvoidtreeifyBin(Node[] tab,inthash) {intn,index; Node e;if(tab ==null|| (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();elseif((e = tab[index= (n -1) & hash]) !=null) {
TreeNode hd =null, tl =null;do {TreeNode p = replacementTreeNode(e,null);if(tl ==null)
hd = p;else{
p.prev = tl;
tl.next = p;
}
tl = p;
}while((e = e.next) !=null);if((tab[index] = hd) !=null)
hd.treeify(tab);
}
}finalNode[] resize() {
Node[] oldTab = table;intoldCap = (oldTab ==null) ?0: oldTab.length;intoldThr = threshold;intnewCap, newThr =0;if(oldCap >0) {if(oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;returnoldTab;
}elseif((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr <<1;}elseif(oldThr >0)newCap = oldThr;else{newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}if(newThr ==0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])newNode[newCap];
table = newTab;if(oldTab !=null) {for(intj =0; j < oldCap; ++j) {
Node e;if((e = oldTab[j]) !=null) {
oldTab[j] =null;if(e.next ==null)
newTab[e.hash & (newCap -1)] = e;elseif(e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);else{Node loHead =null, loTail =null;
Node hiHead =null, hiTail =null;
Node next;
do {
next = e.next;if((e.hash & oldCap) ==0) {if(loTail ==null)
loHead = e;elseloTail.next = e;
loTail = e;
}else{if(hiTail ==null)
hiHead = e;elsehiTail.next = e;
hiTail = e;
}
}while((e = next) !=null);if(loTail !=null) {loTail.next =null;
newTab[j] = loHead;
}if(hiTail !=null) {hiTail.next =null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}returnnewTab;
}publicV remove(Object key) {
Node e;return(e = removeNode(hash(key), key,null,false,true)) ==null?null: e.value;
}finalNode removeNode(inthash, Object key, Object value,booleanmatchValue,booleanmovable) {
Node[] tab; Node p;intn,index;if((tab = table) !=null&& (n = tab.length) >0&&
(p = tab[index= (n -1) & hash]) !=null) {
Node node =null, e; K k; V v;if(p.hash == hash &&
((k = p.key) == key || (key !=null&& key.equals(k))))
node = p;elseif((e = p.next) !=null) {if(p instanceof TreeNode)node = ((TreeNode)p).getTreeNode(hash, key);else{do {if(e.hash == hash &&
((k = e.key) == key ||
(key !=null&& key.equals(k)))) {
node = e;break;
}
p = e;
}while((e = e.next) !=null);
}
}if(node !=null&& (!matchValue || (v = node.value) == value ||
(value !=null&& value.equals(v)))) {if(node instanceof TreeNode)((TreeNode)node).removeTreeNode(this, tab, movable);elseif(node == p)tab[index] = node.next;elsep.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);returnnode;
}
}returnnull;
}publicvoidclear() {
Node[] tab;
modCount++;if((tab = table) !=null&& size >0) {
size =0;for(inti =0; i < tab.length; ++i)
tab[i] =null;
}
}
}
来源: http://blog.csdn.net/jack__frost/article/details/69388422