LeetCode 哈希表 380. 常数时间插入、删除和获取随机元素（设计数据结构 List HashMap底层时间复杂度）

take-it-easy 2020-07-06 原文

比起之前那些问计数哈希表的题目，这道题好像更接近哈希表的底层机制。

java中hashmap的实现是通过List<Node>,即链表的list，如果链表过长则换为红黑树，如果容量不足（装填因子下）则扩充数组容量。解决冲突的方式是直接接在对应位置的链表上。

首先看看哈希表几个操作的时间复杂度：

HashMap的新增：

计算key的哈希值
哈希值作为index，找到对应的数组位置
如果数组位置为空，直接存入
如果数组位置不为空，遍历该链表，插入末尾

这里考虑理想情况（无冲突），时间复杂度为O1

HashMap的删除，查询都是一样的理解，如果没得冲突，都是O1的复杂度。

如果冲突，可能出现On情况（链表），Ologn情况（红黑树）

返回随机元素，这个则不好实现，因为HashMap是无序的，又没得类似List那样的索引，很难返回一个random的值。

接着考虑的一个方式就是，能不能把HashMap的key以0，1。。。的方式存到一个数组中，用random得到一个随机的序号，然后在通过序号去找。

然而这里犯了一个错误。这样的方式其实无疑与把这个HashMap变成了一个LIst。当然插入是O1，但是删除则不好操作了。

第二个想法是Hashset，但问题其实也一样，这是一个无序的set，没办法搞random。这里的无序set指的是插入进去之后放到的位置就是hash算出来的位置，显然无法用随机的方式使得每一个元素返回的概率相同。

第三个想法则是List作为基础，再用HashMap来补缺陷。

LIst的操作复杂度：

append，直接在尾端加，O1
pop，直接去掉尾端，O1
特定位置插入/删除，都需要萝卜挪坑，On
访问特定位置元素，索引直接访问，O1
查，要跑一遍整个数组，On

所以Random很好做到，其余的需要用append和pop搞事

append需要去重，我们把索引和值分别存入HashMap作为辅助

这样要插入时，先用HashMap判断有无（O1），然后直接插尾端（O1）

删除稍麻烦一些，我们如果直接删除真正位置，则需要挪位置变为On

所以用HashMap找到位置后，将该位置和List末尾做交换，然后PoP，这样就是O1了。

class RandomizedSet {
  Map<Integer, Integer> dict;
  List<Integer> list;
  Random rand = new Random();

  /** Initialize your data structure here. */
  public RandomizedSet() {
    dict = new HashMap();
    list = new ArrayList();
  }

  /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
  public boolean insert(int val) {
    if (dict.containsKey(val)) return false;

    dict.put(val, list.size());
    list.add(list.size(), val);
    return true;
  }

  /** Removes a value from the set. Returns true if the set contained the specified element. */
  public boolean remove(int val) {
    if (! dict.containsKey(val)) return false;

    // move the last element to the place idx of the element to delete
    int lastElement = list.get(list.size() - 1);
    int idx = dict.get(val);
    list.set(idx, lastElement);
    dict.put(lastElement, idx);
    // delete the last element
    list.remove(list.size() - 1);
    dict.remove(val);
    return true;
  }

  /** Get a random element from the set. */
  public int getRandom() {
    return list.get(rand.nextInt(list.size()));
  }
}