HashMap/HashSet
Basic
- insert, find, remove: O(1)
- 常用来优化contains,或者是否visited的情况
- HashMap中数据是用一个叫table的数组来存的，table的索引在逻辑上叫做“桶”(bucket)，它存储了链表的第一个元素。 HashMap有一个叫做Entry的内部类，它用来存储key-value对。table数组存的就是它。Entry用一个next属性实现多个Entry以单向链表存放，插入元素时，如果两条Key落在同一个桶，并且这两条key不equals,后入桶的Entry将next指向桶当前的Entry，否则后入桶的会将前面的给覆盖（确保key的唯一性）; 使用HashMap的时候最好使用泛型，如果key放的是自己的对象，最好重写equals()和hashcode()。
什么时候会使用HashMap？他有什么特点？ 是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
你知道HashMap的工作原理吗？ 通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
你知道get和put的原理吗？equals()和hashCode()的都有什么作用？ 通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
Collision
- open address
- when collision happens, keep finding the next empty position following certain pattern
- separate chaining
- create a LL for each hash value，当发生冲突时，将记录插入到链表中
Longest Consecutive Sequence
- 第一个想法是sort。排序后遍历即可，复杂度O(nlogn)
- 第二个想法是暴力，求出每个点的LCS，遍历每个点，对于每个点都往比他大的找，如果数组里存在这个点(HashSet)，则继续找同时更新currentLength
- O(n^2) 进一步优化，发现里面存在重复的计算，而真正起作用的只有连续序列中，最小的那个数，所以可以跳过所有比他大的数，因为不可能是全局最优解。于是这样的话，每个点只会被算到最多两次（一次是判断是否有比他小的树，一次是在构成LCS的时候），所以时间复杂度为O(n)
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums)
set.add(n);
int ans = 0;
for (int n : nums) {
int len = 1;
int temp = n;
while (set.contains(--n)) {
set.remove(n);
len++;
}
while (set.contains(++temp)) {
set.remove(temp);
len++;
}
ans = Math.max(ans, len);
}
return ans;
}
//跳过比他大的数，可以用
for
if (!set.contains(num-1))
while (set.contains(++num))