LeetCode通关：哈希表六连，这个还真有点简单
精品刷题路线参考：
哈希表基础
哈希表也叫散列表，哈希表是一种映射型的数据结构。
哈希表是根据关键码的值而直接进行访问的数据结构。
就好像老三和老三的工位：有人来找老三，前台小姐姐一指，那个像狗窝一样的就是老三的工位。
总体来说，散列表由两个要素构成：桶数组与散列函数。
桶及桶数组
散列表使用的桶数组（Bucket array ），其实就是一个容量为 N 的普通数组，只不过在这里，我们将其中的每个单元都想象为一个“桶”（Bucket），每个桶单元里都可以存放一个条目。
比如，所有的关键码都是整数，我们就可以直接将 key 为关键码的那个条目存放在桶单元 A[key]内；为了节省空间，空闲的单元都被置为 null。
例如，吴零、熊大、王二、张三、李四，我们可以把他们放到桶数组对应的位置。
那么查找的时候，我们根据对应的名字编号，直接去找数组的下标就行了，这样一来，时间复杂度就是O(1)。
但是老三表示，怎么会老有人的名字老叫什么三、什么四的，起码得叫个”阿刚”、”小明”吧。
那么问题来了，阿刚、小明我们应该放在哪里呢？他们没法直接放到桶数组的对应下标位置。
所以，就引入了我们第二个关键要素哈希函数。
哈希函数
为了让映射能推广到所有情况，我们需要借助哈希函数 hashFunction映射到桶数组对应的位置。
例如，我们上面说到的一些平平无奇的名字，阿刚、小明……我们要把它们映射到对应的桶中。
一般情况下，哈希函数通过对名字的HashCode进行运算，将名字映射到桶数组对应的索引。
哈希碰撞
我们最理想的情况，就是通过哈希计算，各个元素找到空闲的坑位，但是现实往往不那么尽如人意，有时候，会发现，心上的城，已经长满了别人家的青藤。
阿刚和小明映射到了同一个位置，但这个位置只能容下一个人，这就叫哈希碰撞。
所以为了尽可能避免哈希碰撞呢，就需要精心设计哈希函数，我们希望哈希函数满足以下要求：
- 必须是一致的
- 计算简单
- 散列地址分布均匀
哈希函数构造方法
哈希函数的构造方法有很多，如下图，有些方法见名知义，篇幅所限，就不多讲。
这里提一下HashMap的哈希函数：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
整个过程大概如下：
- 利用hashCode()方法获取int类型的hashCode
- hashCode的高16位和hashCode的低16位做一个异或运算
hashCode右移16位，正好是32bit的一半。与自己本身做异或操作（相同为0，不同为1）。就是为了混合哈希值的高位和地位，增加低位的随机性。并且混合后的值也变相保持了高位的特征。
- 32位int型hashCode范围过大，需要与桶数组长度取模运算，得到索引值
int index = hash & (arrays.length-1);
HashMap的哈希函数是非常优秀的设计，很值得学习。
处理哈希冲突的办法
即使再好的设计，也难免发生哈希碰撞。
那么，发生哈希碰撞，应该怎么处理呢？
拉链法
阿刚和小明在桶中发生了冲突，那我们在桶数组接一个小尾巴——用一个链表将他们俩存起来就可以了。
除了这个，还有啥办法呢？
唉，假如我们的桶数组还是有坑位，我们可以重新分配，这就是