87网站一起做天河网站建设信科网络
1.哈希表的介绍
在哈希表中插入、删除或查找一个元素都只需要O(1)的时间，因此经常被用来优化时间效率。
在Java中，哈希表有两个对应的类型，即HashSet和HashMap。
2.HashSet的应用
若每个元素都只有一个值，则用HashSet，如，HashSet在图搜索时经常用来存储已经搜索过的节点。
以下为HashSet的常用函数：
| 函数 | 功能 |
|---|---|
| add | 添加一个元素 |
| contains | 判断是否包含一个元素 |
| remove | 删除一个元素 |
| size | 返回元素的数目 |
3.HashMap的应用
若每个元素都存在一个值到另外一个值的映射，那么就用HashMap。
以下为HashMap的常用函数：
| 函数 | 功能 |
|---|---|
| containsKey | 判断HashMap中是否包括某个键 |
| get | 返回键对应的值，否则null |
| getOrDefault | 返回键对应的值，否则返回输入的默认值 |
| put | 添加一组映射，否则修改键对应的值 |
| putIfAbsent | 当键不存在时，添加一组映射 |
| remove | 删除某个键 |
| replace | 修改某个键对应的值 |
| size | 返回映射数目 |
可以基于数组实现哈希表。
4.题目
面试30-插入、删除和随机访问都是O(1)的容器
解题思路：
需要结合哈希表和数组的特性来设计数据容器。
采用长度可变的数组：
ArrayList list = new ArrayList();
其中删除操作若考虑O(1)的时间复杂度，因为不能保证删除的元素总在末尾，所以，将末尾的元素与要删除的元素换位置（单方面交换–看代码），然后删除末尾的元素，注意，都是从0开始。
提交的代码：
class RandomizedSet {HashMap<Integer,Integer> map;//定义哈希表ArrayList<Integer> 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的用法
