Java集合框架(三):Map体系与ConcurrentHashMap

简介: 本文深入解析Java中Map接口体系及其实现类,包括HashMap、ConcurrentHashMap等的工作原理与线程安全机制。内容涵盖哈希冲突解决、扩容策略、并发优化,以及不同Map实现的适用场景,助你掌握高并发编程核心技巧。

💡 摘要:你是否曾在多线程环境下遭遇HashMap的无限循环?是否对ConcurrentHashMap的高并发性能感到好奇?是否疑惑为什么要有这么多Map实现类?

别担心,Map作为键值对存储的核心接口,其线程安全问题和并发优化是Java高级编程的必考知识点。

本文将带你从Map接口体系讲起,对比HashMap、Hashtable、LinkedHashMap的特性差异。然后深入HashMap的实现原理,包括哈希冲突解决、树化优化和扩容机制。

接着重点剖析ConcurrentHashMap的并发实现,从分段锁到CAS优化,让你理解其高性能的奥秘。从内存模型到线程安全,从性能对比到适用场景,让你全面掌握Map体系的精髓。文末附实战案例和面试高频问题,助你应对高并发挑战。

一、Map接口体系:键值对的王国

1. Map核心特性与方法

Map与Collection的区别

  • Map存储键值对(Key-Value),Key不可重复
  • Collection存储单列元素

核心方法

java

// 基本操作

V put(K key, V value);           // 添加键值对

V get(Object key);               // 根据key获取value

V remove(Object key);            // 删除key对应的键值对

boolean containsKey(Object key); // 是否包含key

boolean containsValue(Object value); // 是否包含value


// 视图操作

Set<K> keySet();                 // 返回所有key的Set视图

Collection<V> values();          // 返回所有value的Collection视图  

Set<Map.Entry<K, V>> entrySet(); // 返回所有键值对的Set视图


// 批量操作

void putAll(Map<? extends K, ? extends V> m); // 添加所有键值对

void clear();                      // 清空所有映射

2. Map体系结构

text

Map接口

├── HashMap:基于哈希表,无序,线程不安全

│     ├── LinkedHashMap:保持插入顺序/访问顺序

│     └── ConcurrentHashMap:线程安全的高并发版本

├── Hashtable:线程安全的哈希表(已过时)

│     └── Properties:配置文件处理

├── TreeMap:基于红黑树,按键排序

└── WeakHashMap:弱键映射,适合缓存场景

二、HashMap:哈希表的经典实现

1. 内部结构与初始化

JDK 8的优化:数组 + 链表 + 红黑树

java

public class HashMap<K,V> extends AbstractMap<K,V>

   implements Map<K,V>, Cloneable, Serializable {

   

   // 默认初始容量:16

   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

   

   // 默认加载因子: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;

   

   // 存储数据的Node数组

   transient Node<K,V>[] table;

   

   // 节点定义

   static class Node<K,V> implements Map.Entry<K,V> {

       final int hash;

       final K key;

       V value;

       Node<K,V> next; // 链表下一个节点

   }

}

2. 哈希计算与索引定位

哈希扰动函数:减少哈希冲突

java

static final int hash(Object key) {

   int h;

   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}


// 计算数组索引

int index = (table.length - 1) & hash(key);

3. put方法详细流程

java

public V put(K key, V value) {

   return putVal(hash(key), key, value, false, true);

}


final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

   Node<K,V>[] tab; Node<K,V> p; int n, i;

   

   // 1. 表为空或长度为0,进行扩容

   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);

   else {

       // 3. 发生哈希冲突

       Node<K,V> e; K k;

       

       // 3.1 key相同,直接覆盖

       if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

           e = p;

       

       // 3.2 如果是树节点,调用红黑树的插入方法

       else if (p instanceof TreeNode)

           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

       

       // 3.3 链表遍历

       else {

           for (int binCount = 0; ; ++binCount) {

               if ((e = p.next) == null) {

                   p.next = newNode(hash, key, value, null);

                   // 链表长度达到阈值,转换为红黑树

                   if (binCount >= TREEIFY_THRESHOLD - 1)

                       treeifyBin(tab, hash);

                   break;

               }

               if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

                   break;

               p = e;

           }

       }

       

       // 4. 存在相同的key,替换value

       if (e != null) {

           V oldValue = e.value;

           if (!onlyIfAbsent || oldValue == null)

               e.value = value;

           afterNodeAccess(e);

           return oldValue;

       }

   }

   

   // 5. 修改计数器增加,检查是否需要扩容

   ++modCount;

   if (++size > threshold)

       resize();

   afterNodeInsertion(evict);

   return null;

}

4. 扩容机制

java

final Node<K,V>[] resize() {

   Node<K,V>[] oldTab = table;

   int oldCap = (oldTab == null) ? 0 : oldTab.length;

   int oldThr = threshold;

   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)

           newThr = oldThr << 1; // 双倍扩容

   }

   

   // 创建新数组,重新哈希

   Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

   table = newTab;

   

   // 将旧数组元素重新分配到新数组

   if (oldTab != null) {

       for (int j = 0; j < oldCap; ++j) {

           Node<K,V> e;

           if ((e = oldTab[j]) != null) {

               oldTab[j] = null;

               if (e.next == null)

                   newTab[e.hash & (newCap - 1)] = e;

               else if (e instanceof TreeNode)

                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

               else {

                   // 链表优化重哈希

                   Node<K,V> loHead = null, loTail = null;

                   Node<K,V> hiHead = null, hiTail = null;

                   Node<K,V> next;

                   do {

                       next = e.next;

                       if ((e.hash & oldCap) == 0) {

                           if (loTail == null)

                               loHead = e;

                           else

                               loTail.next = e;

                           loTail = e;

                       }

                       else {

                           if (hiTail == null)

                               hiHead = e;

                           else

                               hiTail.next = e;

                           hiTail = e;

                       }

                   } while ((e = next) != null);

                   

                   if (loTail != null) {

                       loTail.next = null;

                       newTab[j] = loHead;

                   }

                   if (hiTail != null) {

                       hiTail.next = null;

                       newTab[j + oldCap] = hiHead;

                   }

               }

           }

       }

   }

   return newTab;

}

三、ConcurrentHashMap:高并发的最佳实践

1. JDK 7的分段锁实现

分段锁机制

java

// JDK 7的实现:Segment数组 + HashEntry数组

static final class Segment<K,V> extends ReentrantLock {

   transient volatile HashEntry<K,V>[] table;

}


public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>

   implements ConcurrentMap<K,V>, Serializable {

   

   final Segment<K,V>[] segments; // 分段锁数组

   

   // 默认并发级别:16

   public ConcurrentHashMap() {

       this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);

   }

}

2. JDK 8的CAS优化实现

抛弃分段锁,采用CAS + synchronized

java

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>

   implements ConcurrentMap<K,V>, Serializable {

   

   // 使用volatile修饰的Node数组

   transient volatile Node<K,V>[] table;

   

   //  sizeCtl:控制标识符

   private transient volatile int sizeCtl;

   

   // 节点定义(与HashMap类似,但value和next是volatile的)

   static class Node<K,V> implements Map.Entry<K,V> {

       final int hash;

       final K key;

       volatile V val;        // volatile保证可见性

       volatile Node<K,V> next; // volatile保证可见性

   }

}

3. put方法的并发实现

java

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<K,V>[] tab = table;;) {

       Node<K,V> f; int n, i, fh;

       

       // 1. 表为空,初始化

       if (tab == null || (n = tab.length) == 0)

           tab = initTable();

       

       // 2. 计算索引位置,如果该位置为空,CAS插入新节点

       else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {

           if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))

               break; // CAS成功,插入完成

       }

       

       // 3. 如果正在扩容,帮助扩容

       else if ((fh = f.hash) == MOVED)

           tab = helpTransfer(tab, f);

       

       // 4. 发生哈希冲突

       else {

           V oldVal = null;

           synchronized (f) { // 对桶的头节点加锁

               if (tabAt(tab, i) == f) {

                   if (fh >= 0) { // 链表节点

                       binCount = 1;

                       for (Node<K,V> 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<K,V> pred = e;

                           if ((e = e.next) == null) {

                               pred.next = new Node<K,V>(hash, key, value, null);

                               break;

                           }

                       }

                   }

                   else if (f instanceof TreeBin) { // 树节点

                       Node<K,V> p;

                       binCount = 2;

                       if ((p = ((TreeBin<K,V>)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;

           }

       }

   }

   

   // 5. 更新size,检查是否需要扩容

   addCount(1L, binCount);

   return null;

}

4. 并发安全特性

CAS操作

java

// 原子操作:比较并交换

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {

   return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);

}


// 原子获取

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {

   return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);

}


// 原子设置

static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {

   U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);

}

四、其他重要Map实现

1. LinkedHashMap:保持插入顺序

java

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {

   

   // 双向链表节点

   static class Entry<K,V> extends HashMap.Node<K,V> {

       Entry<K,V> before, after; // 前后指针

   }

   

   // 访问顺序模式

   final boolean accessOrder;

   

   // LRU缓存实现

   protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {

       return size() > MAX_ENTRIES;

   }

}

2. TreeMap:红黑树排序

java

public class TreeMap<K,V> extends AbstractMap<K,V>

   implements NavigableMap<K,V>, Cloneable, java.io.Serializable {

   

   // 红黑树节点

   static final class Entry<K,V> implements Map.Entry<K,V> {

       K key;

       V value;

       Entry<K,V> left;    // 左孩子

       Entry<K,V> right;   // 右孩子

       Entry<K,V> parent;  // 父节点

       boolean color = BLACK; // 颜色

   }

   

   // 比较器

   private final Comparator<? super K> comparator;

}

3. Hashtable vs ConcurrentHashMap

特性 Hashtable ConcurrentHashMap
锁机制 全表锁 分段锁(JKD7)/CAS+synchronized(JDK8)
并发度 1 默认16(JDK7)/更高(JDK8)
null值 不允许 不允许
迭代器 强一致性 弱一致性
性能

五、实战应用与最佳实践

1. Map选择指南

场景 推荐实现 理由
单线程缓存 HashMap 性能最好
保持插入顺序 LinkedHashMap 维护插入顺序
需要排序 TreeMap 红黑树排序
低并发线程安全 Collections.synchronizedMap 简单包装
高并发场景 ConcurrentHashMap 最佳并发性能
配置读取 Properties 专为配置设计

2. 并发实战示例

java

// 线程安全的缓存实现

public class CacheManager {

   private final ConcurrentHashMap<String, Object> cache = new ConcurrentHashMap<>();

   private final ScheduledExecutorService cleaner = Executors.newScheduledThreadPool(1);

   

   public CacheManager() {

       // 定期清理过期缓存

       cleaner.scheduleAtFixedRate(this::cleanExpired, 1, 1, TimeUnit.HOURS);

   }

   

   public void put(String key, Object value, long ttl) {

       CacheEntry entry = new CacheEntry(value, System.currentTimeMillis() + ttl);

       cache.put(key, entry);

   }

   

   public Object get(String key) {

       CacheEntry entry = (CacheEntry) cache.get(key);

       if (entry != null && entry.isExpired()) {

           cache.remove(key);

           return null;

       }

       return entry != null ? entry.value : null;

   }

   

   private void cleanExpired() {

       cache.entrySet().removeIf(entry -> {

           CacheEntry cacheEntry = (CacheEntry) entry.getValue();

           return cacheEntry.isExpired();

       });

   }

   

   private static class CacheEntry {

       Object value;

       long expireTime;

       

       CacheEntry(Object value, long expireTime) {

           this.value = value;

           this.expireTime = expireTime;

       }

       

       boolean isExpired() {

           return System.currentTimeMillis() > expireTime;

       }

   }

}

六、总结:Map的精髓

  1. 理解哈希机制:hashCode()、equals()、哈希冲突解决
  2. 掌握并发原理:synchronized、CAS、volatile的应用
  3. 根据场景选择:单线程用HashMap,高并发用ConcurrentHashMap
  4. 注意线程安全:不要在并发环境下使用非线程安全集合
  5. 善用特殊Map:排序用TreeMap,顺序用LinkedHashMap

🚀 深入理解Map体系特别是ConcurrentHashMap的实现原理,是Java高级开发的必备技能。

七、面试高频问题

❓1. HashMap和Hashtable的区别?

  • 线程安全:HashMap非线程安全,Hashtable线程安全
  • null值:HashMap允许null键值,Hashtable不允许
  • 性能:HashMap性能更好
  • 迭代器:HashMap是fail-fast,Hashtable不是

❓2. ConcurrentHashMap如何保证线程安全?

  • JDK7:分段锁机制,每个Segment独立加锁
  • JDK8:CAS + synchronized,锁粒度更细

❓3. HashMap的扩容机制是怎样的?

:当元素数量超过容量×加载因子时,创建新数组(2倍大小),重新哈希所有元素。JDK8优化了重新哈希的过程。

❓4. 为什么HashMap链表长度超过8要转为红黑树?

:根据泊松分布,链表长度达到8的概率极低(0.00000006),转为红黑树可以保证最坏情况下的性能。

❓5. ConcurrentHashMap的size()方法如何实现?

:JDK8中使用CounterCell数组和baseCount来统计大小,通过分段计数来减少竞争。

相关文章
|
15天前
|
Java 大数据 API
Java Stream API:现代集合处理与函数式编程
Java Stream API:现代集合处理与函数式编程
176 100
|
15天前
|
Java API 数据处理
Java Stream API:现代集合处理新方式
Java Stream API:现代集合处理新方式
184 101
|
19天前
|
人工智能 Java 开发者
阿里出手!Java 开发者狂喜!开源 AI Agent 框架 JManus 来了,初次见面就心动~
JManus是阿里开源的Java版OpenManus,基于Spring AI Alibaba框架,助力Java开发者便捷应用AI技术。支持多Agent框架、网页配置、MCP协议及PLAN-ACT模式,可集成多模型,适配阿里云百炼平台与本地ollama。提供Docker与源码部署方式,具备无限上下文处理能力,适用于复杂AI场景。当前仍在完善模型配置等功能,欢迎参与开源共建。
593 58
阿里出手!Java 开发者狂喜!开源 AI Agent 框架 JManus 来了,初次见面就心动~
|
28天前
|
算法 Java
50道java集合面试题
50道 java 集合面试题
|
19天前
|
存储 Java Go
对比Java学习Go——函数、集合和OOP
Go语言的函数支持声明与调用,具备多返回值、命名返回值等特性,结合`func`关键字与类型后置语法,使函数定义简洁直观。函数可作为一等公民传递、赋值或作为参数,支持匿名函数与闭包。Go通过组合与接口实现面向对象编程,结构体定义数据,方法定义行为,接口实现多态,体现了Go语言的简洁与高效设计。
|
2月前
|
存储 缓存 安全
Java集合框架(二):Set接口与哈希表原理
本文深入解析Java中Set集合的工作原理及其实现机制,涵盖HashSet、LinkedHashSet和TreeSet三大实现类。从Set接口的特性出发,对比List理解去重机制,并详解哈希表原理、hashCode与equals方法的作用。进一步剖析HashSet的底层HashMap实现、LinkedHashSet的双向链表维护顺序特性,以及TreeSet基于红黑树的排序功能。文章还包含性能对比、自定义对象去重、集合运算实战和线程安全方案,帮助读者全面掌握Set的应用与选择策略。
163 23
|
1月前
|
SQL Java 数据库连接
区分iBatis与MyBatis:两个Java数据库框架的比较
总结起来:虽然从技术角度看,iBATIS已经停止更新但仍然可用;然而考虑到长期项目健康度及未来可能需求变化情况下MYBATISS无疑会是一个更佳选择因其具备良好生命周期管理机制同时也因为社区力量背书确保问题修复新特征添加速度快捷有效.
80 12
|
2月前
|
安全 Java 开发者
Java集合框架:详解Deque接口的栈操作方法全集
理解和掌握这些方法对于实现像浏览器后退功能这样的栈操作来说至关重要,它们能够帮助开发者编写既高效又稳定的应用程序。此外,在多线程环境中想保证线程安全,可以考虑使用ConcurrentLinkedDeque,它是Deque的线程安全版本,尽管它并未直接实现栈操作的方法,但是Deque的接口方法可以相对应地使用。
128 12
|
2月前
|
存储 NoSQL Java
Java Stream API:集合操作与并行处理
Stream API 是 Java 8 提供的集合处理工具,通过声明式编程简化数据操作。它支持链式调用、延迟执行和并行处理,能够高效实现过滤、转换、聚合等操作,提升代码可读性和性能。
|
2月前
|
存储 安全 Java
Java集合框架(一):List接口及其实现类剖析
本文深入解析Java中List集合的实现原理,涵盖ArrayList的动态数组机制、LinkedList的链表结构、Vector与Stack的线程安全性及其不推荐使用的原因,对比了不同实现的性能与适用场景,帮助开发者根据实际需求选择合适的List实现。

热门文章

最新文章