一个泛型的有序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 {
	Key   K
	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, false
}
func (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
			}
		}
	}
}