一、概述

　　HashMap，基于哈希结构的Map接口的一个实现，无序，允许null键值对，线程不安全的。可以使用集合工具类Collections中的synchronizedMap方法，去创建一个线程安全的集合map。

　　文中内容，主要基于jdk1.7。

二、结构

　　

　　HashMap默认初始化size=16的哈希数组，然后通过计算待存储的key的hash值，去计算得到哈希数组的下标值，然后放入链表中（新增节点或更新）。链表的存在即是解决hash冲突的。

三、代码实现

　　1、存储具体数据的table数组：

　　　　　　

　　　　Entry为HashMap中的静态内部类，其具体结构如下图

　　　　　　

　　　　key、value属性就是存储键值对的，next则是指向链表的下一个元素节点。

     2、 默认初始化方法：

　　　　

　　  默认构造方法，不对table进行初始化new（真正初始化动作放在put中，后面会看到），只是设置参数的默认值，hashmap长度和table长度初始化成DEFAULT_INITIAL_CAPACITY（16），加载因子loadFactor默认DEFAULT_LOAD_FACTOR（0.75f）。

　　  加载因子：默认情况下，16*0.75=12，也就是在存储第13个元素的时候，就会进行扩容（jdk1.7的threshold真正计算放在第一次初始化中，后面会再提及）。此元素的设置，直接影响到的是key的hash冲突问题。

　　3、put方法

public V put(K key, V value) {
    　　　   if (table == EMPTY_TABLE) {            inflateTable(threshold);        }        if (key == null)            return putForNullKey(value);        int hash = hash(key);        int i = indexFor(hash, table.length);        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 = e.value;                e.value = value;                e.recordAccess(this);                return oldValue;            }        }        modCount++;        addEntry(hash, key, value, i);        return null;    }
     

3.1、EMPTY_TABLE是HashMap中的一个静态的空的Entry数组，table也是HashMap的一个属性，默认就是EMPTY_TABLE（这两句可参见上面源码），table就是我们真正数据存储使用的。 3.2、前面提及，无参构造的时候，并未真正完成对HashMap的初始化new操作，而仅仅只是设置几个常量，所以在第一次put数据的时候，table是空的。则会进入下面的初始化table方法中。

if (table == EMPTY_TABLE) {    inflateTable(threshold);}private void inflateTable(int toSize) {    // Find a power of 2 >= toSize    int capacity = roundUpToPowerOf2(toSize);    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //计算加载因子，默认情况下结果为12    table = new Entry[capacity];  //真正的初始化table数组    initHashSeedAsNeeded(capacity);}

3.3、key的null判断

if (key == null)    return putForNullKey(value);private V putForNullKey(V value) {    for (Entry
     
       e = table[0]; e != null; e = e.next) {        if (e.key == null) {            V oldValue = e.value;            e.value = value;            e.recordAccess(this);            return oldValue;        }    }    modCount++;    addEntry(0, null, value, 0);    return null;}void addEntry(int hash, K key, V value, int bucketIndex) {    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);}void createEntry(int hash, K key, V value, int bucketIndex) {    Entry
      
        e = table[bucketIndex];    table[bucketIndex] = new Entry<>(hash, key, value, e);    size++;}
      
     

　　步骤解析：

　　　　1、key为null，取出table[0]的链表结构Enrty，如果取出的元素不为null，则对其进行循环遍历，查找其中是否存在key为null的节点元素。

　　  　  2、如果存在key == null的节点，则使用新的value去更新节点的oldValue，并且将oldValue返回。

　　　　3、如果不存在key == null的元素，则执行新增元素addEntry方法：

　　　　　　（1）判断是否需要扩容，size为当前数组table中，已存放的Entry链表个数，更直接点说，就是map.size()方法的返回值。threshold上面的真正初始化HashMap的时候已经提到，默认情况下，计算得到 threshold=12。

　　　　　　　　  若同时满足　 (size >= threshold) && (null != table[bucketIndex]) ，则对map进行2倍的扩容，然后对key进行重新计算hash值和新的数组下标。

　　　　　　（2）创建新的节点原色createEntry方法，首先获取table数组中下标为bucketIndex的链表的表头元素，然后新建个Entry作为新的表头，并且新表头其中的next指向老的表头数据。

3.4、key不为null的存储 　　 　　　　原理以及过程上通key==null的大体相同，只不过，key==null的时候，固定是获取table[0]的链表进行操作，而在不为key ！= null的时候，下标位置是通过  int hash = hash(key); int i = indexFor(hash, table.length); 计算得到的，

static int indexFor(int h, int length) {        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";        return h & (length-1);    }

　　很清晰的就能看明白，先计算key的hash，然后与当前table的长度进行相与，这样计算得到待存放数据的下标。得到下标后，过程就与key==null一致了，遍历是否存在，存在则更新并返回oldVlaue，不存在则新建Entry。 　　

　　4、get方法

public V get(Object key) {        if (key == null)            return getForNullKey();        Entry
     
       entry = getEntry(key);        return null == entry ? null : entry.getValue();    }
     

如果key == null，则调用getForNullKey方法，遍历table[0]处的链表。

private V getForNullKey() {        if (size == 0) {            return null;        }        for (Entry
     
       e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;    }
     

　　如果key ！= null，则调用getEntry，根据key计算得到在table数组中的下标，获取链表Entry，然后遍历查找元素，key相等，则返回该节点元素。

final Entry
     
       getEntry(Object key) {        if (size == 0) {            return null;        }        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;    }
      
     

四、总结

　　写的比较简单粗糙，主要介绍存取。