bycigo/omap：Go 的有序 map 实现

Go 语言内置的 map 是开发中使用频率最高的数据结构之一，它有一个被反复提及的“特性”：遍历顺序是随机的。这并非缺陷，而是 Go 团队刻意为之的设计，通过随机化遍历顺序，避免开发者依赖某种隐式的顺序，从而写出更健壮的代码。

然而还是存在一些小众场景需要明确 map 的“插入顺序”，bycigo/omap 就是为此而生的一个轻量、泛型的有序 map 实现。本文将带你从使用到源码，完整理解它的设计与实现。

一、安装与特性

先来介绍一下 omap 的安装与特性：

安装

go get github.com/bycigo/omap

创建

// 创建一个新的omap
m1 := omap.New[string, int]()

// 预分配容量
m2 := omap.Make[string, int](10)

得益于 Go 泛型，键类型需满足 comparable，值可以是任意类型。

基础操作

m := omap.New[string, int]()

// 插入
m.Set("foo", 1)
m.Set("bar", 2)

// 仅当键不存在时才写入，返回是否写入成功
ok := m.TrySet("foo", 99) // false，"foo" 已存在
ok = m.TrySet("baz", 3)   // true

// 读取
v := m.Get("foo")          // 不存在则返回零值
v, ok := m.TryGet("foo")   // 同时返回是否存在

// 其它操作
m.Has("bar")               // true
m.Delete("foo")            // 删除单个键
m.Delete("bar", "baz")     // 一次删除多个键
m.Clear()                  // 清空
m.Len()                    // 元素数量

顺序遍历

omap 实现了迭代器接口，通过 All() 返回一个 iter.Seq2[K, V]，可直接用于 range：

m := omap.New[string, int]()
m.Set("one", 1)
m.Set("two", 2)
m.Set("three", 3)

for k, v := range m.All() {
    fmt.Printf("%s: %d\n", k, v)
}

// 输出严格按插入顺序：
// one: 1
// two: 2
// three: 3

如果只需要键或值的切片：

keys := m.Keys()     // []string{"one", "two", "three"}
values := m.Values() // []int{1, 2, 3}

合并与反转

m1.Merge(m2, m3)  // 把多个 map 依次合并进 m1，保持顺序
m.Reverse()       // 原地反转键的顺序

排序

当键类型满足 cmp.Ordered 时，可以进行排序操作：

omap.Sort(m)      // 升序
omap.SortDesc(m)  // 降序

// 自定义比较函数，例如按键长度排序
omap.SortFunc(m, func(a, b string) int {
    return len(a) - len(b)
})

序列化

这是 omap 最实用的特性之一：Marshal 和 Unmarshal 都严格保留键顺序。

// JSON
data, _ := json.Marshal(m)   // {"foo":1,"bar":2}
_ = json.Unmarshal(data, m)  // 解析后键顺序与原文一致

// YAML（基于 go.yaml.in/yaml/v3）
data, _ := yaml.Marshal(m)   // foo: 1\nbar: 2
_ = yaml.Unmarshal(data, m)

二、实现原理

omap 的实现思路非常经典：用原生 map 保证 O(1) 性能，用双向链表保证插入顺序。核心结构如下：

type Map[K comparable, V any] struct {
    kv map[K]*elem[K, V] // 哈希索引：键 -> 链表节点
    kl list[K, V]        // 维护插入顺序的双向链表
}

• kv 是一个标准 Go map，但值不是 V，而是指向链表节点的指针 *elem[K, V]。这样查找时既能拿到值，又能定位它在顺序链表中的位置。
• kl 是一个循环双向链表，记录了所有元素的插入顺序。

节点结构：

type elem[K comparable, V any] struct {
    next, prev *elem[K, V]
    key        K
    val        V
}

这种“哈希表 + 链表”的组合，本质上和 Java 的 LinkedHashMap、Python 的有序 dict 是同一思路。

插入：Set 与 TrySet

Set 和 TrySet 都可以插入新的键值对，区别是 TrySet 仅当键不存在时才能插入成功，并且 Set 在遇到键已存在的情况时会遵循： 只替换值不改变键的插入顺序。插入的底层原理就是往 kl 里面 append 一个新的 *elem，并将这个 *elem 保存到 kv 里面，时间复杂度是 O(1)。

func (m *Map[K, V]) Set(key K, value V) {
    ...
    e = m.kl.append(key, value)
    m.kv[key] = e
    ...
}

查找：Get 与 TryGet

Get 和 TryGet 都可以通过键查找值，区别是 TryGet 会多返回一个 bool 值明确告知此次查找的键是否存在，当键不存在时返回的值是对应类型的零值。查找的时间复杂度是 O(1)，因为是直接从 kv 中查找。

func (m *Map[K, V]) Get(key K) (value V) {
    e, ok := m.kv[key]
    if ok {
        value = e.val
    }
    return
}

删除：Delete

删除也只需要将键从 kl 和 kv 中移除即可，由于 kl 是个双向链表且 kv 中也保存了节点指针，因此删除操作的时间复杂度也是 O(1)。

func (m *Map[K, V]) Delete(key K) {
    if e, ok := m.kv[key]; ok {
        m.kl.delete(e)
        delete(m.kv, key)
    }
}

遍历：All

All 本质是在遍历 kl 链表，所以遍历顺序是严格按照插入顺序来的。由于 All 方法还实现了 iter.Seq2 迭代器，因此可以使用 range 语法来遍历 omap，使用break、continue控制遍历节奏。

func (m *Map[K, V]) All() iter.Seq2[K, V] {
    return func(yield func(K, V) bool) {
        for e := m.kl.root.next; e != nil && e != &m.kl.root; {
            next := e.next
            if !yield(e.key, e.val) {
                return
            }
            e = next
        }
    }
}

此处代码实现中有个细节：在 yield 之前使用临时变量提前保存 next 节点 next := e.next。如果不这样做，一旦在遍历过程中删除了当前节点 e.next 就会变成 nil，从而无法继续遍历后续节点，提前保存 next 节点能确保迭代的完整性。

排序

包里提供了 3 个函数对 omap 进行排序：Sort()、SortDesc()、SortFunc()。由于底层决定顺序的数据结构是链表，因此选择了对链表非常友好的归并排序算法，时间复杂度是 O(nlogn)。

序列化：JSON 与 YAML

标准库 encoding/json 对 map 序列化时会按键的字典顺序排序，无法保留插入顺序。omap 通过实现 json.Marshaler 接口，确保序列化时保留键的插入顺序，并且与标准库类似会将整型的键序列化为字符串格式。反序列化时，omap 通过实现 json.Unmarshaler 接口来确保键的顺序与原始 json 一致。值得一提的是，omap 已经为 Go 即将到来的 encoding/json/v2 做了准备，通过 build 标签区分两套实现，当开发者编译时指定 GOEXPERIMENT=jsonv2，会自动选用基于新 API 的实现，对使用者完全透明。

YAML 部分则基于其官方维护的 go.yaml.in/yaml/v3 组件来实现序列化与反序列化。序列化时通过构造 yaml.MappingNode 来控制键的顺序，YAML 的 MappingNode.Content 是一个 []*yaml.Node，按 key, value, key, value... 交替排列，天然支持顺序控制。

三、核心特性回顾

• 有序：严格维护插入顺序；
• 泛型：键 comparable，值任意类型，类型安全；
• 高效：增删查改均为 O(1)；
• 迭代器：拥抱 iter.Seq2，range 即可遍历；
• 序列化：JSON / YAML 双向都保留顺序，并已适配 encoding/json/v2；
• 排序：提供升序、降序及自定义比较。

回头看，omap 虽然代码量不大，但整体设计保持不错的工程审美。如果你正在寻找一个既保留插入顺序、又能无痛序列化的 Go map 替代品，omap 是一个值得一试的选择。

完整源码与更多示例见仓库：github.com/bycigo/omap ，欢迎 Star、Issue、MR。

本作品采用《CC 协议》，转载必须注明作者和本文链接