Java 数据结构基础知识（一）

一、数组与链表

数组

数组在内存中的存放

数组是java中的一种基本类型，他可以通过下标（地址）获得对用位置的数据，所以获得数组中第i个元素，其时间复杂度为O(1)，同理修改元素也一样。

总结：

• 创建数组时，必须声明其长度，所以数组的大小是固定的，我们无法动态更改，所以可能会产生许多的碎片，当然还会存在找不到足够的内存块，导致数组的创建失败。
• 获取或修改第i个元素时，时间复杂度为O（1），而数组对查询的表现一般，想要查找某个元素就必须要遍历，所以时间复杂度为O（n）。
• 数组的插入和删除元素操作也比较复杂，他需要从插入或删除的位置起到最后一个元素，一次向后或向前移动。而当数组存满后，无法进行插入操作。

一句话就是：大小固定，查改迅速，增删复杂，需要完整内存空间，容易产生内存碎片。

链表

链表是一种离散存储结构，其在内存中存储不是连续的，每个数据元素都通过一个指针指向其下一个元素的地址。根据指针域的不同，链表又分为单链表、双向链表、循环链表等，这里我们只分析单链表，如图：

单链表

相较于数组，链表的这种结构的特点又有不一样：

• 链表的大小可以动态改变，也没有链表长度这一说，不需要连续的内存空间
• 由于链表每个元素都分为数据域和指针域，所以每个元素占据的内存空间更大。
• 每个元素的指针域存放的都是下一个元素的数据域地址，所以要执行查找第i个元素只能从头开始遍历，需要i次操作
• 链表查找某个元素的时间复杂度为O（n），因为也需要遍历
• 链表的插入删除无疑会方便很多，他不会有数组那样大范围的影响，只需要处理一下插入或删除前后节点指针的指向，就可以完成操作。

数组与链表总结

• 数组按位置查找迅速，链表增删方便
• 数组是固定大小，链表可以随时扩充与缩减
• 链表每个元素占据内存略多于数组
• 数组和链表在查询方面表现都比较一般，耗时较长

二、哈希表与Hash函数

哈希表就是通过关键字来获取数据的一种数据结构，它通过把关键字映射为表中的位置来获取元素，这种映射主要是使用Hash函数。
Hash函数，实际上是建立起key值与int值映射关系的函数。这就好比我们每个人都有一个身份证号一样，无论是男是女，出生在何处，都可以通过身份证号来分辨，这就是把人的信息映射成一串数字的典型做法。Hash函数和此类似，不过是把任意的Java对象，映射成一个int数值，供哈希表使用。
而哈希表，就是一个数组，只是其元素不是按照数组的规则排列的。任何一个元素要放进哈希表中，都必须先通过Hash函数获取到一个int数值，这个数值经过处理后将作为它的存放位置，然后这个元素才能放进哈希表中。
可以发现，数组与哈希表的操作不同之处主要在于，前者是直接插入，后者需要通过Hash函数计算后再插入。可以通过下图对比来理解：

哈希表完全继承了数组的优点，又显著的提高了查询的速度，通过Hash函数使得查询速度达到了O(1)。既然有了哈希表，它这么优秀，为何还需要数组的存在呢？那是因为Hash表是有缺陷的，这个缺陷就是哈希碰撞。

哈希碰撞

Hash函数所做的事，就是无论什么对象，都根据一个规则映射为一个int值。被转换的对象有无数种可能，但是int的值是有限的，它只有2³²个，这样一来，必然会有不同的对象，映射得到相同的int值，这就是所谓的哈希碰撞。发生碰撞之后，就要把不同的元素插入到相同的位置，这时候单纯的使用一维数组已经无法满足需求了。

如何解决哈希碰撞

要解决哈希碰撞，我们可以想到多种解决方案。目前比较通用的方法，就是使用数组+链表组合的方式。当出现哈希碰撞时，在该位置的数据就通过链表的方式链接起来，如下图所示：

这是当前比较理想的方法，既继承了数组的优点，又在碰撞时继承了链表的优点，这也是哈希表强大的地方之一。在JDK1.7及之前的版本中，HashMap的存储结构和上图是一致的，在JDK1.8之后还加入了红黑树以进一步优化

哈希表特点

哈希表是一种优化存储的思想，具体存储元素的依然是其他的数据结构。设计良好的哈希表，能同时兼备数组和链表的优点，它能在插入和查找时都具备良好的性能。然而设计不好的哈希表，有可能会出现较多的哈希碰撞，导致链表过长，从而哈希表会更像一个链表。还有当数据量很大时，为防止链表过长，就需要对数组进行扩容，这时就涉及到了数组的拷贝，其对性能的影响也很严重，所以需要提前对可能的情况有良好的预测，才能真正发挥哈希表的优势