1.哈希表的介绍

在哈希表中插入、删除或查找一个元素都只需要O(1)的时间，因此经常被用来优化时间效率。

在Java中，哈希表有两个对应的类型，即HashSet和HashMap。

2.HashSet的应用

若每个元素都只有一个值，则用HashSet，如，HashSet在图搜索时经常用来存储已经搜索过的节点。
以下为HashSet的常用函数：

3.HashMap的应用

若每个元素都存在一个值到另外一个值的映射，那么就用HashMap。
以下为HashMap的常用函数：

可以基于数组实现哈希表。

4.题目

面试30-插入、删除和随机访问都是O(1)的容器

解题思路：
需要结合哈希表和数组的特性来设计数据容器。
采用长度可变的数组：

ArrayList list = new ArrayList();

其中删除操作若考虑O(1)的时间复杂度，因为不能保证删除的元素总在末尾，所以，将末尾的元素与要删除的元素换位置（单方面交换–看代码），然后删除末尾的元素，注意，都是从0开始。
提交的代码：

class RandomizedSet {HashMap map;//定义哈希表ArrayList nums;//定义长度可变的数组//初始化public RandomizedSet(){map=new HashMap<>();nums=new ArrayList<>();}//插入public boolean insert(int val){if(map.containsKey(val)){return false;}map.put(val,nums.size());nums.add(val);return true;}//删除public boolean remove(int val){if(!map.containsKey(val)){return false;}int loc=map.get(val);map.put(nums.get(nums.size()-1),loc);//数组中最后一个元素放在要删除的位置map.remove(val);//map中删除val对应的键值对nums.set(loc,nums.get(nums.size()-1));//数组中最后一个元素放在要删除的位置nums.remove(nums.size()-1);return true;}//返回一个随机数public int getRandom(){Random random=new Random();int r=random.nextInt(nums.size());//随机生成0-nums.size()-1中的数字return nums.get(r);}
}

ArrayList的用法