Java集合框架解析及常见数据结构

1.Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象

实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。

算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。

除了集合，该框架也定义了几个 Map 接口和类。Map 里存储的是键/值对。尽管 Map 不是集合，但是它们完全整合在集合中。

集合可以看作是一种容器，用来存储对象信息。所有集合类都位于java.util包下，但支持多线程的集合类位于java.util.concurrent包下。

2.数组与集合的区别如下：

1）数组长度不可变化而且无法保存具有映射关系的数据；集合类用于保存数量不确定的数据，以及保存具有映射关系的数据。

2）数组元素既可以是基本类型的值，也可以是对象；集合只能保存对象。

​ 3) 数组是java语言中内置的数据类型,是线性排列的,执行效率最快

3.Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue（Java5新增的队列），因此Java集合大致也可分成List、Set、Queue、Map四种接口体系，（注意：Map不是Collection的子接口）。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FUbZCmXC-1593789137356)(C:\Users\QZM\Desktop\2020-06-27_155028.png)]

4.ArrayList是使用JAVA的基本数组实现的动态数组集合，源码底层维护着List的容量与实际长度。

数组结构的特点:

查询快:数组的地址是连续的，通过索引 增删慢 :数组的长度是固定的，增加删除一个元素，必须创建一个新数组，把源数组的数据复制过来

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;//初始容量为10 /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {};//数组初始默认为空

ArrayList因为使用的基本数组，不像哈希数组一样需要考虑哈希碰撞问题，因此负载因子默认为1(即当元素个数超过数组容量时,进行扩容)。当List数组容量不够时才进行扩容，扩容的倍数为1.5倍。通过Arrays.copyOf方法，返回复制的新数组。Arrays.copyOf底层调用的System.arraycopy方法。

5.LinkedList是一个双向链表，其中节点用的是LinkedList的内部类。和数据结构中的链表差不多。可以用它实现栈和队列。

LinkedList继承于AbstractSequentialList，并且实现了Deque接口。 LinkedList包含两个重要的成员：header 和 size。 　　header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。

链表结构:优势劣势和数组相反

单链表

头结点不存储数据 其他节点存储的结构看下图 是数据加上下一个节点的地址

双向链表

特点:

查询慢:链表地址不是连续的，每次查询都不是从头开始查询增删快:链表结构增加或者是删除一个元素对链表整体结构没有影响，所以增删快链表中的每一个元素也称之为结点,一个结点包含了一个数据域（存储数据）,两个指针域(存储地址)

从源码中可以总结其特点:

LinkedList 是一个继承于AbstractSequentialList的双向链表。LinkedList 可以被当作堆栈、队列或双端队列进行操作。LinkedList 实现 List 接口，所以能对它进行队列操作。LinkedList 实现 Deque 接口，能将LinkedList当作双端队列使用。LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。LinkedList 实现java.io.Serializable接口，所以LinkedList支持序列化，能通过序列化去传输。 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first;//头节点 /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;//尾节点 public boolean add(E e) {//从尾节点插入 linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

值得一提的是ArrayList随机读的时间复杂度是O(1)，LinkedList是O(n)。而ArrayList在中间插入和删除的时间复杂度是O(n)，LinekdList在中间插入删除时间复杂度也是O(n)

(引入一个概念时间复杂度用时: O（1）< O（logn）< O（n）< O（n^2）)

详情可参考 :https://blog.csdn.net/qq_41523096/article/details/82142747

可以明显看出来ArrayList在插入删除上和LinkedList理论上所用的时间是一个级别的，但是ArrayList慢于LinkedList是因为在修改集合后需要进行其他数组数据的移动，而LinkedList则是查找节点花费了O(n)，不需要额外移动数据，所以在同样数据量时，LinkedList进行数据修改优于ArrayList。

HashSet底层new了一个HashMap，然后把数据存在了Key里。这就是Set的底层实现了。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); /** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() { map = new HashMap<>(); } public boolean add(E e) { return map.put(e, PRESENT)==null; }

总结–两者区别比较:

List 元素是有序的、可重复; Set 存放键值对，无序不重复。

ArrayList：线程不安全，查询速度快,底层数据结构是数组结构,扩容增量：原容量的 1.5倍,允许元素为null

ArrayList是某种程度上的哈希表，适合随机读，但是不适合在集合中间插入和删除（会造成后续数据的位移）。 而LinkedList适合在头尾部插入删除，不适合随机读。

HashSet：线程不安全，存取速度快,　底层实现是一个HashMap（保存数据），实现Set接口.默认初始容量为16,加载因子为0.75：即当元素个数超过容量长度的0.75倍 时，进行扩容,允许元素为null

6.HashMap是底层用哈希数组实现的Map。HashMap就是一个个Entry（Key-Value键值对）存储在一个哈希数组上（Entry是HashMap的内部类）。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; /** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16,默认初始容量必须是2的幂 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量为2的30次幂 /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } }

在JDK1.8中，HashMap关于取模运算还做了另一个优化。在JDK1.8之前，每次哈希数组扩容时，链表里的数据都会再次进行哈希运算。而在JDK1.8后，不需要再进行运算了，只需要在每个桶中选择一半数据往后移动oldLength位就行（oldLength是集合在扩容前的容量）。

哈希数组的使用不可避免的需要考虑哈希碰撞问题，在JDK里，使用的就是拉链法解决的哈希碰撞问题，因此每个哈希数组上的数组元素（又被称为桶——bucket），都是一个链表的表头。这样基本保证了HashMap的平均查找时间是O(1)。

但是当出现频繁哈希碰撞时，会导致某个链表过长进而导致了查找时间会趋近于O(n)。对此JDK原本的解决方案是设置负载因子为0.75。当哈希表总负载量达到0.75时，就会进行扩容，扩容为原本的2倍。这样当数据平均下来后，不太容易出现过长的链表（因为扩容会分解链表重新放入桶中）。但是这并没有解决特殊情况下查找效率的问题，只是让这种特殊情况更难以出现了。

因此在JDK1.8中又做出了改进，当某个桶中的链表的长度大于8时。链表会重构成一个红黑树。这样保证了HashMap的最坏时间复杂度也仅仅是O(logn)。同时负载因子引起的扩容也保证了红黑树的重构不会频繁发生，不会因为频繁建树导致过多的性能开销。

总结:

jdk1.8中HashMap底层是哈希表数据结构，数组+链表+红黑树，HashMap是线程不安全的，允许使用null键和null值，

HashMap根据键的HashCode值存储数据，具有很快的访问速度。

HashMap存入的键值对在遍历时的顺序是随机的。

HashMap不支持并发

(HashTable 线程安全，使用synchronized锁住全部数据，效率较低。)

(5)红黑树结构:

首先我们需要了解一下二叉查找树

二叉查找树是具有下列性质的一种树结构:

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

下图是一个标准二叉树:

为了解决上述情况,所以有了自平衡二叉树也就是红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

每个节点要么是黑色，要么是红色。

根节点是黑色。

每个叶子节点（NIL）是黑色。

每个红色结点的两个子结点一定都是黑色。

任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

下图是一个标准的红黑树

当我们在某一结点插入数据时(例如插入21),原本的树结构可能不再满足红黑树原则如下图所示

这里就要用到红黑树的自平衡算法了,红黑树自平衡有三种操作：左旋、右旋和变色。

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

变色：结点的颜色由红变黑或由黑变红。

红黑树概述引用自 : https://baijiahao.baidu.com/s?id=1641940303518144126&wfr=spider&for=pc