Collection of ordered map and ordered multimap implementations:
- omap.OMapLinked
implements an ordered map using a double-linked list to keep the ordering. It is the default and
recommended implementation of
OMap
. - omap.OMapSync implements an ordered map using OMapLinked underneath and providing synchronization to be parallel-safe. Use this only if you need to operate on the map in multiple goroutines at same time (writing once and reading many concurrently is safe, only writing in parallel with other reads/writes is an issue).
- omultimap.OMultiMapLinked implements an ordered multimap that can hold many values per key, and still keep then in order using a linked list internally
- omultimap.OMultiMapSync implements an ordered multimap using OMultiMapLinked underneath and providing synchronization to be parallel-safe
Implementation not recommended, in general (use only if you prove it better):
- omap.OMapLinkedHash
implements an ordered map similar to OMapLinked, but hashes the value before saving, it is
adivised to use only in very few occasions, see benchmarks for details.
This implementation is an attempt to have a map without the memory overhead to copy keys twice
(one in the element and another in the mapping), but it has proven not to be very useful in
most cases, so the recommendation is to use this only, and only if, you have a heavy object being
used as key and can provide a custom hashing implementation. Note: do not use this with string
key, even if you have large string keys, since Golang internal string is immutable and use a
pointer to the actual string,
copying it around is not an issue for
OMapLinked
.
Implementations used only for testing (do not use this in production code):
- omap.OMapSimple
provides a very simple implementation of
OMap
using an slice to keep the order of the keys. It has proven not a very efficient implementation on benchmarks, but as it has been kept around as it is a very simple implementation and helps on fuzz and unit testing. - omap.OMapBuiltin
DO NOT USE THIS! It is used internally only to test/compare with builtin map using
the
OMap
interface, but iterating over this map is a bit expensive (use of goroutine and channels, which can leak) and it is not ordered.
Requirements:
- Go version >= 1.18, since it needs generics.
- That is it, no external dependencies.
Installation:
go get -u github.com/matheusoliveira/go-ordered-map/
Then simple import omap
or omultimap
and use New*
functions. Import paths:
"github.com/matheusoliveira/go-ordered-map/omap"
"github.com/matheusoliveira/go-ordered-map/omultimap"
This package implements map in Golang, very similar to builtin map, but in which the iteration returns keys in the same ordering as originally inserted.
The time complexity of operations are the same as builtin maps, with very little memory overhead, and an advantage of faster full-iteration of long maps, see benchmarks for more details.
Example:
package main
import (
"encoding/json"
"fmt"
"github.com/matheusoliveira/go-ordered-map/omap"
)
func main() {
m := omap.New[string, int]()
m.Put("foo", 1)
m.Put("x", -1)
m.Put("bar", 2)
m.Put("y", -1)
m.Put("baz", 3)
m.Delete("x")
m.Delete("y")
// iterate
for it := m.Iterator(); it.Next(); {
fmt.Printf("%s = %d\n", it.Key(), it.Value())
}
// JSON, keys are preserved in same order for marshal/unmarshal
input := []byte(`{"hi":"Hello","name":"World!"}`)
hello := omap.New[string, string]()
json.Unmarshal(input, &hello)
fmt.Println(hello)
// marshal JSON
output, _ := json.Marshal(hello)
fmt.Println(string(output))
if string(output) == string(input) {
fmt.Println("Sucess!")
}
// reverse iterator
for it := m.Iterator().MoveBack(); it.Prev(); {
fmt.Printf("%s = %d\n", it.Key(), it.Value())
}
}
Output:
foo = 1
bar = 2
baz = 3
omap.OMapLinked[hi:Hello name:World!]
{"hi":"Hello","name":"World!"}
Sucess!
baz = 3
bar = 2
foo = 1
See omap API reference for more details.
It is an ordered multimap, each key can hold multiple values and iterating over the full map will return in the same ordering as originally inserted. It is handy for cases when you want the multiple values for the same key or if you want to marshal/unmarshal and keep the original state.
Example:
package main
import (
"encoding/json"
"fmt"
"github.com/matheusoliveira/go-ordered-map/omultimap"
"github.com/matheusoliveira/go-ordered-map/omap"
)
func main() {
mm := omultimap.New[string, int]()
mm.Put("foo", 1)
mm.Put("bar", 2)
mm.Put("baz", 3)
mm.Put("foo", 4)
mm.Put("bar", 5)
mm.Put("baz", 6)
mm.Put("foo", 7)
mm.Put("bar", 8)
mm.Put("baz", 9)
fmt.Println("iterate all keys/values:")
for it := mm.Iterator(); it.Next(); {
fmt.Printf(" %q / %d\n", it.Key(), it.Value())
}
// iterate values of a given key
fmt.Printf("values of foo: ")
fooIt := mm.GetValuesOf("foo")
fmt.Println(omap.IteratorValuesToSlice(fooIt))
// marshal JSON
fmt.Printf("marshal output:\n ")
js, _ := json.Marshal(mm)
fmt.Println(string(js))
// unmarshal JSON
fmt.Printf("unmarshal output:\n ")
mm2 := omultimap.New[string, int]()
json.Unmarshal(js, mm2)
fmt.Println(mm2)
}
Output:
iterate all keys/values:
"foo" / 1
"bar" / 2
"baz" / 3
"foo" / 4
"bar" / 5
"baz" / 6
"foo" / 7
"bar" / 8
"baz" / 9
values of foo: [1 4 7]
marshal output:
{"foo":1,"bar":2,"baz":3,"foo":4,"bar":5,"baz":6,"foo":7,"bar":8,"baz":9}
unmarshal output:
omultimap.OMultiMapLinked[foo:1 bar:2 baz:3 foo:4 bar:5 baz:6 foo:7 bar:8 baz:9]
See omultimap API reference for more details.
- zero external dependencies, use only stdlib packages
- insert, update and delete keys into the map
- implements json.Marshaler to convert map to json, keeping keys order, of course
- implements json.Unmarshaler to convert json to map, keeping keys order, of course
- implements fmt.Stringer to convert map to string, in a similar fashion as builtin map
- support multiple implementations
- Get performance should be very close to builtin map (see benchmarks)
- have builtin sync implementation
- implements multimap (
omultimap
) - start iterator at specific key
- support reverse ordering iterator
- support add/remove at iterator position
Did I miss anything? Create an issue or open a pull request and let's discuss.
There is a series of benchmarks comparing omap
implementations with Go's builtin map, see benchmarks for more details.