数组，链表和哈希表的区别

首先，我们来说一下数组，在任何一种开发语言中，数组是最常用的一种数据结构，它的存储数据，是放在一块连续的内存空间中。在使用它时，需要先指定数组的类型和数量，然后根据这两个值，来确定需要的内存大小，比如我们定义一个int类型的数组Data，数量为21个，在linux系统中，int型占4个字节，所以整个数组所占的内存大小为84个字节，如果起始内存地址为0x1000，则末尾地址为0x1023，如下图所示

然后，我们来看一下链表，与数组相比，链表不需要预先指定数量，它的每一项数据，还不用存放在连续的内存空间中，乍看起来，优点很多，但它的缺点也很明显，如果要定位链表中靠后的数据，它只能从第一项开始遍历，直到获取想要的数据项。

链表的每项数据，一般由保存数据和下一项位置信息两部分组成，通过指定下一项数据的地址空间，我们将整个链表像链条一样串了起来，这就是链表的名称由来，下面我们用图片来更形象地表述一下链表的特征

最后，我们来看一下哈希表，结合前面的数组和链表，我们既想灵活地存储数据，又想快速地定位数据，因此哈希表应运而生，哈希表从表象上来说，就是先定义一个数组，存放关键码的映射，然后再用链表，完成相同关键码的数据存放，具体的图片表述如下

链表中的数据，是以键值对的形式存取的，即key=>value，一个key经过一定的映射，能变换为key数组中的特定索引值，然后根据索引值再获取所在链表的起始地址，当数据分布足够分散时，即一个key只对应一个数据，则查寻任何数据，都仅需要一次索引变换即可完成，检索速度相比链表，有了质的提升。