浅谈java中的HashMap及那些踩过的坑

浅谈java中的HashMap及那些踩过的坑 1. 简述

在java开发中，最常用的集合类莫过于ArrayList和HashMap,hashmap作为map的派生基类，以hash码为key值存储，大大提高了存储和检索效率，在数据kv映射下有着广泛的应用场景。

2. 使用示例

Map map = new HashMap<>();
map.put("a","hello");
System.out.println(map);

输出：{a=hello}

示例中key和value都使用了string类型，实际情况下value大多是其他对象或者集合，key也可能会变为某个object。

3. HashMap分析 3.1 存储

在1.7以前，HashMap使用了链表数组进行数据存储，当put一个方法的时候，通过计算key的hash码获取数组索引号（桶位索引）进行链表挂载存储。

下面是简要描述1.7put的过程，仅链表数组计算存储部分

    int hash=key==null?0:key.hashCode()>>>16;
    Node node=new Node(key,value);
    // hash未碰撞
    if(nodeTab[hash]==null){
      nodeTab[hash]=node;
      return;
    }
    // hash碰撞
    Node pre=nodeTab[hash];
    // 若key相同，则直接覆盖
    if(Objects.equals(pre.key,key)){
      nodeTab[hash]=node;
      return;
    }
    // 遍历链表节点，检查是否有相同key
    while(true){
      if(pre.next==null){
        pre.next=node;
        return;
      }
      if(Objects.equals(pre.next.key,key)){
        node=pre.next.next;
        pre.next=node;
        return;
      }
      pre=pre.next;
    }

从1.8开始。HashMap开始增加了红黑树，当链表长度超过定值（8）之后，存储结构会从链表数组改为红黑树，用于加快检索
红黑树基于平衡树，但不绝对追求平衡，这样就减去了平衡树部分旋转平衡的时间

下面是jdk1.8在put方法时的源码

// hash码计算逻辑与1.7一致
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; // 扩容数组大小，结果为当前容量*2
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null); // 创建node
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; // key相同，直接覆盖
            else if (p instanceof TreeNode)
            	// 红黑树直接加入
                e = ((TreeNode)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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

3.2 Hash计算及hash碰撞

对象hash码的计算默认调用native方法，当然可以重写方法达到自己的hash定制。
下面是map中hash码计算源码

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

关于hash碰撞，hash码计算出来有重复的可能性，在map的hash计算中更是对高16位进行了异或，更加增加了重复率，所以map中针对hash计算一致的key进行了再次equals比较和链表存储，确保了hash碰撞的key值重复的准确性。

4. 容易踩到的坑 4.1 几种线程安全的map

在1.7之前的jdk里，线程安全的map主要有hashtable和通过Collections.synchronizedMap包装出来的SynchronizedMap。
首先说说hashtable，他的加锁方式比较粗暴重量级，加锁力度是方法级，也就是他在涉及数据的几个方法都添加了synchronized上锁达到互斥阻塞的效果，但这种性能也是比较差的。
而SynchronizedMap这是通过方法内加锁形成互斥，但通过分析源码看到，SynchronizedMap的同步块代码量基本等同于方发锁。

在1.8开始，提供了ConcurrentHashMap作为一个轻量级的线程安全map，其实简单一点理解就是相较于SynchronizedMap的全代码块加锁，ConcurrentHashMap更注重于针对必要的代码加锁来达到性能的提升。

4.2 map的内存泄漏

如果看过threadlocal内存泄漏风险的小伙伴就知道，threadlocal内部维护的就是一个map，当数据量增大而map没有及时清理，就有造成内存溢出的风险。
map的内存泄漏没有很好的解决方法，只能是在上层代码维护内map的数据量，防止过度扩张。

4.3 ConcurrentHashMap中的坑

在ConcurrentHashMap中，主要针对了数据修改的代码块加锁，想想我们常用的几个map方法，put，get，remove，下面贴出他们的部分源码
put方法（put调用putVal）

final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node p;
                            binCount = 2;
                            if ((p = ((TreeBin)f).putTreeval(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

get方法

    public V get(Object key) {
        Node[] tab; Node e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

remove方法（remove调用replaceNode）

    final V replaceNode(Object key, V value, Object cv) {
        int hash = spread(key.hashCode());
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
                break;
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                boolean validated = false;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            validated = true;
                            for (Node e = f, pred = null;;) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    V ev = e.val;
                                    if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                        oldVal = ev;
                                        if (value != null)
                                            e.val = value;
                                        else if (pred != null)
                                            pred.next = e.next;
                                        else
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
                        else if (f instanceof TreeBin) {
                            validated = true;
                            TreeBin t = (TreeBin)f;
                            TreeNode r, p;
                            if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                                V pv = p.val;
                                if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) {
                                    oldVal = pv;
                                    if (value != null)
                                        p.val = value;
                                    else if (t.removeTreeNode(p))
                                        setTabAt(tab, i, untreeify(t.first));
                                }
                            }
                        }
                    }
                }
                if (validated) {
                    if (oldVal != null) {
                        if (value == null)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }

因为没有删减代码，所以代码较长
细心的小伙伴发现了吗，在get方法里，因为不涉及修改map中维护的tabs，所以没有加锁！！！
这样就会造成什么场景呢，在get的时候可能会获取到被其他线程删除了的脏数据，切记切记！！！

最后

同学们还可以关注公众号【暴走的怪兽君】
可以获取更多资源内容