java源码之数组、链表与哈希表
数组
在java中，数组定义为一种基本类型，其可以通过下标获取到对应位置的数据。数组在内存中是一段连续的存储单元，每个数据依次放在每个单元中。分析这种结构，可以得出以下几个结论：
- 创建一个数组，必须声明其长度，以在内存中寻找合适的一段连续存储单元。这也意味着数组的大小是固定的，我们无法动态调整其大小。
- 想要获取数组中第i个元素，其时间复杂度是 O(1)，因为可以根据其地址直接找到它。同理修改也是。
- 数组对查询表现一般，要想查找一个元素，需要遍历，时间复杂度为O(n)。
- 因为地址连续，想要在数组中插入一个元素是复杂的，因为从插入位置起，后边的所有元素都需要向后移动一位。同理删除也是，只是移动方向为向前。并且，当数组存满时，就无法继续插入了。
- 因为数组要占据一整块内存，有可能产生许多的碎片，也可能因为找不到合适的内存块，而导致存储失败。
总结起来就是：数组大小固定，查找迅速，增删复杂，需要完整的内存块，容易产生碎片。
链表
链表是一种离散存储结构，其在内存中存储不是连续的，每个数据元素都通过一个指针指向其下一个元素的地址。根据指针域的不同，链表又分为单链表、双向链表、循环链表等。对于单链表而言，可以得出以下几个结论：
- 声明一个链表时，不需要知道其长度，也不需要连续的内存块，所以其大小可以动态调整。
- 链表的每个元素都分为数据域和指针域，前者是实际存储的数据，后者则指向下一个元素的地址。和数组相比，每个元素需要占用的内存更大了。
- 要获取链表的第 i 个元素变得复杂，因为其地址存放在它上一个元素的指针域里，所以只能从第一个元素起，进行 i 次操作。同理修改也是。
- 链表对查询表现也一般，需要遍历，时间复杂度为O(n)。
- 增加与删除一个元素更方便了，因为没有对内存地址的限制，我们只需要在对应节点合理处理下指针域的值，就可以把一个元素插入链表或者从链表删除。
- 链表对内存的要求很小，只要能够存储下一个数据元素的内存块都可以使用，因此不会造成碎片化。
总结起来就是：大小可以动态调整，增删迅速，查找较慢，数据元素所占内存略多，不需要整块内存块，不会造成碎片化。
数组与链表的选择
通过以上分析，数组和链表对我们影响最大的几点区别在于：
- 数组按位置查找迅速，链表增删方便
- 数组是固定大小，链表可以随时扩充与缩减
- 链表每个元素占据内存略多于数组
- 数组和链表在查询方面表现都比较一般，耗时较长
在数据量很小，内容基本固定时，选择何种数据结构的影响并不大。但当数据量较大时，如果我们需要对数据进行频繁的插入删除，就应该选择链表，如果我们需要频繁的获取某个位置的元素，就应该选择数组。数组与链表并没有明确的优劣之分，根据不同的使用场景进行不同的选择，才是这两种结构使用的最佳方式。
哈希表
无论是数组还是链表，其对数据的查询表现都比较无力，要想知道一个元素是否在数组或链表中，只能从前向后挨个对比。出现这个问题的根源在于，我们没有办法直接根据一个元素找到它存储的位置。哈希表就是解决查询问题的一种方案。
哈希表与Hash函数
通俗来讲，哈希表就是通过关键字来获取数据的一种数据结构，它通过把关键字映射为表中的位置来获取元素，这种映射主要是使用Hash函数。
Hash函数，实际上是建立起key值与int值映射关系的函数。这就好比每个人都有一个身份证号一样，无论是男是女，出生在何处，都可以通过身份证号来分辨，这就是把人的信息映射成一串数字的典型做法。Hash函数和此类似，不过是把任意的Java对象，映射成一个int数值，供哈希表使用。
而哈希表，就是一个数组，只是其元素不是按照数组的规则排列的。任何一个元素要放进哈希表中，都必须先通过Hash函数获取到一个int数值，这个数值经过处理后将作为它的存放位置，然后这个元素才能放进哈希表中。
哈希表完全继承了数组的优点，又显著的提高了查询的速度，通过Hash函数使得查询速度达到了O(1)。既然有了哈希表，它这么优秀，为何还需要数组的存在呢？那是因为Hash表是有缺陷的，这个缺陷就是哈希碰撞。
哈希碰撞
Hash函数所做的事，就是无论什么对象，都根据一个规则映射为一个int值。被转换的对象有无数种可能，但是int的值是有限的，它只有2^32个，这样一来，必然会有不同的对象，映射得到相同的int值，这就是所谓的哈希碰撞。发生碰撞之后，就要把不同的元素插入到相同的位置，这时候单纯的使用一维数组已经无法满足需求了。
目前比较通用的解决哈希碰撞的方法，就是使用数组+链表组合的方式。当出现哈希碰撞时，在该位置的数据就通过链表的方式链接起来，如下图所示：
这是当前比较理想的方法，既继承了数组的优点，又在碰撞时继承了链表的优点，这也是哈希表强大的地方之一。
在JDK1.7及之前的版本中，HashMap的存储结构和上图是一致的，在JDK1.8之后还加入了红黑树以进一步优化。
哈希表的优缺点
哈希表是一种优化存储的思想，具体存储元素的依然是其他的数据结构。设计良好的哈希表，能同时兼备数组和链表的优点，它能在插入和查找时都具备良好的性能。然而设计不好的哈希表，有可能会出现较多的哈希碰撞，导致链表过长，从而哈希表会更像一个链表。还有当数据量很大时，为防止链表过长，就需要对数组进行扩容，这时就涉及到了数组的拷贝，其对性能的影响也很严重，所以需要提前对可能的情况有良好的预测，才能真正发挥哈希表的优势。