优化 Golang 中映射/哈希表的迭代效率

对于一个Golang开发者来说，牢固扎实的基础是十分重要的，golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《优化 Golang 中映射/哈希表的迭代效率》，主要介绍了，希望对大家的知识积累有所帮助，快点收藏起来吧，否则需要时就找不到了！

当将生产 nodejs 应用程序迁移到 golang 时，我注意到 go 原生 map 的迭代实际上比 node 慢。

我提出了一种替代解决方案，通过公开一个可以迭代的数组并将 key=>index 对存储在单独的映射中，以牺牲删除/插入速度和迭代速度。

虽然这个解决方案有效，并且性能显着提高，但我想知道是否有更好的解决方案可以研究。

我的设置是，从哈希图中删除的内容非常罕见，只有添加和替换是常见的，此实现“有效”，尽管感觉更像是一种解决方法，而不是实际的解决方案。

地图始终按整数索引，包含任意数据。

fastmap:    500000 iterations -  0.153000ms
native map: 500000 iterations -  4.988000ms

/*
  unordered hash map optimized for iteration speed.
  stores values in an array and holds key=>index mappings inside a separate hashmap
*/

type fastmapentry[k comparable, t any] struct {
    key   k
    value t
}

type fastmap[k comparable, t any] struct {
    m       map[k]int            // stores key => array index mappings
    entries []fastmapentry[k, t] // array holding entries and their keys
    len     int                  // total map size
}

func makefastmap[k comparable, t any]() *fastmap[k, t] {
    return &fastmap[k, t]{
        m:       make(map[k]int),
        entries: make([]fastmapentry[k, t], 0),
    }
}

func (m *fastmap[k, t]) set(key k, value t) {
    index, exists := m.m[key]
    if exists {
        // replace if key already exists
        m.entries[index] = fastmapentry[k, t]{
            key:   key,
            value: value,
        }
    } else {
        // store the key=>index pair in the map and add value to entries. increase total len by one
        m.m[key] = m.len
        m.entries = append(m.entries, fastmapentry[k, t]{
            key:   key,
            value: value,
        })
        m.len++
    }
}

func (m *fastmap[k, t]) has(key k) bool {
    _, exists := m.m[key]

    return exists
}

func (m *fastmap[k, t]) get(key k) (value t, found bool) {
    index, exists := m.m[key]
    if exists {
        found = true
        value = m.entries[index].value
    }

    return
}

func (m *fastmap[k, t]) remove(key k) bool {
    index, exists := m.m[key]
    if exists {
        // remove value from entries
        m.entries = append(m.entries[:index], m.entries[index+1:]...)
        // remove key=>index mapping
        delete(m.m, key)
        m.len--

        for i := index; i < m.len; i++ {
            // move all index mappings up, starting from current index
            m.m[m.entries[i].key] = i
        }
    }

    return exists
}

func (m *fastmap[k, t]) entries() []fastmapentry[k, t] {
    return m.entries
}

func (m *fastmap[k, t]) len() int {
    return m.len
}

运行的测试代码是：

// s.Variations is a native map holding ~500k records

start := time.Now()
iterations := 0
for _, variation := range s.Variations {
    if variation.Id > 0 {

    }
    iterations++
}
log.Printf("Native Map: %d Iterations -  %fms\n", iterations, float64(time.Since(start).Microseconds())/1000)

// Copy data into FastMap
fm := helpers.MakeFastMap[state.VariationId, models.ItemVariation]()
for key, variation := range s.Variations {
    fm.Set(key, variation)
}

start = time.Now()
iterations = 0
for _, variation := range fm.Entries() {
    if variation.Value.Id > 0 {

    }
    iterations++
}
log.Printf("FastMap: %d Iterations -  %fms\n", iterations, float64(time.Since(start).Microseconds())/1000)

正确答案

我认为这种比较和基准测试有点题外话。 map 的 go 实现与您的实现有很大不同，基本上是因为它需要覆盖更广泛的条目区域，编译时使用的结构实际上有点重（不过，它们基本上存储了有关您使用的类型的一些信息）在你的地图等），而且实现方式不同！ map 的 go 实现基本上是一个 hashmap（你的显然不是，或者确实是，但实际的哈希实现委托给你内部保存的 m 映射）。

导致您得到此结果的其他因素之一是，如果您看一下：

for _, variation := range fm.entries() {
    if variation.value.id > 0 {

    }
    iterations++
}

基本上，您正在迭代切片，这比映射更容易、更快地迭代，您可以查看数组，该数组将相同类型的元素彼此相邻，这是有道理的，对吧？
为了进行更好的比较，您应该这样做：

for _, y := range fastMap.m {
        _ = fastMap.Entries()[y].Value + 1 // some simple calculation
}

如果您确实追求性能，那么编写良好的哈希函数和固定大小的数组将是您的最佳选择。

终于介绍完啦！小伙伴们，这篇关于《优化 Golang 中映射/哈希表的迭代效率》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识，快来关注吧！