HashMap学习笔记

作者: cpyl | 来源:发表于2019-02-27 00:41 被阅读0次

一、HashMap解析

HashMap类继承体系

1.1 HashMap的数据结构

image.png

可以看出HashMap是数组+链表+红黑树构成。我们把数组中的每一个节点叫做桶。向哈希表中插入元素时，首先会根据key建算出对应的hash值，将hash值和桶的个数进行取余操作（hash&（n-1））确定元素在桶中的位置。当不同的元素计算的相同的hash值就认为发生了碰撞。这时，就是比较key是否一致，相同替换value，不同就在这个元素的后面挂上去，形成了链表。当链表长度超过8就会自动转成红黑树。

1.2 JDK8中的HashMap

在 HashMap 中定义了几个常量:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

依次解释以上常量:

DEFAULT_INITIAL_CAPACITY: 初始容量，也就是默认会创建 16 个桶，桶的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
MAXIMUM_CAPACITY: 哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。
DEFAULT_LOAD_FACTOR: 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
TREEIFY_THRESHOLD: 如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。
MIN_TREEIFY_CAPACITY: 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。

成员属性：

image.png

其中Node是HashMap的节点类型。既是HashMap底层数组的组成元素，又是每个单向链表的组成元素

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

构造方法：

image.png

判断大小是否合理，如果超过，赋最大值，调用tableSizeFor（initialCapacity),返回一个最小的大于输入参数的2的整数次幂的数

threshold这个成员变量是阈值，决定了是否要将散列表再散列。它的值应该是：capacity * load factor才对的。
其实这里仅仅是一个初始化，当创建哈希表的时候，它会重新赋值的

put方法

     public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

根据key计算出hash值，调用putVal方法

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

扰动函数：根据键计算出hashCode，将hashCode由于16位与自己做异或操作。目的是将高位和低位结合后，使hashCode上1分布更均匀，增加了随机性，减少了碰撞发生的可能。（默认的初始容量是16，要放到散列表中，就是0-15的位置上。也就是tab[i = (n - 1) & hash]。可以发现的是：在做&运算的时候，仅仅是后4位有效~那如果我们key的哈希值高位变化很大，低位变化很小。直接拿过去做&运算，这就会导致计算出来的Hash值相同的很多）

   /**
 * Map.put和其他相关方法的实现需要的方法
 * 
 * @param hash 指定参数key的哈希值
 * @param key 指定参数key
 * @param value 指定参数value
 * @param onlyIfAbsent 如果为true，即使指定参数key在map中已经存在，也不会替换value
 * @param evict 如果为false，数组table在创建模式中
 * @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的value就是null。
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果哈希表为空，调用resize()创建一个哈希表，并用变量n记录哈希表长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//调用resize方法，每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置
    //如果指定参数hash在表中没有对应的桶，即为没有碰撞
    if ((p = tab[i = (n - 1) & hash]) == null)
        //直接将键值对插入到map中即可
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //如果碰撞了，且桶中的第一个节点就匹配了
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //将桶中的第一个节点记录起来
            e = p;
        //如果桶中的第一个节点没有匹配上，且桶内为红黑树结构，则调用红黑树对应的方法插入键值对
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //不是红黑树结构，那么就肯定是链式结构
        else {
            //遍历链式结构
            for (int binCount = 0; ; ++binCount) {
                //如果到了链表尾部
                if ((e = p.next) == null) {
                    //在链表尾部插入键值对
                    p.next = newNode(hash, key, value, null);
                    //如果链的长度大于TREEIFY_THRESHOLD这个临界值，则把链变为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    //跳出循环
                    break;
                }
                //如果找到了重复的key，判断链表中结点的key值与插入的元素的key值是否相等，如果相等，跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        //如果key映射的节点不为null
        if (e != null) { // existing mapping for key
            //记录节点的vlaue
            V oldValue = e.value;
            //如果onlyIfAbsent为false，或者oldValue为null
            if (!onlyIfAbsent || oldValue == null)
                //替换value
                e.value = value;
            //访问后回调
            afterNodeAccess(e);
            //返回节点的旧值
            return oldValue;
        }
    }
    //结构型修改次数+1
    ++modCount;
    //判断是否需要扩容
    if (++size > threshold)
        resize();
    //插入后回调
    afterNodeInsertion(evict);
    return null;
}

putVal方法可以分为下面的几个步骤：

如果哈希表为空（当我们放入第一个元素时，如果底层数组还是null），调用resize()创建一初始容量为16的Node数组，但逻辑长度size还是0，类似于ArrayList的初始化。
如果指定参数hash在表中没有对应的桶，即为没有碰撞，直接将键值对插入到哈希表中即可。
如果有碰撞，遍历桶，找到key映射的节点

桶中的第一个节点就匹配了，将桶中的第一个节点记录起来。
如果桶中的第一个节点没有匹配，且桶中结构为红黑树，则调用红黑树对应的方法插入键值对。
如果不是红黑树，那么就肯定是链表。遍历链表，如果找到了key映射的节点，就记录这个节点，退出循环。如果没有找到，在链表尾部插入节点。插入后，如果链的长度大于TREEIFY_THRESHOLD这个临界值，则使用treeifyBin方法把链表转为红黑树。
如果找到了key映射的节点，且节点不为null
记录节点的vlaue。

如果参数onlyIfAbsent为false，或者oldValue为null，替换value，否则不替换。
返回记录下来的节点的value。
如果没有找到key映射的节点（2、3步中讲了，这种情况会插入到hashMap中），插入节点后size会加1，这时要检查size是否大于临界值threshold，如果大于会使用resize方法进行扩容。

get方法

 public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

从源码中可以看到，get(E e)可以分为三个步骤：

通过hash(Object key)方法计算key的哈希值hash。
通过getNode( int hash, Object key)方法获取node。
如果node为null，返回null，否则返回node.value。

    final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果哈希表不为空，而且key对应的桶上不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //如果桶中的第一个节点就和指定参数hash和key匹配上了
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            //返回桶中的第一个节点
            return first;
        //如果桶中的第一个节点没有匹配上，而且有后续节点
        if ((e = first.next) != null) {
            //如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果当前的桶不采用红黑树，即桶中节点结构为链式结构
            do {
                //遍历链表，直到key匹配
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //如果哈希表为空，或者没有找到节点，返回null
    return null;
}

getNode方法可分为以下几个步骤：

如果哈希表为空，或key对应的桶为空，返回null
如果桶中的第一个节点就和指定参数hash和key匹配上了，返回这个节点。
如果桶中的第一个节点没有匹配上，而且有后续节点

如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配

找到节点返回节点，否则返回null。

remove（Object key）

    /**
 * 删除hashMap中key映射的node
 *
 * @param  key 参数key
 * @return 如果没有映射到node，返回null，否则返回对应的value。
 */
public V remove(Object key) {
    Node<K,V> e;
    //根据key来删除node。removeNode方法的具体实现在下面
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

image.png

二、HashMap与Hashtable

从存储结构和实现来讲基本上都是相同的。它和HashMap的最大的不同是它是线程安全的，另外它不允许key和value为null。Hashtable是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换

image.png

三、小结

在JDK8中，HashMap是数组+链表+红黑树实现的
在散列表中有装载因子这么一个属性，当装载因子*初始容量小于散列表元素时，该散列表会再散列，扩容2倍！
HashMap并不是直接拿key的哈希值来用的，它会将key的哈希值的高16位进行异或操作，使得我们将元素放入哈希表的时候增加了一定的随机性
值得注意的是：并不是桶子上有8位元素的时候它就能变成红黑树，它得同时满足我们的散列表容量大于64才行的

HashMap学习笔记

一、HashMap解析

1.1 HashMap的数据结构

1.2 JDK8中的HashMap

image.png

二、HashMap与Hashtable

image.png

三、小结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读