Java集合类（3）
时间：2010-10-12 来源：huangfox
转载请注明出处！
author：huangfox
http://www.cnblogs.com/huangfox/archive/2010/10/12/1848863.html
HashMap
一般的线性表、树中，记录在数据结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。这里提到的对应关系称之为散列函数，常用的散列函数包括：
Ø 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数（这种散列函数叫做自身函数）
Ø 数字分析法
Ø 平方取中法
Ø 折叠法
Ø 随机数法
Ø 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
1.1 创建：HashMap()
HashMap 的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
public HashMap(intinitialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity:" +
initialCapacity);
if (initialCapacity >MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 ||Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor:" +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity *loadFactor);
table = newEntry[capacity];
init();
}
注意：
HashMap初始容量并非传入的initialCapacity的值，而是大于initialCapacity的2的最小指数：
while (capacity < initialCapacity)
capacity <<= 1;
table = newEntry[capacity];
threshold等于实际容量capacity与loadFactor的乘积，是HashMap扩容的一个标准值。
HashMap是基于数组对键值对进行存放的
transient Entry[] table;
Entry类属性包括：
final K key;
V value;
Entry<K,V>next;
final int hash;
HashMap虽然是用数组进行存储，为什么还需要使用Entry next 属性对后续节点进行指定呢？这是因为在解决hash冲突的时候HasnMap采用的链表的方式。
1.2 添加数据：put(Object key , Object value)
HashMap容许添加null值，如果该映射以前包含了一个该键的映射关系，则旧值被替换。
public V put(K key,V value) {
//key为null的情况
if (key == null)
return putForNullKey(value);
//key不为null的情况
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分成两种情况。
当Key值为null时执行putForUnllKey( Object value) ；
private V putForNullKey(Vvalue) {
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值为null，无法通过现有的方式获取其散列值，因此取出数组中第一个Entry对象并遍历，但找到key值为null的Entry实例后，将其value值替换成新的value值，然后返回。若没有找到key值为null的Entry实例，则添加一个Entry实例。
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);//扩容，有兴趣可以更深入了解
}
默认其hash值为0，并且存放在数组的头部。当添加一个新Entry实例导致数组长度大于等于threshold，需要对数组进行扩容，并且对数组中所有元素重新hash，重新填充数组。
当key值不为null，首先获取key对象自身的hashCode，然后再对此hashCode做Hash操作：
static int hash(int h) {
// This function ensures that hashCodes that differ onlyby
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default loadfactor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h>>> 4);
}
传入参数h及key对象自身的hashCode值。Hash完毕后与Entry对象数组的大小减1的值进行按位与操作（h & (length-1)），获得当前key要存储的数组的位置。
从上述内容可知key值到Entry数组的位置的过程：求自身hashCode；求hash值；与数组大小做与操作。这个过程可能会对不同的key值产生相同的数组位置，这也就是常说的hash冲突。之前简单描述过HashMap是通过链表的方式解决这种冲突的，具体步骤如下所述。
获得key对应的位置后，获取该位置的Entry对象，使用next对其进行遍历，若存在hash值相等，且key值相等或equal的Entry对象，则将新的value覆盖该对象的value值。若不存在则在新增一个Entry实例，加入到该位置上链表的表头。示例：
图——（hash冲突）链表处理方式
假设之前位置5上有一个Entry实例（key5），现添加一个key9，假设key5和key9计算出来的位置都是位置5，并且key5不等于key9，那么就新增一个Entry（key9），并且将其next指向原位置链表的首元素（key5 Entry实例）。
1.3 通过key值获取value：get(Object key)
在6.2添加数据方法中，已经包括了get(Object key)的主要步骤。根据参数key是否为null分成两种情况。当key为null时，从Entry数组的第一个实例开始遍历（基于next），直至找到key为null的Entry实例，获取其value值并返回。当key不为null时，获得其位置信息，进而获取该位置上的Entry实例，基于next进行遍历，直至找到hash值相等，并且key相等或equal的Entry实例（e.hash == hash && ((k = e.key) == key ||key.equals(k))），获取其value值并返回。
public V get(Objectkey) {
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;
}
1.4 移除数据：remove(Object key)
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash,table.length);//找到对应的位置
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next =next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
和get方法类似，凡是类似get的方法分两个步骤。步骤1：获取给定key的位置index；步骤2：获取Entry数组位置为index的Entry实例，根据next进行遍历，比较key值和hash值。如果是get方法到此返回即可，不过remove则还需要修改next的值。
由于containKey(Object key)和get方法类似，不再重述。
1.5 注意
HashMap在遇到hash冲突时，使用的是链表的方式。
HashMap的initialCapacity和loadFactor会影响其添加、读取等动作的效率，在必要的时候可以进行调整、优化。
HashMap采用的数据进行存储，无容量限制。
HashMap线程不安全。
相关阅读 更多 +
