An Ordered Map in Go

Elliot Chance
Nov 19 · 2 min read
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:

m := orderedmap.NewOrderedMap()// Keys and values can be any type.
m.Set("foo", "bar")
m.Set("qux", 1.23)
m.Set(123, true)
m.Delete("qux")value, exists := m.Get("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!

The Startup

Medium's largest active publication, followed by +535K people. Follow to join our community.

Elliot Chance

Written by

I’m a data nerd and TDD enthusiast from Sydney. I love exploring new technologies and working on modern ways to solve age old problems 🤓 elliotchance@gmail.com

The Startup

Medium's largest active publication, followed by +535K people. Follow to join our community.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade