6.4 实例3
以平均时间复杂度 O （1）实现插入、删除和获取随机值

设计一个数据结构，以平均时间复杂度 O （1）支持所有以下操作。

❑insert（val）：将val插入集合（如果该项尚未存在）。

❑remove（val）：从集合中删除val（如果该项存在）。

❑getRandom：从当前元素集中返回一个随机元素（保证在调用此方法时至少存在一个元素），每个元素必须具有相同的返回概率。

思路：利用一个数组和哈希表来实现。调用insert函数的时候，如果此元素已经在数组中，则返回；否则，将其插入数组的末尾，同时记录其位置idx。删除元素的时候，利用哈希表以 O （1）的时间找到其位置，然后和最后一个元素互换位置，同时删除次元素。getRandom函数则根据数组大小，从中选取一个输出。

对于插入数字，以插入数字8为例，把数字8加入到数组的末端，同时利用哈希表记录数字8所在的索引位置，如图6-1所示。

对于删除数字，以删除数字1为例。首先利用哈希表找到1在数组中的索引位置2，以及最后一个元素8的索引位置7，得到最后一个元素是8。更新元素8所对应的索引位置为2，交换数字1和8，最后把1从数组中删除，如图6-2所示。

示例代码如下。