【第三章：BAT等名企面试真题解析8讲】第10节：阿里面试真题解析之并发安全的map

前言

秋招面阿里的时候被问到一个这样的问题：

平时你使用过map么？是并发安全的么？如何实现一个并发安全的map? 考虑过效率么？

相信大家平时使用最多的结构就是各种hash map了，无论哪种语言都有自身提供的实现，比如Java当中的HashMap,Golang当中的Sync.Map等等。在技术面试当中，对于hash Map实现的考察非常频繁。本文将从阿里的面试真题切入，结合相关代码简要的介绍几种实现并发安全的map的方法。

阿里面试真题再现：

1.普通的map是并发安全的么？

答：不是并发安全的，在并发访问的过程当中会出现竞争，导致数据不一致。

2.unordered_map 和 map的区别?

答：unordered_map是基于哈希实现的，查找和插入开销都是O(1)，而map是基于红黑树实现的，查找和插入的开销都是O(logn)。

3.如何实现一个并发安全的map?

答：1.封装读写锁实现；

2.分段锁实现；

3.读写分离实现；

解析：

方法1：通过将读写锁和非并发安全的map封装在一起，实现一个并发安全的map结构。

如下面go语言的一个简单的实现，将一个并发不安全的map和一个读写锁结合，对于读写操作的接口进行封装。

type MyMap struct {
    sync.RWMutex
    mp map[interface{}]interface{}
  ...
}

func (m *MyMap) Read(key interface{}) interface{} {
    m.RLock()
    value := m.mp[key]
    m.RUnlock()
    return value
}

func (m *MyMap) Write(key, value interface{}) {
    m.Lock()
    m.mp[key] = value
    m.Unlock()
}

优势：

实现简单，几行代码就可以实现。
并发量很小，或者竞争使用map的情况较少时对性能的影响并不大。

缺点：

锁的粒度太大。举例来说，线程A调用Write方法写key1的时候锁住了map，此时线程B调用Read方法，读取和key1不相关的key2时就会被阻塞。当并发量增大时，该方案带来的线程阻塞等待的开销会很大，在高并发情况下就需要进行优化。

方法2：锁分段技术

相比方法1使用全局锁的方式，锁分段技术将数据分段存储，给每一段数据配一把锁。实现思路：当线程需要读取map当中某个key的时候，线程不会对整个map进行加锁操作，而是先通过hash取模来找到该key存放在哪一个分段中，然后对这个分段进行加锁，因为每一段数据使用不同的锁，所以对

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

收割BAT：C++校招学习路线总结文章被收录于专栏

《收割BAT：C++校招学习路线总结》，专刊共计17节。专刊分为五大主要内容，包括后台开发学习路线、简历制作，面试技巧、BAT等名企面试真题解析和工作学习常用工具。本专刊将介绍我在技术成长过程当中的经验，通关BAT的面试技巧，并结合亲身经历的面试真题由浅入深的讲解后台开发方向的重点问题，让你们的求职之路更加顺畅。本专刊购买后即可解锁所有章节，故不可以退换哦~