[数据结构与算法]HashMap详解，拿过来吧你（部分）

HashMap

1、介绍和底层原理

? 散列表，又称哈希表，是基于快速存取的角度设计的，典型的“空间换时间”的做法。顾名思义，该数据结构是一种线性表，但是其中的元素并不是紧密排布的，而是元素与元素之间可能存在一个间隙

? 散列表（hash table，哈希表），是根据key-value形式存储的，使用key直接访问的数据结构。即它通过把key映射成表的一个位置来访问，以加快访问速度。这个用于映射的函数，我们称为哈希函数，存放key-value的数组成为哈希表。

? 我们是根据key去映射出它将存放的位置的，这样在下次需要取这个数据时，可以再次映射这个key找到键值对对应的数组下标，直接获取数据。但是，由于映射的算法并不是完全完美的，所以会出现不同的key映射后是同一个位置，这就是所谓的“哈希冲突”，对“哈希冲突”的解决方法有很多，JDK中的HashMap和HashTable是采用链地址法来解决的，即哈希后得到相同下标的元素使用链表结构进行连接，链表存放在这个位置下，将在后面阐述。

? HashMap允许key和value为null，后序会详细介绍。

2、属性

// 允许哈希表被序列化
private static final long serialVersionUID = 362498820763181265L;

// 默认容量，为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量为(2^30)
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的扩容因子为0.75，即超过0.75时，哈希表会进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 哈希冲突产生的指定链表超过8个节点，会变成树
static final int TREEIFY_THRESHOLD = 8;

// 哈希冲突产生的指定红黑树小于6个节点，会变回链表
static final int UNTREEIFY_THRESHOLD = 6;

// 当数组的长度超过64，所有的因哈希冲突产生的链表都会变成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;

/* ---------------- Fields -------------- */
// 注：transient修饰，表示这个属性值是不可序列化的

// 用于真正存储数据的数组，即哈希表
transient Node<K,V>[] table;

// 用于保存含有key-value的Entry节点，这个可以通过entrySet()方法获取
transient Set<Map.Entry<K,V>> entrySet;

// 当前存入的元素个数
transient int size;

// 集合被修改的次数
transient int modCount;

// 阈值，是判断是否需要扩容的依据,容器的size大于它就进行扩容。
// 通过size * loadFactor 计算而来
int threshold;

// 元素个数跟数组容量占比多少时开始扩容，即负载因子
final float loadFactor;    

3、构造器

指定初始化阈值(真实容量可能并不是这个值)以及负载因子的方式创建对象；

// 指定初始化的集合阈值和这个集合对象所使用的负载因子
public HashMap(int initialCapacity, float loadFactor) {
    // 要求集合的容量不能小于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 如果集合的容量超过了最大的容量，那么使用静态属性MAXIMUM_CAPACITY作为集合容量，即(2^30)
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 要求给定的扩容因子大于0并且必须是数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    // 完成初始化
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

// 用于返回大于cap且是最小的2的n次幂的数，用于保证hashmap的容量一直为2的整数次幂
static final int tableSizeFor(int cap) {
    // 输入15为例
    int n = cap - 1;	// n为14，二进制为1110
    n |= n >>> 1;		// 1110向右移动一位为n >>> 1 = 111,然后1110和111进行或运算，得到1111
    n |= n >>> 2;		// 运算后值不变
    n |= n >>> 4;		// 运算后值不变
    n |= n >>> 8;		// 运算后值不变
    n |= n >>> 16;		// 运算后值不变
   	// 传入cap是负数，那么返回1；
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // 运算后n = 10000,即16
}

使用一个Map去初始化一个HashMap;

// 使用Map初始化HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    // 默认负载因子为0.75
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 把元素存入集合
    putMapEntries(m, false);
}
// 默认构造器，所有的配置都使用static属性默认的
public HashMap() {
    // 把当前集合对象扩容因子设置为0.75
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 指定阈值初始化HashMap
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

4、putMapEntried方法

• 如果原HashMap是空集合
  • 根据传入的集合的size为0.75，来获取HashMap的准总容量t(由于是小数，加1确保向下取整不会容量不足)，获取大于等于准总容量t的最小2的整数次幂，这个值作为HashMap的容量，需要resize还会自动resize（扩容），然后循环put进元素
• 如果原HashMap不是空集合
  • 就直接扩容后，然后循环put进元素。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 获取传入的集合的元素个数
    int s = m.size();
    // 如果不是空集合
    if (s > 0) {
        // 如果当前HashMap是一个空集合
        if (this.table == null) {
            /*
            	ft是用来计算HashMap的容量的，this.loadFactor已经初始化为0.75了
            	用m.size()/0.75,然后再加1，是为了得到一个刚好不大于阈值的容量t,但是它并不一定是最后的容量
            	最终设置为HashMap的size属性的值，需要将得到的t传入tableSizeFor()方法获取
           	*/
            float ft = ((float)s / this.loadFactor) + 1.0F;
            /* 
            	判断初步得到的容量ft是否大于允许的最大值MAXIMUM_CAPACITY，
            	如没有，那就将ft取整得到容量t，这里取整是向下取整的;
            	在获取ft的时候之所以需要去"+1"操作，就是因为这里，
            	防止传入集合的数量大于我们初始化后HashMap的size，那会导致容量不足
            */
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 如果这个容量t大于阈值，那就需要进行扩容为原来的2倍
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果集合不是空的，并且集合的长度大于当前HashMap的阈值时
        else if (s > this.threshold)
            // 进行扩容
            resize();
        // 循环遍历，放入值到集合
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

5、put方法

在put的时候，使用key对象作为依据，取得它的hashcode值，在进行hash算法得到下标，然后去判断这个下标上是链表、节点还是树，然后创建节点放入数组/接在树/接在链表后；

如果有遇到和key对象相同hashCode()返回值，那么可能会出现覆盖原来value的情况，取决于这次put进去的key是否和原有的key地址相同（同个对象）或者相互equals（要求hashCode也要一致），即两个key不仅hashCode()返回值相同，而且相互equals；

其实，这个方法不仅用于新增键值对，还==会把key原有的value返回（如果有的话），如果key是新增的，那么返回null==；

// 存入key-value
public V put(K key, V value) {
    // 存入key-value，并且要求如果key已经存在，就进行替换
    return putVal(hash(key), key, value, false, true);
}

// 传入对象的hash值，key，value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    
    // 创建tab指针，待用来执行HashMap的底层数组
    Node<K,V>[] tab; 
    // 创建一个p指针，待用来指向hash后的下标位置上的节点
    Node<K,V> p; 
    // n将用来保存哈希表底层数组的长度，i保存hash后的下标
    int n, i;
    
    // 如果HashMap是空的
    if ((tab = table) == null || (n = tab.length) == 0)
        // 进行扩容，然后n用来保存扩容后数组的长度
        n = (tab = resize()).length;
    
    // (n - 1)获取数组最大的下标，对hash值进行与运算，即截取hash值末尾指定位数的二进制码作为下标
    // 如:hash = 11111010,n = 1111(15),那么计算后得到下标1010(10).其实本质就是取余嘛
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果得到的下标位置是null，那就创建一个新节点进行填充
        tab[i] = newNode(hash, key, value, null);
    // 如果得到的下标位置上已经有别的节点    
    else {
        // 指向和待存入对象equals的节点
        Node<K,V> e;
        // 保存指定下标的
        K k;
        // 如果指定下标有节点，并且第一个节点和要放入的key相同的话(地址相同或者equals相同)
        if (p.hash == hash &&
            // 再次确定key对象是否相同
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果要存入的key在哈希表已经存在，就让e指向这个hash后坐标的原节点
            e = p;
        
        // 如果指定的下标有节点并且是树节点的话，就是用树的方式去put
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 如果指定的下标是一条链表而不是一个节点
        else {
            // 遍历哈希表指定下标的链表，binCount记录的当前遍历的链表的那个节点
            for (int binCount = 0; ; ++binCount) {
                // 如果遍历到链表的最后一个节点
                if ((e = p.next) == null) {
                    // 将新节点接在它后面
                    p.next = newNode(hash, key, value, null);
                    // 如果binCount已经不小于TREEIFY_THRESHOLD - 1，即链表的长度已经达到8
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        // 根据条件把这个位置下的链表重构成红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果遍历到的当前的节点和要放入的key相同，就进行break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 处理集合中已经存在节点和要放入的key相同
        if (e != null) {
            // 获取旧value值
            V oldValue = e.value;
            // 如果oldValue是null或者是onlyIfAbsent为false，都会让新的value去覆盖原本的value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 记录一下，当前集合已经发生改变，版本+1
    ++modCount;
    // 如果添加元素后，size达到了阈值，就进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

特别说明，只要两个对象的hashCode()返回值相同，并且可以equals，那么就认为是相同的对象，对于内部支持类String来说，是重写过hashCode()和equals()的,返回值根据实际的字符串来返回的，所以会出现以下情况：

public static void main(String[] args){
    String str1 = new String("string");
    String str2 = new String("string");
    /* 
    	以上的代码共创建了三个对象;
    	两个处于堆中(使用new开辟的)，一个处于方法区的常量池中,"string"(由于字符串对象的唯一性);
    	即str1和str2虽然是两个地址不同的对象，但是由于String类重写过hashCode()和equals();
    	这两个方法都是通过实际保存的字符串来返回的，对于同一个字符串来说，返回的hashCode唯一，能equals
    	所以在HashMap中，使用以上两个引用无法都添加进去
    */
    HashMap<String,Object> map = new HashMap<>();
    map.put(str1,"str1");// 存进去了
    map.put(str2,"str2");// 存不进去，但是"str2"，覆盖了"str1"
    // 最终容器中为	HashMap{ < string, str2 > }
}

6、hash方法

获取hash值的方法：把对象的hashCode值向右移动16位，然后跟原来的hashCode进行异或；但是**在获取下标的时候，还要再和数组的最大下标进行与运算**。

// 用于返回指定对象key的hash值
static final int hash(Object key) {
    // 创建返回值变量
    int h;
    // 如果传入的对象是null，那么返回0，如果不是null，那么调用key的hashCode方法。
    // hash函数是这样:调用对象的hashCode()，返回将hashCode进行右移16位，然后跟原本hashCode进行异或运算
    // 异或运算也是二进制运算，在同一个位上如果相同，返回1;不同就返回0.如0001 ^ 1001 = 0111
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

8、resize方法

• reset方法，就是将作为哈希表的数组扩容两倍，然后通过对节点的hash和数组最大下标重新"与运算"来计算下标；

• 值得一提的是，SUN对于因为哈希冲突产生链表结构的处理：

  • /*
    	HashMap对于数组下标的计算是这样的:	hash & (array.length - 1)
    	数组扩容后，就是进行了array.length <<< 1操作，那么计算数组下标的时候，就可能比原来的多出一个1，举个例子:
    	原容量为:10000(十进制的16)，此时有一个节点{ hash:19(二进制为10011) }
    		扩容前下标为: 10011 & (10000 - 1) = 10011 & 01111 = 00011
    		
    	扩容后，容量为100000(十进制的32)，对于原来的节点{ hash:19(10011) }
    		扩容后下标为: 10011 & (100000 - 1) = 010011 & 11111 = 10011
    	结果比原来的多了一位，新下标 = 原下标 + 原数组长度
    	
    	那么SUN，对于这种情况的处理，是使用:hash & oldCap == 0?index:index + oldCapacity
    	由于扩容后就是让原数组的容量的二进制向左移动一位，所以新数组容量比原数组容量高出一位；
    	允许元素的下标超过原来的数组容量，即这个元素的下标二进制在原数组的最高位1处可以是1；
    	只要跟原数组容量进行与运算，即可判断链表的节点新下标是否在原数组的最高位1处为1
    */
    

• 树的部分单独讲

// 对当前HashMap底层的哈希表数组进行扩容
final Node<K,V>[] resize() {
    // 获取当前HashMap底层的哈希表数组
    Node<K,V>[] oldTab = this.table;
    // 获取哈希表数组的长度，如果数组是null，则为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 获取哈希表的阈值，数组扩容的元素个数临界值
    int oldThr = this.threshold;
    // newCap用于保存扩容后的容量
    int newCap, newThr = 0;
    // 如果原数组不是空的
    if (oldCap > 0) {
        // 判断容量是否最大了
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 如果容量最大，就不允许再进行扩容
            threshold = Integer.MAX_VALUE;
            // 返回原数组
            return oldTab;
        }
        // 如果容量还没有达到最大值。
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值也扩容为原来的2倍
            newThr = oldThr << 1; // double threshold
    }
    // 如果原哈希表的阈值大于0，走到这里说明集合使用自定义负载因子初始创建，这是首次放入元素
    else if (oldThr > 0) 
        // 新容量就等于阈值，阈值刚初始化时默认为16(DEFAULT_INITIAL_CAPACITY = 1 << 4)
        // 当然，如果有指定initialCap的话，那么阈值为不小于它的最小2的整除次幂
        newCap = oldThr;
    else {
        // 如果阈值和容量都没有的话，即使用无参构造创建的HashMap后首次加入元素
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新阈值是0的话
    if (newThr == 0) {
        // 通过默认的负载因子乘上新容量获取阈值
        float ft = (float)newCap * this.loadFactor;
        // 获取判断新容量是否超过了最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    } 
    this.threshold = newThr;
    
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建哈希表底层的新的数组结构，即扩容后的数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    this.table = newTab;
    // 如果原本的哈希表的底层数组不是空的
    if (oldTab != null) {
        // 遍历每一个数组下标
        for (int j = 0; j < oldCap; ++j) {
            // 用于指向当前遍历到的节点
            Node<K,V> e;
            // 如果当前拿到的节点不是空，说明有内容，下标在[0,size - 1]之间
            if ((e = oldTab[j]) != null) {
                // 把老数组的当前下标的位置置为null
                oldTab[j] = null;
                
                // 如果这个位置是单个节点
                if (e.next == null)
                    // 通过hash获取下标，然后把原数组的值，迁移到新数组下
                    newTab[e.hash & (newCap - 1)] = e;
                
                // 如果这个位置是树节点
                else if (e instanceof TreeNode)
                    // 对树进行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                
                // 如果这个位置是链表
                else {
                    /*
                    	SUN将处于数组"原位置"的链表和新下标为"原位置+原数组容量"的分开
                    	loHead、loTail分别指向原位置的链表的头和尾
                    	hiHead、hiTail分别指向下标为"原位置+原数组容量"的头和尾
                    	以下代码的思路是先把链表分别拼接好，然后再统一将头节点放入数组对应位置中
                    */
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    // 指向下一个要操作的节点
                    Node<K,V> next;
                    // 循环遍历链表的所有节点
                    do {
                        // 让next指向e（当前要操作的节点）的next
                        next = e.next;
                        // hash和原数组容量"&运算"为0情况，即链表是处于原位置，详情查看resize方法开头的讲解
                        if ((e.hash & oldCap) == 0) {
                            // 如果尾指针是null，说明刚开始拼接节点
                            if (loTail == null)
                                // 让头指针指针当前遍历到的节点
                                loHead = e;
                            // 如果尾指针不是null，说明已经拼接一部分
                            else
                                // 直接让当前遍历到的节点拼接到尾指针指向的节点的next即可
                                loTail.next = e;
                            // 让尾指针指向最新拼接的节点
                            loTail = e;
                        }
                        // 扩容后新下标为“原位置+原数组长度”，以下的处理跟上面的一致
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 如果尾指针不是null，说明有拼接在原位置的链表存在
                    if (loTail != null) {
                        // 把尾指针指向的next置为null
                        loTail.next = null;
                        // 在新数组的原位置上接入链表
                        newTab[j] = loHead;
                    }
                    // 如果尾指针不是null，说明有拼接在"原位置+原数组长度"的链表存在
                    if (hiTail != null) {
                        // 把尾指针指向的next置为null
                        hiTail.next = null;
                        // 在新数组的"原位置+原数组长度"下标上接入链表
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回新数组
    return newTab;
}

9、remove方法

// 指定key进行删除，并且返回被删除的键值对的value，key不存在返回null
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}


/** 
  *	@param hash 指定key的hash值
  * @param key 指定的key
  * @param value 指定的value
  * @param matchValue 匹配到key后是否要判断value是不是和传入的value一致才删除
  * @param movable 删除后是否移动节点
  */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    // 用于指向当前HashMap的底层数组结构
    Node<K,V>[] tab; 
    // 用于指向要被删除的节点对象或节点对象所在的链表/树
    Node<K,V> p; 
    // n用于保存当前的集合底层数组的长度，index用于保存要删除节点所在的下标
    int n, index;
    // 获取数组，并且判断是否有这个Node
    if ((tab = this.table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        // node用来确切的指向要被删除的节点，e指向node.next
        Node<K,V> node = null, e;
        // 要被删除的节点的key
        K k; 
        // 要被删除的节点的value
        V v;
        // 被被删除的节点是直接放入数组中的(可能是树的根节点或链表的头节点)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 被删除的节点拥有线性结构(树、链表)
        else if ((e = p.next) != null) {
            // 如果是树
            if (p instanceof TreeNode)
                // 获取要删除的树节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 如果要删除的节点位于链表中
            else {
                do {
                    // 判断的当前的节点是否为被删除节点
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 判断执行删除操作，如果node不是null，不需要matchValue或者value是匹配的，就执行删除
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果是树节点
            if (node instanceof TreeNode)
                // 单独删除树节点
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // node指向确切删除节点，p指向要删除的节点或者链表的头节点/树节点
            // 如果node == p，说明被删节点为单节点或者链表的头节点
            else if (node == p)
                // 删除
                tab[index] = node.next;
            // 被删除节点是链表中的父节点
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    // 查找不到节点，返回null
    return null;
}

10、get方法

// 通过key获取value
public V get(Object key) {
    Node<K,V> e;
    // 如果获取的到就返回value，获取不到返回null
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * get方法实现逻辑
 * @param hash key的哈希值
 * @param key key
 */
final Node<K,V> getNode(int hash, Object key) {
    // 指向当前的哈希表数组
    Node<K,V>[] tab; 
    // 指向
    Node<K,V> first, e; 
    // 保存哈希表数组的长度
    int n;
    // 保存key
    K k;
    // 判断集合是否为空，如果不为空，元素是否存在
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 查看指定的下标位置是否有节点，并查看第一个节点是否为要查询的目标节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 如果是的话，然后这个节点
            return first;
        // 走到这里说明首个节点不是目标节点
        // 判断该下标位置的节点是否处于线性结构中(链表或树)
        if ((e = first.next) != null) {
             // 如果是树
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 如果是链表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 查询不到返回null
    return null;
}