【数据结构】初识集合框架及背后的数据结构（简单了解）

前言

如何学好数据结构

1. 什么是集合框架

2. 集合框架的重要性

3. 背后所涉及的数据结构以及算法

3.1 什么是数据结构

3.2 容器背后对应的数据结构

3.3 相关java知识

3.4 什么是算法

3.5 基本关系说明（重要，简单了解）

前言

什么是数据结构？

数据结构是一门单独的学科，它和语言没有关系。
数据 + 结构：用来描述和组织数据的。
为什么会有那么多的数据结构?︰是因为我们描述和组织数据的方式不一样所以我们有很多种数据结构，来应付不同的场景来使用。

经常会听到同学问：C++的数据结构和Java的数据结构有什么区别?
这个问题是错误的问题。数据结构的实现只是用的工具(编程语言)不一样。当前数据结构的思想一样的。
C+＋和Java只是语言不一样，工具不一样。

什么是数据库？

数据库（服务器MySQL)也是单独的学科。oracle数据库是付费的，一般大的企业在用。
数据库是用来持久化存储数据的。数据库底层用到数据结构来描述存储的数据。
数据库服务器-》数据库s-》表s -》数据。

什么是集合类？

Java当中的集合类其实就是被封装好的数据结构。
写博客的逻辑：先讲某个数据结构具体的实现，然后类比在Java当中封装好的数据结构类（集合）。
原始的数据结构 -》告诉你Java封装成的集合对应的是哪个 -》你再用。
在C++中叫STL，在Java中叫集合类或者集合框架。

如何学好数据结构

学好数据结构你会有一个质的飞跃！和别人拉开差距就看数据结构了！！

多画图
多思考
多写代码（不写2遍以上是不会理解的，写5遍基本上问题不大了）

遇见题目：

如果每个地方不懂，看代码画图。
看图写代码，不会的再看代码。
思考
全部删除，重新画图再写。(这一遍尽量不要频繁看，慢慢脱离代码)

数据结构是一门逻辑非常严谨的学科。理解思想很重要。学习数据结构不仅能锻炼逻辑思维，还能提升对代码书写的流畅度。大大提高代码量。

集合框架及背后的数据结构，怎么理解标题的含义：

集合：就是java写好的一些数据结构
框架：数据结构之间存在一定的联系
数据结构：描述和组织数据的一种方式

1. 什么是集合框架

Java 集合框架(Java Collection Framework)，又被称为容器(container)，是定义在 java.util 包下的一组接口 (interfaces) 和其实现类 (classes)。util 工具，称工具包，因此基本上在Java当中与工具相关的都在util包底下。

其主要表现为将多个元素(element)置于一个单元中，用于对这些元素进行快速、便捷的存储 store 、检索 retrieve 、管理 manipulate ，即平时我们俗称的增删查改 CRUD .

例如，一副扑克牌(一组牌的集合)、一个邮箱(一组邮件的集合)、一个通讯录(一组姓名和电话的映射关系)等等。

类和接口总览：（下图并非把所有的接口，抽象类，实现类都给列举出来了。只列举出了重要的部分）每个实现类都是集合类

这张图描述了Java当中，类与类，类与接口之间的关系
了解清楚，接口与接口之间的关系 extends（拓展)关系
了解清楚，类与接口之间的关系 implemments 实现的关系
了解清楚，每个类背后的数据结构大概是个啥？
重要的接口有四个：List、Queue、Set、Map，其他类都是实现了这些接口。

2. 集合框架的重要性

1. 开发中的使用

使用成熟的集合框架，有助于我们便捷、快速的写出高效、稳定的代码。
学习背后的数据结构知识，有助于我们理解各个集合的优缺点及使用场景。

2. 笔试及面试题

3. 背后所涉及的数据结构以及算法

3.1 什么是数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

3.2 容器背后对应的数据结构

该阶段，我们主要学习以下容器，每个容器其实都是对某种特定数据结构的封装，大概了解一下，后序会给大家详细讲解并模拟实现：

1. Collection：是一个接口，包含了大部分容器常用的一些方法

2. List：是一个接口，规范了ArrayList 和 LinkedList中要实现的方法

ArrayList：实现了List接口，底层为动态类型顺序表
LinkedList：实现了List接口，底层为双向链表

3. Stack：底层是栈，栈是一种特殊的顺序表

4. Queue：底层是队列，队列是一种特殊的顺序表

5. Deque：是一个接口

6. Set：集合，是一个接口，里面放置的是K模型

HashSet：底层为哈希桶，查询的时间复杂度为O(1)
TreeSet：底层为红黑树，查询的时间复杂度为O(log2 N),关于key有序的

7. Map：映射，里面存储的是K-V模型的键值对

HashMap：底层为哈希桶，查询时间复杂度为O(1)
TreeMap：底层为红黑树，查询的时间复杂度为O(log2 N)，关于key有序

3.3 相关java知识

学数据结构前，需要先掌握的一些知识：

泛型 Generic
自动装箱 autobox 和自动拆箱 autounbox
Object 的 equals 方法
Comparable 和 Comparator 接口

3.4 什么是算法

算法(Algorithm)：就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
数据结构与算法：相辅相成的

3.5 基本关系说明（重要，简单了解）

lterable 接口：有一个for-each() 功能
Collection 接口 ：用来存储管理一组对象(objects)，这些对象一般被成为元素 (elements)
List 接口：多半部分为线性结构
Queue 接口：队列（其实队列也属于线性结构，但是有一种队列不属于线性结构，如：优先级队列——底层是一个二叉树，树形结构）
PriorityQueue类：优先级队列，每个元素都具备优先级，根据优先级入队出队
Deque接口：双端队列
Set接口：集合(元素不能重复)
SortedSet接口：有序且不能重复的元素集合
Map接口：底层是

队列：例如，排队打饭；有队尾和队头，队尾进队头出。

双端队列：有队尾和队头；队尾进队尾出，队头进队头出，两端都可以进也可以出。