简介
packagejava.util;
importjava.io.*;
HashMap属于包java.util，实现中使用到了包java.io中的某些类。
它继承自AbstractMap，实现了Map接口，Cloneable接口，Serializable接口
默认值
staticfinal int DEFAULT_INITIAL_CAPACITY = 16;
默认容量大小为16
staticfinal int MAXIMUM_CAPACITY = 1 << 30;
最大值为2的30次方
staticfinal float DEFAULT_LOAD_FACTOR = 0.75f;
默认装载因子为0.75
transientEntry[] table;
Entry的数组，即实际存储key和value对的容器。
staticclass Entry<K,V> implements Map.Entry<K,V>{}
Entry实现了Map里的Entry接口。
四种构建方法
publicHashMap(int initialCapacity, float loadFactor)
publicHashMap(int initialCapacity)
publicHashMap()
publicHashMap(Map<? extends K, ? extends V> m)
hash的实现:
static int hash(int h) {
// This function ensures that hashCodesthat differ only by
// constant multiples at each bitposition have a bounded
// number of collisions (approximately8 at default load factor).
h ^= (h >>> 20) ^ (h>>> 12);
return h ^ (h >>> 7) ^ (h>>> 4);
}
只是二进制数本身的移位与异或运算。
索引的实现:
static int indexFor(int h, int length) {
return h & (length-1);
}
注意这里，就决定了length最好是2的n次方。
获取key对应的value
publicV get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e =table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k =e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
-----------end---------------
if(key == null) return getForNullKey();
这一句单独用于处理key为null的情况.这也是HashMap允许任何形式null值的原因所在.
如果key不为null,则获取key的hashCode,根据静态方法hash(int h)
h^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^(h >>> 4);
求得对应的hash值,然后用求得的hash值去table里找到该hash值对应的索引.
table是一个Entry数组,对应的table[i]即是一个Entry对象(实现了Map.Entry),里边有K,V,hash值,和next.
如果没有预先put进去,会是一个null值,即返回null; 如果有,则判断该处的hash值与key值是否与get(key)里的key一致,如果不一致则e= e.next();直到找到一致的或者e == null;
null值的处理
get:
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e!= null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
get时,当key为null执行此方法.即是索引的0位置.
put:
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e!= null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
由for循环中的循环体可知,如果table[0]位置不为null则直接将V替换掉原来Entry中的V;
否则,则在table[0]直接增加一个Entry;
put的实现 & hash值冲突的处理
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
如果key为null,则直接调用null值的put方法;
否则,计算hash值 => 找hash值在table中对应的索引=> 判断该索引是否为null =>
为null,直接添加;
不为null,判断hash值和key值是否相同(即使不同的hash值得到的索引i也可能相同),相同直接更新V,不相同则继续e = e.next();直到找到具有完全相同hash值和key值的e(Entry), 或e == null;
如果最终e == null; 而且未找到完全相同的Entry,则运行addEntry(hash, key,value, i);
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V>e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length); //增长方式: *2;
}
利用一个单链的方式处理hash冲突.
假如本来table[i]为A,且A.next() == null;
这时候put方法获取了一个hash值与A的相同,但key值与A的不同的参数,则利用获得的两个参数key和value以及hash值与索引i值组合生成一个Entry B, 则将B放入table[i],将B.next 指向A;
同理,put了一个C,则将C放入table[i],C.next指向B;
containsKey
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
很猥琐吧,还是少用点;
containsValue
public boolean containsValue(Object value) {
if(value == null)
return containsNullValue();
Entry[]tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
returnfalse;
}
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ;i++)
for (Entry e = tab[i] ; e != null ;e = e.next)
if (e.value == null)
return true;
return false;
}
更猥琐.
默认值与增长方式:
默认值为16,且即使指定初值,大小也只能是第一个比指定值大的2^n!
增长方式, 只有addEntry和putAll中直接会调用
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next =e.next;
int i = indexFor(e.hash,newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
当扩容的时候要去遍历所有的Entry，所以事先指定容量是能节约很多时间的。
遍历方式:
遍历Entry,Set<Map.Entry<K,V>>;
publicSet<Map.Entry<K,V>> entrySet();
遍历value,Collection<V>;
publicCollection<V> values();
遍历key, Set<K>; //与Hashtable不同
publicSet<K> keySet();
其他的方法基本上都是基于这些方法的.
OK~
No comments:
Post a Comment