数组, 链表, 哈希表

数组:

数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。
数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数，造成数组越界；当数据减少时，造成内存浪费。

特点:

  1. 数组是相同数据类型的元素的集合
  2. 数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起
  3. 数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。

    链表:

    集合 - 图1
    链表有很多种不同的类型：单向链表，双向链表，循环链表。
    链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
    使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

    特点:

    链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。因为数组中插入、删除数据项时，需要移动其它数据项，而链表的插入与删除时，只需要改变个别元素之间的关系即可，这大大提高了链表的删除与插入的速度。

    哈希表

    散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
    集合 - 图2
    左边是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

    特点:

    1) 访问速度很快

    由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。

    2) 需要额外的空间

    首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。

这个特点有个很常用的词可以表达，叫作“空间换时间”，在大多数时候，对于算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快些。

3) 无序

散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。

4) 可能会产生碰撞

没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。

集合概述

图示集合关系

Iterable, Collection 家族 (List, Set, Queue)

集合 - 图3

Map 家族

集合 - 图4

集合和数组的区别:

1. 长度区别

  • 集合长度可变

  • 数组长度固定

    2. 存储数据类型区别:

  • 数组可以存储基本类型, 也可以存储引用类型

  • 集合只能存储引用类型

    3. 存储元素内容区别:

  • 数组只能存储同一种类型

  • 集合可以存储不用类型 (不加泛型的前提下, 加泛型的话, 可以使用反射来添加不同类型的元素)

    Collection 中各常用集合的特点:

    List接口: 有序存储, 可重复

    ArrayList: 数组; 查询快，增删慢，线程不安全，效率高，可以存储重复元素

    LinkedList: 双向链表(1.6之前是循环, 1.7取消了循环); 查询慢，增删快，线程不安全，效率高，可以存储重复元素

    Vector: 数组; 查询快，增删慢，线程安全，效率低，可以存储重复元素

    Stack: 栈, 是Vector的子类, 先进后出, 后进先出, 线程安全

    Set接口: 不可重复, 做内部排序

    HashSet: 哈希表; 元素无序且唯一, 线程不安全，效率高, 可以存储null

    LinkedHashSet: 链表+哈希表; 链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高, 可存null

    TreeSet: 二叉树, 可以保证元素顺序, 要添加的元素必须实现Comparable接口, 否则报错

    Map接口: 键值对存储, 双列集合 (注意: Map 没有继承 Collection 接口)

    HashMap: 哈希表; Key 可以为null, 但只能有一个, value可以为null, 非线程安全

    注意: HashMap的get方法在没有查询到key所对应的value时, 也会返回null, 所以想要判断是否存在key, 应该使用 containsKey 方法

    LinkedHashMap: 双向链表+hash表;

    TreeMap: 红黑树, 要put的元素中key必须实现Comparable接口, 否则报错; 非线程安全

    HashTable: 哈希表; 线程安全; Key, Value 都不能为null

    源码分析(面试)

    ArrayList

    继承, 实现图

    集合 - 图5
    ArrayList继承于 **AbstractList** ，实现了 **List**, **RandomAccess**, **Cloneable**, **java.io.Serializable** 这些接口。

  • RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们可以通过元素的序号快速获取元素对象，这就是快速随机访问。

  • ArrayList 实现了 **Cloneable** 接口 ，即覆盖了函数clone()，能被克隆。

  • ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

    扩容机制★★★★★

    image.png

    多线程下不安全

    image.png
    红框中的其实是两句话, 非原子:
    element[size] = e;
    size++;
    所以会出现线程安全问题

    HashMap

    底层数据结构:

    在jdk1.7中底层是数组+链表, jdk1.8中是数组+链表/红黑树, 使用Node类来存储Key和Value

    Node 类

    集合 - 图8

    为什么需要链表?

    首先，数组的长度是有限的对吧，在有限的数组上使用哈希，那么哈希冲突是不可避免的，很有可能两个元素计算得出的 index 是相同的，那么如何解决哈希冲突呢？拉链法。也就是把 hash 后值相同的元素放在同一条链表上。比如说：
    集合 - 图9

    为什么jdk1.8要在特定条件下转为红黑树? 什么特定条件?

    当然这里还有一个问题，那就是当 Hash 冲突严重时，在数组上形成的链表会变的越来越长，由于链表不支持索引，要想在链表中找一个元素就需要遍历一遍链表，那显然效率是比较低的。为此，JDK 1.8 引入了红黑树，当链表的长度大于 8 的时候就会转换为红黑树，不过，在转换之前，会先去查看 table 数组的长度是否大于 64，如果数组的长度小于 64，那么 HashMap 会优先选择对数组进行扩容 **resize**，而不是把链表转换成红黑树。
    集合 - 图10

    JDK1.8下HashMap 的完整示意图

    集合 - 图11

    节点插入链表时, JDK1.7 和 JDK1.8的不同

    1.7 采用 头插法

    集合 - 图12

    1.8 采用 尾插法

    为什么不再用头插法而改用尾插法? JDK 1.7 中采用的头插法在多线程环境下可能会造成循环链表问题

    由于 JDK 1.7 中 HashMap 使用头插会改变链表上元素的的顺序，在旧数组向新数组转移元素的过程中修改了链表中节点的引用关系，因此 JDK 1.8 改成了尾插法，在扩容时会保持链表元素原本的顺序，避免了链表成环的问题

    数组扩容 resize()方法:

    何时扩容?

    1）Capacity：HashMap 当前最大容量/长度
    2）LoadFactor：负载因子，默认值0.75f
    如果当前存入的数据数量大于 Capacity * LoadFactor 的时候，就会进行数组扩容 resize。就比如当前的 HashMap 的最大容量大小为 100，当你存进第 76 个的时候，判断发现需要进行 resize了，那就进行扩容。当然，HashMap 的扩容不是简单的扩大点容量这么简单的。

    如何扩容? 分为两步:

    1）扩容：创建一个新的 Entry 或 Node 空数组，长度是原数组的 2 倍
    2）ReHash：遍历原 Entry 或 Node 数组，把所有的 Entry 或 Node 节点重新 Hash 到新数组

    为什么要 ReHash 呢？直接复制到新数组不行吗？

    显然是不行的，因为数组的长度改变以后，Hash 的规则也随之改变。index 的计算公式是这样的：
    index = HashCode(key) & (Length - 1)
    比如说数组原来的长度（Length）是 4，Hash 出来的值是 2 ，然后数组长度翻倍了变成 16，显然 Hash 出来的值也就会变了。画个图解释下：
    集合 - 图13

    初始化容量是多少? 有什么规定?

    初始化容量是16, 经验得来的, 最常用; 规定必须是2的次幂, 跟hash函数有关系, 为了能够均匀分布

    HashMap线程不安全的表现?

    关于 JDK 1.7 中 HashMap 的线程不安全，上面已经说过了，就是会出现环形链表。虽然 JDK 1.8 采用尾插法避免了环形链表的问题，但是它仍然是线程不安全的，我们来看看 JDK 1.8 中 HashMap 的 put 方法：
    集合 - 图14注意上图我圈出来的代码，如果没有发生 Hash 冲突就会直接插入元素。
    假设线程 1 和线程 2 同时进行 put 操作，恰好这两条不同的数据的 hash 值是一样的，并且该位置数据为null，这样，线程 1 和线程 2 都会进入这段代码进行插入元素。假设线程 1 进入后还没有开始进行元素插入就被挂起，而线程 2 正常执行，并且正常插入数据，随后线程 1 得到 CPU 调度进行元素插入，这样，线程 2 插入的数据就被覆盖了。
    总结一下 HashMap 在 JDK 1.7 和 JDK 1.8 中为什么不安全：

  • JDK 1.7：由于采用头插法改变了链表上元素的的顺序，并发环境下扩容可能导致循环链表的问题

  • JDK 1.8：由于 put 操作并没有上锁，并发环境下可能发生某个线程插入的数据被覆盖的问题

    如何保证 HashMap 线程安全？

    1）使用 java.util.Collections 类的 synchronizedMap 方法包装一下 HashMap，得到线程安全的HashMap，其原理就是对所有的修改操作都加上 synchronized。方法如下：

    public static Map synchronizedMap(Map m)

    2）使用线程安全的 HashTable 类代替，该类在对数据操作的时候都会上锁，也就是加上 synchronized

    3）使用线程安全的 ConcurrentHashMap 类代替，该类在 JDK 1.7 和 JDK 1.8 的底层原理有所不同，JDK 1.7 采用数组 + 链表存储数据，使用分段锁 Segment 保证线程安全；JDK 1.8 采用数组 + 链表/红黑树存储数据，使用 CAS + synchronized 保证线程安全。

    为什么HashTable和ConCurrtntHashMap不允许键值为null?

    处于多线程安全的考虑, 因为如果允许的话, 那么map.get(key)==null就会存在两种结果, 一是不存在该键值对, 二是该key对应的value就是null, 就需要再调用map.containsKey(key)再去判断是那种情况, 单线程下没有问题, 但是到了多线程下, 如果A线程调用map.get(key)==null, 正要调用map.containsKey(key)时, B线程正好map.put(key, null), 就会出现问题.

    HashMap和HashTable的异同点:

    1. 键值对是否为空: HashMap可以允许键值对为null, HashTable不允许

    2. 初始化容量: HashMap是16, HashTable是11; 两者的加载因子都是0.75

    3. 扩容机制不同: 当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1；

    4. 迭代器不同: 两者都有Iterator迭代器, 并且该迭代器是 fail-fast(快速失败) 的; 但是, HashTable还有另外一个迭代器, Enumeration, 这个是 fail-safe(失败安全) 的.

    介绍下 fail-safe 和 fail-fast 机制

    1）快速失败 fail-fast：一种快速发现系统故障的机制。一旦发生异常，立即停止当前的操作，并上报给上层的系统来处理这些故障。(java.util包下的集合都是快速失败的)

    个人理解: 在调用前尽可能的预先识别出一些错误信息, 一方面可以避免执行复杂的其他代码, 另一方面可以对预先识别的错误做一些针对性的处理; 例如java.util包下的集合, 当 Iterator 这个迭代器被创建后，除了迭代器本身的方法 remove 可以改变集合的结构外，其他的因素如若改变了集合的结构，都将会抛出ConcurrentModificationException 异常

    1. HashMap<String, String> map = new HashMap();
    2. map.put("a" , "a");
    3. map.put("b" , "b");
    4. Iterator<String> iterator = map.keySet().iterator();
    5. while (iterator.hasNext()) {
    6.   String key = (String) iterator.next(); // 执行删除后再遍历时, java.util.ConcurrentModificationException
    7.   if(Objects.equals("a", key)) {
    8.       map.remove(key);
    9.   }
    10. }
    11. // 第一次循环遍历的时候，我们删除了集合 key = "a" 的元素，集合的结构被改变了，
    12. // 所以第二次遍历迭代器的时候，就会抛出异常。

    2）失败安全 fail-safe：在故障发生之后会维持系统继续运行。(java.util.concurretnt包下的集合都是失败安全的)

    顾名思义，和 fail-fast 恰恰相反，当我们对集合的结构做出改变的时候，fail-safe 机制不会抛出异常。
    java.util.concurrent 包下的容器都是 fail-safe 的，比如 **ConcurrentHashMap**，可以在多线程下并发使用，并发修改。同时也可以在 for-each 增强循环中进行 add/remove。

    1. ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
    2. map.put("a", "a");
    3. map.put("b", "b");
    4. map.put("c", "c");
    5. Iterator<String> iterator = map.keySet().iterator();
    6. while (iterator.hasNext()) {
    7.   String key = (String) iterator.next();
    8.   if(Objects.equals("a", key)) {
    9.       map.remove(key);
    10.   }
    11. }
    12. for (String s : map.keySet()) {
    13.   System.out.println(s);
    14. }
    15. /**
    16. * 输出结果
    17. * b
    18. * c
    19. */

    为什么 fail-safe 不会抛出异常

    这是因为，当集合的结构被改变的时候，fail-safe 机制会复制一份原集合的数据，然后在复制的那份数据上进行遍历。因此，虽然 fail-safe 不会抛出异常，但存在以下缺点：

  • 不能保证遍历的是最新内容。也就是说迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的；

  • 复制时需要额外的空间和时间上的开销。

    fail-fast 的原理是什么

    从源码我们可以发现，迭代器在执行 next() 等方法的时候，都会调用 checkForComodification 这个方法，查看 modCount 和 expectedModCount 是否相等，如果不相等则抛出异常终止遍历，如果相等就返回遍历。
    集合 - 图15
    expectedModcount 这个值在对象被创建的时候就被赋予了一个固定的值即 modCount，也就是说 expectedModcount 是不变的，但是 modCount 在我们对集合的元素的个数做出改变（删除、插入）的时候会被改变（修改操作不会）。那如果在迭代器下次遍历元素的时候，发现 modCount 这个值发生了改变，那么走到这个判断语句时就会抛出异常。