I am new to Go and now I want to get an arbitrary item from a map; what's the idiomatic way to do that? I can only think of something like this:
func get_some_key(m map[int]int) int {
for k := range m {
return k
}
return 0
}
The reason I want that is I am using a map to maintain a set of jobs, and with a map I can get a pending job or remove a finished job in O(1). I guess this should be a common requirement but it's not obvious how to do it in Go.
Whether getting an arbitrary key from a hash table is a common requirement may be discussed. Other language map implementations often lack this feature (eg. Dictionary in C# )
However, your solution is probably the fastest one, but you will be left with a pseudo-random algorithm that you do not control. And while the current implementation uses a pseudo-random algorithm, the Go Specification doesn't give you any assurance it will actually be random, only that it is not guaranteed to be predictable:
The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.
If you want more control of the randomization, you can also in parallel keep an updated slice of values (or keys) contained in the map, using the randomization of your choice (math/rand or crypto/rand for more extreme cases) to get the value stored at an index, selected randomly, in the slice.
Here is a more generic version, although it may be less efficient:
keys := reflect.ValueOf(mapI).MapKeys()
return keys[rand.Intn(len(keys))].Interface()
Here you go.
Concurrent safe and O(1)
This is a wrapper for a map that adds "random" methods.
Example usage:
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)
}
Data Structure:
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)
}
Here is a faster way I found to do this :
In my test, I created the following function
type ItemType interface{}
func getMapItemRandKey(m map[string]ItemType) string {
return reflect.ValueOf(m).MapKeys()[0].String()
}
The key to each map is in the following format:
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{}
As a test, I'm getting the first key from my value as I request all keys but there is only one (... MapKeys()[0]).
This is super fast and can be adapted to any kind of map very easily.
Maybe what you want is a array, which is easy to access randomly, especially the container is random read heavy but changed infrequently.
In my case, the map only had one key which I needed to extract so for that you can do:
var key string
var val string
for k, v := range myMap {
key = k
val = v
break
}
For multiple keys you could do something like,
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
}
While for accessing ith element,
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 "", ""
}
It is usually not a good idea to force an API on a data-structure that doesn't intrinsically support it. At best it will be slow, hacky, hard-to-test, hard-to-debug and unstable. Go's map natively supports upsert, get, delete, and length but not GetRandom.
Of the two concrete solutions mentioned here
The other solutions talk about using additional data structures to help the map support this operation. This is what I think makes the most sense
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
As a "global" solution, as I am a big fan of elasticsearch, you could use another map/array to store your data, to build a kind of an inverted dictionary.
