关于set的实现原理问题

来源：4-1 set的使用 Intersection of Two Arrays

烈焰卡卡

2020-06-05

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

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

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

写回答

1回答

liuyubobobo

2020-06-05

已采纳

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

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

继续加油！：）

烈焰卡卡

liuyubobobo

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

2020-06-05

共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1