HashMap 哈希算法

HashMap类

一个HashMap数据结构：不规则的二位数组，一维链表数组， 

源码中使用table[]数组存储数据。

中主要成员变量：

1）capacity：table数组的大小，默认为16

2）loadFactory：负载因子，默认0.75

3）threshold：扩容限制，为capacity*loadFactory,  当map中数据量达到threshold值时，就会扩容。

     扩容规则：原有capacity <<1 二进制向左移动一位，即capacity*2变为扩容之后的容量大小。

     注意：扩容后需要重新计算原有数据需要放在什么位置，并全部复制过去，耗费性能。

                 capacity和loadFactory需要合理设置， loadFactory 过小，扩容频繁发生，不利于空间的有效利用。loadFactory过大，影响map操作效率。

主要方法实现：

1）put（k,v）

if (key == null) return putForNullKey(value); int hash = hash(key); 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; static int indexFor(int h, int length) { return h & (length-1); }

如果k为null，直接放在table[0]的位置；

计算k的hash值，根据hash计算一个在table的0-（capacity-1）之中的一个值i，就是k需要放在table数组的位置i

i位置的entry链中，如果有一个entry的key和k相同，则覆盖此entry的value，返回oldValue；

如果entry链中，没有和k相同的entry的key，则添加一个新的entry，并放在table[i]位置，把原来table[i]位置的entry链作为new entry的next处理。如下图：new entry的位置。

2）get(k,v)

if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); 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; } 如果key为null，返回table[0]位置的对象；

计算key的hash值；

indexFor，根据hash值查找在table数组的位置i处的第一个entry<k,v>;

循环找到k的hash相同并且key相同的entry 返回。