练习题合集

要求实现一个 map
(1) 面向高并发;
(2) 只存在插入和查询操作 o(1);
(3)查询时，若 key 存在，直接返回 val; 若 key 不存在，阻塞直到 key val 对被放入后，获取 val 返回;等待指定时长仍未放入，返回超时错误;
(4)写出真实代码，不能有死锁或者 panic 风险

1. 使用sync.Mutex保护临界区
2. 使用close(ch)会给所有读取ch的协程返回的机制通知接触阻塞，相当于sync.Cond的作用
3. 需要注意并发情况下的多次Put操作可能导致的重复close的问题

package main

import (
    "errors"
    "fmt"
    "math/rand"
    "sync"
    "time"
)

func main()  {
    rand.Seed(time.Now().Unix())
    ncm := NewConcurrentMap()
    for i:=0;i<10;i++{
        go func(i int) {
            key := rand.Intn(2)+1
            get, err := ncm.Get(key, time.Second*2)
            if err != nil {
                fmt.Println("err: ",err)
                return
            }
            fmt.Printf("goid: %d key: %d res: %d \n",i,key,get)
        }(i)
    }
    time.Sleep(time.Second)
    //time.Sleep(time.Second*2)
    //time.Sleep(time.Second*3)
    for i:=0;i<100;i++{
        go func(i int) {
            key := rand.Intn(2)+1
            ncm.Put(key,i)
        }(i)
    }

    for i:=0;i<100;i++{
        go func(i int) {
            key := rand.Intn(2)+1
            ncm.Delete(key)
        }(i)
    }

    time.Sleep(time.Second*10)
}


type ConcurrentMap struct {
    local map[int]int
    localChan map[int]*SingleSync //每个key对应的阻塞
    mu sync.Mutex // 保护local和localChan
}

type SingleSync struct {
    ch chan struct{} // 用于通知阻塞和释放的信号
    count int // 对解题可不用 不过加一个没问题
}

func NewConcurrentMap()*ConcurrentMap{
    localChan := make(map[int]*SingleSync)
    local := make(map[int]int)
    return &ConcurrentMap{
        localChan: localChan,
        local:local,
    }
}

func (m *ConcurrentMap)Delete(k int){
    m.mu.Lock()
    defer m.mu.Unlock()
    if _,ok := m.local[k];ok{
        delete(m.local, k)
        delete(m.localChan, k)
        return
    }
}

func (m *ConcurrentMap)Put(k, v int){
    m.mu.Lock()
    defer m.mu.Unlock()
    m.local[k] = v
    if s,ok := m.localChan[k];ok{ // 虽然有锁，但是同一个key的并发的Put调用还是可能会有多个协程进入if中，所以要删掉这个key
        close(s.ch)
        delete(m.localChan, k) //
    }
}

func (m *ConcurrentMap)Get(k int, maxDuration time.Duration)(int, error){
    var ch chan struct{}
    m.mu.Lock()
    if v,ok := m.local[k];ok{
        m.mu.Unlock()
        return v, nil
    }
    if s, ok := m.localChan[k];ok{
        ch = s.ch
        s.count++
    }else {
        ch = make(chan struct{})
        s = &SingleSync{
            ch: ch,
            count: 1,
        }
        m.localChan[k] = s
    }
    m.mu.Unlock()

    if ch!=nil{
        d := time.NewTimer(maxDuration)
        select {
        case <-d.C:
            return 0, errors.New("timeout")
        case <-ch:
            m.mu.Lock()
            if v,ok := m.local[k];ok{
                m.mu.Unlock()
                return v, nil
            }
            m.mu.Unlock()
            return 0 ,errors.New("un reach 1")
        }
    }else {
        return 0 ,errors.New("un reach 2")
    }

}

改进 锁粒度太大