哈希表理论基础
一般来说哈希表都是快速判断一个元素是否出现在集合里。
哈希函数是把传入的key映射到符号表的索引上。
哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。
hashset
hashmap
java中的哈希知识
Java集合可以分为collection和map两种体系
List：元素有序、可重复
Set：元素无序，不可重复
hashset添加元素的过程，
预设一个数组空间存储，首先计算哈希值，通过哈希值确定存在数组空间的位置，然后位置冲突之后再比较哈希值和equals，位置冲突时以链表形式存
hashmap
Hashmap的底层实现原理
Jdk7
在实例化以后，底层创建了长度是16的一维数组entry[] table
Map.put(key1,value1)
首先调用key1所在类的hashcode计算哈希值，此哈希值经过某种算法计算后，得到在entry数组中存放的位置。如果此位置上的数据为空，则key1-value1添加成功
如果此位置数据不为空，比较key1与已存在数据哈希值。
如果哈希值都不相同，则添加成功
如果哈希值存在相同的情况，则比较equals，如果不一样，则添加成功，如果一样，使用value1替换原value值。
涉及到扩容问题，超过临界值并且要添加的位置不为空的时候扩容，默认的扩容方式扩容为原来的2倍
经典题目
- 数组作为哈希表：
长度有限，可能性有限，比如26个字母 - set作为哈希表
数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
所以此时一样的做映射的话，就可以使用set了。 - map作为哈希表
<key,value>结构