Java常用的数据结构有哪些？

ArrayList(基于数组)、链表(基于双向链表，可以作为双端队列使用)、HashSet（去重）、TreeSet、HashMap、堆、栈（FILO）、队列（FIFO）、二叉树、红黑树、图…

ArrayList和LinkedList的区别

  1. 存储方式：<数组> 存储元素的方式是根据初始化容量分配一段连续的内存空间；<链表>存储节点的方式是在添加元素后才会分配内存空间用来存储节点的数据、前驱指针、后继指针，并且节点可以是不连续的，所以链表在初始化时并不会申请初始容量而且只开辟一个头节点的内存空间（头节点只是用来指向第一个节点，链表每个节点需要的空间是比数组大的）
  2. 初始化方式：<数组>初始化后会事先分配 默认/指定 的内存空间，申请的最大空间大小为整形的最大值；<链表>初始化时并不需要指定初始化容量，并且会在初始化时分配一个头指针空间，这个空间并不存储数据，只会有一个指向第一个节点的头指针。
  3. 扩容方式：<数组>扩容会发生在添加、插入元素并出现空间不足时会将当前空间乘于1.5倍的大小作为扩容后的大小，然后判断扩容后的空间是否足够，如果不足则按照这次操作需要的最大空间作为扩容大小，数组的扩容会有一次数组拷贝，数组拷贝主要是保证元素的准确性；<链表>的容量是比较灵活的，只有当有新元素插入时才会申请合适的内存进行分配，而且不会提前分配。
  4. 访问元素：<数组>在进行随机访问时由于在内存中是连续的，所以只需要先定位到数组头元素所在的内存地址并根据索引下标就可以很轻松的以big O(1)的复杂度访问元素；<链表>在进行遍历时由于节点之间的访问方式是通过前驱指针、后继指针来进行访问的，所以除头节点和末尾节点之外，访问中间节点的耗时都比数组要长

  5. 删除、插入元素：<数组>在进行删除、插入元素的操作时，由于其在内存中时连续的，所以进行操作的元素前面所有元素都要进行位移。如果插入后导致空间不足还进行一次数组拷贝。<链表>在每次插入新的节点时申请节点所需要的内存空间，保证了内存的高使用效率。由于链表存储的相邻元素使用指针串联的方式进行，所以当进行插入、删除元素时只需要进行big O(1) 的指针改写和申请、释放内存就行。

    ArrayList

  6. ArrayList继承自AbstractList，并且实现了List接口，他的底层是基于数组来实现容量大小动态变化的。并且其中的元素允许null值存在。除此之外，ArrayList还实现了RandomAccess、Cloneable、Serializable接口，所以也使得ArrayList支持快速访问、复制、序列化。但ArrayList是线程不安全的，如果会出现多线程访问数组的情况应该使用Vector

  7. ArrayList里定义了两种长度，一种是实际占用元素，另一种是允许的最大容量。如果在初始化时不指定初始容量也就是使用无参构造函数时是在第一次添加元素时初始化容量为 10 的。
  8. 如果后续添加元素时需要的容量超过了当前的容量就会触发扩容机制：ArrayList的扩容机制是动态的，并不一定是1.5倍。ArrayList的源码中有一个grow方法来控制着扩容机制，入参是当添加了此次元素后的最小容量，如果这个最小容量大于原来的容量的1.5倍时会以这个最小容量为扩容后的容量。数组扩容后通过数组拷贝保证了元素的准确性
  9. 数组(ArrayList)存储元素需要事先分配一组连续的内存空间，当需要改变存储结构例如：删除、插入操作时会为了保持元素的连续存储进行一个big O(n)复杂度的整体移动操作，如果空间不够还会进行数组拷贝。但数组的随机读取效率高，因为在内存中是连续的所以只需要先定位到头结点的地址后根据索引即可获取到元素值；

LinkedList

  1. LinkedList是一个继承于AbstractSequentialList的双向链表，由于实现了对应的接口所以LinkedList也可以进行队列操作并且能当做双端队列使用。但LinkedList是线程不安全的；
  2. LinkedList继承AbstractSequentialList的目的是减低List接口的复杂度，因为AbstractSequentialList已经有了一些主要的方法，只需要拓展这个类就可以了；
  3. 链表(LinkedList)存储元素并不是连续的，并且在初始化时并不需要声明内存大小，存储方式是在每次插入新的节点时申请节点所需要的内存空间，保证了内存的高使用效率。由于链表存储的相邻元素使用指针串联的方式进行，所以当进行插入、删除元素时只需要进行big O(1) 的指针改写和申请、释放内存就行。但是由于存储空间并不是连续的，所以当需要访问链表中的某一个节点时就需要从头开始遍历；
  4. 链表除了头节点，其他节点均存储了三种值：前驱指针、值、后继指针。而头节点中只存在第一个被插入的节点指针；

HashMap（关联式容器）

  1. JDK实现方式：HashMap使用链表+数组或数组+红黑树的方式实现

介绍HashMap

HashMap是一个用于映射键值对处理的数据类型，1.8及以上版本的实现是基于数组+链表或数组+红黑树实现的；HashMap中维护了一个哈希桶数组，数组上的每个元素又有一个链表结构，这个数组的主要意义是使用可以快速定位到键值对可能存在的桶中，具体是对key使用特定的哈希算法（经过高位运算和取模）后获得链表或红黑树的头节点位置,；哈希桶数组的默认初始长度是16，负载因子为0.75；然后如果HashMap中实际存储的键值对超过了哈希桶长度与负载因子的乘积，就会扩容。扩容后的容量是原来的两倍。但是由于负载因子和哈希算法对性能优化的局限性，就算设计的再合理再科学也会出现链表过长的情况，一旦链表过长就会影响HashMap性能，所以当HashMap中的链表结构节点数超过8个时会将链表转换为红黑树。

默认的负载因子这样设计的理由

负载因子其实就是HashMap触发扩容机制的一个阈值，默认的负载因子0.75是对空间和时间效率的一个平衡选择；如果想要时间效率高点可以降低负载因子的值，想要省空间可以加大负载因子的值；

什么是哈希冲突

哈希冲突是指两个不同的值的对象通过哈希算法后计算出的哈希值相同，这样保存到原始数组中时会产生冲突；哈希表中为了优化哈希冲突采用了拉链法，就是数组+链表的形式，即通过哈希算法定位到具体的桶，如果这个桶的头节点为空则直接插入，如果有数据就会通过哈希值和equals方法判断是否为同一key，是则覆盖否则将遍历链表或红黑树。

源码注释

put方法源码解释

  1.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                    boolean evict) {
  3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.         //  判断table==null || length=0,条件成立则进行resize()扩容
  5.         if ((tab = table) == null || (n = tab.length) == 0)
  6.             n = (tab = resize()).length;
  8.         //  (n - 1) & hash：是为了计算索引下标，以便快速找到桶
  9.         //  如果tab[i]==null（头节点为空），则直接插入
  10.         if ((p = tab[i = (n - 1) & hash]) == null)
  11.             tab[i] = newNode(hash, key, value, null);
  13.         //  tab[i] != null时
  14.         else {
  15.             Node<K,V> e; K k;
  17.             // 判断头节点的key是否与传入的key相等
  18.             //  相等时覆盖
  19.             if (p.hash == hash &&
  20.                 ((k = p.key) == key || (key != null && key.equals(k))))
  21.                 e = p;
  23.             //  不相等时判断table[i]是否为 红黑树的TreeNode
  24.             //  是的话进行红黑树形式的插入键值对操作
  25.             else if (p instanceof TreeNode)
  26.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  28.             //  不是红黑树的话开始遍历链表准备插入
  29.             else {
  30.                 //  遍历链表
  31.                 for (int binCount = 0; ; ++binCount) {
  32.                     //  判断下一个节点是否为空，为空时插入
  33.                     if ((e = p.next) == null) {
  34.                         p.next = newNode(hash, key, value, null);
  35.                         //  判断此时节点数是否超过8个，如果超过了则转换为红黑树
  36.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  37.                             treeifyBin(tab, hash);
  38.                         break;
  39.                     }
  40.                     //  如果链表中节点的key与待插入节点key相同则覆盖
  41.                     if (e.hash == hash &&
  42.                         ((k = e.key) == key || (key != null && key.equals(k))))
  43.                         break;
  44.                     p = e;
  45.                 }
  46.             }
  47.             if (e != null) { // existing mapping for key
  48.                 V oldValue = e.value;
  49.                 if (!onlyIfAbsent || oldValue == null)
  50.                     e.value = value;
  51.                 afterNodeAccess(e);
  52.                 return oldValue;
  53.             }
  54.         }
  55.         ++modCount;
  57.         //  判断插入后有无超过最大容量，有就扩容
  58.         if (++size > threshold)
  59.             resize();
  60.         afterNodeInsertion(evict);
  61.         return null;
  62.     }

TreeMap

基于红黑树的TreeMap维护的键值对是有序排列的。

HashSet

去重的主要实现：根据hash得到具体的位置，然后判断这个位置上面你的值是否hash一样并且key是否一样，如果一样，那么就替换掉，如果不一样就填加进去。

堆

栈

FILO形式（先入后出）：Java中对栈实现的类是Stack类，主要的方法有push（压栈）、pop（弹出栈顶的元素）、peek（返回栈顶的元素，不弹出）

队列

FIFO形式（先入先出）的线性表。一般都会通过链表或数组的形式实现，使用数组实现的队列叫顺序队列，使用链表实现的队列叫链式队列；

图

一种复杂的非线性结构（图形结构的元素之间的关系是任意的），图是由顶点的有穷非空集合和顶点之间的边组成的集合；通常可以简写为 G(V,E) G表示一个图、V表示顶点的集合、E表示边的集合
image.png
图的顶点：图中的数据元素，可以称之为顶点，图至少有一个顶点（非空有穷集合）。
图的边：顶点之间的关系用边表示
图的度：度表示一个顶点包含多少条边，在有向图中，还分为出度和入度；出度表示从该顶点出去的边的条数，入度表示进入该顶点的边的条数

无向图和有向图

边表示的是顶点之间的关系，有的关系是双向的，比如：同学关系。name在表示A和B的关系时，就不用关注方向，用不带箭头的边表示，这样的图就是无向的。
有的关系是有方向的，例如：父子关系、社交产品的关注关系。在这种情况下，就用带箭头的边表示二者的关系，这样的图就是有向的。

无权图和带权图

对于一个关系，如果我们只关心关系的有无，而不关心关系的强度，那么就可以用无权图表示二者之间的关系；
对于一个关系，如果我们既关心关系的有无，又关心关系的强度，例如：地图上两座城市的关系，需要用到距离就会用带权图来表示，其中带权图中的每一条边一个数值表示权值，代表关系的强度。
image.png

堆

堆是一个公平的树，只作为子树中 最大/最小 的数据才能作为根节点

只要满足以下条件的树都是堆：
每一个节点值都大于等于（或小于等于）子树中所有节点的值。

  1. 堆不一定是完全二叉树
  2. 堆是一个数组，并且可以被看成是一个近似的完全二叉树

堆的分类

堆分为最大堆和最小堆，二者的区别在于节点的排序方式

  • 最大堆：堆中的每一个节点的值都大于等于子树中所有节点的值
  • 最小堆：堆中的每一个节点的值都小于等于子树中所有节点的值

image.png

堆的用途

当我们存储数据时考虑的重要因素只有数据中的最大值或最小值，存在多次获取最大值或者最小值、多次插入或删除数据时，就可以使用堆。

堆与有序数组的差别
  • 有序数组：初始化有序数组的时间复杂度是O(nlog(n))，查找最大值或最小值时间复杂度是O(1)，更新（插入、删除）数据的时间复杂度为O(n)；即使是使用复杂度为O(log(n))的二分法找到要插入或删除的数据，在移动数据时也需要O(n)的时间复杂度
  • 堆：堆的初始化时间复杂度O(nlog(n))，查找最大值或最小值的时间复杂度可以做到O(1)，在更新（插入、删除）时的时间复杂度为O(nlog(n))

堆的操作

  1. 插入元素
  2. 删除堆顶元素

插入元素（最大堆）
  1. 在插入元素时要将插入的元素放至最后

image.png

  1. 从底层逐级往上，如果父节点比该元素小则节点互换，直到无法交换

image.png
image.png

删除堆顶元素

根据堆的性质可知，最大堆的堆顶元素为所有元素中最大的，最小堆的堆顶元素是所有元素中最小的。当我们需要多次查找最大元素或者最小元素的时候，可以利用堆来实现。

删除堆顶元素后，为了保持堆的性质，需要对堆的结构进行调整，这个过程称之为“堆化”，堆化的方法分为两种：

  1. 自底向上的堆化：上述的插入元素的操作就是使用了自底向上的堆化，元素从最底部向上移动。
  2. 自顶向下的堆化：元素由最顶部向下移动。

堆操作总结

  • 插入元素：先将元素放置数组末尾，再自底向上堆化，将末尾元素上浮
  • 删除堆顶元素：删除堆顶元素，将末尾元素放至堆顶，再自顶向下堆化，将堆顶元素下沉。（也可以自底向上堆化，只是会产生“气泡”，庞飞存储空间。最好采用自顶向下的方式删除元素）

堆排序

堆排序的过程分为两步：

  1. 建堆：将一个无序的数组建立为一个堆
  2. 排序：将堆顶元素取出，然后对剩下的元素进行堆化，反复迭代 ，直到所有元素被取出为止。

树

树就是一种类似现实生活中的树的数据结构（倒置的树）。任何一颗非空树只有一个根节点。

一棵树具有以下特点：

  1. 树中的任意两个节点有且仅有唯一的一条路径联通
  2. 树如果有N个节点，那么这棵树一定恰好有N-1条边
  3. 树不包含回路

树的常用概念：

  • 节点：树中的每个元素都可以统称为节点
  • 根节点：顶层节点或者说没有父节点的节点
  • 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
  • 子节点：一个节点含有的子树的根节点称为该节点的子节点
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点
  • 叶子结点：没有子节点的节点
  • 节点高度：该节点到叶子节点的最长路径所包含的边数
  • 节点的深度：根节点到该节点的路径所包含的边数
  • 节点的层数：节点的深度+1
  • 树的高度：根节点的高度

image.png

二叉树

二叉树是每个节点最多只有两个分支的树结构。

二叉树的分支被称作“左子树”或“右子树”。并且，二叉树的分支具有左右次序，不能随意颠倒。

满二叉树

如果每一个层的结点数都达到最大值，则这个二叉树就是 满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是(2^k) -1 ，则它就是 满二叉树。
image.png

完全二叉树

完全二叉树：树中所含的N个节点和满二叉树中编号为1~N的节点一一对应（也就是按照满二叉树的规则排列，但并未排满）

平衡二叉树

平衡二叉树 是一棵二叉排序树，且具有以下性质：

  1. 可以是一棵空树
  2. 如果不是空树，它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树的常用实现方法有 红黑树、AVL 树、替罪羊树、加权平衡树、伸展树 等。

二分查找树

  1. 若左子树不为空，则左子树上所有节点的值均小于等于根节点的值
  2. 若右子树不为空，则左子树上所有节点的值均小于等于根节点的值
  3. 左右子树均为二分查找树

二叉查找树会有极端情况（退化为单链表）：
image.png
这时就引出了平衡二叉查找树。

平衡二分查找树

对于一个平衡的有 N 个元素的二分查找树，其高度可以近似认为是 logN，所以查找的时间复杂度就是 O(logN)。 这意味着一张有 10000 个元素的符号表，我们想要查询出任意一个元素，最多也只需要进行大约 13 次左右的比较即可。

二叉树的存储

二叉树的存储主要分为链式存储和顺序存储。

链式存储

和链表类似，二叉树的链式存储依靠指针将各个节点串联起来（Java可以直接引用对象），不需要连续的存储空间。
每个节点包括三个属性：

  • 数据 data。data 不一定是单一的数据，根据不同情况，可以是多个具有不同类型的数据。
  • 左节点指针 left
  • 右节点指针 right。

顺序存储

顺序存储就是利用数组进行存储，数组中的每一个位置仅存储节点的 data，不存储左右子节点的指针，子节点的索引通过数组下标完成。根结点的序号为 1，对于每个节点 Node，假设它存储在数组中下标为 i 的位置，那么它的左子节点就存储在 2 i 的位置，它的右子节点存储在下标为 2 i+1 的位置。

一棵完全二叉树的数组顺序存储如下图所示：

image.png

二叉树的遍历

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
image.png

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
（对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列）
image.png

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

image.png

B树

简述B树：B树是一种多叉平衡查找树，主要解决磁盘或其他存储设备的存储问题。

红黑树

简述红黑树：红黑树是一种自平衡二叉查找树。它在最差的情况下都能以O（logN）的复杂度进行查找、插入、删除。它是2-3树或2-3-4树的一种实现。像散列表的桶在超过8个节点时会从双向链表转为红黑树。

2-3树

红黑树本质上是对 2-3树 的一种实现

2-3树是一种平衡查找树
image.png

在2-3树中，2节点和普通二叉树的节点基本相同（有一个键和两条链，分别链向左子树和右子树），而3节点则在2节点的基础上增加了一个键，构成了一个有两个键和三条链的结构。下图是3节点的示意图，左链链向了小于a的节点，右链链向了大于b的节点，中间区域则是a和b之间的节点。

image.png
所以，2-3树在搜索时和二叉树没有太大区别，只是当遇到3节点时多判断一次是否介于a、b之间。

2-3树的树形状并没有规律，是完全按照数据情况进行分布的。
所以在插入时，当我们查找到了某个叶子结点发现没有该键时，如果遇到了2节点可以直接插入升级为3节点。但如果遇到了3节点，由于不能存在4节点，所以会将当前数向上移，附加到父节点上，然后将当前节点的父节点升级为3节点，并将当前节点由三键拆分为二键，拆分出去的键成为第三节点。

image.png

如果父节点也是3节点，就需要逐步往根节点递归，如果路上以及根节点都为3节点，那么最后会将根节点的中键上提。

image.png

这样的操作保证整个2-3树是一个真正意义上的平衡树

而根据2-3树实现的红黑树，正是采用标准的二叉查找树及诶单附着上额外的颜色信息来表示2-3树的实现，每一个红色节点都和它的父节点一起，构成了一个3节点的模拟，这就是红黑树设计的本质。

红黑树

红黑树五大定义：
性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一节结点到其每个叶子的所有路径都包含相同数目的黑色结点

左偏红黑树的定义：

  1. 根节点为黑色
  2. 相邻节点不能同时为红色
  3. 每个节点从自身到各个能到达的叶子结点的所有路径中的黑色节点数量相同
  4. 红节点只能作为左子节点存在（左偏红黑树特有的要求）

有了这些约束，就可以保证每一颗红黑树和2-3树是一一对应的
image.png

2-3树中的一个3节点有两个键、三条链，所以可以看成是红黑树中的一个以红节点为左子节点的黑节点和子节点一起看成一个3节点。

image.png
可以通过红黑树的三个普遍约束来理解：

  1. 因为红节点只是3节点的一部分，那对应到红黑树撒花姑娘，显然不会出现两个连续的红节点。
  2. 2-3树上，每个节点到叶子结点的数量一定是一样的，且每个节点对应到红黑树上一定包含且只包含一个黑色节点，所以红黑树每个节点到叶子结点路径中的黑色节点数量也必然是一样的。

唯一不一样的就是“根节点为黑色”。事实上，如果只是为了让红黑树保持平衡，我们完全可以抛弃这条规则。
对应到红黑树中，当根节点为红色，插入新节点后很可能为了使根节点到每条路径上的黑色节点数量相等，进行变色和旋转操作，最终根节点还是会变成黑色；既然如此，我们何不直接约束根节点必须调整成黑色，方便进行插入操作呢。
这样，我们就可以将每一个红黑树都映射成一个 2-3 树，也因此就获得了 2-3 树高效的平衡插入的能力，并保留了二叉树查找的简洁性。
BlackTree——2-3Tree.jpg

红黑树的基本操作

旋转（以左偏红黑树为例）

红黑树中最基本的平衡操作是“旋转”，分为“左旋”和“右旋”。这两种操作主要用于处理在插入和删除时产生的右偏红节点或两个红节点，通过调整红节点的位置，可以修复这些不满足约束的情况。
左旋：本质就是将某个3节点以较小的键为根转移成较大的键为根。（也就是从a为根转为b为根，同时需要将介于a、b之间的节点挂到a的右节点下。通过这样旋转后的树就是以b为根节点的结构，并且在整个过程中，树的平衡性和有序性都没有破坏，而原来不符合约束的右偏红节点已被转移成“正确”的左偏节点）
image.png
插入时的情况可以分为两种：

  1. 2节点插入：针对2节点的插入其实就是对普通黑色节点的插入。由于该落点为2节点所以只会出现插入左/右两种情况。如果插入左边，只需要直接将2节点提升为3节点，并且当前插入的为红节点且在左边，所以不会破坏树的平衡性（对应红黑树上，就是简单地将新节点放到查找到的最后一个节点的左边）。如果插入右边，，可以将2节点提升成一个不符合“左偏”规则的3节点，然后进行一次左旋。

image.png

  1. 3节点插入：3节点的插入情况可以从插入的结点在 3 节点中左键的左侧、右键的右侧和两者之间分开讨论（左偏红黑树）。

先从最简单的插入在右键的右侧这种情况进行说明。和3节点分解的方式一样，只需要将中间的节点提升到上一层，并将左右节点染为黑色即可。

（待补充）