· 集合 set

集合是一个其内所存储的所有元素具有唯一性、随机性和无序性的复合型数据结构。

唯一性指所有元素不重复；

随机性指从集合中pop出一个元素时，集合内所有元素被pop出来的概率一样；

无序性指集合中的元素无序；

集合 set 这种数据结构被广泛引用，像python的set结构、redis的set结构 和 java 的 hashset结构，都具有上述特性。

下面我们通过一道题目看看 集合 set 结构如何实现。

力扣380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象

bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。

bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。

int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

实际上，集合的无序性和唯一性可以使用hashmap来实现，因为hashmap的key是无序的（准确的说是不按key的大小排序，而只按key被插入hashmap的时序排序），而且hashmap的key是唯一的，一个key不可能对应多个value。

以Go语言为例，用hashmap模拟一个整型集合，只需用hashmap的key存储集合的value，而hashmap的value存储空结构体即可。

type set map[int]struct{}

但是用 hashmap 实现的 set结构不具有随机性。原因很简单，随机选择一个元素需要用到类似于rand(n)的随机函数得到元素所在的位置（n是元素个数），而hashmap中的key是离散的，不是连续的。如果遍历hashmap并选择第rand(n)个元素作为元素是可以实现随机性的，但如此一来set集合的get方法复杂度就达到O(n)。

为了能实现O(1)的get，并且使用rand(n)获取随机元素的位置，元素必须是紧密存储的，因此需要用数组作为set的底层容器，通过数组 + rand(n) 实现set取出元素的随机性，通过hashmap实现set存储元素的无序性和唯一性。hashmap的key为集合的元素值，value为元素在数组的下标。

综上，set结构是一个 hashmap + 数组 的复合数据结构。

get() 操作只需从数组获取 arr[rand(n)] 元素即可获取到随机元素。

insert()操作只需往数组末尾添加元素，并在hashmap中添加元素。

delete()操作如果删除的是数组的中间元素，可以将数组的最后一个元素覆盖到被删除元素的位置，保持数组的元素依旧是紧密相连的。

代码实现如下：

import "math/rand"
type RandomizedSet struct {
    mp map[int]int
    arr []int
}
func Constructor() RandomizedSet {
    mp := make(map[int]int)
    arr := make([]int,0)
    return RandomizedSet{mp: mp, arr: arr}
}
func (this *RandomizedSet) Insert(val int) bool {
    _, ok := this.mp[val]
    if ok{
        return false
    }
    this.arr = append(this.arr, val)
    this.mp[val] = len(this.arr) - 1
    return true
}
func (this *RandomizedSet) Remove(val int) bool {
    _, ok := this.mp[val]
    if !ok{
        return false
    }
    valNum := len(this.arr)
    offset := this.mp[val]
    this.arr[offset], this.arr[valNum-1] = this.arr[valNum-1], this.arr[offset]
    this.mp[this.arr[offset]] = offset  // 修改被挪动位置的元素在mp中的值
    this.arr = this.arr[:valNum-1]  // 删除数组元素
    delete(this.mp, val)            // 删除hashmap元素
    return true
}
func (this *RandomizedSet) GetRandom() int {
    return this.arr[rand.Intn(len(this.arr))]
}

更多内容请关注微信公众号