Shawn's Blog

蒸汽兔

---

深入理解HashMap

2020-04-05 字数：1461 字 阅读时长：约 8 分钟 阅读次

• jdk1.7与1.8区别
  • Base1.7
  • Base1.8
• 扩容
• 疑问

jdk1.7与1.8区别

Base1.7

使用数据结构是数组加链表，数据节点是使用的entry(内部类)节点；

/** 
 * Entry类实现了Map.Entry接口
 * 即 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
**/  
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;  // 键
    V value;  // 值
    Entry<K,V> next; // 指向下一个节点 ，也是一个Entry对象，从而形成解决hash冲突的单链表
    int hash;  // hash值
  
    /** 
     * 构造方法，创建一个Entry 
     * 参数：哈希值h，键值k，值v、下一个节点n 
     */  
    Entry(int h, K k, V v, Entry<K,V> n) {  
        value = v;  
        next = n;  
        key = k;  
        hash = h;  
    }  
  
    // 返回 与 此项 对应的键
    public final K getKey() {  
        return key;  
    }  

    // 返回 与 此项 对应的值
    public final V getValue() {  
        return value;  
    }  
  
    public final V setValue(V newValue) {  
        V oldValue = value;  
        value = newValue;  
        return oldValue;  
    }  
    
   /** 
     * equals（）
     * 作用：判断2个Entry是否相等，必须key和value都相等，才返回true  
     */ 
      public final boolean equals(Object o) {  
        if (!(o instanceof Map.Entry))  
            return false;  
        Map.Entry e = (Map.Entry)o;  
        Object k1 = getKey();  
        Object k2 = e.getKey();  
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
            Object v1 = getValue();  
            Object v2 = e.getValue();  
            if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                return true;  
        }  
        return false;  
    }  
    
    /** 
     * hashCode（） 
     */ 
    public final int hashCode() { 
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
    }  
  
    public final String toString() {  
        return getKey() + "=" + getValue();  
    }  
  
    /** 
     * 当向HashMap中添加元素时，即调用put(k,v)时， 
     * 对已经在HashMap中k位置进行v的覆盖时，会调用此方法 
     * 此处没做任何处理 
     */  
    void recordAccess(HashMap<K,V> m) {  
    }  
  
    /** 
     * 当从HashMap中删除了一个Entry时，会调用该函数 
     * 此处没做任何处理 
     */  
    void recordRemoval(HashMap<K,V> m) {  
    } 

}

数据插入使用头插法：

​ 缺点： 在扩容resize时会调用transfer方法，在transfer方法中把存在的entry节点做了一个rehash操作，在这个过程当中可能会再多线程情况下造成一个链表的循环，则可能会在下一次get的时候造成一个死循环；也有另外一个情况就是他对方法没有加锁，所以它也有可能在多个并发情况下，数据不能保证是安全的，也就是我put进去的值，取出来还是我put进去的那个值；

1.7 transfer()方法
void transfer(Entry[] newTable) {
    Entry[] src = table; //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                e.next = newTable[i]; //标记[1]
                newTable[i] = e; //将元素放在数组上
                e = next; //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

transfer方法由于使用的是单链表的头插法方式，同一位置上新元素总会放在链表的头部位置；这样先放在一个索引上的元素终会被放在entry链的尾部。在数组中同一条entry链上的元素，在重新计算索引位置后，有可能会放在了新数组的不同位置上

Base1.8

使用的数据结构是数组加链表加红黑树，数据节点改使用为Node节点，也对put的过程做了一些优化;

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // hash值
        final K key; // 键
        V value; // 值
        Node<K,V> next; // 指向下一个节点

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

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

优化过程：

​ 对数据结构做了进一步的优化，引入了红黑树。而当判断当前链表长度>TREEIFY_THRESHOLD 时（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

扩容

​ 首先需要了解capacity参数，在初始化hashmap的时候，如果我们没有设置capacity就会默认设置为默认值16来作为我们这个hashmap的容量，负载因子loadFactor为0.75，会根据这两个参数计算出一个threshold（阈值），在put时会判断当前这个size是不是大于这个阈值，如果大于时，他就会新创建一个2倍容量大小的一个数据，对旧的entry节点进行rehash的操作，将旧entry节点转移到新容器的这么一个resize的过程；

resize()源码解释：

void resize(int newCapacity) { //传入新的容量
    Entry[] oldTable = table; //引用扩容前的Entry数组
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
    	threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
    	return;
	}
    Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
    transfer(newTable); //！！将数据转移到新的Entry数组里
    table = newTable; //HashMap的table属性引用新的Entry数组
    threshold = (int)(newCapacity * loadFactor);//修改阈值
}
这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
    Entry[] src = table; //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                e.next = newTable[i]; //标记[1]
                newTable[i] = e; //将元素放在数组上
                e = next; //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

疑问

观察源码发现HashSet底层是new一个hashmap所实现的，那为什么还要保留HashSet呢

上一页 下一页

---