一個泛型的有序 Go Map 實現

Go 內建的 map 類型對於插入的元素並沒有保持它們的插入順序，遍歷的時候也故意設置成隨機的 [1]。因此，如果我們想讓 map 保持元素的插入順序，需要藉助第三方的庫纔行，今天就給大家介紹一個這樣的庫 OrderedMap](https://rpcx.io/r/12DuBuGc8O5)。

其實在其他編程語言中，也有類似的數據結構，比如 java 中的 LinkedHashMap[2], python 中的OrderedDict。

本文介紹如何使用 Go 語言實現這樣的一種數據類型。注意我們要實現的是 OrderedMap, 不是 SortedMap 或者 TreeMap，SortedMap 遍歷的時候是按照 Key 的排序順序遍歷的，我們可以通過先獲取所有的 key 並排序，再逐個訪問對應的值。

但是 OrderedMap 遍歷的時候要是保持插入的順序，這怎麼辦到的呢？

我們看看 OrderedMap 的功能，既要有 HashMap 的功能，可以快速得到一個鍵值對，又要保持插入順序，那麼我們可以通過組合的方式實現。

下面就是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
   }
  }
 }
}

這是這個數據結構最主要的方法，當然它還提供更多的方法，比如最老值、最新值、隨機遍歷等，如果你有相應的需求場景，可以考慮使用它。

參考資料

[1]

隨機: https://github.com/golang/go/issues/6719

[2]

LinkedHashMap: https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/LinkedHashMap.html

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/26PlfCFLc9Giuv_7nmgxjg

猜你喜歡