1 简介

为什么map数据结构在大多语言是无序？本文通过一些计算例子说明和帮助理解。

通过一个具体的例子来说明 哈希值的计算是基于键的内容，而不是插入顺序。

示例：假设我们有一个 map，它的键是字符串，值是整数。我们将通过计算每个键的哈希值来展示 map 中的元素是如何存储的。

2 计算原理和示例

• 哈希表的基本原理

哈希表通过一个 哈希函数 将键映射到哈希表的桶（bucket）中。哈希函数通常会根据键的内容来生成哈希值。这个哈希值决定了键在哈希表中的存储位置。因此，不同的键（即使它们的插入顺序不同）会根据它们的哈希值映射到不同的位置。

• 简单的哈希示例：

为了简化，假设我们有一个简单的哈希函数，它将键字符串的字符编码值的总和作为哈希值。实际的哈希函数在 Go 中要复杂得多（使用更精确的算法），但我们通过这个简化版来展示哈希值是如何计算的。

假设我们的 map 中有以下键值对：

    m := map[string]int{
        "apple":  1,
        "banana": 2,
        "pear":   3,
        "orange": 4,
    }

我们简单的哈希函数是将每个字符的 ASCII 值相加，作为键的哈希值：

  func simpleHash(key string) int {
      sum := 0
      for i := 0; i < len(key); i++ {
          sum += int(key[i])
      }
      return sum
  }

• 计算每个键的哈希值

现在我们计算每个键的哈希值：

“apple” 的哈希值：

    a 的 ASCII 值是 97

    p 的 ASCII 值是 112

    p 的 ASCII 值是 112

    l 的 ASCII 值是 108

    e 的 ASCII 值是 101

总和：97 + 112 + 112 + 108 + 101 = 530

“banana” 的哈希值：

b 的 ASCII 值是 98

a 的 ASCII 值是 97

n 的 ASCII 值是 110

a 的 ASCII 值是 97

n 的 ASCII 值是 110

a 的 ASCII 值是 97

总和：98 + 97 + 110 + 97 + 110 + 97 = 609

“pear” 的哈希值：

p 的 ASCII 值是 112

e 的 ASCII 值是 101

a 的 ASCII 值是 97

r 的 ASCII 值是 114

总和：112 + 101 + 97 + 114 = 424

“orange” 的哈希值：

o 的 ASCII 值是 111

r 的 ASCII 值是 114

a 的 ASCII 值是 97

n 的 ASCII 值是 110

g 的 ASCII 值是 103

e 的 ASCII 值是 101

总和：111 + 114 + 97 + 110 + 103 + 101 = 636

3 模拟哈希表存储

假设我们的哈希表容量只有 10 个桶（显然，这只是一个简化的例子，实际哈希表的容量通常会更大）。

我们通过计算每个哈希值模上哈希表的大小来确定键应该放在哪个桶中：

		bucketCount := 10

“apple” 的哈希值是 530，530 % 10 = 0，所以它存储在桶 0。

“banana” 的哈希值是 609，609 % 10 = 9，所以它存储在桶 9。

“pear” 的哈希值是 424，424 % 10 = 4，所以它存储在桶 4。

“orange” 的哈希值是 636，636 % 10 = 6，所以它存储在桶 6。

• 分析哈希值与插入顺序的关系

在我们的哈希示例中，即使我们按照不同的顺序插入这些键值对，map 中的元素在哈希表中的存储顺序也不会按照插入顺序进行排列，而是基于哈希值来决定存储位置。

例如：

如果我们先插入 apple，再插入 banana，再插入 pear，再插入 orange，哈希表中每个元素的位置依然是根据它们的哈希值来决定的。

无论它们的插入顺序如何，哈希表的存储位置（桶的索引）都是固定的：apple 存在桶 0，banana 存在桶 9，pear 存在桶 4，orange 存在桶 6。

• Go 中 map 的无序性

在 Go 中，map 的无序性源于哈希表的工作方式。哈希表不保留元素的插入顺序，而是根据 哈希值 来存储元素。因此，当我们遍历 map 时，遍历的顺序是由底层哈希表的实现和哈希冲突的处理决定的。

例如，使用 Go 内置的 map：

    m := map[string]int{
        "apple":  1,
        "banana": 2,
        "pear":   3,
        "orange": 4,
    }

    for k, v := range m {
        fmt.Println(k, v)
    }

每次输出的顺序可能都会不同，因为哈希表并不保证输出时的顺序。即使我们知道 apple、banana、pear 和 orange 的哈希值，它们在哈希表中的存储顺序还是会受哈希函数和底层数据结构的影响。

4 小结

哈希值的计算是基于键的内容，与键的插入顺序无关。

哈希表通过哈希函数将键映射到桶中，决定了键的存储位置。

哈希表不保留元素的插入顺序，遍历 map 时的顺序是由哈希表内部的实现和哈希冲突的处理方式决定的。

如果需要保证顺序，可以将 map 的键提取到切片并进行排序，或使用第三方库来实现有序的 map。

希望这个例子能帮助你理解哈希值的计算与存储顺序之间的关系