Example
Solution
题目要求设计一个插入、删除、取随机值都为 $O(1)$ 的不包含重复值的 Set。
使用 ArrayList ，可以实现 $O(1)$ 的插入和取随机值（只需要用 Random 生成一个上界为 size 的索引值就可以取到随机的元素），但是元素是否重复的判断以及获取指定值的操作都需要从头遍历——也就是 $O(n)$ 。
为了避免遍历操作，我们可以用一个 HashMap 来记录元素的值和索引的对应关系。
那么删除操作应该怎么处理呢？我们知道 ArrayList 删除末尾元素不会引起 List 的移动，只需要 $O(1)$ 。因此需要想办法将要删除的元素和最后一个元素作交换。所以只需要用最后的元素覆盖被删除元素（幸好！map 记录了值的索引），然后在 map 中更新元素的新索引，最后删除 map 中被删除元素的记录以及 List 的最后一个元素即可。
总结
利用
ArrayList来保存元素，实现 $O(1)$ 的插入和取随机数。利用
HashMap来记录元素和索引的对应关系，避免遍历操作（空间换时间）。注意在删除的过程中，
List最后的值和被删除值交换，同时要更新map的记录。