手撕HashMap+版本答案

​
public class HashMap extends AbstractMapimplements Map{
    
    //操作数
    transient int modCount;//3
    //空数组的实例（长度为0的数组）
    static final Entry[] EMPTY_TABLE = {};
    //存入数据的容器（hash数组/hash表） --  new Entry[16];
    transient Entry[] table = (Entry[]) EMPTY_TABLE;
    //数组默认初始化容量（必须是2的幂）
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//16
    //默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //数组最大长度
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //映射关系个数
    transient int size;//3
    //阈值
    int threshold;//12
    //负载因子
    final float loadFactor;//0.75
    //hash种子数
    transient int hashSeed = 0;
    
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    
    //initialCapacity - 16
    //loadFactor - 0.75
    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))//NaN - Not a Number
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
​
        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }
    
    //key - null
    //value - '女'
    public V put(K key, V value) {
        //第一次添加元素时，进入此判断
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);//阈值-12，数组初始化，获取hashSeed
        }
        if (key == null)
            return putForNullKey(value);
        //获取在key的hash+散列算法
        int hash = hash(key);
        //通过hash值计算出在数组中的下标
        int i = indexFor(hash, table.length);
        //e - 卢永刚的Entry
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                //oldValue - 男
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;//key相同，返回被覆盖的value值
            }
        }
​
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
    
    //添加null键的方法
    private V putForNullKey(V value) {
        //e - 0x004
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                //oldValue - 男
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;//返回被覆盖的value值
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
    
    // hash- 0
    // key- null
    // value-'男'
    //bucketIndex-0
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //判断是否扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //扩容
            resize(2 * table.length);
            //重新计算hash值
            hash = (null != key) ? hash(key) : 0;
            //重新计算在数组中的下标
            bucketIndex = indexFor(hash, table.length);
        }
​
        createEntry(hash, key, value, bucketIndex);
    }
    
    //newCapacity - 32
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        //oldCapacity - 16
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
​
        //创建新的hash数组
        Entry[] newTable = new Entry[newCapacity];
        //initHashSeedAsNeeded(newCapacity)根据新数组的容量重新计算hash种子数
        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 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;
            }
        }
    }
    
    // hash- 0
    // key- null
    // value-'男'
    // bucketIndex-0
    void createEntry(int hash, K key, V value, int bucketIndex) {
        //e - null
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
    
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
    
    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            //key为String类型时，回去的hash值是有hash种子数参与的
            return sun.misc.Hashing.stringHash32((String) k);
        }
​
        h ^= k.hashCode();
​
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    
    //toSize - 16
    private void inflateTable(int toSize) {
        
        //capacity - 16
        int capacity = roundUpToPowerOf2(toSize);//不管传什么int数据，都返回与之对应的2的幂
        //threshold - 12
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //初始化数组
        table = new Entry[capacity];
        //初始化hash种子数
        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 = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }
    
    private static int roundUpToPowerOf2(int number) {
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestoneBit((number - 1) << 1) : 1;
    }
​
    
    //映射关系类/节点类
    static class Entry implements Map.Entry {
        final K key; ---- key
        V value; -------- 值
        Entry next;- 下一个节点的地址
        int hash; ------- key的hash值
​
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    }
}

场景： HashMap map = new HashMap<>();

    map.put(new Student("林成", "2107", "001"), '男');
    map.put(new Student("李科", "2107", "002"), '男');
    
    Student stu = new Student("卢永刚", "2107", "003");
    map.put(stu, '男');
    Character put = map.put(stu, '女');
    System.out.println(put);
    
    map.put(null, '男');
    map.put(null, '女');

1. JDK1.7版本，HashMap的数据结构是什么？

   数组+单向链表

2. 什么叫做Hash桶

   数组中的单向链表

3. HashMap的数组长度为什么必须是2的幂？

   计算元素存在数组中下标的算法：hash值 & 数组长度-1

   如果数组长度不是2的幂，减1后二进制的某一位有可能出现0，导致数组某个位置永远存不到数据

4. HashMap的默认负载因子是多少，作用是什么？

   默认负载因子是0.75

   作用：数组长度*负载因子=阈值（扩容条件）

5. HashMap的默认负载因子为什么是0.75？

   取得了时间和空间的平衡

   假设负载因子过大，导致数组装满后才扩容，牺牲时间，利用空间

   假设负载因子过小，导致数组装载较少内容就扩容，牺牲空间，利用时间

6. HashMax数组最大长度是多少？

   1 << 30

7. HashMap数组最大长度为什么是1 << 30？

   因为数组长度必须是2的幂并且HashMap数组最大长度的变量为int类型，所有1<<30

8. 什么叫做Hash碰撞/冲突？

   两个对象的hash值一样，导致在数组中的下标一样

9. HashMap何时扩容？

   元素个数>=阈值，并且存入数据的位置不等于null

10. HashMap扩容机制是什么？

    原来的2倍

11. HashMap存入null键的位置？

    hash数组下标为0的位置

12. 什么叫做Hash回环？

    多线程下会出现Hash回环

    线程1：不断添加数据，导致不断扩容

    线程2：不断遍历

    出现Hash回环，活该，HashMap明确说明该集合不是个线程安全的集合，多线程下应该使用ConcurrentHashMap

13. JDK1.7版本和JDK1.8版本的HashMap的区别

    JDK1.7：数组+链表，头插法，通过散列算法获取hash值

    JDK1.8：数组+链表+红黑树，尾插法，通过低16位^高16位让hash值更加散列

14. JDK1.8版本HashMap为什么添加红黑树的数据结构？

    因为链表查询慢，红黑树查询快

15. JDK1.8版本什么时候由数组+链表变成数组+红黑树

    链表长度>8并且数组长度>64时，从数组+链表变成数组+红黑树

16. JDK1.8版本为什么链表长度大于8时，变成数组+红黑树

    因为泊松部分（统计概率学），当红黑树里的数据小于6时，又会将数组+红黑树变会数组+链表