Original link: https://colobu.com/2023/06/18/a-generic-sortedmap-in-go/
We know that the built-in map type of Go does not maintain the insertion order of the inserted elements, and it is deliberately set to be random when traversing. Therefore, if we want the map to maintain the insertion order of elements, we need to use a third-party library. Today I will introduce such a library OrderedMap to you.
In fact, there are similar data structures in other programming languages, such asLinkedHashMap in java and OrderedDict in python.
This article describes how to implement such a data type in Go language. Note that what we want to implement is OrderedMap, not SortedMap or TreeMap. When traversing SortedMap, it traverses according to the sorting order of Keys. We can first obtain all keys and sort them, and then access the corresponding values one by one.
But if the order of insertion is maintained when OrderedMap is traversed, how can this be done?
Let’s take a look at the functions of OrderedMap. It must have the function of HashMap to quickly get a key-value pair and maintain the insertion order. Then we can achieve it through combination.
- The function of HashMap: realized by the built-in map
- Preserve insertion order: This could have been implemented with
container/list, but to support generics we usegithub.com/smallnest/exp/container/list.
The following is OrderedMap data structure, which contains two fields, entries and list . entries is a map, its value type is *Entry ; the element in list is *Entry , and the value in the map points to the same element:
|
1
2
3
4
|
type OrderedMap[K comparable, V any] struct {
entries map [K]*Entry[K, V]
list *list.List[*Entry[K, V]]
}
|
The definition of Entry is as follows. In addition to containing Key and Value values, it also contains a list of Element elements, so that it implements a double-line linked list, and each Entry can find its predecessor and successor:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
twenty one
twenty two
twenty three
twenty four
25
26
27
28
|
// Entry is a key-value pair in OrderedMap.
type Entry[K comparable, V any] struct {
Key K
Value V
element *list.Element[*Entry[K, V]]
}
// Next returns a pointer to the next entry.
func (e *Entry[K, V]) Next() *Entry[K, V] {
entry := e. element. Next()
if entry == nil {
return nil
}
return entry. Value
}
// Prev returns a pointer to the previous entry.
func (e *Entry[K, V]) Prev() *Entry[K, V] {
entry := e.element.Prev()
if entry == nil {
return nil
}
return entry. Value
}
|
When adding and deleting, we need to operate on both fields to maintain consistency:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
twenty one
twenty two
twenty three
twenty four
25
|
func (m *OrderedMap[K, V]) Set(key K, value V) (val V, existing bool ) {
if entry, existed := m.entries[key]; existed { // If the key exists, it is updated
oldValue := entry. Value
entry.Value = value
return oldValue, true
}
entry := &Entry[K, V]{
Key: key,
Value: value,
}
entry.element = m.list.PushBack(entry) // Add to the linked list
m.entries[key] = entry // add to map
return value, false
}
func (m *OrderedMap[K, V]) Delete(key K) (val V, existing bool ) {
if entry, existed := m.entries[key]; existed { // if exists
m.list.Remove(entry.element) // remove from the linked list
delete (m.entries, key) // delete from map
return entry. Value, true
}
return
}
|
When searching, you can directly search the map, and there is no loss in performance:
|
1
2
3
4
5
6
7
|
func (m *OrderedMap[K, V]) Get(key K) (val V, existing bool ) {
if entry, existed := m.entries[key]; existed {
return entry. Value, true
}
return
}
|
When traversing, traverse the linked list structure because it maintains the insertion order:
|
1
2
3
4
5
6
7
8
9
10
|
func (m *OrderedMap[K, V]) Range(f func (key K, value V) bool ) {
list := m.list
for e := list.Front(); e != nil ; e = e.Next() {
if e. Value != nil {
if ok := f(e.Value.Key, e.Value.Value); !ok {
return
}
}
}
}
|
This is the main method of this data structure. Of course, it also provides more methods, such as the oldest value, the latest value, random traversal, etc. If you have a corresponding demand scenario, you can consider using it.
This article is transferred from: https://colobu.com/2023/06/18/a-generic-sortedmap-in-go/
This site is only for collection, and the copyright belongs to the original author.