参考博文1 Yikun，参考博文2 zhangshixi

简单理解HashMap

1. 什么时候会使用HashMap？他有什么特点？
2. 你知道HashMap的工作原理吗？
3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
4. 你知道hash的实现吗？为什么要这样实现？
5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

说明：HashMap的源码每个版本是有一些细微的差别，但是大体上都差不多，下面我整理的是jdk1.6的。有一个比较明显的区别是在1.8如果发生了碰撞的时候在一定值之前使用链表进行表示，在超过这个值的时候用的是红黑树。

HashMap是实现Map接口的类，是非线程安全的。允许null键，和null值。不保证映射的顺序

• 结构示意图：在java里，所有的数据结构基本上都是由数组，引用来组成的。HashMap实际上是由 一个数组链表组成的。如图所示：

  
  

HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("语文", 1);
map.put("数学", 2);
map.put("英语", 3);
map.put("历史", 4);
map.put("政治", 5);
map.put("地理", 6);
map.put("生物", 7);
map.put("化学", 8);

• HashMap中的数组里的类型是Entry的（java8里换了个，叫Node：节点，它是用树这种数据结构）
• Entry的源码如下，next的就是向下的引用（指针），这个会构成链表

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    ……
}

HashMap的put方法：

public V put(K key, V value) {
    // 存了null的key
    if (key == null)
        return putForNullKey(value);
    // 根据key的keyCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
     // 假如新加的key值相同，那么则覆盖
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引处的Entry为null，表明此处还没有Entry。
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}

• 假如table[bucketIndex]上已经存值了，那么则会把新加的放在链表的第一个，这个Entry的next则会指向之前的那个值。

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)
          resize (2 * table. length);
}

    Entry (int h , K k, V v , Entry <K,V> n ) {
            value = v ;
            next = n ;
            key = k ;
            hash = h ;
      }

---

hash方法和indexFor方法

• jdk 1.6

static int hash( int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h , int length) {
        return h & (length-1);
    }

• jdk 1.8

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(n - 1) & hash

---

• put方法的总结：

根据上面 put 方法的源代码可以看出:

• 当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置
• 如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。
• 如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。
• 如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

---

get方法

理解了上面的put方法，自然get方法也就很好理解了

public V get( Object key ) {
        if (key == null)
            return getForNullKey();     //取出键值是null的value
         //计算优化过的hash值
        inthash= hash(key.hashCode());
         //计算了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. equals( k)))
                return e. value;
        }
        return null;
    }

---

resize方法：

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，

• 代码如下：

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];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

• 所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能

---

前方高能预警！
让我们来看看jdk1.8中是怎么实现的吧：

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

• 怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：

  
  
• 因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

• 因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

思考？为什么所HashMap不是线程安全的：

此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示： Map m = Collections.synchronizedMap(new HashMap(...));

自己的理解：当有多个线程同时要put和remove的时候，假如都获取到了HashMap的头结点，那么这时多个线程就会同时操作，导致先操作的被后操作的覆盖了。另外就是在addEntry中当加入新的键值对后键值对总数量超过门限值的时候会调用一个resize操作，这时会重新计算hash值,然后知道算出index位置，先计算的会被后计算的覆盖，另外假如一个线程已经计算完毕，另外一个刚开始，就会导致另外的问题。

• 就是没有实现同步...

HashMap有两个参数，
一个是CAPACITY //容量
另外一个是LOAD_FACTOR //比例
这两个参数应该在一个合适的比例范围内，默认的容量是16，默认的比例是0.75。假如容量过大会太占用内存，太小会经常的扩容。比例太大会让难以填满，比例太小也会浪费内存。

1. 什么时候会使用HashMap？他有什么特点？

是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。

2. 你知道HashMap的工作原理吗？

通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

4. 你知道hash的实现吗？为什么要这样实现？

在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。