哈希表

哈希表

描述：

​ 将较大的数值映射到较小的数组下标里。

核心思路：

1、开放取址法
可以怎么去理解呢？
每次先找到插入数或者查找数的映射值，然后从该映射值开始找
插入的时候往后找空位，如果找到了空位，就停止，返回空位的下标
查询的时候，往后找，一个一个对比是否存在查找的数，直至查到空位位置，说明不存在这个数，
因为每一个数，一定是存在其映射数后面的，如果找到了空位，说明映射到这个数的后面的数已经找完了，说明不存在该数

需要注意的是：数组长度最好开到题给的2~3倍
实现：
（1）映射数： t = (x % N + N) % N;
（2）这里将查找和插入进行同步操作：
while (h != null && h[t] != x)
没有找到需要的东西（插入：空位，查找：相同的值或者空位）就继续查找：t ++;
找了数组末尾没有找到，就从数组开头继续查找 if (t == N) t = 0;
（3）最后返回目标下标即可 return t

代码模板：

int find(int x) //返回 查找后或者放入后x的位置
{
    int t = (x % N + N) % N; //哈希函数，将大范围的值，全部映射到数组下标内

    while (h[t] != null && h[t] != x)   //如果当前位置已经有值了，并且不等于那个值
    {
        t ++;   //往后找
        if (t == N) t = 0; //找到了最后，仍然没有找到，从头开始找
    }
    return t;   //返回x的位置
}