An Ordered Map in Go

Elliot Chance
Nov 19, 2019 · 2 min read
Image for post
Image for post
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 +732K people. Follow to join our community.

Elliot Chance

Written by

I’m a data nerd and TDD enthusiast originally from Sydney. Currently working for Uber in New York. My thoughts here are my own. 🤓 elliotchance@gmail.com

The Startup

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

Elliot Chance

Written by

I’m a data nerd and TDD enthusiast originally from Sydney. Currently working for Uber in New York. My thoughts here are my own. 🤓 elliotchance@gmail.com

The Startup

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

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store