2021-02-14 16:53 门头沟学院 Java

关注

HashMap

简介

HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。

JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间，具体可以参考 treeifyBin方法。

HashMap的底层实现

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

扰动函数

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

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);
}

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

拉链法解决哈希冲突

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

JDK1.7下的HashMap

属性声明

//初始化容量    
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//阈值 扩容时会用到
int threshold;

构造方法

//自定义初始化容量和加载因子，会进行判断两个值合不合法
// The default initial capacity - MUST be a power of two. 容量必须是2的幂次方
public HashMap(int initialCapacity, float loadFactor)
//自定义初始化容量，使用默认的加载因子
public HashMap(int initialCapacity) 
//使用默认的初始化容量和默认的加载因子
public HashMap()

//归根结底 最终都是调用了这个构造方法
public HashMap(int initialCapacity, float loadFactor) {
     //判断初始化容量是否合法
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
     //当初始化容量大于等于最大容量时，直接赋值为最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
     //判断加载因子是否和法
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
  //给加载因子赋值
        this.loadFactor = loadFactor;
     //这里留个问题？ 这个究竟是干嘛的？为什么要赋值给它。
        threshold = initialCapacity;
        init(); //hashMap中该方法为空，没有实现，在LinkedList才有实现，所以这里不做研究 
}

put方法

public V put(K key, V value) {
     //当前table数组为空，则去进行初始化大小，在这里我们就能够知道在构造方法中，为什么要将初始化容量赋值给threshold了，根据我的理解其实就是起到一个懒初始化的效果吧，就是当你去put第一个值的时候，它才去进行初始化数组的大小
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);  //设置阈值和初始化数组大小的
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);    //干扰函数 求出hash值
        int i = indexFor(hash, table.length); //求出位置
        for (Entry<K,V> 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;
    }

inflateTable(threshold)

private void inflateTable(int toSize) {

          // Find a power of 2 >= toSize  根据注释可以知道是找到一个大于等于toSize的2的幂次方
       // 例如toSize=5 时，则capacity此时就会等于8
          int capacity = roundUpToPowerOf2(toSize);  

          threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
          table = new Entry[capacity];
          initHashSeedAsNeeded(capacity);
 }

private static int roundUpToPowerOf2(int number) {
           // assert number >= 0 : "number must be non-negative";
        // 进来看我们可以发现这是两个三目表达式嵌套
        // 又出现了一个我们不认识的函数， 我们继续深究它
           return number >= MAXIMUM_CAPACITY
                   ? MAXIMUM_CAPACITY
                   : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

// 这个函数看上去很是简洁，全是位运算，那么它就是是在干嘛呢？
public static int highestOneBit(int i) {
           // HD, Figure 3-1
           i |= (i >>  1);
           i |= (i >>  2);
           i |= (i >>  4);
           i |= (i >>  8);
           i |= (i >> 16);
           return i - (i >>> 1);
}

//在highestOneBit(int i)中第一次右移了1位，第二次右移了2位，第三次右移了4位，到了第五次右移了16位，一共是31位。
//因为int类型在内存中占4个字节，一共32位。假设i非常大，占满了32位。
1000 0000 0000 0000 0000 0000 0000 0000
//此时右移1位
0100 0000 0000 0000 0000 0000 0000 0000
//或运算后
1100 0000 0000 0000 0000 0000 0000 0000
//接着右移2位
0011 0000 0000 0000 0000 0000 0000 0000
//或运算后
1111 0000 0000 0000 0000 0000 0000 0000
//接着右移4位
0000 1111 0000 0000 0000 0000 0000 0000
//或运算后
1111 1111 0000 0000 0000 0000 0000 0000 
//接着右移8位
0000 0000 1111 1111 0000 0000 0000 0000
//或运算后
1111 1111 1111 1111 0000 0000 0000 0000
//接着右移16位
0000 0000 0000 0000 1111 1111 1111 1111
//或运算后
1111 1111 1111 1111 1111 1111 1111 1111
//i - (i >>> 1)后
1000 0000 0000 0000 0000 0000 0000 0000
//这就是小于等于i的2的幂次方了

现在一层一层返回去

//此时我们返回到这里，highestOneBit是传进去5返回4 
//然后该函数是传进去5返回8
//很明显是相反的，那么它是怎么实现的呢？
/**
假设现在number等于5，它最终回去调用这个Integer.highestOneBit((number - 1) << 1)，
下面我们都用位运算表示 0000 0101 - 0000 0001 = 0000 0100 << 1 = 0000 1000 = 8
此时调用highestOneBit函数，传进去的是8,小于等于8的2幂次方的数不就是8吗？
此时roundUpToPowerOf2该函数不就得到的数不就是大于等于5的2的幂次方的数吗？
 **/
private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

继续往上返回

private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
     //此时我们就可以看到它给table开辟了一个大小为capacity的数组了。
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

HashMap每次插入都是头插入法

接着看

      // hash为hash值   bucketIndex为上面算出来的key要放进去的下标
      void addEntry(int hash, K key, V value, int bucketIndex) {
           //这里出现了threshold，默认情况是12
          //当Map大小大等于threshold 且 将要放入的数组位置不为空时
              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);
          }

      //这个函数就是简单的将key添加进去
      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++;   //标记table数组中已存储key-val的个数，为了判断是否需要扩容
          }

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


void resize(int newCapacity) {
      Entry[] oldTable = table;
     //old数组容量如果等于最大容量 1<<30 这么大，直接将阈值设置为一样的大小然后返回。
      int oldCapacity = oldTable.length;
      if (oldCapacity == MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return;
      }
  //新建一个数组，数组的长度为原来的两倍，上面传进来的参数
      Entry[] newTable = new Entry[newCapacity];
     //调用transfer函数  initHashSeedAsNeeded函数为初始化哈希种子的值，HashSeed
    //移动链表到新数组中
      transfer(newTable, initHashSeedAsNeeded(newCapacity));
      table = newTable;
    //算出新的阈值
      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

那么，哈希表最多存储多少个值后才会进行扩容呢？最多可以存11+15+1 = 27个，怎么算出来的呢？

在极端情况下，在第一个位置，可以put进去11个k-v，此时小于阈值12，不会发生扩容，然后接下来在剩余的15个位置中put进去k-v，此时size大于阈值，但是没有发生哈希碰撞，不会扩容，接下来再put进去一个k-v，此时必定会发生哈希碰撞，所以就发生了扩容，所以才有了 11+15+1。

JDK1.8下的HashMap

用的是数组+链表+红黑树结构，数组里的一个位置中所占的所有数据也叫哈希桶。

属性声明

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    //序列号，序列化的时候使用。
    private static final long serialVersionUID = 362498820763181265L;
    /**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //最大容量，2的30次方。
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //加载因子，用于扩容使用。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //当某个桶节点数量大于8时，会转换为红黑树。
    static final int TREEIFY_THRESHOLD = 8;
    //当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
    static final int UNTREEIFY_THRESHOLD = 6;
    //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
    static final int MIN_TREEIFY_CAPACITY = 64;
    //存储元素的数组，transient关键字表示该属性不能被序列化
    transient Node<K,V>[] table;
    //将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
    transient Set<Map.Entry<K,V>> entrySet;
    //元素数量
    transient int size;
    //统计该map修改的次数
    transient int modCount;
    //临界值，也就是元素数量达到临界值时，会进行扩容。
    int threshold;
    //也是加载因子，只不过这个是变量。
    final float loadFactor;

这里讲讲为什么默认容量大小为16，加载因子为0.75，主要原因是这两个常量的值都是经过大量的计算和统计得出来的最优解，仅仅是这样而已。

添加操作

    public V put(K key, V value) {
        /**四个参数，第一个hash值，第四个参数表示如果该key存在值，如果为null的话，则插入新的value，最后一个参数，在hashMap中没有用，可以不用管，使用默认的即可**/
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //获取长度并进行扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /**如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p**/
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //发生哈希冲突的几种情况
        else {
            // e 临时节点的作用， k 存放该当前节点的key 
            Node<K,V> e; K k;
            //第一种，插入的key-value的hash值，key都与当前节点的相等，e = p，则表示为首节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //第二种，hash值不等于首节点，判断该p是否属于红黑树的节点
            else if (p instanceof TreeNode)
                /**为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），该值很重要，用来判断put操作是否成功，如果添加成功返回null**/
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点
            else {
                //遍历该链表
                for (int binCount = 0; ; ++binCount) {
                    //如果找到尾部，则表明添加的key-value没有重复，在尾部进行添加
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //判断是否要转换为红黑树结构
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果链表中有重复的key，e则为当前重复的节点，结束循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //有重复的key，则用待插入值进行覆盖，返回旧值。
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null
        //修改次数+1
        ++modCount;
        //实际长度+1，判断是否大于临界值，大于则扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        //添加成功
        return null;
    }

扩容机制 resize()

//在初始化时会调用，超过阈值时会调用，转换成红黑树前若数组大小超过64会调用
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //旧容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //旧阈值
        int oldThr = threshold;
        //定义新的容量和阈值
        int newCap, newThr = 0;
        //说明不是首次初始化 因为hashMap用的是懒加载
        if (oldCap > 0) {
            //大于最大值
            if (oldCap >= MAXIMUM_CAPACITY) {
                //阈值为整数的最大倍
                threshold = Integer.MAX_VALUE;
                //返回
                return oldTab;
            }
            //扩容2倍，并且扩容后的长度要小于最大值， 旧容量大等于16
            //其他情况 标记为##
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //临界值扩容为原来的2倍
                newThr = oldThr << 1; // double threshold
        }
        /**
         * 以下是Map数组还没有初始化的情况：
         分两种：
         1. 显示传入初始 capacity时，threshold在构造函数时被赋值，其值为数组初始容量
         2. 使用无参构造函数 new HashMap，threshold = 0
         */
        //属于第一种情况
        else if (oldThr > 0) // initial capacity was placed in threshold
            //新容量为旧阈值
            newCap = oldThr;
        //属于第二种情况
        else {               // zero initial threshold signifies using defaults
            //赋值为默认16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //默认 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //此处的if是上面标记的##其他情况，也就是初始化容量小于默认值16，此时newThr没有赋值
        if (newThr == 0) {
            //新的阈值
            float ft = (float)newCap * loadFactor;
            //当新容量小于最大值 且 新阈值小于最大值时，新阈值等于新阈值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //把上面各种情况分析出的临界值，在此处真正进行改变，也就是容量和临界值都改变了。
        threshold = newThr;

        //初始化
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //赋予当前的table
        table = newTab;
        //此处自然是把old中的元素，遍历到new中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                //临时变量
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { //当前哈希桶的位置值不为null，也就是数组下标处有值，因为有值表示可能会发生冲突
                    //把已经赋值之后的变量置位null，当然是为了好回收，释放内存
                    oldTab[j] = null;
                    if (e.next == null) //如果下标处的节点没有下一个元素
                        newTab[e.hash & (newCap - 1)] = e; //把该变量的值存入newCap中，e.hash & (newCap - 1)并不等于
                    // 该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { //此处表示为链表结构，同样把链表转移到newCap中，就是把链表遍历后，把值转过去，在置位null
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //将两部分 分装进新数组中
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //返回扩容后的hashMap
        return newTab;
    }

这边也可以引申到一个问题HashMap是先插入还是先扩容：HashMap初始化后首次插入数据时，先发生resize扩容再插入数据，之后每当插入的数据个数达到threshold时就会发生resize，此时是先插入数据再resize。

1.8下的扩容机制

整体流程：

newTab = new 一个二倍原长度的Node数组，threshold也为2倍。
将table指向newTab。
依次遍历原来Node数组每个坑位，将坑中的元素进行rehash。

第一步中扩容细节：

不是第一次扩容，table容量会等于旧容量的两倍；若旧容量大等于默认容量16，阈值也设置为旧阈值的两倍。
首次初始化时使用无参构造函数，容量为默认16，阈值为默认12
首次初始化使用有参构造函数，此时阈值已经初始化过了。新容量为它的阈值。

第三步rehash细节：

原坑位中没有元素：oldTab[j] == null，不用管，保持原样就好。
原坑位中元素被树化了（就是在单个坑位中元素大于8时，链表变成二叉树），调用TreeNode.split()函数将原树分成两部分，分别装进新table不同坑位。
原坑位是一个链表，分装成两部分。

(e.hash & oldCap) 是否为 0 即：Node<K,V> 节点中 key 的二进制 hash 值的从右往左第 n+1 位 (2^n = oldCap) 是否为1. 因为数组长度一定是 2 的次方，其二进制值只有一位是 1，其余全为 0.

现在，原链表被分成了两部分：
- loHead 指向的部分放在 newTab[1] 中；
- hiHead 指向的部分放在 newTab[1+8] = newTab[9] 中。

hashMap为什么链表超过8转化为红黑树？

首先先说下红黑树是一个特殊的平衡二叉树，查找的时间复杂度是 O(logn) ；而链表查找元素的时间复杂度为 O(n)，远远大于红黑树的 O(logn)，尤其是在节点越来越多的情况下，O(logn) 体现出的优势会更加明显；简而言之就是为了提升查询的效率。

那为什么不一开始就用红黑树，反而要经历一个转换的过程呢？其实在 JDK 的源码注释中已经对这个问题作了解释：

     * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.

单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值（默认值8）决定的。而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间，这个阈值是 UNTREEIFY_THRESHOLD（默认值6）。

那阈值为什么选择了8

通过查看源码可以发现，默认是链表长度达到8就转成红黑树，而当长度降为6就转换回去，这体现了时间和空间平衡的思想，最开始使用链表，空间占用少，由于链表短，查询时间也没有太大问题。当链表越来越长时，需要用红黑树的形式来保证查询的效率O(logN)，而在何时进行转换，需要确定一个阈值，默认是8。JDK的源码也做了解释为什么是8：

     * In usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

如果hashCode分布良好，就是离散好的话，红黑树这种形式是很少被用到的，因为每个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。

但是HashMap决定某一个元素落到哪一个桶里，是和这个对象的hashCode有关，JDK并不能阻止我们用户实现自己的哈希算法，如果我们故意把哈希算法变得不均匀，那么就很容易导致HashMap里的链表变得很长。

因此，链表长度超过8就转换为红黑树，更多是为了防止用户自己实现了不好的哈希算法时导致链表很长，从而导致查询效率低，而此时转为红黑树更多是一种保底策略，用来保证极端情况下的查询效率。如果哈希算法良好，链表长度不会很长，也没有必要增加空间负担来转为红黑树，因为此时红黑树并不会带来明显的查询时间上的优势。

所以，在开发中，如果HashMap或者ConcurrentHashMap内部出现了红黑树的结构，这时候可能是我们的哈希算法出了问题。

HashMap的长度为什么是2的幂次方

HashMap为了存取高效，要尽量减少哈希冲突，就是要尽量把数据分配均匀。

Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (length - 1) & hash”。

其实也可以用%取余来实现，但是，采用二进制位操作&，相对%能够提高运算效率。

源码中做了优化hash&(length-1)，
hash%length==hash&(length-1)的前提是length是2的n次方也是为了减少哈希碰撞。

2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1。

不然

例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了

就是容易产生碰撞；而%取余不会。

所以HashMap的长度为什么是2的幂次方。

HashMap多线程操作导致死循环问题

主要原因在于并发下的Rehash 会造成元素之间会形成⼀个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使⽤ HashMap,因为多线程下使⽤ HashMap 还是会存在其他问题⽐如数据丢失。并发环境下推荐使⽤ ConcurrentHashMap。

Rehash发生在扩容阶段：

//调用resize函数
//传进去两倍的oldtable.length
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);


void resize(int newCapacity) {
      Entry[] oldTable = table;
     //old数组容量如果等于最大容量 1<<30 这么大，直接将阈值设置为一样的大小然后返回。
      int oldCapacity = oldTable.length;
      if (oldCapacity == MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return;
      }
  //新建一个数组，数组的长度为原来的两倍，上面传进来的参数
      Entry[] newTable = new Entry[newCapacity];
     //调用transfer函数  initHashSeedAsNeeded函数为初始化哈希种子的值，HashSeed
      transfer(newTable, initHashSeedAsNeeded(newCapacity));
      table = newTable;
    //算出新的阈值
      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}


void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {  //去遍历数组中的节点
            while(null != e) {
                Entry<K,V> next = e.next; //遍历链表
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);    //重新计算出hash值
                }
                int i = indexFor(e.hash, newCapacity);//分配新位置
                e.next = newTable[i];  //将e指向新数组的位置
                newTable[i] = e; //使用头插入法
                e = next; //再将e指向刚刚保存的next，好继续原链表的移动
            }
        }
    }

举个例子：

但是若有多个线程：

假设线程一执行完Entry<K,V> next = e.next;后就被挂起，线程二执行，执行完后是这样：

此时线程一被调度回来执行，

先是执行 newTalbe[i] = e;
然后是e = next，导致了e指向了key(7)，
而下一次循环的next = e.next导致了next指向了key(3)

这样就造成了链表循环。

HashMap 和 Hashtable 的区别

线程是否安全： HashMap 是⾮线程安全的，HashTable 是线程安全的,因为 HashTable 内部的⽅法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使⽤ConcurrentHashMap 吧！）；
效率：因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable 基本被淘汰，不要在代码中使⽤它；
对 Null key和 Null value 的⽀持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有⼀个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
*初始容量⼤⼩和每次扩充容量⼤⼩的不同 *： ① 创建时如果不指定容量初始值，Hashtable 默认的初始⼤⼩为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化⼤⼩为16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为 2 的幂次⽅⼤⼩（HashMap 中的tableSizeFor() ⽅法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤ 2 的幂作为哈希表的⼤⼩。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间。Hashtable 没有这样的机制。

HashTable 如何保证线程安全，两个线程可以同时分别调用get()和put()方法吗？

HashTable给提供的方法几乎都加上了synchronized关键字，保证在任一时刻只有一个线程操作hashTable对象。所以两个线程无法同时分别调用它的任两个方法。

`ConcurrentHashMap`并发哈希表

`ConcurrentHashMap`如何实现线程安全

JDK1.7下的实现

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

分段锁如果加多了，那么可以容许更多的线程并发数，不会造成太多线程在等待和阻塞，但是多个分段锁会浪费空间。如果加少了，就会造成性能的下降。

JDK1.8下的实现

ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

ConcurrentHashMap 和 Hashtable 的区别

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采⽤分段的数组+链表实现，JDK1.8 采⽤的数据结构跟 HashMap1.8 的结构⼀样，数组+链表/红⿊⼆叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采⽤数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的；
实现线程安全的⽅式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁）对整个桶数组进⾏了分割分段(Segment)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率。到了 JDK1.8 的时候已经摒弃了Segment 的概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，并发控制使⽤synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同⼀把锁) :使⽤ synchronized 来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤get，竞争会越来越激烈效率越低。