HsahMap源码解析

hash是什么？

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。

hash的特点

1. 输入消息的长度不受限制，输出得到的长度是固定的
2. 不可逆，可以把原文计算出密文，但是不能倒回去
3. 算法不固定，只要满足hash的思想就是hash算法。
4. 检索速度快
5. 防篡改：密码学里的主要用途，因为只能加密不能解密，所以发送数据时会把原文加密后把原文和密文一起发给对方，对方收到后，先对原文做个加密，如果密文和收到的一样说明内容没被改过。常见的比如用迅雷下载时，一般会带一个md5文件，如果下载完成后提示文件不安全，那可能就是源文件被修改过和提供的密文不一致。
6. 密码保存：注册密码都是加密后保存在数据库的，这样做的好处就是维护人员不能直接看到用户的密码，并且无法倒推。

HashMap 数据结构及其工作原理？

数据结构

HashMap 数据结构为 数组+链表，其中：链表的节点存储的是一个 Entry 对象，每个Entry 对象存储四个属性（hash，key，value，next）

• 数组

内存中的一片连续区域，同类型数据的集合，有索引，查询快，增删慢，不可扩容。

• 链表

不连续的区域，每个节点放值和指向下一个节点的指针。查询慢，增删块。

•  

  哈希表

可以理解为数组和链表的组合。即一个一维数组，但是数组中的每个元素是一个链表。

工作原理

首先，初始化 HashMap，提供了有参构造和无参构造，无参构造中，容器默认的数组大小 initialCapacity 为 16，加载因子loadFactor 为0.75。容器的阈(yu)值为 initialCapacity * loadFactor，默认情况下阈值为 16 * 0.75 = 12; 后面会讲到阈啥用。然后，这里我们拿 PUT 方法来做研究：

第一步：通过 HashMap 自己提供的hash 算法算出当前 key 的hash 值

第二步：通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组的几号位置

第三步：判断size 是否已经达到了当前阈值，如果没有，继续；如果已经达到阈值，则先进行数组扩容，将数组长度扩容为原来的2倍。

 请注意：size 是当前容器中已有 Entry 的数量，不是数组长度。

第四步：将当前对应的 hash，key，value封装成一个 Entry，去数组中查找当前位置有没有元素，如果没有，放在这个位置上；如果此位置上已经存在链表，那么遍历链表，如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true，则把原来节点上的value 返回，将当前新的 value替换掉原来的value，如果遍历完链表，没有找到key 与当前 key equals为 true的，就把刚才封装的新的 Entry中next 指向当前链表的始节点，也就是说当前节点现在在链表的第一个位置，简单来说即，先来的往后退。

基本参数

// 默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 定义一个空数组
static final Entry<?,?>[] EMPTY_TABLE = {};
// 存储键值对的数组，默认为空数组，根据需要进行扩容，长度必须是2的整数幂
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 容量*加载因子，根据此判断是否需要扩容
int threshold;
// map中的键值对个数
transient int size;
// 此 HashMap 已在结构上修改的次数。结构修改是指更改 HashMap 中的映射数量或以其他方式修改其内部结构（例如，重新散列）的那些。该字段用于使 HashMap 的 Collection-views 上的迭代器快速失败。 （请参阅 ConcurrentModificationException）。
// 结构上的修改一般来说就是添加和删除
transient int modCount;

构造函数

//指定容量大小的构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/*
     指定“容量大小”和“加载因子”的构造函数
     initialCapacity: 指定的容量
     loadFactor:指定的加载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
    //判断初始化容量initialCapacity是否小于0
    if (initialCapacity < 0)
        //如果小于0，则抛出非法的参数异常IllegalArgumentException
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    
    //判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂
    if (initialCapacity > MAXIMUM_CAPACITY)
        //如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
        initialCapacity = MAXIMUM_CAPACITY;
    
    //判断负载因子loadFactor是否小于等于0或者是否是一个非数值
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        //如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    //将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
    this.loadFactor = loadFactor;
    /*
            tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。
            但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写：
            this.threshold = tableSizeFor(initialCapacity) *this.loadFactor;
            这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。
            但是，请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算
        */
    this.threshold = tableSizeFor(initialCapacity);
}

/**
      Returns a power of two size for the given target capacity.
      返回比指定初始化容量大的最小的2的n次幂
*/
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

put方法

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            // 如果是空数组，根据容量进行初始化，
            inflateTable(threshold);
        }
        if (key == null)
            // 有则更新，无则新增，下标为0
            return putForNullKey(value);
        // 根据key取hash值
        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;
    }
 
     private void inflateTable(int toSize) {
        // 容量是2的整数幂
        int capacity = roundUpToPowerOf2(toSize);
 
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }
 
    final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            // 最后结果是 hashSeed=0
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }
 
     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;
    }
    // 原理（扰动函数），尽可能使生成的hash值分布均匀，随机，避免冲突
    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
 
        h ^= k.hashCode();
 
        // 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);
    }
 
    // 当length始终为2的n次方时，h&(length-1)等价于h%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);
    }
 
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length); // 当size大于容量*负载因子的时候进行扩容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
 
        createEntry(hash, key, value, bucketIndex);
    }
    // 新增一个entry
    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++;
    }
 
    // 扩容
    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);
    }
    // 将旧数组的元素转移到新数组
    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);
                }
                int i = indexFor(e.hash, newCapacity);
                // 这里采用了“头插法”，相当于倒序插入
                // 假如原来的链表为 a->b->c->d->null
                // 转移后的新的链表为 d->c->b->a->null
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

1.首先获取Node数组table对象和长度，若table为null或长度为0，则调用resize()扩容方法获取table最新对象，并通过此对象获取长度大小

2.判定数组中指定索引下的节点是否为Null，若为Null 则new出一个单向链表赋给table中索引下的这个节点

3.若判定不为Null,我们的判断再做分支
3.1 首先对hash和key进行匹配,若判定成功直接赋予e

3.2 若匹配判定失败,则进行类型匹配是否为TreeNode 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给e

3.3 若以上判定全部失败则进行最后操作,向单向链表中添加数据若单向链表的长度大于等于8,则将其转为红黑树保存，记录下一个节点,对e进行判定若成功则返回旧值

4.最后判定数组大小需不需要扩容

resize方法

//重新设置table大小/扩容 并返回扩容的Node数组即HashMap的最新数据
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; //table赋予oldTab作为扩充前的table数据
        int oldCap = (oldTab == null) ? 0 : oldTab.length; 
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
             //判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
             //若新表大小(oldCap*2)小于数组极限大小 并且 老表大于等于数组初始化大小
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr*2当作新数组的大小
                newThr = oldThr << 1; // double threshold
        }
         //若老表中下次扩容大小oldThr大于0
        else if (oldThr > 0)
            newCap = oldThr;  //将oldThr赋予控制新表大小的newCap
        else { //若其他情况则将获取初始默认大小
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //若新表的下表下一次扩容大小为0
        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 = newTab; //将当前表赋予table
        if (oldTab != null) { //若oldTab中有值需要通过循环将oldTab中的值保存到新表中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {//获取老表中第j个元素 赋予e
                    oldTab[j] = null; //并将老表中的元素数据置Null
                    if (e.next == null) //若此判定成立 则代表e的下面没有节点了
                        newTab[e.hash & (newCap - 1)] = e; //将e直接存于新表的指定位置
                    else if (e instanceof TreeNode)  //若e是TreeNode类型
                        //分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null; //存储与旧索引的相同的节点
                        Node<K,V> hiHead = null, hiTail = null; //存储与新索引相同的节点
                        Node<K,V> next;
                        //通过Do循环 获取新旧索引的节点
                        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;
                        }
                    }
                }
            }
        }
        //返回新表
        return newTab;
    }

1. 判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回
2. 若新表大小(oldCap2)小于数组极限大小&老表大于等于数组初始化大小 判定成功则 旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr2当作新数组的大小
   1. 若[2]的判定不成功，则继续判定 oldThr （代表 老表的下一次扩容量）大于0，若判定成功 则将oldThr赋给newCap作为新表的容量
   2.  若 [2] 和[2.1]判定都失败,则走默认赋值 代表 表为初次创建
3. 确定下一次表的扩容量, 将新表赋予当前表
4. 通过for循环将老表中德值存入扩容后的新表中
   1.  获取旧表中指定索引下的Node对象 赋予e 并将旧表中的索引位置数据置空
   2. 若e的下面没有其他节点则将e直接赋到新表中的索引位置
   3. 若e的类型为TreeNode红黑树类型
      1. 分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
      2. 通过Do循环 不断获取新旧索引的节点
      3. 通过判定将旧数据和新数据存储到新表指定的位置

HashMap常见面试题

• 什么是哈希碰撞
  •  哈希碰撞就是有有限的值碰到了无限的输出，总会有碰撞。
• 为什么要引入红黑树

  • 为了提高HashMap的性能，之前是链表过长导致索引慢的的问题。当没有冲突的时候放在数组中，当冲突<8放在链表中，当>8的时候放在红黑树中时间复杂读从o(n)降到了o（logn）

• 什么时候扩容 
  • 当达到阈值并不会立即扩容，还要一个条件是存在Hash碰撞才会扩容
• 时间复杂度

  • 没有发生碰撞时间复制度O(1)，只需要查询一次

    当时链表的时候O(n)，

    采用红黑树就是O(logn)

    Haximap的底层存放没有顺序。

• jdk7和8的区别
  • 1.7的是底层hashtable 1.8后是hashtable和红黑树
• jdk8中对hashMap做了哪些修改

  • 由数组+链表的结构改为数组+链表+红黑树。

  • 优化了高位运算的hash算法：h^(h>>>16)

  • 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。

  • 不会在出现死循环问题。

• 为什么不用Hashtable而用ConcurrentHashMap?

• 有线程安全的替代类吗

• 扩容方式？负载因子？为什么？

• 为什么在解决hash冲突的时候，不直接用红黑树?而选择先用链表，再转红黑树?

  • 因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。 当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。