README
Go OrderedMap
An implementation of ordered map in Go. An ordered map preserves the original insertion order when iterating.
It's implemented by wrapping a sync.Map
and a doubly linked list.
The interface is intentionally kept the same with sync.Map
to be used
interchangeably.
Benchmark
This package comes with benchmark test to test against
builtin map and sync.Map
:
$ go test -bench . -benchmem
goos: linux
goarch: amd64
pkg: go.yhsif.com/orderedmap
BenchmarkMap/DeleteEmpty/builtin-4 96833191 12.1 ns/op 0 B/op 0 allocs/op
BenchmarkMap/DeleteEmpty/sync-4 79389284 15.0 ns/op 0 B/op 0 allocs/op
BenchmarkMap/DeleteEmpty/ordered-4 66165724 18.0 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/builtin-4 98423847 12.1 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/sync-4 77803774 15.3 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/ordered-4 66868016 17.9 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Store1/builtin-4 13271734 88.9 ns/op 32 B/op 2 allocs/op
BenchmarkMap/Store1/sync-4 7618335 157 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Store1/ordered-4 9210949 129 ns/op 64 B/op 3 allocs/op
BenchmarkMap/Store2/builtin-4 12802537 94.4 ns/op 32 B/op 2 allocs/op
BenchmarkMap/Store2/sync-4 7385720 162 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Store2/ordered-4 9084321 131 ns/op 64 B/op 3 allocs/op
BenchmarkMap/Update1/builtin-4 13431109 89.5 ns/op 32 B/op 2 allocs/op
BenchmarkMap/Update1/sync-4 7723395 156 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Update1/ordered-4 9167068 129 ns/op 64 B/op 3 allocs/op
BenchmarkMap/Load1/builtin-4 44437922 26.9 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load1/sync-4 38100231 31.4 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load1/ordered-4 29717439 40.3 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/builtin-4 76247488 15.6 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/sync-4 59924874 20.0 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/ordered-4 34028864 35.2 ns/op 0 B/op 0 allocs/op
BenchmarkLoadOrStoreStore/builtin-4 11663713 103 ns/op 32 B/op 2 allocs/op
BenchmarkLoadOrStoreStore/sync-4 2815587 426 ns/op 376 B/op 8 allocs/op
BenchmarkLoadOrStoreStore/ordered-4 2138095 560 ns/op 520 B/op 11 allocs/op
BenchmarkLoadOrStoreLoad/builtin-4 14577663 81.9 ns/op 32 B/op 2 allocs/op
BenchmarkLoadOrStoreLoad/sync-4 12393217 95.9 ns/op 32 B/op 2 allocs/op
BenchmarkLoadOrStoreLoad/ordered-4 12630664 94.0 ns/op 32 B/op 2 allocs/op
BenchmarkStoreThenDelete/builtin-4 9594682 126 ns/op 32 B/op 2 allocs/op
BenchmarkStoreThenDelete/sync-4 2062261 580 ns/op 360 B/op 9 allocs/op
BenchmarkStoreThenDelete/ordered-4 1765857 680 ns/op 440 B/op 11 allocs/op
BenchmarkRange/10/builtin-4 8392304 142 ns/op 0 B/op 0 allocs/op
BenchmarkRange/10/sync-4 7705442 155 ns/op 0 B/op 0 allocs/op
BenchmarkRange/10/ordered-4 34963722 34.2 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/builtin-4 859714 1377 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/sync-4 827470 1439 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/ordered-4 3568192 337 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/builtin-4 77983 15334 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/sync-4 72570 16524 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/ordered-4 354681 3372 ns/op 0 B/op 0 allocs/op
PASS
ok go.yhsif.com/orderedmap 51.884s
As you can see, all operations except Range
are on-par or only slightly slower
than sync.Map
, while Range
is a lot faster.
License
Documentation
Overview ¶
Package orderedmap provides an implementation of ordered map.
An ordered map guarantees that the iteration order preserves the original insertion order. If an existing key is updated later, that doesn't change its iteration order. But if a key was deleted then later inserted again, the iteration order reflects its last insertion order.
Example ¶
Code:
package main import ( "fmt" "go.yhsif.com/orderedmap" ) func main() { var m orderedmap.Map fmt.Println(m.Load("key1")) fmt.Println(m.LoadOrStore("key1", "value1")) fmt.Println(m.LoadOrStore("key1", "value2")) m.Store("key2", "value2") fmt.Println(m.Load("key2")) m.Store("key1", "new value1") fmt.Println(m.Load("key1")) fmt.Println("Range1:") m.Range(func(k, v interface{}) bool { fmt.Println(k, v) return true }) m.Delete("key1") m.Store("key1", "value1") fmt.Println("Range2:") m.Range(func(k, v interface{}) bool { fmt.Println(k, v) return true }) }
<nil> false value1 false value1 true value2 true new value1 true Range1: key1 new value1 key2 value2 Range2: key2 value2 key1 value1
Index ¶
- type Interface
- type Map
- func (m *Map) Delete(key interface{})
- func (m *Map) Load(key interface{}) (value interface{}, ok bool)
- func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool)
- func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)
- func (m *Map) Range(f func(key, value interface{}) bool)
- func (m *Map) Store(key, value interface{})
Examples ¶
Constants ¶
Variables ¶
Functions ¶
Types ¶
type Interface ¶
type Interface interface { Delete(key interface{}) Load(key interface{}) (value interface{}, ok bool) LoadAndDelete(key interface{}) (value interface{}, loaded bool) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) Range(f func(key, value interface{}) bool) Store(key, value interface{}) }
Interface defines the common interface between orderedmap.Map and sync.Map.
type Map ¶
type Map struct {
// contains filtered or unexported fields
}
Map represents an ordered map.
An ordered map preserves the inserting order when iterating.
Underlying it's wrapping a sync.Map with a doubly linked list.
The interface is intentionally kept the same with sync.Map to be used interchangeably.
The zero value is an empty map ready to use. A map must not be copied after first use.
func (*Map) Delete ¶
func (m *Map) Delete(key interface{})
Delete deletes key from the map.
key must be hashable.
func (*Map) Load ¶
Load loads key from the map.
key must be hashable.
The ok result indicates whether the value is found in the map.
func (*Map) LoadAndDelete ¶
LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present.
func (*Map) LoadOrStore ¶
LoadOrStore returns the existing value for the key if present. Otherwise, it stores and returns the given value. The loaded result is true if the value was loaded, false if stored.
key must be hashable.