hash与动态数组

2017.5.3中午，lkb大犇传授了XD们两个新的数据结构------

哈希表、动态数组

    哈希表是一种数据结构（栈、队列也是数据结构）。我们通常会将它用在存储方面，如：

有n（n<=10^6）个数的数组a，a1….an<=10^9。要求统计出每个数在数组中是第几次出现的。

当然了，如果是数组计数的话是百分百爆空间的，我们以用到哈希表。哈希表就是将数据进行处理，存储到一个数组里。

打个比方吧，我们可以将数据取模。一般的，10^n+7 为质数，我们可以用它取模。比方：

        就像图片演示的，向7取模，在余数的点进行处理。

        但很明显，我们的图片中的1,8取摸都为1，导致了冲突，官方的语言称 哈希冲突 。当然，冲突是不可避免的，所以我们可以用方法来解决。

        拉链法：

                拉链法就是用到了动态数组。动态数组就相当于一个string一样的，给定多少用多少内存（当然，在很多的情况下还是会爆），一般大赛里存储时可能会浪费空间，而导致爆空间，但有了动态数组，就不会有数组浪费的情况。

                  那么，怎么拉法呢？

                 遇到冲突，我们可以将他往后拉多一个量，将我们的数据存进去。就像草图一样：

                  

                  就是这么简单。代码如下:

                 

                 

                各种处理方法：

                      测有多少个赋值变量：变量名.size()

                 卖广告:来自lty中犇的标程(经作者允许转载)：

                 

                 

                 懂得了动态数组，那么就会使用拉链法了吧。

                 (学习kb，好榜样····)