HashMap分析及散列的冲突处理(2)

在HashMap的实现中，采用的链地址法来解决冲突，它有一个桶的概念:对于Entry数组而言，数组的每个元素处存储的是链表，而不是直接的Value。在链表中的每个元素才是真正的<Key, Value>。而一个链表，就是一个桶！因此HashMap最多可以有Entry.length 个桶。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { static final Entry<?,?>[] EMPTY_TABLE = {}; ..... .....

HashMap中有一个Entry数组，而Entry类是HashMap的内部类。由Entry类来封装实际的<Key, Value>

static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash;

HashMap中还有两个变量： int threshold 和 float loadFactor。loadFactor 默认是0.75，threshold作用如下：当HashMap中的元素个数超过threshold时，就会重新调整哈希的大小。

void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);

而loadFactor作用是：指定threshold，一般情况下，哈希表的大小乘以0.75等于threshold。

threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

在HashMap中，addEntry()方法添加新元素时，总是将新元素添加在链表的表头。而不是链表的其它位置。