While working on a cryptographic library, I needed a map that could serialize itself in a deterministic way. This is because I needed to create a digest of the message, and couldn’t have it wiggling around on me. The solution was to create a struct that contains a map along with an array with pointers into that map. It’s got deterministic binary serialization (essential for my digest needs), backed by msgpack, and thread safety. I realised that this could be useful as a standalone package.

Stable Map is basically an ordered set. In fact, I probably should have called it that. Insertion order of keys is preserved. That’s the long and short of what it provides; maps whose keys are ordered. It’s concurrency safe. It provides range over iterators for your ranging pleasure, and several convenience methods to access and mutate the data.

Stable Map

Space Complexity

Is pretty good: 𝒪(n)

Time Complexity

Is also pretty good

Operation Complexity
Get(key) val 𝒪(1)
Length() int 𝒪(1)
Entries() iter.Seq2 𝒪(n)
AsMap() map 𝒪(n)
Set(key, val) 𝒪(1)
Delete(key) 𝒪(n)
DeleteAt(index) 𝒪(n)*
IndexOf(key) int 𝒪(n)
GetAt(index) val 𝒪(1)

*The underlying operation from the standard library is:

// Delete removes the elements s[i:j] from s, returning the modified slice.
// Delete panics if j > len(s) or s[i:j] is not a valid slice of s.
// Delete is O(len(s)-i), so if many items must be deleted, it is better to
// make a single call deleting them all together than to delete one at a time.
// Delete zeroes the elements s[len(s)-(j-i):len(s)].
func Delete[S ~[]E, E any](s S, i, j int) S {
	_ = s[i:j:len(s)] // bounds check

	if i == j {
		return s
	}

	oldlen := len(s)
	s = append(s[:i], s[j:]...)
	clear(s[len(s):oldlen]) // zero/nil out the obsolete elements, for GC
	return s
}

Getting Started

package main

import (
	"fmt"

	smap "github.com/sean9999/go-stable-map"
)

func main() {

	m := smap.New[string, string]()

	m.Set("foo", "bar")
	m.Set("bing", "bat")

	//	dump the map 10 times. See that the order is always the same
	for range 10 {
		for k, v := range m.Entries() {
			fmt.Printf("%s:\t%s\n", k, v)
		}
		
		//	see that the binary representation is always the same
		bin, _ := m.MarshalBinary()
		fmt.Printf("hex:\t%x\n\n", bin)
	}

}