一. 什么是哈希表

哈希表（hash table） 也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表。

其他数据结构在新增，查找等基础操作执行性能与哈希表对比：

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。

数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。

比如要新增或查找某个元素，我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。

这个函数可以简单描述为：存储位置 = f(关键字) ，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如要在哈希表中执行插入操作：

插入过程如下图所示：

查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

哈希冲突

如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？

也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。

前面提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是，需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。

二. HashMap基本使用

public class hashmapTest1 {
    public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("a", "apple");//put设值
        hashMap.put("b", "boy");
        hashMap.put("c", "cat");

        System.out.println(hashMap);
        System.out.println(hashMap.size());//返回hashMap内key-value数量
        System.out.println("a:" + hashMap.get("a"));//get取值
        System.out.println(hashMap.containsKey("a"));//containsKey查找hashMap是否包含指定key
        System.out.println(hashMap.containsValue("apple"));//containsValue查找hashMap是否包含指定value
        System.out.println(hashMap.remove("b"));//remove移除hashMap中指定key的数据，没有指定key就返回null

        System.out.println(hashMap.keySet());//返回hashMap所有key
        System.out.println(hashMap.isEmpty());//判断hashMap是否为空
        
        //采用Iterator遍历HashMap
        Iterator it = hashMap.keySet().iterator();
        while(it.hasNext()) {
            String key = (String)it.next();
            System.out.println("key:" + key);
            System.out.println("value:" + hashMap.get(key));
        }

        //遍历HashMap的另一个方法
        Set<Map.Entry<String, String>> sets = hashMap.entrySet();
        for(Map.Entry<String, String> entry : sets) {
            System.out.print(entry.getKey() + ", ");
            System.out.println(entry.getValue());
        }
    }
}

三. HashMap的实现原理

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry是HashMap中的一个静态内部类。代码如下：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
    int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。

如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；

如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

3.1 HashMap的默认值

DEFAULT_INITIAL_CAPACITY：

默认的初始容量，必须是2的倍数。默认16也就是默认会创建 16 个箱子，箱子的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
MAXIMUM_CAPACITY：哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。
DEFAULT_LOAD_FACTOR：默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容，扩容到32。
TREEIFY_THRESHOLD：如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
UNTREEIFY_THRESHOLD：在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。
MIN_TREEIFY_CAPACITY：在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。

其中MAXIMUM_CAPACITY 为什么设置成1 << 30？

因为HashMap在确定数组下标Index的时候，采用的是( length-1) & hash的方式，只有当length为2的指数幂的时候才能较均匀的分布元素，所以HashMap规定了其容量必须是2的n次方。

而采用位运算<<来控制HashMap的大小，使用位运算同时还提高了Java的处理速度。 HashMap内部由Entry[]数组构成，Java的数组下标是由Int表示的。所以对于HashMap来说其最大的容量应该是不超过int最大值的一个2的指数幂，而最接近int最大值的2个指数幂用位运算符表示就是 1 << 30。

3.2 其他几个重要字段

查看hashmap源码：

transient int size：实际存储的key-value键值对的个数
int threshold：

阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold。
final float loadFactor：
- 负载因子，代表了table的填充度有多少，默认是0.75。
- 负载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。
- 所以负载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
transient int modCount：
- HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作）， 需要抛出异常ConcurrentModificationException

四. JDK1.8中HashMap的性能优化

4.1 传统 HashMap的缺点

JDK 1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题，即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

4.2 桶的树形化 treeifyBin()

在Java 8 中，如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 )，就使用红黑树来替换链表，从而提高速度。

这个替换的方法叫 treeifyBin() 即树形化。

//将桶内所有的 链表节点 替换成 红黑树节点

final void treeifyBin(Node<K,V>[] tab, int hash) {

   int n, index; Node<K,V> e;
    
    //如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容
   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY){
        resize();
   }else if ((e = tab[index = (n - 1) & hash]) != null) {
        //如果哈希表中的元素个数超过了 树形化阈值，进行树形化
        // e 是哈希表中指定位置桶里的链表节点，从第一个开始
       TreeNode<K,V> hd = null, tl = null; //红黑树的头、尾节点
        do {
            //新建一个树形节点，内容和当前链表节点 e 一致
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null){
                 hd = p; //确定树头节点
            }else {
               	p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null); 
       //让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
        if ((tab[index] = hd) != null){
             hd.treeify(tab);
        }
    }

 }
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {

    return new TreeNode<>(p.hash, p.key, p.value, next);

 }

上述操作做了这些事:

(1)根据哈希表中元素个数确定是扩容还是树形化

(2)如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系

(3)然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容

4.3 HashMap的put方法

JDK1.7HashMap的put方法源码

public V put(K key, V value) {
    
    if (table == EMPTY_TABLE) {//如果table为空，则根据size的阈值填充，即为空则初始化
        inflateTable(threshold);
    }
    if (key == null){
        return putForNullKey(value);
    }
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    //遍历当前索引的冲突链，找是否存在对应的key
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //如果存在对应的key， 则替换oldValue并返回oldValue
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
	//冲突链中不存在新写入的Entry的key，则直接add
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

其中：if (key == null)，则进入putForNullKey( )方法

private V putForNullKey(V value) {
    for (Entry<K,V> 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;
}

putForNullKey()方法的执行逻辑为：

遍历table并判断其中是否已经存在一个entry的key==null。
- 如果已经存在则返回旧值并用新值替换。
- 如果没有，则调用第三个方法：addEntry( )

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//扩容方法，原有基础上容量乘以2
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

addEntry()方法中看到首先根据threshold和table中你所给出的桶索引位置是否为null来判断是否需要扩展map。不是要说的重点。接下来不管扩不扩容，第四个方法createEntry()才是真正意义上的插入方法：

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

createEntry( )方法中可以看到，首先根据你给出的桶索引去到对应的entry e; 然后执行赋值：table[bucketIndex] = new Entry<>(hash, key, value, e)；那么这句就是把新的已经携带了你要添加的key和value值的entry添加到map中。这句的关键就是第五个方法也就是new Entry<>的构建了：

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

根据Entry的构造函数可以看出，把最后一个参数赋值给了next,而当前的k和value就是当前值。而n值就是原有的entry的完整值。 所以可以得出是添加到头部，而不是结尾处。

JDK1.8HashMap的put方法源码

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤1：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤2：计算index，并对null做处理
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤3：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 步骤4：判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤5：该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
      // 步骤6：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

附：HashMap put方法逻辑图（JDK1.8）

4.4 红黑树中查找元素 getTreeNode()

HashMap 在 JDK 1.8 中新增的操作：红黑树中查找元素 getTreeNode()

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

(1)HashMap 的查找方法是 get(),它通过计算指定 key 的哈希值后，调用内部方法 getNode()；
(2)这个 getNode() 方法就是根据哈希表元素个数与哈希值求模（使用的公式是 (n - 1) &hash）得到 key 所在的桶的头结点，如果头节点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。
(3)getTreeNode 方法使通过调用树形节点的 find()方法进行查找：

 final TreeNode<K,V> getTreeNode(int h, Object k) {
     
    return ((parent != null) ? root() : this).find(h, k, null);
     
}

(4)由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。
(5)这里和插入时一样，如果对比节点的哈希值和要查找的哈希值相等，就会判断 key 是否相等，相等就直接返回；不相等就从子树中递归查找。

4.5 HashMap扩容机制

当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作。

Java 7 中Hashmap扩容机制

JAVA7扩容必须同时满足两个条件：

(1)存放新值的时候当前已有元素的个数必须大于等于阈值

(2)存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）

因为扩容要同时满足上面这两个条件，所以存在下面这些情况：

就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。
当然也有可能存储更多值（超或16个值，最多可以存26个值）都还没有扩容。
- 原因：前11个值全部hash碰撞，存到数组的同一个位置（虽然hash冲突，但是这时元素个数小于阈值12，并没有同时满足扩容的两个条件。所以不会扩容），后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，也没有同时满足扩容的两个条件，所以叶不会扩容），前面11+15=26，所以在存入第27个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

Java 8 中Hashmap扩容机制

Java8不再像Java7中那样需要同时满足两个条件。

Java8中扩容只需要满足一个条件：当前存放新值（注意不是替换已有元素位置时）的时候已有元素的个数大于等于阈值（已有元素等于阈值，下一个存放后必然触发扩容机制）

即hashmap默认大小为16，负载因子0.75，阈值12；在java8中，当存入第13个值时必定触发扩容。

　注：

　　（1）扩容一定是放入新值的时候，该新值不是替换以前位置的情况下（比如：put（“name”,"zhangsan"），而map里面原有数据<"name","lisi">，则该存放过程就是替换一个原有值，而不是新增值，则不会扩容）

　　（2）扩容发生在存放后，即是数据存放后（先存放后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容。

4.6 底层结构

Java7中Hashmap底层采用的是Entry对数组，而每一个Entry对又向下延伸是一个链表，在链表上的每一个Entry对不仅存储着自己的key/value值，还存了前一个和后一个Entry对的地址。
Java8中的Hashmap底层结构有一定的变化，还是使用的数组，但是数组的对象以前是Entry对，现在换成了Node对象（可以理解是Entry对，结构一样，存储时也会存key/value键值对、前一个和后一个Node的地址），以前所有的Entry向下延伸都是链表，Java8变成链表和红黑树的组合，数据少量存入的时候优先还是链表，当链表长度大于8，且总数据量大于64的时候，链表就会转化成红黑树，所以你会看到Java8的Hashmap的数据存储是链表+红黑树的组合，如果数据量小于64则只有链表，如果数据量大于64，且某一个数组下标数据量大于8，那么该处即为红黑树。

注：在jdk7中，当new Hashmap()的时候会对对象进行初始化，而jdk8中new Hashmap()并没有对对象进行初始化，而是在put()方法中通过判断对象是否为空，如果为空通过调用resize()来初始化对象。

HashMap