Hash表的基础知识
关于Hash表
哈希表(Hash Table)是根据关键码(key) 值(value)进行直接访问的数据结构。哈希表最大的优点是高效，在哈希表中插入、删除或查找一个元素都只需要O(1)的时间。因此，哈希表常用来优化时间效率。
哈希表的对应类型
在Java中,哈希表有两个对应的类型，即HashSet 和 HashMap。
关于HashSet
HashSet这个类实现了Set集合。这个类允许null。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
并且HashSet提供了三个构造函数：
- 1、第一个是无参构造函数，此函数会创建一个大小为16的容器，加载因子是0.75
public HashSet()
Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).
Set的子类大部分是无序的、不可重复(TreeSet是有序的)。
- HashSet：线程不安全，存取速度快，内部实现是HashMap的key entry
1、默认初识容量为16(为什么是16，16是2^4，可以提高查询效率，另外，32=16<<1,扩容只需左移，速度很快)。
2、加载因子为0.75：即为 元素个数 超过 容量长度的0.75倍时，进行扩容
3、扩容增量：增加一倍，HashSet的容量为16，一次扩容后时容量为32
那么接下来思考，容器怎么保证添加的元素不重复的呢？(由于Set取值的时候调用值本身来取值的，所以不能重复，如果重复了，根据值取的时候就不知道取哪一个。List是根据下标map是根据具体key取值)
接下来看一下HashSet的add方法：
这个方法实际上是添加的一个put方法，描述的意思是：向这个set集合中添加元素，如果这个元素没有在集合中则添加到这个集合中。如果这个集合已经存在元素调用将离开。
e是add添加的元素，而PRESENT 在HashSet中是这样定义的 private static final Object PRESENT = new Object();
- 2、public HashSet(Collection<? extends E> c)
构造一个包含指定集合中的元素的新集合 - 3、public HashSet(int initialCapacity)
构造一个新的空集合; 背景HashMap实例具有指定的初始容量和默认负载因子（0.75）。 - 4、HashSet(int initialCapacity, float loadFactor)
构造一个新的空集合; 背景HashMap实例具有指定的初始容量和指定的负载因子。