Hash表

数组（顺序表）的特点：
寻址容易，插入和删除困难；
链表的特点：
寻址困难，插入和删除容易。
综合两者，做出一种寻址容易，插入删除也容易的数据结构：Hash表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度
关键码值(Key value)也可以当成是key的hash值
这个映射函数叫做散列函数
存放记录的数组叫做散列表

映射关系

Key : {14, 19, 5, 7, 21, 1, 13, 0, 18}
散列表: 大小为13 的数组 a[13];
散列函数: f(x) = x mod 13; (和13取余)
如：14和13取余就是1，这个1就是散列表(数组)的下标，即把value存储在数组下标为1的地方。但是key值为1的时候和13取余也是1，两个小标都是1，这就造成了冲突，就叫hash冲突。

解决冲突：

左边数组存储的是右边单链表的收个元素，下标相同的key存储在一个链表中。取的时候按照下标取到数组中的元素，这个元素也是链表的第一个元素，然后遍历链表得到具体的元素。
hash表的优点：
查找，插入，删除只需要接近常量的时间O(1),实际上就是几条机器指令。
哈希表在速度和易用性方面是无与伦比的
缺点：
基于数组的，数组创建后难于拓展，当hash表被基本填满后，性能下降非常严重，
所以要求程序员预先清楚表中存储多少数据。
因为数据量越满冲突发生的越多，所以在基本填满的时候性能下降的严重。
装填因子是：表中已经存入的数据元素个数n 与hash表地址空间大小m的比值。 n/m
一般填充因子在0.6~0.9 的范围内最佳
遍历HashMap得到的结果是无序的。
LinkedHashMap有序，在图中右边的链表中除了next指向下一个之外又多了两个指针after和before，这两个指针就是用来解决排序。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

获取元素的hash值，然后跟 之前的hash值友移后做与运算 ，其目的是为了让元素的hash算出来的索引比较均匀散列