从地图中获取任意键/项

Question

我是golang的新手,现在我想从地图中获取一个任意项目,这样做的惯用方法是什么？我只能想到如下:

func get_some_key(m map[int]int) int {
    for k := range m {
        return k
    }
    return 0
}

我想要的原因是我使用地图来维护一组作业,并使用地图我可以获得待处理作业或删除O(1)中的已完成作业.我想这应该是一个常见的要求,但在go中做这件事并不明显.

提前致谢!

Answer 1

是否可以讨论从散列表中获取任意密钥是否是常见要求.其他语言地图实现通常缺少此功能(例如C#中的字典)

但是,您的解决方案可能是最快的解决方案,但您将使用您无法控制的伪随机算法.虽然目前的实现使用了pseduo-random算法,但Go规范并没有给你任何保证它实际上是随机的,只是它不能保证是可预测的:

未指定地图上的迭代顺序,并且不保证从一次迭代到下一次迭代是相同的.

如果您想要更多地控制随机化,您还可以并行地保留地图中包含的更新的值(或键)片段,使用您选择的随机化(math/rand或crypto/rand更极端的情况)来获取存储在索引中的值,在切片中随机选择.

Answer 2

干得好。

并发安全且 O(1)

这是添加“随机”方法的映射的包装器。

用法示例：

package main

func main() {
    s := NewRandMap[string, string]()

    s.Add("myKey", "Item1")
    s.Add("myKey2", "Item2")
    s.Add("myKey3", "Item3")

    randomItem, _ := s.Random()

    fmt.Println(randomItem)
}

数据结构：

type RandMap[K comparable, V any] struct {
    m sync.RWMutex

    // Where the objects you care about are stored.
    container map[K]V

    // A slice of the map keys used in the map above. We put them in a slice
    // so that we can get a random key by choosing a random index.
    keys []K

    // We store the index of each key, so that when we remove an item, we can
    // quickly remove it from the slice above.
    sliceKeyIndex map[K]int
}

func NewRandMap[K comparable, V any]() *RandMap[K, V] {
    return &RandMap[K, V]{
        container:     make(map[K]V),
        sliceKeyIndex: make(map[K]int),
    }
}

func (s *RandMap[K, V]) Add(key K, item V) {
    s.m.Lock()
    defer s.m.Unlock()

    // store object in map
    s.container[key] = item

    // add map key to slice of map keys
    s.keys = append(s.keys, key)

    // store the index of the map key
    index := len(s.keys) - 1
    s.sliceKeyIndex[key] = index
}

func (s *RandMap[K, V]) Get(key K) (val V, ok bool) {
    s.m.RLock()
    defer s.m.RUnlock()

    item, ok := s.container[key]
    if !ok {
        return *new(V), false
    }

    return item, true
}

func (s *RandMap[K, V]) Remove(key K) {
    s.m.Lock()
    defer s.m.Unlock()

    s.remove(key)
}

// caller is responsible for locking
func (s *RandMap[K, V]) remove(key K) {
    // get index in key slice for key
    index, exists := s.sliceKeyIndex[key]
    if !exists {
        // item does not exist
        return
    }

    delete(s.sliceKeyIndex, key)

    wasLastIndex := len(s.keys)-1 == index

    // remove key from slice of keys
    s.keys[index] = s.keys[len(s.keys)-1]
    s.keys = s.keys[:len(s.keys)-1]

    // we just swapped the last element to another position.
    // so we need to update it's index (if it was not in last position)
    if !wasLastIndex {
        otherKey := s.keys[index]
        s.sliceKeyIndex[otherKey] = index
    }

    // remove object from map
    delete(s.container, key)
}

func (s *RandMap[K, V]) Random() (val V, ok bool) {
    s.m.RLock()
    defer s.m.RUnlock()

    if len(s.keys) == 0 {
        return *new(V), false
    }

    randomIndex := rand.Intn(len(s.keys))
    key := s.keys[randomIndex]

    item := s.container[key]

    return item, true
}

func (s *RandMap[K, V]) PopRandom() (val V, ok bool) {
    s.m.Lock()
    defer s.m.Unlock()

    if len(s.container) == 0 {
        return *new(V), false
    }

    randomIndex := rand.Intn(len(s.keys))
    key := s.keys[randomIndex]

    item, ok := s.container[key]
    if !ok {
        return *new(V), false
    }

    s.remove(key)

    return item, true
}

func (s *RandMap[K, V]) Len() int {
    s.m.RLock()
    defer s.m.RUnlock()

    return len(s.container)
}

Answer 3

这是一个通用的版本，尽管效率可能较低：

    keys := reflect.ValueOf(mapI).MapKeys()
    return keys[rand.Intn(len(keys))].Interface()

https://play.golang.org/p/0uvpJ0diG4e

Answer 4

这是我发现的一种更快的方法：

在我的测试中，我创建了以下函数

type ItemType interface{}

func getMapItemRandKey(m map[string]ItemType) string {
    return reflect.ValueOf(m).MapKeys()[0].String()
}

每个地图的密钥采用以下格式：

b := new(big.Int)
rbytes := (some random function to generate cryptographically safe random bytes)
b.SetBytes(rbytes)

key := b.String()
m := map[string]ItemType
m[key] = &ItemType{}

作为测试，当我请求所有密钥时，我从我的值中获取第一个密钥，但只有一个 (... MapKeys()[0])。

这是超级快，可以很容易地适应任何类型的地图。