关于set的实现原理问题

Question

老师您好，我想问一个非常基础的问题，关于set集合这种数据类型，底层的实现问题。

通过以往的学习和了解，集合的底层都是通过哈希表来实现的，当我们存或者取的时候，根据key计算出其对应数组的位置，该位置上可能是一个链表，然后再寻找链表中对应该key的value。

但是无论是哪种语言，或者是redis中，set都实现了一个方法叫pop，也就是随机取出一个值，这种对于set结构，他随机取出其中一个值是如何来实现的呢？还是说，每个set都维护了一个值，来表示这个set内部数组第一个有数值位置的索引，所谓随机取出只是取出了该第一个索引位置的第一个key

Answer 1

liuyubobobo 2020-06-05 13:16:18

标准的 set 是没有“随机取一个值”这个方法的。可以参考 C++ 或者 Java 的 set 文档（无论有序无序）。

我不确定 redis，但因为 redis 内部使用的是跳表（而不是哈希表），所以可以随机取一个数。

继续加油！：）

• 提问者 烈焰卡卡 #1

  哦哦那我明白了。。。平时用redis和python都比较多，这俩都实现了随机取的方法，应该是在标准set上又封装了新的方法，谢谢老师

• liuyubobobo 回复 提问者 烈焰卡卡 #2

  python 的 pop 就是遍历，具体维护记录一个指纹，通过这个指纹获得一个哈希值，从这个哈希值开始找，找到第一个值就返回。更具体的我也没有仔细研究过，可以参考这里的 set_pop：https://hg.python.org/releasing/3.6/file/tip/Objects/setobject.c

• 提问者 烈焰卡卡 回复 liuyubobobo #3

  明白了，我后来也琢磨了一下，所谓pop应该不是类似随机数一样的随机，而是通过某种方法定位到其中第一个或某个位置，然后取出