1、非线性表之哈希表(散列表)

1、散列表-概述
    1-1、散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
        1-1-1、这个映射函数叫做散列函数/哈希函数，存放记录的数组叫做散列表/哈希表。
        1-1-2、每个关键字被映射到0到数组大小N-1范围，并且放到合适的位置，这个映射规则就叫散列函数
    1-2、散列/哈希碰撞/冲突    
        1-2-1、关键字范围可能远超数组单元，因此就会出现两个关键字散列到同一个值得时候
        1-2-2、解决方式
            -- 开地址法：数组中重新找位置保存数据(如果冲突发生，就选择另外一个可用的位置)
                -- 线性探测法-策略
                -- 平方探测法-策略
                -- 双散列-策略
            -- 拉链法：形成链表(将同一个值的关键字保存在同一个表中)
            -- 再散列

1.1、哈希冲突

1、哈希表的实现
    1-1、哈希表本质就是一个数组
    1-2、实现哈希表我们可以采用两种方法：
        1-2-1、数组 + 链表
        1-2-2、数组 + 二叉树
2、哈希冲突/哈希碰撞处理：
    2-1、链地址法
        2-1-1、当哈希冲突达到了一定的程度，java7为链表，java8是红黑树。
    2-2、开放地址法,比如：ThreadLocal
        2-2-1、当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
            -- 用公式描述为：
                H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))
                其中： H ( key ) 为关键字 key 的直接哈希地址， m 为哈希表的长度， di 为每次再探测时的地址增量。
采                用这种方法时，首先计算出元素的直接哈希地址 H ( key ) ，如果该存储单元已被其他元素占用，则继续查看地址为 H ( key ) + d 2 的存储单元，如此重复直至找到某个存储单元为空时，将关键字为 key的数据元素存放到该单元。
                增量 d 可以有不同的取法，并根据其取法有不同的称呼：
                    -- d i ＝ 1 ， 2 ， 3 ， …… 线性探测再散列；
                    -- d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列；
                    -- d i ＝ 伪随机序列 伪随机再散列；