在java开发中,最常用的集合类莫过于ArrayList和HashMap,hashmap作为map的派生基类,以hash码为key值存储,大大提高了存储和检索效率,在数据kv映射下有着广泛的应用场景。
2. 使用示例Mapmap = 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) { Node3.2 Hash计算及hash碰撞[] 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; }
对象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更注重于针对必要的代码加锁来达到性能的提升。
如果看过threadlocal内存泄漏风险的小伙伴就知道,threadlocal内部维护的就是一个map,当数据量增大而map没有及时清理,就有造成内存溢出的风险。
map的内存泄漏没有很好的解决方法,只能是在上层代码维护内map的数据量,防止过度扩张。
在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的时候可能会获取到被其他线程删除了的脏数据,切记切记!!!
同学们还可以关注公众号【暴走的怪兽君】
可以获取更多资源内容
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)