数据结构和算法：08.HashMap 源码分析和手写

具体代码请看：JavaJniTest项目的datastructure33hashmap

常见面试题：

• equals 和 == 的区别，hashCode 与它们之间的联系？
• HashMap 的长度为什么是 2 的幂次？
• 五个线程同时往 HashMap 中 put 数据会发生什么？
• ConcurrentHashMap 是怎么保证线程安全的？
• HashMap在jdk1.8之后为何引入了红黑树

1. HashMap默认的一些参数：

• HashMap 数组长度默认大小：16、默认阈值：12、加载因子：0.75f，扩容为当前数组长度大小的一倍
• vector ：没指定大小的情况下，初始大小为 10,扩容为当前大小的一倍
• ArrayList ： 没指定大小的情况下，初始大小为 10,扩容为当前大小的二分之一

为什么加载因子是 0.75

• 加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大了；

• 加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。

2. == 和 equals

== 判断的是地址

equals 也是判断两个对象相等，但是更多的是判断内容相等，多用于集合判断

3. hashCode：

如果你复写了 equals 一般要复写 hashCode,一般集合中都是通过hashcode去减少时间复杂度,获取的时候也会判断hashcode是否相等

hashcode = 地址值 >> 16

总结:

1. hash 值相等两个对象不一定相等
2. 两个对象不相等 hash 值有可能相等
3. hash 值不相等的两个对象，这两个对象肯定不相等

4. HashMap 的长度为什么是 2 的幂次？

为了能让HashMap存取高效，尽量减少碰撞，也就是要尽量把数据分配均匀，Hash值的范围是-2147483648到2147483647，前后加起来有40亿的映射空间。

这个散列值是不能直接拿来用的。用之前需要先对数组长度取模运算，得到的才是在数组中存储的位置。

总结：hash%length=hash&(length-1)，但前提是length是2的n次方，并且采用&运算比%运算效率高，且为了减少碰撞，分配均匀，所以长度才会是 2的幂次。

举例：
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

5. 手写HashMap时关键代码分析：

/**
 *  手写 HashMap 一些关键性的代码
 */
public class HashMap<K,V> {

    class MapEntry<K,V>{
        K key;
        V value;
        MapEntry<K,V> next;
        int hash; // Key 的 hash 值

        public MapEntry(int hash,K key, V value,MapEntry<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    /**
     *  散列 table （桶）
     */
    transient MapEntry[] table;

    /**
     *  总共多少的键值对
     */
    int size;


    /**
     *  初始大小为 16
     */
    final int DEFAULT_INITIAL_CAPACITY =  1 << 4;

    /**
     *  扩容阈值（满足这个条件时扩容）
     */
    int threshold;

    /**
     *  扩容因子，如何扩容
     */
    final float loadFactory = 0.75f;

    public V put(K key,V value){
        if(table == null){
            table = new MapEntry[DEFAULT_INITIAL_CAPACITY];
            threshold = (int) (DEFAULT_INITIAL_CAPACITY * loadFactory);
        }

        // 是不是空
        if(key == null){
            // 自行看 hashMap 的源码
            return null;
        }

        // 1. 找到 table 的位置
        int hash = hash(key);
        int index = getIndex(hash,table.length);

        // 2. 判断有没有存在该key
        for (MapEntry<K,V> e = table[index]; e!=null; e = e.next){
            K k;
            if(e.hash == hash && ((k = e.key) == key || (key!=null && key.equals(k)))){
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        // 3. 添加一个新的 MapEntry
        addEntry(hash,key,value,index);
        return null;

    }

    /**
     * 添加一个新的 Entry
     * @param hash
     * @param key
     * @param value
     * @param index
     */
    private void addEntry(int hash, K key, V value, int index) {
        // hash_shift 16 value() >> 16
        // 判断要不要扩容 jni 源码记住 mask_bits(value() >> hash_shift,hash_mask)
        // 1. hash 值相等两个对象不一定相等，（两个对象不相等，hash值可能相等）
        // 2. hash 值不相等的两个对象肯定不相等
        if(size >= threshold && table[index] != null){
            resize(table.length << 1);
            // 重新计算 index
            index = getIndex(hash,table.length);
        }
        // 添加
        createEntry(hash,key,value,index);

        size++;
    }

    private void resize(int newCapacity) {
        MapEntry<K,V>[] newTable = new MapEntry[newCapacity];
        // 直接把之前的数组搬过来，不行！！ 扩容之后 Index 会变 复杂度 O(n)
        transform(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactory);
    }

    /**
     * 重新计算 挪动，散列
     * @param newTable
     */
    private void transform(MapEntry<K, V>[] newTable) {
        int newCapacity = newTable.length;

        for (MapEntry<K, V> entry : table) {
            while (entry!=null){
                // 从原来的数组中获取数据 Entry , 保证新的数组能链上
                MapEntry<K,V> next = entry.next;

                // 重新计算 index
                int index = getIndex(entry.hash,newCapacity);
                // 保证新的数组能链上
                entry.next = newTable[index];
                newTable[index] = entry;

                entry = next;
            }
        }
    }

    private void createEntry(int hash, K key, V value, int index) {
        MapEntry<K,V> newEntry = new MapEntry<>(hash,key,value,table[index]);
        table[index] = newEntry;
    }


    private int hash(K key){
        int h;
        return (key == null) ? 0 : (h=key.hashCode()) ^ (h >>> 16);
    }

    private int getIndex(int hash,int length){
        return hash & length -1; // - 运算符比 & 优先级高
    }

    public V get(K key){
        if(key == null){
            return null;
        }

        MapEntry<K,V> entry = getEntry(key);
        return entry == null ? null : entry.value;
    }

    private MapEntry<K, V> getEntry(K key) {
        // 1. 找到 table 的位置
        int hash = hash(key);
        int index = getIndex(hash, table.length);

        // 2. 判断有没有存在该 key
        for(MapEntry<K,V> e = table[index]; e!=null; e = e.next){
            K k;
            if(hash == e.hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                return e;
            }
        }
        return null;
    }

    public int size(){
        return size;
    }

}