从映射中获取任意键/项

Question

我刚学习Go语言，现在想从map中获取任意一个元素；有没有更符合惯用方式的方法？我只能想到类似下面这样的代码：

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

我想要这样做的原因是，我正在使用一个映射来维护一组作业，并且使用映射，我可以在O（1）时间内获取未完成的作业或删除已完成的作业。我猜这应该是一个常见的需求，但在Go中如何实现并不明显。

- chuchao333

---

你知道你正在尝试获取或设置的键的值吗？还是你正在尝试查找一个随机的键或一些你事先不知道的键？ - dethtron5000

你正在寻找具有特定值的键吗？如果你只是在寻找与键相关联的值，那么它就是简单的 m[i]。 - Dmitri Goldring

你的方法看起来不错。如果地图可以被两个goroutine并发访问，请使用sync.Mutex保护检索/删除操作，以便两个goroutine不会获取相同的作业（因为为了速度而不是本地线程安全）。 - twotwotwo

@dethtron5000 我不需要随机密钥或其他东西，我只需要为地图中的任何元素提供一个密钥，如果有的话。 - chuchao333

@twotwotwo 是的，我从maps in action这篇文章中看到了这一点，并且要明确一下，我正在使用sync.RWMutex。 - chuchao333

Answer 1

讨论是否从哈希表中获取任意键是一个常见的需求。其他语言的映射实现通常缺乏此功能（例如，C#字典）。

但是，您的解决方案可能是最快的，但是您将获得一个您无法控制的伪随机算法。虽然当前的实现使用了伪随机算法，但是Go规范并不保证它实际上是随机的，只是它不能保证是可预测的：

映射上的迭代顺序未指定，并且不能保证从一次迭代到下一次迭代是相同的。

如果您想对随机化获得更多控制权，也可以并行地保持一个包含在映射中的值（或键）的更新切片，使用您选择的随机化（math/rand 或者 crypto/rand用于更极端的情况），以随机选择的索引在切片中获取存储的值。

- ANisus

---

@chuchao333 那么你的解决方案很好。另一种类似的方式是 var k, v int; for k, v = range m { break } 如果你想要内联执行的话。为了确保你得到一个值，你可以这样做：var k, v int; var ok bool; for k, v = range m { ok = true; break } - ANisus

你在最后一句话中说的“从切片中获取索引”是什么意思？ - jochen

@jochen：可能用词不当。我的意思是获取切片中特定索引处存储的值。例如：slice[rand.Intn(len(slice))] - ANisus

@jochen：是的。问题是关于地图的。但是地图不允许您以O(1)的方式选择项目i。因此，我还建议使用既有地图又有切片的解决方案。在不需要从地图中删除的情况下效果最佳，否则删除将成为O(n)操作，因为您还需要遍历切片。 - ANisus

C#有这个特性：dict.First()。它并不是在Dictionary中实现的，而是在Linq中实现的，但它确切地做到了这里所要求的。 - TheJP

Answer 2

这里有一个更通用的版本，虽然可能不够高效：

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

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

- Briank

---

它的运行速度大约比 Xeoncross 建议的方法慢了5倍。（尽管我喜欢这个版本，因为它更简单。）我在这里制作了一个测试代码：https://play.golang.org/p/L2z5kGJ7WsW - Coconut

这太糟糕了！它具有O(N)的运行时间和内存消耗！ - Bryan

Answer 3

请看这里。

并发安全且O(1)

这是一个为map添加“随机”方法的包装器。

使用示例：

package main

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

func main() {
    rand.Seed(time.Now().UnixNano())
    
    s := NewRandMap()

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

    randomItem := s.Random()
    myItem := randomItem.(string)

    fmt.Println(myItem)
}

数据结构：

type RandMap struct {
    m sync.RWMutex

    // Where the objects you care about are stored.
    container map[string]interface{}

    // 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  []string

    // 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[string]int
}

func NewRandMap() *RandMap {
    return &RandMap{
        container: make(map[string]interface{}),
        sliceKeyIndex: make(map[string]int),
    }
}

func (s *RandMap) Add(key string, item interface{}) {
    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) Get(key string) interface{} {
    s.m.RLock()
    defer s.m.RUnlock()

    return s.container[key]
}

func (s *RandMap) Remove(key string) {
    s.m.Lock()
    defer s.m.Unlock()

    // 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) Random() interface{} {

    if s.Len() == 0 {
        return nil
    }

    s.m.RLock()
    defer s.m.RUnlock()

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

    return s.container[key]
}

func (s *RandMap) PopRandom() interface{} {

    if s.Len() == 0 {
        return nil
    }

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

    item := s.container[key]
    s.m.RUnlock()

    s.Remove(key)

    return item
}

func (s *RandMap) Len() int {
    s.m.RLock()
    defer s.m.RUnlock()

    return len(s.container)
}

- squirtgun

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]）。

这是超级快速的，并且可以很容易地适用于任何类型的映射。

- Nick AKX

Answer 5

在我的情况下，地图只有一个键需要提取，因此您可以执行以下操作：

    var key string
    var val string
    for k, v := range myMap {
        key = k
        val = v
        break
    }

对于多个键，你可以这样做：

func split_map(myMap map[string]string, idx int) (string[], string[]) {
    keys := make([]string, len(myMap))
    values := make([]string, len(myMap))
    count := 0
    for k, v := range myMap {
        keys[count] = k
        values[count] = v
        count = count + 1
    }
    return keys, values
}

当访问第i个元素时，

func get_ith(myMap map[string]string, idx int) (string, string) {
    count := 0
    for k, v := range myMap {
        if idx == count {
            return k, v
        }
        count = count + 1
    }
    return "", ""
}

- eshaan7

Answer 6

也许你需要的是一个数组，它很容易随机访问，特别是当容器需要频繁进行随机读取但不经常更改时。

- tangxinfa

Answer 7

通常强制将API应用于本质上不支持它的数据结构并不是一个好主意。最好的情况下，它会变得缓慢、笨拙、难以测试、难以调试和不稳定。Go的map原生支持upsert、get、delete和length，但不支持GetRandom。

在这里提到的两个具体解决方案中：

• 遍历范围并选择第一个并不能保证选择一个随机项或对随机程度（如均匀、高斯和种子）进行任何控制
• 反射是笨拙的、缓慢的，并需要额外的内存，与映射的大小成比例

其他解决方案涉及使用其他数据结构来帮助映射支持此操作。我认为这是最有意义的做法。

type RandomizedSet interface {
    Delete(key int) // O(1)
    Get(key int) int // O(1)
    GetRandomKey() int // O(1)
    Len() int // O(1)
    Upsert(key int, val int) // O(1)
}

type randomizedset struct {
    h map[int]int // map key to its index in the slice
    indexes []int // each index in the slice contains the value
    source rand.Source // rng for testability, seeding, and distribution
}

func New(source rand.Source) RandomizedSet {
    return &randomizedset{
        h: make(map[int]int, 0),
        indexes: make([]int, 0),
        source: source,
    }
}

// helper to accomodate Delete operation
func (r *randomizedset) swap(i, j int) {
    r.indexes[i], r.indexes[j] = r.indexes[j], r.indexes[i]
    r.h[r.indexes[i]] = i
    r.h[r.indexes[j]] = j
}

// remainder of implementations here

- rossb83

Answer 8

作为一种“全球性”的解决方案，我是elasticsearch的忠实粉丝，你可以使用另一个映射/数组来存储数据，构建一种倒排索引字典。

- Thomas Decaux