在前面我们学习了最重要的类和对象，了解了面向对象编程的思想，注意，非常重要，面向对象是必须要深入理解和掌握的内容，不能草草结束。在本章节，我们会继续深入了解，从我们的泛型开始，再到我们的数据结构，最后再开始我们的集合类学习。

通过以上四种情况的处理，最终得到维护平衡二叉树的算法。

红黑树也是二叉排序树的一种改进，同平衡二叉树一样，红黑树也是一种维护平衡的二叉排序树，但是没有平衡二叉树那样严格（平衡二叉树每次插入新结点时，可能会出现大量的旋转，而红黑树保证不超过三次），红黑树降低了对于旋转的要求，因此效率有一定的提升同时实现起来也更加简单。但是红黑树的效率却高于平衡二叉树，红黑树也是JDK1.8中使用的数据结构！

红黑树的特性: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点的两边也需要表示（虽然没有，但是null也需要表示出来）是黑色。 （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

我们来看看一个节点，是如何插入到红黑树中的：

基本的 插入规则和平衡二叉树一样，但是在插入后：

1. 将新插入的节点标记为红色
2. 如果 X 是根结点(root)，则标记为黑色

• 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同，然后重复步骤 2、3

• 3.2 如果 X 的 uncle (叔叔) 是黑色，我们要分四种情况处理

• 其实这种情况下处理就和我们的平衡二叉树一样了

---

集合表示一组对象，称为其元素。一些集合允许重复的元素，而另一些则不允许。一些集合是有序的，而其他则是无序的。

集合类其实就是为了更好地组织、管理和操作我们的数据而存在的，包括列表、集合、队列、映射等数据结构。从这一块开始，我们会从源码角度给大家讲解（数据结构很重要！），不仅仅是教会大家如何去使用。

集合类最顶层不是抽象类而是接口，因为接口代表的是某个功能，而抽象类是已经快要成形的类型，不同的集合类的底层实现是不相同的，同时一个集合类可能会同时具有两种及以上功能（既能做队列也能做列表），所以采用接口会更加合适，接口只需定义支持的功能即可。

1. 它们都是容器，都能够容纳一组元素。

1. 数组的大小是固定的，集合的大小是可变的。
2. 数组可以存放基本数据类型，但集合只能存放对象。
3. 数组存放的类型只能是一种，但集合可以有不同种类的元素。

本接口中定义了全部的集合基本操作，我们可以在源码中看看。

首先介绍ArrayList，它的底层是用数组实现的，内部维护的是一个可改变大小的数组，也就是我们之前所说的线性表！跟我们之前自己写的ArrayList相比，它更加的规范，同时继承自List接口。

我们再来看LinkedList，其实本质就是一个链表！我们来看看源码。

其实与我们之前编写的LinkedList不同之处在于，它内部使用的是一个双向链表：

当然，我们发现它还实现了Queue接口，所以LinkedList也能被当做一个队列或是栈来使用。

利用代码块来快速添加内容

前面我们学习了匿名内部类，我们就可以利用代码块，来快速生成一个自带元素的List

如果是需要快速生成一个只读的List，后面我们会讲解Arrays工具类。

所有的集合类，都支持foreach循环！

当然，也可以使用JDK1.8新增的forEach方法，它接受一个Consumer接口实现：

从JDK1.8开始，lambda表达式开始逐渐成为主流，我们需要去适应函数式编程的这种语法，包括批量替换，也是用到了函数式接口来完成的。

我们之前学习数据结构时，已经得知，不同的线性表实现，在获取元素时的效率也不同，因此我们需要一种更好地方式来统一不同数据结构的遍历。

由于ArrayList对于随机访问的速度更快，而LinkedList对于顺序访问的速度更快，因此在上述的传统for循环遍历操作中，ArrayList的效率更胜一筹，因此我们要使得LinkedList遍历效率提升，就需要采用顺序访问的方式进行遍历，如果没有迭代器帮助我们统一标准，那么我们在应对多种集合类型的时候，就需要对应编写不同的遍历算法，很显然这样会降低我们的开发效率，而迭代器的出现就帮助我们解决了这个问题。

我们先来看看迭代器里面方法：

每个集合类都有自己的迭代器，通过iterator()方法来获取：

迭代器生成后，默认指向第一个元素，每次调用next()方法，都会将指针后移，当指针移动到最后一个元素之后，调用hasNext()将会返回false，迭代器是一次性的，用完即止，如果需要再次使用，需要调用iterator()方法。

ListIterator是List中独有的迭代器，在原有迭代器基础上新增了一些额外的操作。

---

我们之前已经看过Set接口的定义了，我们发现接口中定义的方法都是Collection中直接继承的，因此，Set支持的功能其实也就和Collection中定义的差不多，只不过使用方法上稍有不同。

• 不支持随机访问（不允许通过下标访问）

首先认识一下HashSet，它的底层就是采用哈希表实现的（我们在这里先不去探讨实现原理，因为底层实质上维护的是一个，我们学习了Map之后再来讨论）

运行上面代码发现，最后Set集合中存在的元素顺序，并不是我们的插入顺序，这是因为HashSet底层是采用哈希表来实现的，实际的存放顺序是由Hash算法决定的。

那么我们希望数据按照我们插入的顺序进行保存该怎么办呢？我们可以使用LinkedHashSet：

LinkedHashSet底层维护的不再是一个HashMap，而是LinkedHashMap，它能够在插入数据时利用链表自动维护顺序，因此这样就能够保证我们插入顺序和最后的迭代顺序一致了。

还有一种Set叫做TreeSet，它会在元素插入时进行排序：

可以看到最后得到的结果并不是我们插入顺序，而是按照数字的大小进行排列。当然，我们也可以自定义排序规则：

现在的结果就是我们自定义的排序规则了。

虽然Set集合只是粗略的进行了讲解，但是学习Map之后，我们还会回来看我们Set的底层实现，所以说最重要的还是Map。本节只需要记住Set的性质、使用即可。

---

我们在高中阶段其实已经学习过映射了，映射指两个元素的之间相互“对应”的关系，也就是说，我们的元素之间是两两对应的，是以键值对的形式存在。

Map就是为了实现这种数据结构而存在的，我们通过保存键值对的形式来存储映射关系。

我们先来看看Map接口中定义了哪些操作。

HashMap的实现过程，相比List，就非常地复杂了，它并不是简简单单的表结构，而是利用哈希表存放映射关系，我们来看看HashMap是如何实现的，首先回顾我们之前学习的哈希表，它长这样：

哈希表的本质其实就是一个用于存放后续节点的头结点的数组，数组里面的每一个元素都是一个头结点（也可以说就是一个链表），当要新插入一个数据时，会先计算该数据的哈希值，找到数组下标，然后创建一个新的节点，添加到对应的链表后面。

而HashMap就是采用的这种方式，我们可以看到源码中同样定义了这样的一个结构：

这个表会在第一次使用时初始化，同时在必要时进行扩容，并且它的大小永远是2的倍数！

我们可以看到默认的大小为2的4次方，每次都需要是2的倍数，也就是说，下一次增长之后，大小会变成2的5次方。

我们现在需要思考一个问题，当我们表中的数据不断增加之后，链表会变得越来越长，这样会严重导致查询速度变慢，首先想到办法就是，我们可以对数组的长度进行扩容，来存放更多的链表，那么什么情况下会进行扩容呢？

我们还发现HashMap源码中有这样一个变量，也就是负载因子，那么它是干嘛的呢？

负载因子其实就是用来衡量当前情况是否需要进行扩容的标准。我们可以看到默认的负载因子是0.75

那么负载因子是怎么控制扩容的呢？0.75的意思是，在插入新的结点后，如果当前数组的占用率达到75%则进行扩容。在扩容时，会将所有的数据，重新计算哈希值，得到一个新的下标，组成新的哈希表。

但是这样依然有一个问题，链表过长的情况还是有可能发生，所以，为了从根源上解决这个问题，在JDK1.8时，引入了红黑树这个数据结构。

当链表的长度达到8时，会自动将链表转换为红黑树，这样能使得原有的查询效率大幅度降低！当使用红黑树之后，我们就可以利用二分搜索的思想，快速地去寻找我们想要的结果，而不是像链表一样挨个去看。

除了Node以外，HashMap还有TreeNode，很明显这就是为了实现红黑树而设计的内部类。不过我们发现，TreeNode并不是直接继承Node，而是使用了LinkedHashMap中的Entry实现，它保存了前后节点的顺序（也就是我们的插入顺序）。

LinkedHashMap是直接继承自HashMap，具有HashMap的全部性质，同时得益于每一个节点都是一个双向链表，保存了插入顺序，这样我们在遍历LinkedHashMap时，顺序就同我们的插入顺序一致。当然，也可以使用访问顺序，也就是说对于刚访问过的元素，会被排到最后一位。

观察结果，我们发现，刚访问的结果被排到了最后一位。

TreeMap其实就是自动维护顺序的一种Map，就和我们前面提到的TreeSet一样：

我们发现它的内部直接维护了一个红黑树，就像它的名字一样，就是一个Tree，因为它默认就是有序的，所以说直接采用红黑树会更好。我们在创建时，直接给予一个比较规则即可。

我们首先来看看Map的一些基本操作：

由于Map并未实现迭代器接口，因此不支持foreach，但是JDK1.8为我们提供了forEach方法使用：

我们也可以单独获取所有的值或者是键：

通过观察HashSet的源码发现，HashSet几乎都在操作内部维护的一个HashMap，也就是说，HashSet只是一个表壳，而内部维护的HashMap才是灵魂！

我们发现，在添加元素时，其实添加的是一个键为我们插入的元素，而值就是PRESENT常量：

观察其他的方法，也几乎都是在用HashMap做事，所以说，HashSet利用了HashMap内部的数据结构，轻松地就实现了Set定义的全部功能！

再来看TreeSet，实际上用的就是我们的TreeMap：

同理，这里就不多做阐述了。

最后，我们再来看看JDK1.8中集合类新增的一些操作（之前没有提及的）首先来看看compute方法：

merge方法用于处理数据：

---

既然集合类型中的元素类型是泛型，那么能否嵌套存储呢？

通过Key获取到对应的值后，就是一个列表：

你也可以使用List来套娃别的：

Java 8 API添加了一个新的抽象称为流Stream，可以让你以一种声明的方式处理数据。Stream 使用一种类似用 SQL 语句从数据库查询数据的直观方式来提供一种对 Java 集合运算和表达的高阶抽象。Stream API可以极大提高Java的生产力，让程序员写出高效率、干净、简洁的代码。这种风格将要处理的元素集合看作一种流， 流在管道中传输， 并且可以在管道的节点上进行处理， 比如筛选， 排序，聚合等。元素流在管道中经过中间操作（intermediate operation）的处理，最后由最终操作(terminal

它看起来就像一个工厂的流水线一样！我们就可以把一个Stream当做流水线处理：

可能从上述例子中还不能感受到流处理带来的便捷，我们通过下面这个例子来感受一下：

当遇到大量的复杂操作时，我们就可以使用Stream来快速编写代码，这样不仅代码量大幅度减少，而且逻辑也更加清晰明了（如果你学习过SQL的话，你会发现它更像一个Sql语句）

注意：不能认为每一步是直接依次执行的！

接下来，我们用一堆随机数来进行更多流操作的演示：

我们可以生成一个统计实例来帮助我们快速进行统计：

普通的List只需要一个方法就可以直接转换到方便好用的IntStream了：

我们还可以通过flat来对整个流进行进一步细分：

我们也可以只通过Stream来完成所有数字的和，使用reduce方法：

通过上面的例子，我们发现，Stream不喜欢直接给我们返回一个结果，而是通过Optinal的方式，那么什么是Optional呢？

Optional类是Java8为了解决null值判断问题，使用Optional类可以避免显式的null值判断（null的防御性检查），避免null导致的NPE（NullPointerException）。总而言之，就是对控制的一个判断，为了避免空指针异常。

有了Optional之后，我们就可以这样写：

就类似于Kotlin中的：

我们可以选择直接get或是当值为null时，获取备选值：

同样的，Optional也支持过滤操作和映射操作，不过是对于单对象而言：

Arrays是一个用于操作数组的工具类，它给我们提供了大量的工具方法：

由于操作数组并不像集合那样方便，因此JDK提供了Arrays类来增强对数组操作，比如：

思考：当二维数组使用Arrays.equals()进行比较以及Arrays.toString()进行打印时，还会得到我们想要的结果吗？

那么，一开始提到的当做List进行操作呢？我们可以使用Arrays.asList()来将数组转换为一个 固定长度的List

文字游戏：allows arrays to be viewed as lists，实际上只是当做List使用，本质还是数组，因此数组的属性依然存在！因此如果要将数组快速转换为实际的List，可以像这样：

通过自行创建一个真正的ArrayList并在构造时将Arrays的List值传递。

既然数组操作都这么方便了，集合操作能不能也安排点高级的玩法呢？那必须的，JDK为我们准备的Collocations类就是专用于集合的工具类：

当然，Collections提供的内容相比Arrays会更多，希望大家下去自行了解，这里就不多做介绍了。

---

现在有一个单链表，尝试将其所有节点倒序排列

现在知道二叉树的前序: GDAFEMHZ，以及中序: ADEFGHMZ，请根据已知信息还原这颗二叉树。

实现一个计算器，要求输入一个计算公式（含加减乘除运算符，没有负数但是有小数），得到结果，比如输入：1+4*3/1.321，得到结果为：2.2

字符串匹配（KMP算法）

现在给定一个主字符串和一个子字符串，请判断主字符串是否包含子字符串，例如主字符串：ABCABCDHI，子字符串：ABCD，因此主字符串包含此子字符串；主字符串：ABCABCUISA，子字符串：ABCD，则不包含。

学习编程, 既要考虑诗和远方, 也要考虑眼前的苟且。

每年像你这样的学生不计其数，大一刚进校，一门C语言，学校发一本垃圾C语言教材，按时上课，老师在那里念念PPT，讲讲浮点型变量，malloc啥的，你若认真听了，那你可能懂了，但是发现不会写，你若没听，玩手机了，你是既不懂，也不会写，上来上去，蒙在鼓里的人出不来，水平就一直这样，龟速增长。

有的学生学的一头雾水，开始怀疑自己，准备转专业，放弃计算机，有的学生学懂了，写程序一直报错，开始怀疑自己，有的学生觉得教材写得不好，去书店转了一圈，买了三四本C语言的书，但最后厚厚的灰尘盖在了书上，再也没翻过。

这三种学生，如果继续这样，最后都要凉凉。

马克思教给我们要具体问题具体分析，那我今天就来分析一下，计算机专业的学生，到底应该怎么学计算机，才能效果最好，进步最快。

如果你要学习物理，我推荐你顺着物理的发展史学习，先学习牛顿经典物理，再学习热力学，电磁学这些不那么经典的，再学习相对论，量子力学这种彻底推翻经典物理的，再学习量子电动力学这种硬核的，比较前沿的，整个学习过程，是自底向上。

但是学习计算机，真的适合这样吗？

先学习电路，冯诺依曼结构，造一台计算机？然后再用汇编写个小操作系统？写个小编译器？最后一步一步往上走，最后开始用高级语言编程？

你要是这么学，必然爆炸。

计算机的学习最好应该是自顶向下。

这个顶，顶到什么程度？

有人说，C语言就是高级语言了，从C语言开始学就好了。

但是如果让我教计算机，我第一节课教学生们的，绝对不是C语言，而是教大家如何使用Github，Stackoverflow，告诉世界上正在发生什么，程序员之间是如何协作的，告诉你在这个大社区，你可以读到这个世界最牛逼的程序员写的代码。

我还要告诉大家如何使用云服务，告诉大家可以买一个一个月十块钱的学生服务器，自己做点有趣的事，我还要推荐大家去用Visual Studio Code，而不是简单粗暴的在机房装一个VC6，或者CodeBlocks，美其名曰，“我们当年用记事本还XXXX，现在的学生被惯坏了”这种话。

如果可以，我还会教同学们如何科学上网，让英文编程环境成为习惯，让遇到问题google，而不是百度成为习惯，让大家在第一节课上完，就能进入这个世界编程大社区，哪怕什么都不懂，你也能保证所在的社区，就是世界程序员的大家庭当你进入Github，看着各种有趣的项目的时候，相信我，你的视野就会在此为起点，快速打开，不断增长，进入一个良性循环。

而当刚上大一的学生第一次进入github时候，被眼前的各种没听过，没见过，但感觉很厉害的项目所吸引的时候，当他两眼冒光的时候，我就知道，他这四年，成了。

“Github还用教？刚才你说的那些学生，如果能被C语言的困难打倒，那他也不适合做程序员，转行正好。”

像这种话，我想说，在很多时候，佛和魔仅在一念之间，你在最开始的时候点到了，给了他引导，他以后可能会马上进入一个正反馈状态，如果你没点到，马上可能就负反馈了。

我一直觉得国内的计算机专业的学生很可怜。

当VScode表现越来越优异的时候，学生们还在机房用着VC6，看着密密麻麻的报错无可奈何。

当Google搜索可以精准定位你的问题的时候，学生们还在为百度搜索出来乱七八糟的搜索结果无可奈何。

你用百度，用中文搜索，你连stackoverflow都搜不出来。

但是你可以去问问，做一个调查，有多少大一结束的学生，没上过stackoverflow，不知道怎么在github里提交issue和pull request，你统计一下，看看这个比例有多大？

你再统计一下有多少比例的大一结束的学生没用过google，并且对其用不了的原因不太清楚？

视野打不开，一切都完了。

有人说，刚开始直接学了python这种很简单的高级语言，以后遇到C肯定被吓跑了。

事实恰恰相反，在你了解到python的性能问题时，你才会了解python是解释型语言，C是编程型语言，你才会思考为什么C更快，进而，如果需要用C，去学C。

在你在编程语言中涉及到了“原子性”，“同步”，“异步”，“线程”，“进程”，“内存分配“等概念的时候，你会自然而然地产生很多疑问，进而去学习操作系统，在学操作系统的过程中，你之前的一系列疑问逐渐被解决，这个过程是很爽的。

当你发现某个算法，人家的实现比你快很多的时候，你会自然地去思考，为什么我的程序运行这么慢，然后发现对方用的数据结构与你不同，甚至用了一些算法，比如动态规划等，这也会驱使你去学习算法，学习数据结构。

有了需求和疑问，再去学，这样一个过程，是学习的金钥匙。

你指望学生自己打开视野，但是那些自己打不开，需要你帮忙开下门的呢？

在你的视野被打开之后，我还希望你懂这些：

比如你学C语言，与其去做那些OJ题，不如在github上找个C语言项目，然后阅读，理解，修改，模仿。

个人认为在知识爆炸的年代，两不要：

学个啥都要买本教材，试图线性地，从头读到尾。

（真实情况：经典教材都能下载到免费pdf，语言，框架，文档往往已经写的很好，而且最新，github上有无数优质开源学习资源）

不读优质代码，不参考最佳实践，啥都要自己从头开始搞。

做知识输出，用文字总结自己的学习内容。

我曾听过一种论调，说程序员不会用命令行也没关系。

我想说的是，第一，这个世界没有那么美好，什么都要给你做一个图形界面，第二，对于命令复杂，命令多的工具，就算做出来图形界面，往往比命令行更难用，而且命令行可以用命令行脚本进行批文件自动化执行。

有问题，先文档，再stackoverflow，再技术文章

要用实例驱动学习，不要说你会什么，要说你做了什么

我希望所有程序员明白一个事实是，”我会什么”这句话，其实是最没用，最虚飘飘的东西，你说你会java，python，c，rust，go，然后呢？你怎么证明？写个hello world？会用api？

但是你要说，XX著名项目作者，那你就牛了，我也不需要让你证明什么了。

大概随便说了点，还有很多内容可以补充，先就这样了，谢谢大家。

---

就像文中所说的，自顶向下学习编程，可以尝试从 Python 入手，这里推荐一个入门课程平台，叫夜曲编程，在这个平台上能够以非常低的门槛入门编程，无需自己搭建环境，即可在线开始进行编程练手和尝试：

直接点击运行，即可看到运行结果：

可以通过这种方式快速入门后，再开展更深入的学习比较好～所以推荐大家尝试一下～