An Ordered Map in Go

Photo by Jonah Pettrich on Unsplash

An ordered map (also called a linked hash map in Java) is a data structure that allows amortized O(1) for access and mutation just like a map, but the elements maintain their order.

For this I created the github.com/elliotchance/orderedmap package. Here is some basic usage:

import "github.com/elliotchance/orderedmap/v2"

func main() {
  m := orderedmap.NewOrderedMap[string, any]()

  m.Set("foo", "bar")
  m.Set("qux", 1.23)
  m.Set("123", true)

  m.Delete("qux")
}

The most important feature of the *OrderedMap is that the order of the keys is maintained, so that we can iterate them in their creation order:

for _, key := range m.Keys() {
  value, _ := m.Get(key)
  fmt.Println(key, value)
}

Be careful using Keys() as it will create a copy of all of the keys, so it’s only suitable for a small number of items. For larger maps you should use Front() or Back() to iterate per element:

// Iterate through all elements from oldest to newest:
for el := m.Front(); el != nil; el = el.Next() {
  fmt.Println(el.Key, el.Value)
}

// You can also use Back and Prev to iterate in reverse:
for el := m.Back(); el != nil; el = el.Prev() {
  fmt.Println(el.Key, el.Value)
}

The iterator is safe to use bidirectionally, and will return nil once it goes beyond the first or last item.

If the map is changing while the iteration is in-flight it may produce unexpected behavior. Also, if you share the state between goroutines you will need to provide your own synchronization.

Happy coding!