一个泛型的有序Go Map实现
source link: https://colobu.com/2023/06/18/a-generic-sortedmap-in-go/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一个泛型的有序Go Map实现
我们知道， Go内建的map类型对于插入的元素并没有保持它们的插入顺序，遍历的时候也故意设置成随机的。因此，如果我们想让map保持元素的插入顺序，需要借助第三方的库才行，今天就给大家介绍一个这样的库OrderedMap。
其实在其他编程语言中，也有类似的数据结构，比如java中的 LinkedHashMap, python中的OrderedDict。
本文介绍如何使用Go语言实现这样的一种数据类型。注意我们要实现的是OrderedMap, 不是SortedMap或者TreeMap，SortedMap遍历的时候是按照Key的排序顺序遍历的，我们可以通过先获取所有的key并排序，再逐个访问对应的值。
但是OrderedMap遍历的时候要是保持插入的顺序，这怎么办到的呢？
我们看看OrderedMap的功能，既要有HashMap的功能，可以快速得到一个键值对，又要保持插入顺序，那么我们可以通过组合的方式实现。
- HashMap的功能： 通过内建的map实现
- 保持插入顺序： 本来可以通过
container/list实现，但是为了支持泛型，我们使用github.com/smallnest/exp/container/list实现。
下面就是OrderedMap数据结构，它包含entries和list两个字段。entries是一个map，它的值类型是*Entry; list中的元素是*Entry，和map中的值指向同一个元素:
type OrderedMap[K comparable, V any] struct { entries map[K]*Entry[K, V] list *list.List[*Entry[K, V]]其中Entry的定义如下,除了包含Key和Value值，它还包含一个list的Element元素，这样它就实现了一个双线链表，每个Entry都可以找到对它的前驱和后继：
// Entry is a key-value pair in OrderedMap.type Entry[K comparable, V any] struct { Value V element *list.Element[*Entry[K, V]]// Next returns a pointer to the next entry.func (e *Entry[K, V]) Next() *Entry[K, V] { entry := e.element.Next() if entry == nil { return nil return entry.Value// Prev returns a pointer to the previous entry.func (e *Entry[K, V]) Prev() *Entry[K, V] { entry := e.element.Prev() if entry == nil { return nil return entry.Value增加和删除的时候，我们就需要对这两个字段都进行操作，才能保持一致性：
func (m *OrderedMap[K, V]) Set(key K, value V) (val V, existed bool) { if entry, existed := m.entries[key]; existed { // 如果key存在，就是更新 oldValue := entry.Value entry.Value = value return oldValue, true entry := &Entry[K, V]{ Key: key, Value: value, entry.element = m.list.PushBack(entry) // 加入到链表 m.entries[key] = entry // 加入到map中 return value, falsefunc (m *OrderedMap[K, V]) Delete(key K) (val V, existed bool) { if entry, existed := m.entries[key]; existed { // 如果存在 m.list.Remove(entry.element) // 从链表中移除 delete(m.entries, key) // 从map中删除 return entry.Value, true return查找的时候直接查找map就可以了，性能没有损失:
func (m *OrderedMap[K, V]) Get(key K) (val V, existed bool) { if entry, existed := m.entries[key]; existed { return entry.Value, true return遍历的时候，遍历链表结构，因为它保持了插入顺序：
func (m *OrderedMap[K, V]) Range(f func(key K, value V) bool) { list := m.list for e := list.Front(); e != nil; e = e.Next() { if e.Value != nil { if ok := f(e.Value.Key, e.Value.Value); !ok { return这是这个数据结构最主要的方法，当然它还提供更多的方法，比如最老值、最新值、随机遍历等，如果你有相应的需求场景，可以考虑使用它。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK