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来统计大小,通过分段计数来减少竞争。

相关文章
|
10天前
|
存储 缓存 安全
Java集合框架(二):Set接口与哈希表原理
本文深入解析Java中Set集合的工作原理及其实现机制,涵盖HashSet、LinkedHashSet和TreeSet三大实现类。从Set接口的特性出发,对比List理解去重机制,并详解哈希表原理、hashCode与equals方法的作用。进一步剖析HashSet的底层HashMap实现、LinkedHashSet的双向链表维护顺序特性,以及TreeSet基于红黑树的排序功能。文章还包含性能对比、自定义对象去重、集合运算实战和线程安全方案,帮助读者全面掌握Set的应用与选择策略。
87 23
|
6天前
|
人工智能 自然语言处理 机器人
AI Compass前沿速览:Jetson Thor英伟达AI计算、Gemini 2.5 Flash Image、Youtu腾讯智能体框架、Wan2.2-S2V多模态视频生成、SpatialGen 3D场景生成模型
AI Compass前沿速览:Jetson Thor英伟达AI计算、Gemini 2.5 Flash Image、Youtu腾讯智能体框架、Wan2.2-S2V多模态视频生成、SpatialGen 3D场景生成模型
AI Compass前沿速览:Jetson Thor英伟达AI计算、Gemini 2.5 Flash Image、Youtu腾讯智能体框架、Wan2.2-S2V多模态视频生成、SpatialGen 3D场景生成模型
|
10天前
|
安全 Java API
Java中的Lambda表达式:简洁与功能的结合
Java中的Lambda表达式:简洁与功能的结合
154 91
|
28天前
|
数据采集 边缘计算 缓存
从流量到留量:ESA 安全加速守护零售行业交易全链路
零售业正经历数字技术驱动的深度变革,电商蓬勃发展,消费持续升级。阿里云边缘云推出零售交易行业解决方案,通过分布式边缘计算、智能路由与安全防护,助力企业应对跨地域交易挑战,实现安全高效发展。
106 14
|
30天前
|
人工智能 安全 Nacos
如何实现 AI Agent 自主发现和使用 MCP 服务 —— Nacos MCP Router 部署最佳实践
Nacos社区推出MCP Router与MCP Registry开源解决方案,助力AI Agent高效调用外部工具。Router可智能筛选匹配的MCP Server,减少Token消耗,提升安全性与部署效率。结合Nacos Registry实现服务自动发现与管理,简化AI Agent集成复杂度。支持协议转换与容器化部署,保障服务隔离与数据安全。提供智能路由与代理模式,优化工具调用性能,助力MCP生态普及。
599 24
|
3天前
|
缓存 负载均衡 JavaScript
Nginx:高性能Web服务器与反向代理利器
Nginx:高性能Web服务器与反向代理利器
168 110
|
9天前
|
人工智能 运维 监控
IT运维数字化转型:不是换工具,而是换思路
IT运维数字化转型:不是换工具,而是换思路
69 9
|
23天前
|
运维 Kubernetes 安全
ASM Ambient 模式如何革新 Kubernetes 出口流量管理
ASM Ambient 模式通过 Waypoint 代理简化 Kubernetes 出口流量管理,大幅降低配置复杂度。