POABOB

小小工程師的筆記分享

0%

Golang map 如何順序讀取

發表於 更新於 分類於

前言

在資料結構中，我們很常使用 Hash Map 來儲存 Key-Value 的資料，但是當我們想使用 for range 將資料一一讀出的時候，就會發現每次執行所讀出來的順序皆不同。

那麼要如何確保讀出值的順序是依照自己的需求呢？本篇文章將會告訴您如何去順序讀取 Hash Map 裡頭的資料。

範例

當我們在 go-playground 執行以下程式碼的時候，會發現每次執行順序皆不一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import "fmt"

func main() {
	m := map[string]int{
		"Alice":  1,
		"Bob": 2,
		"Cindy": 3,
		"Duke":  4,
  }

  for k, v := range m {
     fmt.Printf("key=%s, value=%d\n", k, v)
  }
}
// key=Bob, value=2
// key=Cindy, value=3
// key=Duke, value=4
// key=Alice, value=1

解釋

因為 Golang 的 map 是使用 Hash Table 透過 Bucket 來實現的，每次我們在插入的時候，map 就會 對 key 進行 Hash 運算，導致遍歷的順序不會按照 Key 的順序。

然而，每次當我們的 map 進行 擴充 時，就有可能讓原本同一個 bucket 的 key 更換到其他 bucket。

最後，為了避免 Hash-Flooding Attack 的問題發生，在設計 map 的時候就注定不會從第 0 號的 bucket 開始，而是使用 seed 參數讓順序更加隨機。

Hash-Flooding Attack：如果惡意使用者連續插入 n 個 相同 key 的 Hash 值 到 map 之中，就會導致 同一個 Bucket 中有 n 個 Value，查找的時間複雜度也會變成 O(n)，導致查找性能下降。

a.png

解決方法

普通解法

建立一個 Slice 來存放 map 的所有 key，然後在 對 Slice 中的 key 進行排序，最後 使用 Slice 來順序讀取出 map 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package main

import (
  "fmt"
  "sort"
)

func main() {
  m := map[string]int{
    "Alice":  1,
    "Bob": 2,
    "Cindy": 3,
    "Duke":  4,
  }
  
  // keys 存放順序的 key
  keys := make([]string, 0, len(m))
  for k := range m {
    keys = append(keys, k)
  }

  // 排序
  sort.Strings(keys)

  // 根據 keys 順序來輸出 map 的值
  for _, k := range keys {
    fmt.Printf("key=%s, value=%d\n", k, m[k])
  }
}

封裝 map

首先，我們可以定義一個 OrderMap 的 Class，其中為了讓我們可以順序讀取，這便定義了 keys 來存放 key，並且使用泛型 OrderMap[K constraints.Ordered, V any] 方便各種型別可以直接使用。

這邊使用 constraints.Ordered 的原因是我們在排序時，會使用到比較符號 >、>=、<=、<，如果只使用 any 或 comparable 會報錯，如下：
invalid operation: k[i] < k[j] (type parameter K is not comparable with <)

再來，初始化時先為 keys 做排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package utils

import (
  "sort"

  "golang.org/x/exp/constraints"
)

type OrderMap[K constraints.Ordered, V any] struct {
  // 儲存升序的 key 值
  keys []K
  // 原本的 map
  originMap map[K]V
}

// NewOrderMap 實例 OrderMap
func NewOrderMap[K constraints.Ordered, V any](m map[K]V) *OrderMap[K, V] {
  // 排序 keys 值
  k := make([]K, 0, len(m))
  for key := range m {
    k = append(k, key)
  }

  sort.Slice(k, func(i, j int) bool {
    return k[i] < k[j]
  })

  return &OrderMap[K, V]{
    keys:      k,
    originMap: m,
  }
}

建立 Get 函數，相當於 map[key]，還有可以返回 升序、降序 keys 陣列的函數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Get 獲取 Value，相當於 v, ok := o.originMap[key]
func (o *OrderMap[K, V]) Get(key K) (V, bool) {
  v, ok := o.originMap[key]
  return v, ok
}

// GetAscKeys 獲取升序的 Key 值
func (o *OrderMap[K, V]) GetAscKeys() []K {
  return o.keys
}

// GetDescKeys 獲取降序的 Key 值
func (o *OrderMap[K, V]) GetDescKeys() []K {
  descKeys := make([]K, 0, len(o.keys))
  for i := len(o.keys) - 1; i >= 0; i-- {
    descKeys = append(descKeys, o.keys[i])
  }
  return descKeys
}

因為我們目的是要可以 使用 for 來遍歷，這邊分別建立了 升序、降序 map 的遍歷函數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// IterateInAsc 升序遍歷
func (o *OrderMap[K, V]) IterateInAsc(fn func(k K, v V)) {
  for _, k := range o.keys {
    fn(k, o.originMap[k])
  }
}

// IterateInDesc 降序遍歷
func (o *OrderMap[K, V]) IterateInDesc(fn func(k K, v V)) {
  descKeys := o.GetDescKeys()
  for _, k := range descKeys {
    fn(k, o.originMap[k])
  }
}

使用方法非常簡單，只要傳入執行的 func，就自動會幫你遍歷。

1
2
3
orderMap.IterateInDesc(func(k string, v int) {
  fmt.Printf("key=%v, value=%v\n", k, v)
})

最後一步，我們 map 也是需要 新增 Key-Value 和 刪除 功能，因為這邊我使用陣列的關係，為了更快速找出插入的位置，使用了 二元搜尋 O(logn) 的方式提高效率，再使用 Slice 的範圍操作，把插入或刪除以後的值補回來。

b.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Append 新增 Map 值，如果 key 重複就蓋過去
func (o *OrderMap[K, V]) Append(key K, value V) {
  // 重複的 key
  if _, ok := o.originMap[key]; ok {
    o.originMap[key] = value
    return
  }

  o.originMap[key] = value
  index := o.binarySearch(key) + 1
  if index == len(o.keys)-1 { // 要插入的 key 位置在最後面
    o.keys = append(o.keys, key)
  } else { // 要插入的 key 位置在 [0, len(o.keys) - 1)
    temp := make([]K, len(o.keys)-index)
    copy(temp, o.keys[index:])
    o.keys = o.keys[:index]
    o.keys = append(o.keys, key)
    o.keys = append(o.keys, temp...)
  }
}

// Delete 刪除 Map 值，有值就刪除，沒值就忽略
func (o *OrderMap[K, V]) Delete(key K) {
  if _, ok := o.originMap[key]; ok {
    delete(o.originMap, key)
    index := o.binarySearch(key)
    temp := o.keys[index+1:]
    o.keys = o.keys[:index]
    o.keys = append(o.keys, temp...)
  }
}

// binarySearch 搜尋 upper bound 的 index 位置
func (o *OrderMap[K, V]) binarySearch(key K) int {
  left, right := 0, len(o.keys)-1
  for right > left {
    mid := left + (right-left)>>1

    if key < o.keys[mid] {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return right - 1
}

完成之後，就可以直接引入來使用看看！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package main

import (
  "fmt"
  "github.com/POABOB/go-practice/order-map/v2/utils"
)

func main() {
  m := map[string]int{
    "Alice": 1,
    "Bob":   2,
    "Cindy": 3,
    "Duke":  4,
  }
  orderMap := utils.NewOrderMap[string, int](m)

  fmt.Println(orderMap.GetAscKeys())
  fmt.Println(orderMap.GetDescKeys())

  fmt.Println("====================")

  fmt.Println(orderMap.Get("Bob"))
  fmt.Println(orderMap.Get("Bob1"))

  orderMap.Delete("Bob")

  orderMap.Append("Eric", 5)
  orderMap.Append("Bobo", 6)
  orderMap.Append("Zack", 7)

  fmt.Println("====================")

  fmt.Println(orderMap.GetAscKeys())
  fmt.Println(orderMap.GetDescKeys())

  fmt.Println("====================")

  orderMap.IterateInAsc(func(k string, v int) {
    fmt.Printf("key=%v, value=%v\n", k, v)
  })

  fmt.Println("====================")

  orderMap.IterateInDesc(func(k string, v int) {
    fmt.Printf("key=%v, value=%v\n", k, v)
  })
}
// 結果
// [Alice Bob Cindy Duke]
// [Duke Cindy Bob Alice]
// ====================
// 2 true
// 0 false
// ====================
// [Alice Bobo Cindy Duke Eric Zack]
// [Zack Eric Duke Cindy Bobo Alice]
// ====================
// key=Alice, value=1
// key=Bobo, value=6
// key=Cindy, value=3
// key=Duke, value=4
// key=Eric, value=5
// key=Zack, value=7
// ====================
// key=Zack, value=7
// key=Eric, value=5
// key=Duke, value=4
// key=Cindy, value=3
// key=Bobo, value=6
// key=Alice, value=1

本篇文章的程式碼範例。

參考資料

  • https://golang.design/go-questions/map/unordered/
  • https://liangyaopei.github.io/2020/07/13/golang-map/
  • https://www.sobyte.net/post/2022-08/go-map/
------ 本文結束 ------