# 常数时间插入、删除和获取随机元素
设计一个支持在平均时间复杂度`O(1)`下，执行以下操作的数据结构。
* `insert(val)`: 当元素`val`不存在时，向集合中插入该项。
* `remove(val)`: 元素`val`存在时，从集合中移除该项。
* `getRandom`: 随机返回现有集合中的一项，每个元素应该有相同的概率被返回。


## 示例

```
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();
```

## 题解

```javascript
/**
 * Initialize your data structure here.
 */
var RandomizedSet = function() {
    this.hashTable = {};
    this.arr = [];
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(this.hashTable[val] !== undefined) return false;
    this.hashTable[val] = this.arr.length;
    this.arr.push(val);
    return true;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(this.hashTable[val] === undefined) return false;
    var index = this.hashTable[val];
    var key = this.arr[this.arr.length-1];
    this.hashTable[key] = index;
    delete this.hashTable[val];
    this.arr[index] = key;
    this.arr.pop();
    return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    return this.arr[~~(Math.random() * this.arr.length)];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
```

## 思路
题目要求实现对于插入与删除操作时间复杂度为`O(1)`的数据结构，很容易联想到链表与哈希表，题目还要求随机返回值的时间复杂度也是`O(1)`，而单纯的链表与哈希表都无法满足这个要求，且在给定值的情况下链表的查找时间复杂度为`O(n)`，不适用于本题，所以需要使用哈希表配合数组来实现，将值作为哈希表的`key`，在数组中的索引作为哈希表的`value`，这样对于`insert`与`getRandom`操作的时间复杂度都是`O(1)`，对于`remove`操作需要将传入的`value`在数组中的索引值取出，然后将数组中最后一个值覆盖到这个索引，然后更改最后一个值在哈希表中的索引，最后删除数组中最后一个值以及哈希表中该值作为的`key`，这样就实现了`O(1)`复杂度的`remove`操作。首先在构造函数定义对象作为哈希表以及数组，在`insert`操作中，如果哈希表中已存在该值，则直接返回`false`，如果不存在则添加该值到哈希表作为`key`并将数组的长度作为值，在数组后追加该值，返回`true`，在`remove`操作中首先判断如果不存在该值则直接返回`false`，如果存在值则取出该值的`index`，然后将数组的最后一个值取出并在哈希表中将该值作为`key`，将`index`作为值，即将最后一个值覆盖到要删除的位置，然后将哈希表中要删除的值的索引删除，将数组的该值位置覆盖为最后一个值，然后删除数组中最后一个值，在`getRandom`操作中直接返回一个随机的数组值即可。


## 每日一题

```
https://github.com/WindrunnerMax/EveryDay
```

## 参考

```
https://leetcode-cn.com/problems/insert-delete-getrandom-o1
```