Java进阶--深入解析hashmap _数组

原理
先以一个简单的例子来理解的原理。在Java中先随机产生一个大小为20的数组如下：
hash表的大小为7，将上面数组的元素，按mod 7分类如下图：

文章插图
将这些点插入到中（简单）后如下图：

文章插图
由上图可知：
① 是用链地址法进行处理，多个key 对应于表中的一个索引位置的时候进行链地址处理，其实就是一个数组+链表的形式。
② 当有多个key的值相同时，中只保存具有相同key的一个节点，也就是说相同key的节点会进行覆盖。
③在中查找一个值，需要两次定位，先找到元素在数组的位置的链表上，然后在链表上查找，在中的第一次定位是由hash值确定的，第二次定位由key和hash值确定。
④节点在找到所在的链后，插入链中是采用的是头插法，也就是新节点都插在链表的头部。
⑤在中上图左边绿色的数组中也存放元素，新节点都是放在左边的table中的，这个在上图中为了形象的表现链表形式而没有使用。
上面只是简单的模拟了真实的的基本思想和上面是一样的不过更加复杂。中的一个节点是一个类如下图：

文章插图
Entry是的内部类包含四个值（next，key，value，hash），其中next是一个指向 Entry的指针，key相当于上面节点的值 value对应要保存的值，hash值由key产生，中要找到某个元素，需要根据hash值来求得对应数组中的位置，然后在由key来在链表中找Entry的位置。中的一切操作都是以Entry为基础进行的。的重点在于如何处理Entry 。因此中的操作大部分都是调用Entry中的方法。可以说类本身只是提供了一个数组，和对Entry类中方法的一些封装。
下面从源码方面对进行解析：
①的继承关系
public class HashMapextends AbstractMapimplements Map, Cloneable, Serializable
从上面可以看到继承了 , 并且实现了,接口。
②的构造函数
下面的代码都是经过简化处理的代码，基本流程不变只是为了更好的理解修改和删除了一部分内容

public HashMap(int initialCapacity, float loadFactor) {/*initialCapacity 初始化hashmap中table表的大小，前面的图中左边绿色部分的数组就是table 。loadFactor填装因子 。*/if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//如果初始化大小小于0，抛出异常if (initialCapacity > 2^30)initialCapacity = 2^30;//HashMap 中table的最大值为2^30 。/* 生成一个比initialCapacity小的最大的2的n次方的值，这个值就是table的大小 。table就是一个Entry类型的数组 。*/int capacity = 1;while (capacity < initialCapacity)capacity <<= 1;table = new Entry[capacity];//新建一个Entry类型的数组，就是前面图中左边的数组 。不过数组的元素是Entry类型的 。}

上面的代码要做几点说明：
①填装因子: 表示填装因子的大小，简单的介绍一下填装因子：假设数组大小为20，每个放到数组中的元素mod 17，所有元素取模后放的位置是（0–16）此时填装因子的大小为 17/20 ,装填因子就为0.85啦，你装填因子越小，说明你备用的内存空间越多，装填因子的选定，可以影响冲突的产生，装填因子越小，冲突越小。
②初始化过程就是新建一个大小为，类型为Entry的数组，Entry上面已经介绍过这个类，包含一个指针一个key，一个value，和一个hash 。是2的次幂，至于为什么是2的次幂后面会有介绍的。
下面是另外两个构造函数

 public HashMap(int initialCapacity) {HashMap(initialCapacity, 0.75);//调用了上面的构造函数，只不过使用了默认的填装因子0.75}public HashMap() {HashMap(16, 0.75);//生成一个table大小为16，填装因子0.75的HashMap}

③由上可知如果用户直接使用（）构造函数来new一个会生成一个大小为16，填装因子为0.75的。
③中的put（key，value）函数
还是先上源码

public V put(K key, V value) {if (key == null)return putForNullKey(value);/*如果key为null则调用putForNullKey(value) 函数 这个函数先在table[0]这条链上找有没有key 为null的元素如果有就覆盖，如果没有就新建一个new一个key为null，value=http://www.kingceram.com/post/value hash=0，的Entry放在table[0] 。*/int hash = hash(key);//获得key的hash值int i = indexFor(hash, table.length);//由hash值确定放在table表中的那一条链上 。类似于取模后放在数组中的哪个位置 。for (Entry e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = http://www.kingceram.com/post/e.value;e.value = value;e.recordAccess(this);return oldValue;//如果链上原来有一个hash值相同，且key相同的则用新的value值进行覆盖 。}}//否则利用hash，key，value，new一个Entry对象插入到链表中 。modCount++;addEntry(hash, key, value, i);return null;}

对上面代码做几点说明：
① 中的key可以为 null，此时hash=0，为什么key可以为null，因为中放的元素是Entry，而Entry包含了4个值（key，value，hash，next），key为 null 时不影响Entry映射到中。
②hash(key)，产生一个正整数，这个整数与key相关。这个hash（key）函数比较关键，后面会进行说明。
③用户插入的（key，value）对不是直接放到中的，而是用（key，value）以及后面由key value产生的hash，new一个Entry对象后再插入到中的。
④如果对应的链上有一个hash值个key相同的Entry则覆盖value值，不new Entry对象，如果没有会先new 一个对象在将其插到对应的链上。（其中可能会涉及到扩充）。
下面看看hash（key）函数

final int hash(Object k) {int h = 0;h ^= k.hashCode(); //hashCode 返回一个整数值，这个值跟对象有关，不同对象的hashCode值一般不同 。h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

hash函数的作用是使里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。
④中的get( key)函数
上源码

public V get(Object key) {if (key == null)return getForNullKey();//如果key==null则在table[0]这条链上找，如果找到返回value值，否则返回null，因为key==null的都是放在table[0]这条链上的 。Entry entry = getEntry(key);//getEntry(key)先key的hash值找到在数组的哪条链上，然后在链上查找key相同的如果没找到返回null//如果找到了返回Entry的value值 。return null == entry ? null : entry.getValue();}private V getForNullKey() {for (Entry e = table[0]; e != null; e = e.next) {if (e.key == null)return e.value;}return null;}Entry getEntry(Object key) {int hash = (key == null) ? 0 : hash(key);for (Entry 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来链表中查找元素包括两个过程，先由hash找到链（hash由key产生，不同的key可能产生相同的hash值，相同的hash值放在同一条链上），再用key在链上找。
② 如果key为null则只在table[0]和其链上查找，因为key为null都放在table[0]及其链上了。
③因为在中查找到的是Entry对象，返回的值是Entry对象的value值。
重点Entry类
其实理解最重要的在于理解Entry类，Entry类相当于链表中的一个节点，是操作的基础。下面主要从Entry类的几个方法来理解Entry类和的关系。
①Entry中的( hash, key, value, )函数
在中调用put（key，value）时，如果（key，value）是首次加入到中，就会调用
( hash, key, value, )函数，将其加入到table表对应的位置中（注意是table中，不是后面的链中，首次加入的元素都是采用的头插法）。下面是源码：

void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);//如果size的值超过了threshold，将table扩容两倍hash = (null != key) ? hash(key) : 0;//如果key为null则hash=0，否则hash函数利用key来产生hash值 。bucketIndex = indexFor(hash, table.length);//bucketIndex就相当于取模后对应的table表中的哪个位置 。}//如果不存在容量不够问题则直接新建一个Entry对象 。createEntry(hash, key, value, bucketIndex);}void createEntry(int hash, K key, V value, int bucketIndex) {Entry e = table[bucketIndex];//获得原来首位的Entry对象table[bucketIndex] = new Entry<>(hash, key, value, e);//将新建的Entry对象放在链表的首位，然后用next指向原来放在首位的对象 。也就是头插 。size++;}

上面代码的几点说明：
①是由hash取模后对应于table表中的哪个位置。(hash, table.)其实是一个取模函数。它的实现很简单 hash& (-1)，就是用hash值与上table表的长度减1 。
②并不是对每一个（key，value）对都产生一个Entry对象，只是（key，value）对首次放到中时，或者中没有相同的key时，才产生一个Entry对象，否则如果有相同的key则会直接将value值赋个Entry的value 。
③新产生的Entry都是放在了table中，也就是链表的首位，采用链表的头插法。
②中的()函数
作用：返回中key的集合。是中的内部类：

public Set keySet() {Set ks = keySet;return (ks != null ? ks : (keySet = new KeySet()));//如果keyset为null就产生一个keyset对象 。}private final class KeySet extends AbstractSet {public Iterator iterator() {return newKeyIterator();//newKeyIterator迭代器用于遍历key 。}public int size() {return size;//返回keyset的大小}public boolean contains(Object o) {return containsKey(o);//是否包含某个key}public boolean remove(Object o) {return HashMap.this.removeEntryForKey(o) != null;//移除某个key的Entry 。}public void clear() {HashMap.this.clear();}}

是用来遍历整个的，因此是十分重要的，下面做几点说明。
①中有一个迭代器可以迭代的获取下一个key的值，通过key的值就可以获得Entry对象了。
②对应key的迭代遍历是table表中由左向右，由上向下进行的，也就是先遍历table[0]这条链上的，然后遍历table[1]这条链上的依次往下进行。
③具体实现这里就不多介绍，只要知道上面的功能怎么实现就可以了。
下面是利用来实现遍历的例子：

HashMap hashMap=new HashMap();for(int i=0;i<20;i++){hashMap.put(i, i+1);}//新建一个hashmap往里面放入20个（key，value）对 。Iterator iterator= (Iterator) hashMap.keySet().iterator();//获得keyset的iterator，进行遍历整个hashmap 。while(iterator.hasNext()){Integer key=(Integer) iterator.next();Integer val=(Integer)hashMap.get(key);System.out.println(key+": "+val);}

②中的()函数
作用：返回中Entry的集合。对于这里就不上源码了，举一个使用遍历的例子：

HashMap hashMap=new HashMap();for(int i=0;i<20;i++){hashMap.put(i, i+1);}Iterator> iterator=hashMap.entrySet().iterator();while(iterator.hasNext()){Entryentry= iterator.next();System.out.println(entry.getKey()+": "+entry.getValue());}

使用()函数遍历比()函数遍历快，因为()函数是先通过()求出key然后在通过key来遍历获得Entry的，所以速度比()慢很多。
参考文献：
①
【Java进阶--深入解析hashmap】②