Java源码角度分析HashMap用法

优点：超级快速的查询速度，时间复杂度可以达到O（1）的数据结构非HashMap莫属。动态的可变长存储数据（相对于数组而言）。

缺点：需要额外计算一次hash值，如果处理不当会占用额外的空间。

—HashMap如何使用—

平时我们使用hashmap如下

									Map<Integer,String> maps=new HashMap<Integer,String>();   

									maps.put(1, "a");   

									maps.put(2, "b");

上面代码新建了一个HashMap并且插入了两个数据，这里不接受基本数据类型来做K,V

如果这么写的话，就会出问题了：

1	`Map<int,double> maps=new` `HashMap<int,double>();`

我们为什么要这样使用呢？请看源码：

									public class HashMap<K,V>  

									  extends AbstractMap<K,V>  

									  implements Map<K,V>, Cloneable, Serializable

这是HashMap实现类的定义。

—HashMap是一个动态变长的数据结构—

在使用HashMap的时候，为了提高执行效率，我们往往会设置HashMap初始化容量：

1	`Map<String,String> rm=new` `HashMap<String,String>(2)`

或者使用guava的工具类Maps，可以很方便的创建一个集合，并且，带上合适的大小初始化值。

1	`Map<String, Object> map = Maps.newHashMapWithExpectedSize(7);`

那么为什么要这样使用呢？我们来看他们的源码构造函数。

未带参的构造函数：

									public HashMap() {   

									    this.loadFactor = DEFAULT_LOAD_FACTOR;   

									    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);   

									    table = new Entry[DEFAULT_INITIAL_CAPACITY];   

									    init();   

									  }

public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

									/** 

									   * Constructs an empty <tt>HashMap</tt> with the specified initial 

									   * capacity and the default load factor (0.75). 

									   * 

									   * @param initialCapacity the initial capacity. 

									   * @throws IllegalArgumentException if the initial capacity is negative. 

									   */

									  public HashMap(int initialCapacity) { 

									    this(initialCapacity, DEFAULT_LOAD_FACTOR); 

									  }

名词解释：

									DEFAULT_LOAD_FACTOR  //默认加载因子，如果不制定的话是0.75  

									DEFAULT_INITIAL_CAPACITY //默认初始化容量，默认是16  

									threshold //阈（yu）值 根据加载因子和初始化容量计算得出 ，<span style="color: rgb(54, 46, 43); font-family: "microsoft yahei";">threshold表示当HashMap的size大于threshold时会执行resize操作。

因此我们知道了，如果我们调用无参数的构造方法的话，我们将得到一个16容量的数组。

所以问题就来了：如果初始容量不够怎么办？

数组是定长的，如何用一个定长的数据来表示一个不定长的数据呢，答案就是找一个更长的，但是在resize的时候是很降低效率的。所以我们建议HashMap的初始化的时候要给一个靠谱的容量大小。

—HashMap的Put方法—

									public V put(K key, V value) {  

									    if (key == null) //键为空的情况，HashMap和HashTable的一个区别  

									      return putForNullKey(value);  

									    int hash = hash(key.hashCode()); //根据键的hashCode算出hash值  

									    int i = indexFor(hash, table.length); //根据hash值算出究竟该放入哪个数组下标中  

									    for (Entry<K,V> e = table[i]; e != null; e = e.next) {//整个for循环实现了如果存在K那么就替换V  

									      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;  

									  }

如果插入的数据超过现有容量就会执行

1	`addEntry(hash, key, value, i);`

									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)   

									     <span style="color:#ff0000;"><strong> resize(2 * table.length);

									}

这里显示了如果当前 size++ >threshold 的话那么就会扩展当前的size的两倍，执行resize（2*table.length）,那么他们是如何扩展的呢？

									void resize(int newCapacity) {   

									    Entry[] oldTable = table;   

									    int oldCapacity = oldTable.length;   

									    if (oldCapacity == MAXIMUM_CAPACITY) {   

									      threshold = Integer.MAX_VALUE;   

									      return;   

									    }   

									    Entry[] newTable = new Entry[newCapacity]; <span style="color: rgb(51, 51, 51); font-family: Arial;">new 一个新的数组，</span> 

									    <strong> <span style="color:#ff0000;">transfer(newTable);</span> </strong> //将就数组转移到新的数组中 

									    table = newTable;   

									    threshold = (int)(newCapacity * loadFactor);  //重新计算容量 

									  }

对于转移数组transfer是如何转移的呢？

									void transfer(Entry[] newTable) {   

									    Entry[] src = table;   

									    int newCapacity = newTable.length;   

									    for (int j = 0; j < src.length; j++) {   

									      Entry<K,V> e = src[j];   

									      if (e != null) {   

									        src[j] = null;   

									        do {   

									          Entry<K,V> next = e.next;   

									          int i = <strong><span style="color:#ff0000;">indexFor(e.hash, newCapacity);  //根据hash值个容量重新计算下标</span></strong> 

									          e.next = newTable[i];   

									          newTable[i] = e;   

									          e = next;   

									        } while (e != null);   

									      }   

									    }   

									  }