HashMap内部有一个Entry数组，可以称之为hash table。HashMap的默认构造值为初始容量为16，负载因子为0.75，阀值(初始容量*负载因子)为12。其默认构造子如下：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/** *//**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/** *//**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*
* 如果一个较大的值被任意一个带有参数的构造器指定，最大容量被使用。
*/
static final int MAXIMUM_CAPACITY = 1 << 30; //1073741824
/** *//**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** *//**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
/** *//**
* The number of key-value mappings contained in this map.
*/
transient int size;
/** *//**
* The next size value at which to resize (capacity * load factor).
*
* 下一个用来调整的大小值
* @serial
*/
int threshold;
/** *//**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY]; //默认情况下，以容量为16构建Entry数组
init();
}
put方法分析：
<1>HashMap首先判断key是否为null，如果为null，
<1.1>HashMap从hash table中第0个位置的Entry，如果该Entry不等于null且entry.key也不为null，当前value覆盖entry的value。
<1.2>否则，在hash table[0]处创建新的key=null的Entry。
<2>
接下来，以key的hashcode做hash运算，获得hash值。该hash值与hash table的长度-1做与操作，获得key在当前hash table中的位置索引。
然后检查在该索引位置是否存在Entry对象，如果存在，且该Entry对象的key的hash值与上面计算的hash值相等，且entry的key与传入的key相等或者key.equals(entry.key),那么以当前的value值覆盖旧值，并返回旧值。
如果hash table中不存在key所指定的Entry，那么就要增加新的Entry。在增加Entry后，要检查容量是否已经达到阀值，如果达到阀值，就以当前hash table的长度的2倍扩展。同时要重新计算entry在新的hash table中的索引位置。注意，由于hash计算可能导致key的hash值可能是重复的，HashMap采用链表的方式解决hash值冲突的问题，另外一种解决方法是开放地址法。
以下是put方法部分代码：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
/**//*这里对key的hasCode做hash*/
int hash = hash(key.hashCode());
/**//*通过hash值与hash表的长度减1做与操作获取hash表的索引值*/
int i = indexFor(hash, table.length);
/**//*由于hash可能重复，导致获取重复的索引值，这里通过判断传入的key的has值与当前节点的key的has值是否相等，且key相等或者equals相等，来用新的value替换旧值，并返回旧值*/
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为空的情况：
private V putForNullKey(V value) {
/**//*从0桶查找key为null的Entry。如果桶中有null的Entry，那么把当前新的值设置到Entry中，并返回旧值*/
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;
}
计算key的hash值与计算key所应处在hash table中的位置：
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/** *//**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
增加entry节点以及扩容：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//临时存储指定桶索引的Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//在指定桶索引位置创建新的Entry，并自动把原桶索引的Entry作为当前Entry的next
/**//*当size达到阀值(当前容量*负载因子=threshold)，需要扩容*/
if (size++ >= threshold)
resize(2 * table.length);
}
------------------------------------------------
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
/**//*如果就有容量达到默认的的容量最大值(2的30次方),threshold设为整形的最大值（2的31次方-1）*/
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
/**//*这里把源hash表中的数据拷贝到新的hash表中，注意的是，源hash表中链表到新hash表中由头变成了尾*/
transfer(newTable);
table = newTable;
/**//*设置扩容后新的阀值*/
threshold = (int)(newCapacity * loadFactor);
}
get方法分析：
当调用get方法时，HashMap首先判断key是否为null,如果为null，其hash值为0，否则通过hash算法计算。
接下来，通过该hash值与hash table的长度-1做与操作，获得key在hash table中的索引。如果entry不等null，且该传入key的hash值与entry的hash值相等，且key==entry.key或者key.equals(entry.key)，则返回该entry.value.否则返回null.
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : 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 != null && key.equals(k))))
return e;
}
return null;
}
posted on 2012-02-13 14:42
zhangxl 阅读(399)
评论(0) 编辑 收藏 所属分类:
JDK