解決Golang map range遍歷結果不穩定問題

Posted on by

閑言少敘，本文主要是想介紹一個Golang開發常見的一個問題。然而，此問題對於初學者來說卻經常容易陷入坑中。

問題

我在寫一段代碼時，使用瞭Golang的map數據結構，目的是想用map緩存計數結果。簡單來說map的鍵也是整型的，且以遞增順序存儲。我的最初想法是，在統計結束後，按照map中存儲的鍵有序輸出值。可是，當我運行程序時，結果並不是我想要的，而且有一定概率運行結果不同。

問題代碼

func sortByBits(arr []int) []int {
  var bitmap = make(map[int][]int, 0)
  // map緩存
  for i := 0; i < len(arr); i++ {
    bits := calBits(arr[i])
    if _, ok := bitmap[bits]; !ok {
      tmp := make([]int, 0)
      tmp = append(tmp, arr[i])
      bitmap[bits] = tmp
    } else {
      bitmap[bits] = append(bitmap[bits], arr[i])
      for j := len(bitmap[bits]) - 1;j > 0; j-- {
        if bitmap[bits][j] < bitmap[bits][j - 1] {
          bitmap[bits][j], bitmap[bits][j - 1] = bitmap[bits][j - 1], bitmap[bits][j]
        }
      }
    }
  }
  // 輸出
  var res []int
  for _, value := range bitmap {
    res = append(res, value...)
  }
  return res
}
func calBits(n int) int {
  sum := 0
  for n > 0 {
    if n & 1 == 1 {
      sum++
    }
    n = n >> 1
  }
  return sum
}

當發現這個問題後，我使用二維數組替換map，改造代碼如下：

改造代碼

func sortByBits(arr []int) []int {
  var bitmap = make([][]int, 0, 10000)
  // map緩存
  for i := 0; i < len(arr); i++ {
    bits := calBits(arr[i])
    if len(bitmap) <= bits {
      length := bits - len(bitmap) + 1
      for j := 0; j < length; j++ {
        tmp := make([]int, 0)
        bitmap = append(bitmap, tmp)
      }
    }
      
    if len(bitmap[bits]) == 0 {
      bitmap[bits] = append(bitmap[bits], arr[i])
    } else {
      bitmap[bits] = append(bitmap[bits], arr[i])
      for j := len(bitmap[bits]) - 1;j > 0; j-- {
        if bitmap[bits][j] < bitmap[bits][j - 1] {
          bitmap[bits][j], bitmap[bits][j - 1] = bitmap[bits][j - 1], bitmap[bits][j]
        }
      }
    }
  }
  // 輸出
  var res []int
  for _, value := range bitmap {
    res = append(res, value...)
  }
  return res
}
func calBits(n int) int {
  sum := 0
  for n > 0 {
    if n & 1 == 1 {
      sum++
    }
    n = n >> 1
  }
  return sum
}

代碼很簡單，問題也很簡單。原理就是Golang的map按鍵輸出結果是隨機的，這是語言本身的一個特性，或者說是”坑”。作為開發者，要熟練掌握語言最基本特性，才能開發出最穩健的程序。

補充：golang if _,ok:=range map; ok判斷key是否在map中

由於golang沒有提供item是否在array當中的判斷方法，如果程序裡面頻繁用到瞭這種判斷，可以將array轉化為以array當中的成員為key的map再用上面的方法進行判斷，這樣會提高判斷的效率。

判斷方法示例代碼

if _, ok := map[key]; ok {
//存在
}

如果每次都for循環，會影響性能！

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方，望不吝賜教。

推薦閱讀：