集合和映射的插入有序性

Question

在python中

s = set()
s.add(5)
s.add(3)
s.add(1)
s.add(2)
s.add(4)
print(s)

输出结果为[1,2,3,4,5]，说明跟插入顺序无关。

d = {}
d[5] = 5
d[3] = 3
d[1] = 1
d[2] = 2
d[4] = 4
print(d)

输出结果为{5: 5, 3: 3, 1: 1, 2: 2, 4: 4}，说明跟插入顺序有关。
另外我在浏览器使用javascript测试

const s = new Set()
s.add(5)
s.add(3)
s.add(1)
s.add(2)
s.add(4)
console.log(s)

输出结果为 Set(5) {5, 3, 1, 2, 4}，是跟插入顺序有关的。

const m = new Map()
m.set(5, 5)
m.set(3, 3)
m.set(1, 1)
m.set(2, 2)
m.set(4, 4)
console.log(m)

输出结果为 Map(5) {5 => 5, 3 => 3, 1 => 1, 2 => 2, 4 => 4}，是跟插入顺序有关的。

在java中，有TreeMap和HashMap。TreeMap是有序的，这个有序不是指key的有序吗？
为什么在python和javascript中是插入的顺序呢？并且python在set是无序的，javascript的set是有序的。

Answer 1

liuyubobobo 2022-06-28 01:44:08

set 和 map 都是抽象数据结构。只要能承载一个集合，就可以叫 set，只要能表达映射关系，就可以叫 map。具体，不同的数据结构，都可以实现出 set 和 map。数组可以，链表可以，红黑树可以，哈希表也可以。

set 和 map 没有有序和无序，具体的数据结构才有有序和无序。Java 中的 TreeSet 和 TreeMap，底层是红黑树，所以是有序的；HashSet 和 HashMap 底层是哈希表，所以是无序的。

==========

在 Python 中，无论是 set 还是 dict，都是无序的，底层实现都是哈希表。 

你的第一个例子只不过没有触发无序存储的条件而言。（解释起来有点而复杂了，和 python 实现 integer 的方式有关，而和数据结构无关。）但你可以试验一下下面的例子，结果应该是无序的：

s = set();
s.add(1000001)
s.add(2)
print(s)

python 中，当你声明 d = {} 的时候，d 是一个dict，底层也是哈希表，而非红黑树，所以是无序的。

对于 set 底层是哈希表，可以参考这里：https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset 

对于 map 底层是红黑树，可以参考这里：https://docs.python.org/3/library/stdtypes.html#mapping-types-dict

在 python 中，如果你想使用有序的 map，应该用 OrderedDict，可以参考这里：https://docs.python.org/3/library/collections.html#collections.OrderedDict

现在版本的 python 没有专门的 OrderedSet，但你可以非常容易地把 OrderedDict 当做 OrderedSet 用。只要存入的 key 都映射到 None 就好了。（也就是不影射任何东西。）

==========

js 我不熟悉，我也懒得查了，但我相信同理，js 的 set 底层不是有序的数据结构，也就是不是红黑树，而是其他无序的数据结构。

你要感兴趣可以自己在做一下调研，js 的 set 的底层实现到底是什么？

继续加油！：）

• 提问者 慕运维2948618 #1

  老师，貌似您误解我意思了，我指的是输出的顺序跟插入的顺序有关。我在回答里测试里10w数据量的数据，发现还是跟插入的顺序有关。希望老师看看。

• liuyubobobo 回复 提问者 慕运维2948618 #2

  if __name__ == "__main__":
  
      s = set();
      s.add(1000001)
      s.add(10001)
      s.add(2)
      print(s)
  
  用你的 python 版本测试一下，应该和插入序不同。基本上不会有数据结构保持插入序的，因为这没有意义。你的插入序如果对你的业务有意义的话，你在插入的时候，就已经把它整理成这个顺序了，用一个数组存储这个顺序就可以。

• 提问者 慕运维2948618 回复 liuyubobobo #3

  python的set是跟插入顺序无关的，但是我测试了dict是有关的，我在回答区贴了代码。我只是好奇为什么会保持插入的顺序呢？

点开查看后面2条评论

Answer 2

提问者 慕运维2948618 2022-06-28 10:56:27

import random


def shuffle(arr):
    for i in range(len(arr)):
        j = random.randint(0, i)
        [arr[i], arr[j]] = [arr[j], arr[i]]

# 生成列表
arr = list(range(100000))
# 打乱顺序
shuffle(arr)

# 创建字典
d = {}
for v in arr:
    d[v] = v

# 提取键，转为列表
arr2 = list(d.keys())

# 比较两个列表是否相等，返回True。
print(arr == arr2)

Answer 3

提问者 慕运维2948618 2022-06-28 10:44:08

function swap(arr, i, j) {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

function shuffle(arr) {
    for (let i = arr.length - 1; i >= 0; i--) {
        const j = Math.random() * (i + 1) | 0
        swap(arr, i, j)
    }
}

function generateOrderArray(n) {
    const arr = new Array(n)
    for (let i = 0; i < n; i++) {
        arr[i] = i
    }
    return arr
}

// 生成有序的数组
const arr = generateOrderArray(100000)
// 打乱顺序
shuffle(arr)

// 创建集合
const s = new Set()
// 加入集合
for (let i = 0; i < arr.length; i++) {
    s.add(arr[i])
}
// 将集合的值转为数组
const arr2 = [...s.keys()]
// 比较两个数组是否相等。这里打印true
console.log(arr.toString() === arr2.toString())