HashMap总结

类定义

public class HashMap extends AbstractMap 
         implements Map, Cloneable, Serializable

hashmap采用的数据结构是数组+链表

数组可以理解，我们常称为“桶”，根据元素的hash值将它放在xx桶里面。链表是因为存在hash冲突所以使用拉链法。

hash

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

两个数有相同的hash值，但是他们不一定相同。两个数的hash值不同，那么他们一定不相同。

两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。
优点
先分类再查找，通过计算缩小范围，加快查找速度。
例如：

集合：{3,9,8,12,16}

如果想要查找16，那就需要遍历整个集合，时间复杂度为O(n)
如果使用了hash

比如hash函数为H(key)=key%5;
集合的hash值为{3,4,3,2,1}
那么查找16只需要根据hash后的值1去1号桶查找即可，如果1号桶只有16那么查找效率就是O(1)

散列函数
常见的几种Hash函数：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法
1）直接定址法：取Key或者Key的某个线性函数值为散列地址。Hash(k) = k，或者Hash(k) = a*k + b, (ab均为常数).

2）数字分析法：需要知道Key的集合，并且Key的位数比地址位数多，选择Key数字分布均匀的位。
Hash(Key) 取六位：

其中(2、4、6、7、9、13) 这6列数字无重复，分布较均匀，取此六列作为Hash(Key)的值。

Hash(Key1) :225833

Hash(Key2):487741

Hash(Key3):138562

Hash(Key4):342554
3）平方取中法：取Key平方值的中间几位作为Hash地址。因为在设置散列函数时不一定知道所有关键字，选取哪几位不确定。一个数的平方的中间几位和数本身的每一位都有关，这样可以使随机分布的Key，得到的散列地址也是随机分布的。如下：

4）折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。当Key的位数较多的时候数字分布均匀适合采用这种方案.

具体的叠加方法有两种，移位法和折叠法：

例子：若Key为下列数串，地址位数为7，两种方法的Hash(key)分别如下：

Key：7982374 | 1861215 | 9892154 | 56923

5）随机数法：伪随机探测再散列

具体实现：建立一个伪随机数发生器，Hash(Key) = random(Key). 以此伪随机数作为哈希地址。

6）除留余数法：取关键字被某个除数 p 求余，得到的作为散列地址。

即 H(Key) = Key % p；

哈希冲突
不同Key值对应同一个Hash地址的情况，这种情况叫做哈希冲突。

解决方法：

1）开放定址法：

当冲突发生时，探测其他位置是否有空地址 (按一定的增量逐个的寻找空的地址)，将数据存入。根据探测时使用的增量的取法，分为：线性探测、平方探测、伪随机探测等。

新的Hash地址函数为 Hash_new (Key) = (Hash(Key) + d i) mod m；i = 1，2…k (k<= m-1).m表示集合的元素数，i表示已经探测的次数。

线性探测(Linear Probing)

d i = a * i + b; ab为常数。

相当于逐个探测地址列表，直到找到一个空置的，将数据放入。
平方探测(Quadratic Probing)

d i = a * i ^ 2 (i <= m/2) m是Key集合的总数。a是常数。

探测间隔 i^2 个单元的位置是否为空，如果为空，将地址存放进去。
伪随机探测

d i = random(Key);

探测间隔为一个伪随机数。

2)链表法

将散列到同一个位置的所有元素依次存储在单链表中，或者存储在栈中。具体实现根据实际情况决定这些元素的数据存储结构。

首页Hash地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。T 中各分量的初值均应为空指针。

在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。

装填因子（载荷因子）
散列表的载荷因子定义为：

α = 填入表中的元素个数 / 散列表的长度.

α 是散列表装满程度的标志因子。由于表长是定值，α 与“填入表中的元素个数”成正比，所以，α 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α 越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α 的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

参考自：Hash详解

jdk1.7

HashMap的成员变量

int DEFAULT_INITIAL_CAPACITY = 16：默认的初始容量为16 
int MAXIMUM_CAPACITY = 1 << 30：最大的容量为 2 ^ 30 
float DEFAULT_LOAD_FACTOR = 0.75f：默认的加载因子为 0.75f 
Entry< K,V>[] table：Entry类型的数组，HashMap用这个来维护内部的数据结构，它的长度由容量决定 
int size：HashMap的大小 
int threshold：HashMap的极限容量，扩容临界点（容量和加载因子的乘积

HashMap的四个构造函数

public HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap 
public HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap 
public HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap 
public HashMap(Map< ? extends K, ? extends V> m)：构造一个映射关系与指定 Map 相同的新 HashMa

entry的结构

static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;
        int hash;

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

计算hash值
要进行4次位运算 + 5次异或预算（9次扰动）

    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

jdk7的hashmap是先扩容再添加元素
扩容要同时满足两个条件

存放新值的时候当前已有元素的个数必须大于等于阈值
存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）

因为上面这两个条件，所以存在下面这些情况

（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

（2）、当然也有可能存储更多值（超多16个值，最多可以存26个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（这时元素个数小于阈值12，不会扩容），后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，所以不会扩容），前面11+15=26，所以在存入第27个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

参考自：hashMap1.7和1.8的扩容机制条件

死循环问题

采用头插法添加结点，多线程并发扩容造成死循环：
先看源码

//先看key是否已经存在

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);
    // 如果key已经存在，则替换value，并返回旧值
    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;

//检查容量是否到达阈值，到达了要先扩容，把原来的元素移到新map中

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 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, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

//对每个元素重新进行hash,将元素移到新map中

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
        while(null != e) {
            Entry next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

假设插入第4个节点时，发生rehash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组

假设线程2 在执行到Entry < K,V > next = e.next;之后，cpu时间片用完了，这时变量e指向节点a，变量next指向节点b。
线程1继续执行，很不巧，a、b、c节点rehash之后又是在同一个位置7，开始移动节点
第一步，移动节点a

第二步，移动节点b

注意，这里的顺序是反过来的，继续移动节点c

这个时候线程1 的时间片用完，内部的table还没有设置成新的newTable，线程2 开始执行，这时内部的引用关系如下：

节点a和b互相引用，形成了一个环，当在数组该位置get寻找对应的key时，就发生了死循环。

参考自：老生常谈，HashMap的死循环【基于JDK1.7】

jdk1.8

数据结构变成数组+链表+红黑树

结点名称改为Node(实现仍是一样的)

  static class Node implements Map.Entry {

        final int hash; // 哈希
        final K key; // key
        V value; // value
        Node next;// 链表下一个节点

        // 构造方法
        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
         }

红黑树结点

  static final class TreeNode extends linkedHashMap.Entry {  

  	// 属性 = 父节点、左子树、右子树、删除辅助节点 + 颜色
    TreeNode parent;  
    TreeNode left;   
    TreeNode right;
    TreeNode prev;   
    boolean red;   

    // 构造函数
    TreeNode(int hash, K key, V val, Node next) {  
        super(hash, key, val, next);  
    }  
  
    // 返回当前节点的根节点  
    final TreeNode root() {  
        for (TreeNode r = this, p;;) {  
            if ((p = r.parent) == null)  
                return r;  
            r = p;  
        }  
    }

常用API

V get(Object key); // 获得指定键的值
V put(K key, V value);  // 添加键值对
void putAll(Map m);  // 将指定Map中的键值对 复制到 此Map中
V remove(Object key);  // 删除该键值对

boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value);  // 判断是否存在该值的键值对；是 则返回true
 
Set keySet();  // 单独抽取key序列，将所有key生成一个Set
Collection values();  // 单独value序列，将所有value生成一个Collection

void clear(); // 清除哈希表中的所有键值对
int size();  // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为空

示例代码：

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class HashMapTest {

    public static void main(String[] args) {
      
        Map map = new HashMap();

      
        map.put("Android", 1);
        map.put("Java", 2);
        map.put("iOS", 3);
        map.put("数据挖掘", 4);
        map.put("产品经理", 5);

       
        System.out.println("key = 产品经理时的值为：" + map.get("产品经理"));

      

        // 方法1：获得key-value的Set集合 再遍历
        System.out.println("方法1");
        // 1. 获得key-value对（Entry）的Set集合
        Set> entrySet = map.entrySet();

        // 2. 遍历Set集合，从而获取key-value
        // 2.1 通过for循环
        for(Map.Entry entry : entrySet){
            System.out.print(entry.getKey());
            System.out.println(entry.getValue());
        }
        System.out.println("----------");
        // 2.2 通过迭代器：先获得key-value对（Entry）的Iterator，再循环遍历
        Iterator iter1 = entrySet.iterator();
        while (iter1.hasNext()) {
            // 遍历时，需先获取entry，再分别获取key、value
            Map.Entry entry = (Map.Entry) iter1.next();
            System.out.print((String) entry.getKey());
            System.out.println((Integer) entry.getValue());
        }


        // 方法2：获得key的Set集合 再遍历
        System.out.println("方法2");

        // 1. 获得key的Set集合
        Set keySet = map.keySet();

        // 2. 遍历Set集合，从而获取key，再获取value
        // 2.1 通过for循环
        for(String key : keySet){
            System.out.print(key);
            System.out.println(map.get(key));
        }

        System.out.println("----------");

        // 2.2 通过迭代器：先获得key的Iterator，再循环遍历
        Iterator iter2 = keySet.iterator();
        String key = null;
        while (iter2.hasNext()) {
            key = (String)iter2.next();
            System.out.print(key);
            System.out.println(map.get(key));
        }


        // 方法3：获得value的Set集合 再遍历
        System.out.println("方法3");

        // 1. 获得value的Set集合
        Collection valueSet = map.values();

        // 2. 遍历Set集合，从而获取value
        // 2.1 获得values 的Iterator
        Iterator iter3 = valueSet.iterator();
        // 2.2 通过遍历，直接获取value
        while (iter3.hasNext()) {
            System.out.println(iter3.next());
        }

    }


}

// 注：对于遍历方式，推荐使用针对 key-value对（Entry）的方式：效率高
// 原因：
   // 1. 对于 遍历keySet 、valueSet，实质上 = 遍历了2次：1 = 转为 iterator 迭代器遍历、2 = 从 HashMap 中取出 key 的 value 操作（通过 key 值 hashCode 和 equals 索引）
   // 2. 对于 遍历 entrySet ，实质 = 遍历了1次 = 获取存储实体Entry（存储了key 和 value ）

运行结果

方法1
Java2
iOS3
数据挖掘4
Android1
产品经理5
----------
Java2
iOS3
数据挖掘4
Android1
产品经理5
方法2
Java2
iOS3
数据挖掘4
Android1
产品经理5
----------
Java2
iOS3
数据挖掘4
Android1
产品经理5
方法3
2
3
4
1
5

添加元素采用尾插法，避免了头插法导致的扩容死循环问题，但是仍无法避免多线程带来的安全性问题。因为多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。

什么时候用到红黑树？为什么要用？

当链表元素>8时转化为红黑树，当红黑树中元素小于6时退化为链表。
原因：
TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时，又会转成普通的bin。并且查看源码时发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。
这也解释了为什么不是一开始就将其转换为 TreeNodes，而是需要一定节点数才转为 TreeNodes。其实就是权衡，在空间和时间中权衡。
当 hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机 hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机 hashCode算法下所有bin中节点的分布频率会遵循lambda为0.5的泊松分布，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，不是随便决定的，而是根据概率统计决定的。
也就是说：选择8因为符合泊松分布，超过8的时候，概率已经非常小了，所以才会选择8这个数字。

还有另外一种解释：红黑树的平均查找长度是log(n) ，如果长度为8，平均查找长度为log(8) = 3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6,6/2=3，而log(6) = 2.6，虽然速度也比链表快，但是转化为树结构和生成树的时间并不会太短，且红黑树占用的内存比链表更大。

总之，树化阈值选择8是在时间和空间中找到一个最好的平衡点。

初始容量？为什么？

默认初始容量是16，且默认初始容量必须是2的次幂。（ps:采用懒加载，第一次使用时才会初始化数组）
先看hash方法

      // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
      // 1. 取hashCode值： h = key.hashCode() 
      // 2. 高位参与低位的运算：h ^ (h >>> 16)  
      static final int hash(Object key) {
           int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }

**首先说一下为什么要右移16位：**如果当n即数组长度很小，假设是16的话，那么n-1的二进制表示为1111，这样的值和哈希值直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小时，这样就很容易造成哈希碰撞，所以这里把高低位都利用起来，从而解决这个问题。
其次，使用异或可以保留高位和低位的特征，如果使用或就基本都是0了。

那为什么必须是2的幂次？
上面计算出的hash数还要和(map.length-1)进行与操作才能确定最终桶的位置。
因为（2的次幂数 - 1）的二进制形式表示都是1，这样在和经过异或运算的h进行按位与运算的时候才可以最多地保留其特性，减少产生哈希碰撞的概率，让数组空间均匀分配。

如果不是2的幂：
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；
使用2的幂次可以减少hash碰撞。
而使用&运算是因为计算hash一般是用%的方式，而&比%操作快。

那为什么默认值是16：作为默认容量，过大或过小都不合适，所以采取生产上的经验就设置为16

扩容因子？为什么？

负载因子选择0.75主要是在提高空间利用率和减少查询成本的折中下，节点出现在hash桶中遵循泊松分布的情况下，选择0.75。

负载因子过高，如1，虽然减少了空间的开销，提高了空间的利用率，但是链表边长，增加了查询的时间成本，并且hash冲突概率增加。
负载因子过低，如0.5，虽然可以减少查询的时间成本，但空间利用率很低，提高了rehash操作的次数
总的来说，HashMap在负载因子0.75的时候，空间利用率，满足泊松分布，而且避免了相当多的Hash冲突，提升了时间效率。

为什么不直接采用hashCode()处理的哈希码作为hashMap的下标位置？

计算出来的哈希码可能并不在数组大小范围内，从而导致无法匹配位置的情况。解决方法:哈希码 & (数组长度-1)。

哈希码是32位的，其取值范围为-(2^31) ~ 2^31-1之间。

而哈希表的容量范围最大值为2^30.

为什么要对哈希码进行二次处理，扰动计算？

为了进一步提高哈希低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性和均匀性，从而减少hash冲突。

1.7和1.8对比

哈希表如何解决Hash冲突

为什么HashMap具备下述特点：键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化

为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

HashMap 中的 key若 Object类型，则需实现哪些方法？

参考自：Carson带你学Java：深入源码解析HashMap 1.8

为什么HashMap不是线程安全的？

第一点是put时候多线程可能导致数据不一致；

假设有线程A和线程B，一开始线程A希望插入一个键值对到HashMap中，但是计算得到桶的索引坐标，获取到该桶里面的链表头结点后阻塞了，而此时线程B执行，成功地将键值对插入到了HashMap中。假设此时线程A被唤醒继续执行，而线程A保存的插入点正好是线程B插入元素的位置，如此一来ji就覆盖了线程B的插入记录，造成了数据不一致的现象。

第二点是JDK7中HashMap的get操作可能因为resize而引起死锁。

JDK7版本中的HashMap扩容时使用头插法，假设此时有元素一指向元素二的链表，当有两个线程使用HashMap扩容时，若线程一在迁移元素时阻塞，但是已经将指针指向了对应的元素，线程二正常扩容，因为使用的是头插法，迁移元素后将元素二指向元素一。此时若线程一被唤醒，在现有基础上再次使用头插法，将元素一指向元素二，形成循环链表。若查询到此循环链表时，便形成了死锁。而JDK8版本中的HashMap在扩容时保证元素的顺序不发生改变，就不再形成死锁，但是注意此时HashMap还是线程不安全的。

参考自：面试问我，HashMap的默认初始容量是多少，我该怎么说

红黑树

红黑树也是平衡树的一种
所以他满足，左子树的值小于根节点，右子树的值大于根节点

红黑树性质

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

java中实现为TreeMap
实现详解：清晰理解红黑树的演变—红黑的含义

推荐阅读：30张图带你彻底理解红黑树

HashMap总结

Java相关栏目本月热门文章