hash系列集合的性能优化

hash系列的集合：

HashSet、LinkedHashSet 采用hash算法决定元素在集合中的存储位置

HashMap、LinkedHashMap、Hashtable 采用hash算法决定key在集合中的存储位置

hash表中可以存储元素的位置，被称为bucket（桶）。

在通常情况下，一个bucket里只存储一个元素，此时性能最好，可根据hashCode直接定位元素所在的bucket，获得元素。

但hash表的状态是open的，在发生hash冲突时，一个bucket中会存储多个元素，这些hash冲突的元素以链表形式存储在一个bucket中：

此时hash表性能会下降，根据hash算法确定bucket位置后，还要遍历链表，找到指定的元素。

如果我们重写了自定义类的hashCode()、equals()则不会出现hash冲突的情况，一个bucket里只会存储一个元素。

hash系列的集合都有以下属性：

capacity 容量，hash表中bucket的数量
initial capacity 初始容量，创建hash表时bucket的数量
size hash表中已装元素的bucket数量
load factor　　负载因子，等于size/capacity，即已装元素的bucket数占总bucket数的比例。0表示空的hash表，0.5表示半满的hash表。
负载极限　　0~1之间的一个float，表示当前hash表的最大填满程度，即允许的load factor的最大值。

创建hash表时，此hash表的内存就确定了，根据hash算法确定的是元素在此hash表中的位置。

往hash表中添加元素时，会先找到hash表中空的bucket，根据hash算法确定用哪个空的bucket来存储元素。

load factor较小时，添加元素时很容易找到空的bucket，hash冲突少（因为可用的空bucket很多），存储性能较高；已装元素的bucket少，很容易从中找到指定的元素，查找性能较高；但遍历集合（hash表）时，要过滤掉大量的空bucket，很花时间，所以遍历时比较慢。

当load factor达到设置的负载极限时，会发生rehashing（重哈希/再散列），hash表会自动成倍地增加容量（capacity），将原有的元素都移到新的hash表中（会重新分配存储位置），而此时原有的元素是极多的，这会增加很大的开销。

负载极限设置较高时，节省内存（空桶较少），但添加、查找元素效率较低，时间开销会增大；负载极限较低时，添加、查找元素效率较高，但会增加内存开销。默认为0.75，是时间、空间的折中，我们可根据需要自行设置。

如果我们一开始就知道要存储的元素个数，可以在创建hash表时就指定容量：元素总数/负载极限。这样避免了rehashing，节省了时间开销。且前中期hash表负载会很低，添加、查询效率极高。

hash系列集合都有的3个重载构造函数：

() //无形参，使用默认的capacity、负载极限（0.75）

(int capacity) //指定容量

(int capacity,float 负载极限)

巴特西