3回答

liuyubobobo

2022-06-28

已采纳

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 的底层实现到底是什么？

继续加油！：）

0

5

liuyubobobo

回复

慕运维2948618

明白了。以 python 为例，这是 python 从 3.6 开始更新了 dict 的实现，在具体实现上的一个细节。但是官方文档说得很清楚，这一特性不应该被依赖，因为未来可能被更改。（The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon）。具体可以参考这里：https://docs.python.org/3/whatsnew/3.6.html#whatsnew36-compactdict 现在版本的 dict 实现之所以保持了插入的顺序，是因为 dict 内部按照插入顺序排列了所有的元素，然后靠一个 indice 数组来指向每一个元素对应的哈希表的位置。这样做更加节省空间。同时要想遍历所有元素，就不需要去查找哈希表了。具体可以参考这篇文章：https://mail.python.org/pipermail/python-dev/2012-December/123028.html 但依然是，这只是当前版本的具体实现上的一个”特性“，而不应该被认为是 dict 应有的特性。 js 我不熟悉，你可以查一下 js 相关数据结构的内部实现原理。但我相信同理，这一特性有可能”暂时“成立，但不应该被依赖。如果你需要使用元素的插入序，应该自己单独创建一个描述这个顺序的数组，来组织相应的逻辑。 继续加油！：）

2022-06-28

共5条回复

慕运维2948618

提问者

2022-06-28

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)

0

0

慕运维2948618

提问者

2022-06-28

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())

0

0