[Java基础]Hashmap

hashMap实现Map接口，基于hashing原理，以键值对形式存储，允许null键/值，非同步的集合类型；

hashmap的底层存储结构是基于数组和链表的

一、put方法

publicObjectput(Objectkey,Objectvalue);

1、因为hashmap存储的底层结构是数组和链表，所以，当我们put时，需要计算出数组的下标：

1）执行key.hashCode方法，得到哈希码：hashCode=key.hashCode;

2）用哈希码做hash运算，得到一个散列值:inthash=hash(hashCode);

3）散列值与数组的长度做indexFor运算，得到数组下标。

2、了解了这个过程，我们很容易能发现，即使key不同，经过前两步运算，也可能得到相同散列值。所以我们put时，新的entry和旧的entry可能发生冲突，解决hash冲突的方法有很多，在hashmap中采用的是链地址法。即：

对新entry和旧entry进行判断：

1）散列值相同，key相同；

此时说明是相同的entry，用新的entry覆盖旧的entry。

2）散列值相同，key不同；

执行key.equals方法；

如果这两个对象通过hashmap重写的equals方法判断是一样的，说明是同一个entry对象，用新的entry覆盖旧的entry；

如果不同，就把新加入的entry对象放在对应数组下标位置的表头，早进来的entry向后移动一个位置，形成链表；

特别注意：我们存放在数组中的并不只有value，是一个entry（hash,key,value,bucketIndex）对象。

3、链表长度太长，影响查询效率怎么办？

JDK1.8多了一个新特性，当链表的长度>=8时，链表转换为红黑树，提高查询效率：

1.8链表转红黑树的源码staticfinalintTREEIFY_THRESHOLD=8;if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;

4、不断增加对象，是否需要扩容resize？

了解一下API里hashmap的构造方法，里面有initialCapacity和loadFactor两个名词；

initialCapacity是哈希表的数组的初识大小，始终保持2^n，可以扩容，扩容后数组大小为当前的2倍；loadFactor是加载因子；HashMap的默认大小是16，那么他的数组长度是0-15；默认加载因子是0.75；threshold：扩容的阈值，等于capacity*loadFactor

所以，当容量达到threshold时，数组会自动扩容到原来大小的两倍；比如，当前我们的数组的大小是16，当存储到12个元素时，数组会自动扩容到32.

voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){if((size>=threshold)&&(null!=table[bucketIndex])){resize(2*table.length);hash=(null!=key)?hash(key):0;bucketIndex=indexFor(hash,table.length);}createEntry(hash,key,value,bucketIndex);}

voidresize(intnewCapacity){Entry[]oldTable=table;intoldCapacity=oldTable.length;if(oldCapacity==MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;return;}Entry[]newTable=newEntry[newCapacity];booleanoldAltHashing=useAltHashing;useAltHashing|=sun.misc.VM.isBooted&&(newCapacity>=Holder.ALTERNATIVE_HASHING_THRESHOLD);booleanrehash=oldAltHashing^useAltHashing;transfer(newTable,rehash);table=newTable;threshold=(int)(newCapacity*loadFactor);}

5、key为null时

publicVput(Kkey,Vvalue){if(key==null)returnputForNullKey(value);inthash=hash(key);inti=indexFor(hash,table.length);for(Entrye=table[i];e!=null;e=e.next){Objectk;if(e.hash==hash&&((k=e.key)==key