As we know, Go’s built-in map type does not maintain the order of insertion of elements, and is deliberately set to random when traversing. Therefore, if we want to keep the map in the order in which the elements are inserted, we need to use a third party library, and today we will introduce you to one such library, OrderedMap.

In fact, there are similar data structures in other programming languages, such as LinkedHashMap in java and OrderedDict in python.

This article describes how to implement such a data type using Go. Note that we are implementing OrderedMap, not SortedMap or TreeMap. SortedMap is traversed in the sorted order of the keys, and we can access the corresponding values one by one by first getting all the keys and sorting them.

But how does OrderedMap do this if the order of insertion is maintained when it is traversed?

Let’s look at the functionality of OrderedMap, both to have the functionality of a HashMap to get a key-value pair quickly and to keep the insertion order, then we can achieve this by combining.

  • HashMap functionality: Implemented via the built-in map
  • Keeping the order of insertion: could have been done with container/list, but to support generics we use github.com/smallnest/exp/container/list.

The following is the OrderedMap data structure, which contains two fields, entries and list. entries is a map whose values are of type *Entry ; the elements in list are *Entry and point to the same elements as in the map.

1
2
3
4

type OrderedMap[K comparable, V any] struct {
    entries map[K]*Entry[K, V]
    list    *list.List[*Entry[K, V]]
}

The definition of Entry is as follows, in addition to containing Key and Value values, it also contains a list of Element elements, so that it implements a Doubly linked list, where each Entry can find its predecessors and successors.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 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
}

When adding and deleting, we need to operate on both fields in order to maintain consistency.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func (m *OrderedMap[K, V]) Set(key K, value V) (val V, existed bool) {
    if entry, existed := m.entries[key]; existed { // If the key exists, it is updated
        oldValue := entry.Value
        entry.Value = value
        return oldValue, true
    }
    entry := &Entry[K, V]{
        Key:   key,
        Value: value,
    }
    entry.element = m.list.PushBack(entry) // Add to linked list
    m.entries[key] = entry // Add to map
    return value, false
}
func (m *OrderedMap[K, V]) Delete(key K) (val V, existed bool) {
    if entry, existed := m.entries[key]; existed { // If present
        m.list.Remove(entry.element) // Remove from linked list
        delete(m.entries, key) // Remove from map
        return entry.Value, true
    }
    return
}

Get is just a direct query from the map with no loss of performance.

1
2
3
4
5
6

func (m *OrderedMap[K, V]) Get(key K) (val V, existed bool) {
    if entry, existed := m.entries[key]; existed {
        return entry.Value, true
    }
    return
}

When traversing, the linked list structure is traversed as it maintains the insertion order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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
            }
        }
    }
}

This is the most prominent method of this data structure, but of course it offers more methods such as oldest value, newest value, random traversal, etc., so consider using it if you have the appropriate scenario for your needs.

Ref

https://colobu.com/2023/06/18/a-generic-sortedmap-in-go/