我正在寻找一种存储 32 字节字符串并允许以首选 O(1( 或 O(log N( 查找复杂性进行快速查找的数据结构(目标只是确定密钥是否存在(。移除和插入的复杂性并不重要,因为这些操作将不频繁。
并不是说它与问题相关,但我正在用 Go 工作。我可以使用由互斥锁支持的哈希图,但争用将是一个问题,如果有更好的解决方案,我宁愿避免分片。
谢谢
map
对于并发读取是安全的。您可以将所需的地图放在sync/atomic.Value
中,当您要写入它时,复制地图并更改它,然后将其放回Value
中。从文档中:
以下示例演示如何频繁维护可缩放 使用写入时复制读取但不经常更新的数据结构 成语。
法典:
type Map map[string]string var m Value m.Store(make(Map)) var mu sync.Mutex // used only by writers // read function can be used to read the data without further synchronization read := func(key string) (val string) { m1 := m.Load().(Map) return m1[key] } // insert function can be used to update the data without further synchronization insert := func(key, val string) { mu.Lock() // synchronize with other potential writers defer mu.Unlock() m1 := m.Load().(Map) // load current value of the data structure m2 := make(Map) // create a new value for k, v := range m1 { m2[k] = v // copy all data from the current object to the new one } m2[key] = val // do the update that we need m.Store(m2) // atomically replace the current object with the new one // At this point all new readers start working with the new version. // The old version will be garbage collected once the existing readers // (if any) are done with it. } _, _ = read, insert
你也可以使用指向你的map
的指针而不是Value
并使用StorePointer/LoadPointer 原子方式存储它,但这并不干净,因为你应该使用不安全的指针并强制转换它。