帅地

帅地 查看完整档案

广州编辑华南农业大学  |  软件工程 编辑腾讯  |  后端开发 编辑 github.com/iamshuaidi/CS-Book 编辑
编辑
关注公我的众号:苦逼的码农(ID:di201805),获取更多原创文章,后台回复"电子书"送你一份特别的资源大礼包。

个人动态

帅地 发布了文章 · 2019-12-27

【吐血整理】百度云珍藏了四年书籍+临时搜索,帅地给大家整理了几百本常用电子书(附下载链接)!!

计算机类的书籍那么贵,作为一个几个小时看完一本书且机不离身的程序员,天天买纸质书是不可能的了,所以对电子书的需求量还是挺多的。为了方便广大的小伙伴也能方便找到对应的电子书,我花费洪荒之力收集了几百本常用的电子书,然后每天都有好友找我要电子书链接,因为百度云动不动就失效了,,,,,我真的被搞炸了,无奈之下只能让他们加我的百度云,我发给他们

在这里插入图片描述

但是这样下去也不是办法,所以并且为了解决百度云链接容易失效的问题,也考虑到公众号读者有挺多初学者,干脆我就花点时间,把这些电子书分类整理了一波,并且把电子书全部下载,分类,压缩,上传,说实话,把我搞到脖子都酸了,还被迫下载了百度云超级会员,,,,

作为一个良心的博主,目前只整理了一两百本常用书籍。先来个目录压压惊。
在这里插入图片描述
不过呢,微信公众号里面是不支持页内跳转以及百度云链接的,所以我把这些书籍全部都放在了 Github 上,这样方便大家搜索与下载,也方便日后更新,大家可以到 Github 中下载需要的书籍。

Github 地址:https://github.com/iamshuaidi...

给大家看看部分数据结构与算法的书籍
在这里插入图片描述
再看下Java相关书籍:
在这里插入图片描述

当然,这只是一部分,后面会越来越完善哦。如果你们没有找到自己想要的书籍,麻烦到我的微信公众号后台(ID:di201805)给我留言哦,我两三天之内就会更新。因为有很多其他岗位的知识我也没学过,不知道搜索哪些书籍好,所以就搜索了这些我相对熟悉一点是书籍。顺便把这些书籍名单放出来吧。

Github 地址:https://github.com/iamshuaidi...

大佬们如果觉得不错也可以来个 star,star 越多,我后面整理的越上心,嘻嘻。

数据结构与算法相关书籍

  • 挑战程序设计竞赛
  • Java数据结构和算法
  • LeetCode题解
  • 算法图解
  • 算法导论
  • 算法(注意,这是代表算法第4版,为了方便,关键词设置为算法
  • 数据结构与算法分析(包括C语言,Python,Java三种版本)
  • 剑指offer
  • 计算机程序设计艺术(一共有三卷哦)
  • 大话数据结构
  • 程序员代码面试指南(实际书名为:程序员代码面试指南:IT 名企算法与数据结构题目最优解)
  • 编程珠玑
  • 编程之美
  • 啊哈算法

计算机基础

操作系统

  • 30天填自制操作系统
  • 操作系统之哲学原理
  • 程序是怎样跑起来的
  • 深入理解计算机操作系统
  • 现代操作系统

汇编语言

  • 汇编语言(注:这边是王爽写的,我觉得写的很好,适合入门)

计算机网络

  • 计算机网络(注:包括《计算机网络:自顶向下》)
  • 图解HTTP
  • 图解TCP(注:全名实际上是《图解TCP/IP》)
  • 网络是怎样连接的
  • HTTP权威指南
  • UNIX网络编程

计算机组成原理

  • 编码(注:实际书名是《编码:隐匿在计算机软硬件背后的语言》

Python

1、Python基础

  • 编程小白的第一本Python入门书
  • Python编程初学者指南
  • Python高级编程
  • Python高性能编程
  • Python核心编程
  • Python灰帽子
  • Python开发技术详解
  • Python开发实战
  • Python网络编程基础

    Python学习手册

2、数据分析与爬虫

  • 数据科学入门
  • 用Python写网络爬虫
  • Python数据处理
  • Python数据分析实战
  • Python数据科学手册
  • Python数据可视化编程实战

Linux

  • 精通正则表达式
  • 鸟哥的Linux私房菜(注:包括基础篇和服务器篇)
  • 深入Linux内核架构
  • Linux宝典
  • Linux常用命令大全
  • Linux防火墙
  • Linux高级程序设计
  • Linux环境编程
  • Linux命令详解词典

C语言

  • 经典C程序100例
  • C Primer Plus
  • C程序设计语言
  • C和指针
  • C语言编程精粹
  • C语言参考手册
  • C语言函数大全
  • C语言解析教程
  • C语言深度剖析
  • C专家编程

C++

  • C++ Primer
  • C++编程思想
  • C++对象模型
  • 深入探索C++对象模型
  • C++ Templates
  • C++编程规范-101条规则准则与最佳实践
  • C++沉思录中文第2版
  • C++大学教程
  • C++设计新思维-泛型编程与设计之应用
  • Effective STL 中文版
  • More Effective C++中文版
  • STL源码剖析

前端

  • 疯狂aJax讲义
  • Bootstrap实战
  • HTML5揭秘
  • HTML5与CSS3基础教程
  • HTML与CSS入门经典
  • JavaScript DOM编程艺术
  • JavaScript高级程序设计
  • JavaScript高效图形编程
  • jQuery高级编程
  • jQuery技术内幕
  • jQuery权威指南
  • Node.js开发指南

人工智能

  • 贝叶斯思维统计建模的Python学习法
  • 机器学习实战
  • Python机器学习及实践
  • Tensorflow实战Google深度学习框架
  • TensorFlow实践与智能系统

设计模式

  • 图解设计模式
  • 研磨设计模式
  • Head First设计模式

Java

Java 基础

  • 阿里巴巴Java开发手册
  • 码出高效
  • Head First Java
  • Java8实战
  • Java编程思想
  • Java并发编程的艺术
  • Java并发编程实践
  • Java从小白到大牛
  • Java核心技术(注:包括卷1和卷2)
  • 深入理解Java虚拟机

Java进阶

  • 代码大全
  • 代码整洁之道
  • 敏捷软件开发
  • Effective Java
  • Java性能优化权威指南

JavaWeb

  • 轻量级JavaEE企业应用实战
  • 深入分析JavaWeb技术内幕
  • 深入剖析Tomcat
  • Head First Servlet and JSP
  • Maven实战
  • Spring实战

数据库

  • 高性能MySQL
  • 深入浅出MySQL
  • MongoDB权威指南
  • MySQL必知必会
  • MySQL技术内幕(注:实际书名是《MySQL技术内幕InnoDB存储引擎 》)
  • SQL查询的艺术
  • SQLite 权威指南

Go

  • 学习Go语言
  • Go语言实战
  • Go web编程
  • C 程序设计语言第2版

面试相关

  • 阿里巴巴Java面试问题大全
  • 程序员面试宝典
  • 大厂面试真题
  • Java面试突击

其他精选书籍

  • 黑客与画家
  • 浪潮之巅
  • 码农翻身

Git

  • 快速入门Git
  • 专业git中文
  • Git参考手册
  • 《Pro Git》中文版

等等.....

发现啥没有你想要的?因为还在整理嘛,这里只是先弄个大致书单,产生个永久网址

Github地址:https://github.com/iamshuaidi...

如果反馈不错的话,我后面在整理一波常用开发工具,并且附破解教程,其他已经在慢慢搜集一些工具了,如图
在这里插入图片描述

当然,弄这个可能需要点时间,最后也不一定会整理出来,这个得看读者们的需求程度以及反馈。

总结

不满你说,这些书籍很多都是我去搜索例如 C++ 有哪些推荐的书籍,然后找到对应的名单,并且根据读者的平时的反馈搜索而来的,例如(这里感谢小门神的介绍哦)

在这里插入图片描述
然后一本一本搜索,还是整理了挺久滴。所以如果觉得不错,求转发、分享、在看三连击!!!

有收获?希望老铁们来个三连击,给更多的人看到这篇文章

1、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

2、老铁们,关注我的原创微信公众号「苦逼的码农」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux),保存让你看完有所收获,不信你打我。后台回复『电子书』送你一份精选电子书大礼包,包含各类技能的优质电子书。如果关注的人多了,我就要把公众号改为 牛逼的码农了。

查看原文

赞 4 收藏 4 评论 1

帅地 发布了文章 · 2019-12-23

为什么你学不会递归?告别递归,谈谈我的经验

可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了!

可能也有一大部分人知道递归,也能看的懂递归,但在实际做题过程中,却不知道怎么使用,有时候还容易被递归给搞晕。也有好几个人来问我有没有快速掌握递归的捷径啊。说实话,哪来那么多捷径啊,不过,我还是想写一篇文章,谈谈我的一些经验,或许,能够给你带来一些帮助。

为了兼顾初学者,我会从最简单的题讲起!

递归的三大要素

第一要素:明确你这个函数想要干什么

对于递归,我觉得很重要的一个事就是,这个函数的功能是什么,他要完成什么样的一件事,而这个,是完全由你自己来定义的。也就是说,我们先不管函数里面的代码什么,而是要先明白,你这个函数是要用来干什么。

例如,我定义了一个函数

// 算 n 的阶乘(假设n不为0)
int f(int n){
    
}

这个函数的功能是算 n 的阶乘。好了,我们已经定义了一个函数,并且定义了它的功能是什么,接下来我们看第二要素。

第二要素:寻找递归结束条件

所谓递归,就是会在函数内部代码中,调用这个函数本身,所以,我们必须要找出递归的结束条件,不然的话,会一直调用自己,进入无底洞。也就是说,我们需要找出当参数为啥时,递归结束,之后直接把结果返回,请注意,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。

例如,上面那个例子,当 n = 1 时,那你应该能够直接知道 f(n) 是啥吧?此时,f(1) = 1。完善我们函数内部的代码,把第二要素加进代码里面,如下

// 算 n 的阶乘(假设n不为0)
int f(int n){
    if(n == 1){
        return 1;
    }
}

有人可能会说,当 n = 2 时,那我们可以直接知道 f(n) 等于多少啊,那我可以把 n = 2 作为递归的结束条件吗?

当然可以,只要你觉得参数是什么时,你能够直接知道函数的结果,那么你就可以把这个参数作为结束的条件,所以下面这段代码也是可以的。

// 算 n 的阶乘(假设n>=2)
int f(int n){
    if(n == 2){
        return 2;
    }
}

注意我代码里面写的注释,假设 n >= 2,因为如果 n = 1时,会被漏掉,当 n <= 2时,f(n) = n,所以为了更加严谨,我们可以写成这样:

// 算 n 的阶乘(假设n不为0)
int f(int n){
    if(n <= 2){
        return n;
    }
}

第三要素:找出函数的等价关系式

第三要素就是,我们要不断缩小参数的范围,缩小之后,我们可以通过一些辅助的变量或者操作,使原函数的结果不变。

例如,f(n) 这个范围比较大,我们可以让 f(n) = n * f(n-1)。这样,范围就由 n 变成了 n-1 了,范围变小了,并且为了原函数f(n) 不变,我们需要让 f(n-1) 乘以 n。

说白了,就是要找到原函数的一个等价关系式,f(n) 的等价关系式为 n * f(n-1),即

f(n) = n * f(n-1)。

这个等价关系式的寻找,可以说是最难的一步了,如果你不大懂也没关系,因为你不是天才,你还需要多接触几道题,我会在接下来的文章中,找 10 道递归题,让你慢慢熟悉起来

找出了这个等价,继续完善我们的代码,我们把这个等价式写进函数里。如下:

// 算 n 的阶乘(假设n不为0)
int f(int n){
    if(n <= 2){
        return n;
    }
    // 把 f(n) 的等价操作写进去
    return f(n-1) * n;
}

至此,递归三要素已经都写进代码里了,所以这个 f(n) 功能的内部代码我们已经写好了。

这就是递归最重要的三要素,每次做递归的时候,你就强迫自己试着去寻找这三个要素。

还是不懂?没关系,我再按照这个模式讲一些题。

有些有点小基础的可能觉得我写的太简单了,没耐心看?少侠,请继续看,我下面还会讲如何优化递归。当然,大佬请随意,可以直接拉动最下面留言给我一些建议,万分感谢!

案例1:斐波那契数列

斐波那契数列的是这样一个数列:1、1、2、3、5、8、13、21、34....,即第一项 f(1) = 1,第二项 f(2) = 1.....,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

1、第一递归函数功能

假设 f(n) 的功能是求第 n 项的值,代码如下:

int f(int n){
    
}

2、找出递归结束的条件

显然,当 n = 1 或者 n = 2 ,我们可以轻易着知道结果 f(1) = f(2) = 1。所以递归结束条件可以为 n <= 2 时,f(n= = 1。代码如下:

int f(int n){
    if(n <= 2){
        return 1;
    }
}

第三要素:找出函数的等价关系式

题目已经把等价关系式给我们了,所以我们很容易就能够知道 f(n) = f(n-1) + f(n-2)。我说过,等价关系式是最难找的一个,而这个题目却把关系式给我们了,这也太容易,好吧,我这是为了兼顾几乎零基础的读者。

所以最终代码如下:

int f(int n){
    // 1.先写递归结束条件
    if(n <= 2){
        return 1;
    }
    // 2.接着写等价关系式
    return f(n-1) + f(n - 2);
}

搞定,是不是很简单?

零基础的可能还是不大懂,没关系,之后慢慢按照这个模式练习!好吧,有大佬可能在吐槽太简单了。

案例2:小青蛙跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1、第一递归函数功能

假设 f(n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法,代码如下:

int f(int n){
    
}

2、找出递归结束的条件

我说了,求递归结束的条件,你直接把 n 压缩到很小很小就行了,因为 n 越小,我们就越容易直观着算出 f(n) 的多少,所以当 n = 1时,你知道 f(1) 为多少吧?够直观吧?即 f(1) = 1。代码如下:

int f(int n){
    if(n == 1){
        return 1;
    }
}

第三要素:找出函数的等价关系式

每次跳的时候,小青蛙可以跳一个台阶,也可以跳两个台阶,也就是说,每次跳的时候,小青蛙有两种跳法。

第一种跳法:第一次我跳了一个台阶,那么还剩下n-1个台阶还没跳,剩下的n-1个台阶的跳法有f(n-1)种。

第二种跳法:第一次跳了两个台阶,那么还剩下n-2个台阶还没,剩下的n-2个台阶的跳法有f(n-2)种。

所以,小青蛙的全部跳法就是这两种跳法之和了,即 f(n) = f(n-1) + f(n-2)。至此,等价关系式就求出来了。于是写出代码:

int f(int n){
    if(n == 1){
        return 1;
    }
    ruturn f(n-1) + f(n-2);
}

大家觉得上面的代码对不对?

答是不大对,当 n = 2 时,显然会有 f(2) = f(1) + f(0)。我们知道,f(0) = 0,按道理是递归结束,不用继续往下调用的,但我们上面的代码逻辑中,会继续调用 f(0) = f(-1) + f(-2)。这会导致无限调用,进入死循环

这也是我要和你们说的,关于递归结束条件是否够严谨问题,有很多人在使用递归的时候,由于结束条件不够严谨,导致出现死循环。也就是说,当我们在第二步找出了一个递归结束条件的时候,可以把结束条件写进代码,然后进行第三步,但是请注意,当我们第三步找出等价函数之后,还得再返回去第二步,根据第三步函数的调用关系,会不会出现一些漏掉的结束条件。就像上面,f(n-2)这个函数的调用,有可能出现 f(0) 的情况,导致死循环,所以我们把它补上。代码如下:

int f(int n){
    //f(0) = 0,f(1) = 1,f(2) = 2等价于 n<=2时,f(n) = n。
    if(n <= 2){
        return n;
    }
    ruturn f(n-1) + f(n-2);
}

有人可能会说,我不知道我的结束条件有没有漏掉怎么办?别怕,多练几道就知道怎么办了。

看到这里有人可能要吐槽了,这两道题也太容易了吧??能不能被这么敷衍。少侠,别走啊,下面出道难一点的。

下面其实也不难了,就比上面的题目难一点点而已,特别是第三步等价的寻找。

案例3:反转单链表。

反转单链表。例如链表为:1->2->3->4。反转后为 4->3->2->1

链表的节点定义如下:

class Node{
    int date;
    Node next;
}

虽然是 Java语言,但就算你没学过 Java,我觉得也是影响不大,能看懂。

还是老套路,三要素一步一步来。

1、定义递归函数功能

假设函数 reverseList(head) 的功能是反转但链表,其中 head 表示链表的头节点。代码如下:

Node reverseList(Node head){
    
}

2. 寻找结束条件

当链表只有一个节点,或者如果是空表的话,你应该知道结果吧?直接啥也不用干,直接把 head 返回呗。代码如下:

Node reverseList(Node head){
    if(head == null || head.next == null){
        return head;
    }
}

3. 寻找等价关系

这个的等价关系不像 n 是个数值那样,比较容易寻找。但是我告诉你,它的等价条件中,一定是范围不断在缩小,对于链表来说,就是链表的节点个数不断在变小,所以,如果你实在找不出,你就先对 reverseList(head.next) 递归走一遍,看看结果是咋样的。例如链表节点如下

我们就缩小范围,先对 2->3->4递归下试试,即代码如下

Node reverseList(Node head){
    if(head == null || head.next == null){
        return head;
    }
    // 我们先把递归的结果保存起来,先不返回,因为我们还不清楚这样递归是对还是错。,
    Node newList = reverseList(head.next);
}

我们在第一步的时候,就已经定义了 reverseLis t函数的功能可以把一个单链表反转,所以,我们对 2->3->4反转之后的结果应该是这样:

我们把 2->3->4 递归成 4->3->2。不过,1 这个节点我们并没有去碰它,所以 1 的 next 节点仍然是连接这 2。

接下来呢?该怎么办?

其实,接下来就简单了,我们接下来只需要把节点 2 的 next 指向 1,然后把 1 的 next 指向 null,不就行了?,即通过改变 newList 链表之后的结果如下:

也就是说,reverseList(head) 等价于 reverseList(head.next) + 改变一下1,2两个节点的指向。好了,等价关系找出来了,代码如下(有详细的解释):

//用递归的方法反转链表
public static Node reverseList2(Node head){
    // 1.递归结束条件
    if (head == null || head.next == null) {
             return head;
         }
         // 递归反转 子链表
         Node newList = reverseList2(head.next);
         // 改变 1,2节点的指向。
         // 通过 head.next获取节点2
         Node t1  = head.next;
         // 让 2 的 next 指向 2
         t1.next = head;
         // 1 的 next 指向 null.
        head.next = null;
        // 把调整之后的链表返回。
        return newList;
    }

这道题的第三步看的很懵?正常,因为你做的太少了,可能没有想到还可以这样,多练几道就可以了。但是,我希望通过这三道题,给了你以后用递归做题时的一些思路,你以后做题可以按照我这个模式去想。通过一篇文章是不可能掌握递归的,还得多练,我相信,只要你认真看我的这篇文章,多看几次,一定能找到一些思路!!

我已经强调了好多次,多练几道了,所以呢,后面我也会找大概 10 道递归的练习题供大家学习,不过,我找的可能会有一定的难度。不会像今天这样,比较简单,所以呢,初学者还得自己多去找题练练,相信我,掌握了递归,你的思维抽象能力会更强!

接下来我讲讲有关递归的一些优化。

有关递归的一些优化思路

1. 考虑是否重复计算

告诉你吧,如果你使用递归的时候不进行优化,是有非常非常非常多的子问题被重复计算的。

啥是子问题? f(n-1),f(n-2)....就是 f(n) 的子问题了。

例如对于案例2那道题,f(n) = f(n-1) + f(n-2)。递归调用的状态图如下:

(img-adCaaEyJ-1572163241563)(https://user-gold-cdn.xitu.io/2019/3/12/169722f31645ef25?w=729&h=444&f=png&s=88214)]

看到没有,递归计算的时候,重复计算了两次 f(5),五次 f(4)。。。。这是非常恐怖的,n 越大,重复计算的就越多,所以我们必须进行优化。

如何优化?一般我们可以把我们计算的结果保证起来,例如把 f(4) 的计算结果保证起来,当再次要计算 f(4) 的时候,我们先判断一下,之前是否计算过,如果计算过,直接把 f(4) 的结果取出来就可以了,没有计算过的话,再递归计算。

用什么保存呢?可以用数组或者 HashMap 保存,我们用数组来保存把,把 n 作为我们的数组下标,f(n) 作为值,例如 arr[n] = f(n)。f(n) 还没有计算过的时候,我们让 arr[n] 等于一个特殊值,例如 arr[n] = -1。

当我们要判断的时候,如果 arr[n] = -1,则证明 f(n) 没有计算过,否则, f(n) 就已经计算过了,且 f(n) = arr[n]。直接把值取出来就行了。代码如下:

// 我们实现假定 arr 数组已经初始化好的了。
int f(int n){
    if(n <= 1){
        return n;
    }
    //先判断有没计算过
    if(arr[n] != -1){
        //计算过,直接返回
        return arr[n];
    }else{
        // 没有计算过,递归计算,并且把结果保存到 arr数组里
        arr[n] = f(n-1) + f(n-1);
        reutrn arr[n];
    }
}

也就是说,使用递归的时候,必要
须要考虑有没有重复计算,如果重复计算了,一定要把计算过的状态保存起来。

2. 考虑是否可以自底向上

对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。

不过,有时候当 n 比较大的时候,例如当 n = 10000 时,那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。

对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道

f(1) = 1;

f(2) = 2;

那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来取代递归,代码如下:

public int f(int n) {
       if(n <= 2)
           return n;
       int f1 = 1;
       int f2 = 2;
       int sum = 0;

       for (int i = 3; i <= n; i++) {
           sum = f1 + f2;
           f1 = f2;
           f2 = sum;
       }
       return sum;
   }

这种方法,其实也被称之为递推

最后总结

其实,递归不一定总是从上往下,也是有很多是从下往上的,例如 n = 1 开始,一直递归到 n = 1000,例如一些排序组合。对于这种从下往上的,也是有对应的优化技巧,不过,我就先不写了,后面再慢慢写。这篇文章写了很久了,脖子有点受不了了,,,,颈椎病?害怕。。。。

说实话,对于递归这种比较抽象的思想,要把他讲明白,特别是讲给初学者听,还是挺难的,这也是我这篇文章用了很长时间的原因,不过,只要能让你们看完,有所收获,我觉得值得!有些人可能觉得讲的有点简单,没事,我后面会找一些不怎么简单的题。最后如果觉得不错,还请给我转发 or 点赞一波!

另外,我正在整理一份计算机类书单,只为让大家更加方便找到自己想要的书籍,目前已经收集了几百本了,贡献给需要的人计算机的书籍很贵?史上最全计算机类电子书整理(持续更新)

有收获?希望老铁们来个三连击,给更多的人看到这篇文章

1、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

2、老铁们,关注我的原创微信公众号「苦逼的码农」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux)。

保存让你看完有所收获,不信你打我。。如果关注的人多了,我就要把公众号改为 牛逼的码农了。

查看原文

赞 0 收藏 0 评论 0

帅地 发布了文章 · 2018-10-24

我是如何学习数据结构与算法的?

数据结构与算法的地位对于一个程序员来说不言而喻。今天这篇文章不是来劝你们学习数据结构与算法的,也不是来和你们说数据结构与算法有多重要。

主要是最近几天后台有读者问我是如何学习数据结构与算法的,有没有什么捷径,是要看视频还是看书,去哪刷题等.....而且有些还是大三大四的,搞的我都替你们着急、担心.....

所以我今天就分享下自己平时都是怎么学习的。

学习算法的捷径就是多刷题

说实话,要说捷径,我觉得就是脚踏实地着多动手去刷题,多刷题。

但是,如果你是小白,也就是说,你连常见的数据结构,如链表、树以及常见的算法思想,如递归、枚举、动态规划这些都没学过,那么,我不建议你去刷题的。而是先去找本书先去学习这些,然后再去刷题。

也就是说,假如你要去诸如leetcode这些网站刷题,那么,你要先具备一定的基础,这些基础包括:

1、常见数据结构:链表、树(如二叉树)。

2、常见算法思想:贪婪法、分治法、穷举法、动态规划,回溯法。

以上列出来的算是最基本的吧。就是说你刷题之前,要把这些过一遍再去刷题。如果你连这些最基本的都不知道的话,那么你再刷题的过程中,会很难受的,思路也会相对比较少。

总之,千万不要急,先把这些基本的过一遍,力求理解,再去刷题。这些基础的数据结构与算法,我是在大一第二学期学的,我没看视频,我是通过看书学的,那时候看的书是:

1、算法分析与分析基础:这本比较简单,推荐新手看。

2、数据结构与算法分析---C语言描述:代码用C写的,推荐看。

3、挑战程序设计竞赛(第二版):也是很不错的一本书,推荐看。

具体可以看我的另外一篇文章,里面是介绍这几本书的:
算法与数据结构书籍与视频福利

说实话,我那一学期的时间几乎都花在数据结构与算法上,但刷的题很少,只是书本上的一些例题。所以当我把这些基本的过一遍之后,再去一些网站刷题依旧非常菜。

所以你们千万别指望以为自己把这些思想学完之后刷题会很牛,只有多刷题,只有多动手实践,你的灵敏度才会提高起来。

在这里说一下前阵子有个非常火爆的专栏---【数据结构与算法之美】

我没买这个专栏,我想说的是,买了就一定要去看,千万别浪费。也千万不要觉得学完这个专栏你就会变的多牛逼,如果你只是跟着进度去学习这个专栏,自己没有花时间去刷题、去动手时间。那我可以保证,你学完之后还是那么菜。

总结下:

提高数据结构与算法没啥捷径,最好的捷径就是多刷题。但是,刷题的前提是你要先学会一些基本的数据结构与算法思想。

追求完美

如何刷题?如何对待一道算法题?

我觉得,在做题的时候,一定要追求完美,千万不要把一道题做出来之后,提交通过,然后就赶紧下一道。

算法能力的提升和做题的数量是有一定的关系,但并不是线性关系。也就是说,在做题的时候,要力求一题多解,如果自己实在想不出来其他办法了,可以去看看别人是怎么做的,千万不要觉得模仿别人的做法是件丢人的事。

我做题的时候,我一看到一道题,可能第一想法就是用很粗糙的方式做,因为很多题采用暴力法都会很容易做,就是时间复杂度很高。之后,我就会慢慢思考,看看有没其他方法来降低时间复杂度或空间复杂度。最后,我会去看一下别人的做法,当然,并不是每道题都会这样执行。

衡量一道算法题的好坏无非就是时间复杂度空间复杂度,所以我们要力求完美,就要把这两个降到最低,令他们相辅相成。

我举道例题吧:

问题: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?

这道题我在以前的分章分析过,不懂的可以先看下之前写的:递归与动态规划---基础篇1

方法1::暴力递归

这道题不难,或许你会采取下面的做法:

public static int solve(int n){
    if(n == 1 || n == 2){
        return n;
    }else if(n <= 0){
        return 0;
    }else{
        return solve(n-1) + solve(n-2);
    }
}

这种做法的时间复杂度很高,指数级别了。但是如果你提交之后侥幸通过了,然后你就接着下一道题了,那么你就要好好想想了。

方法二:空间换时间

力求完美,我们可以考虑用空间换时间:这道题如何你去仔细想一想,会发现有很多是重复执行了。所以可以采取下面的方法:

//用一个HashMap来保存已经计算过的状态
static Map<Integer,Integer> map = new HashMap();
public static int solve(int n){
    if(n <= 0)return 0;
    else if(n <= 2){
        return n;
    }else{//是否计算过
        if(map.containsKey(n)){
            return map.get(n);
        }else{
            int m = solve(n-1) + solve(n-2);
            map.put(n, m);
            return m;
        }
    }
}

这样,可以大大缩短时间。也就是说,当一道题你做了之后,发现时间复杂度很高,那么可以考虑下,是否有更好的方法,是否可以用空间换时间。

方法三:斐波那契数列

实际上,我们可以把空间复杂度弄的更小,不需要HashMap来保存状态:

public static int solve(int n){
    if(n <= 0)
       return 0;
    if(n <= 2){
        return n;
    }
    
    int f1 = 0;
    int f2 = 1;
    int sum = 0;
    for(int i = 1; i<= n; i++){
        sum = f1 + f2;
        f1 = f2;
        f2 = sum;
    }
    return sum;
}

我弄这道题给你们看,并不是在教你们这道题怎么做,而是有以下目的:

1、在刷题的时候,我们要力求完美。

2、我想不到这些方法啊,怎么办?那么你就可以去看别人的做法,之后,遇到类似的题,你就会更有思路,更知道往哪个方向想。

3、可以从简单暴力入手做一道题,在考虑空间与时间之间的衡量,一点点去优化。

推荐一些刷题网站

我一般是在leetcode和牛客网刷题,感觉挺不错,题目难度不是很大。

在牛客网那里,我主要刷剑指Offer,不过那里也有个在线刷leetcode,不过里面的题量比较少。牛客网刷题有个非常方便的地方就是有个讨论区,那里会有很多大佬分享他们的解题方法,不用我们去百度找题解。所以你做完后,实在想不出,可以很方便着去看别人是怎么做的。

至于leetcode,也是大部分题目官方都有给出答案,也是个不错的刷题网站。你们可以两个挑选一个,或者两个都刷。

当然,还有其他刷题的网站,不过,其他网站没刷过,不大清除如何。

再说数据结构

前面我主要是说了我平时都是怎么学习算法的。在数据结构方法,我只是列举了你们一定要学习链表树(二叉堆),但这是最基本的,刷题之前要掌握的,对于数据结构,我列举下一些比较重要的:

1、链表(如单向链表、双向链表)。

2、树(如二叉树、平衡树、红黑树)。

3、图(如最短路径的几种算法)。

4、队列、栈、矩阵。

对于这些,自己一定要动手实现一遍。你可以看书,也可以看视频,新手可以先看视频,不过前期可以看视频,之后我建议是一定要看书。

视频和书我以前有推荐过:
算法与数据结构书籍与视频福利

例如对于平衡树,可能你跟着书本的代码实现之后,过阵子你就忘记,不过这不要紧,虽然你忘记了,但是如果你之前用代码实现过,理解过,那么当你再次看到的时候,会很快就记起来,很快就知道思路,而且你的抽象能力等等会在不知不觉中提升起来。之后再学习红黑树啊,什么数据结构啊,都会学的很快。

最最重要

动手去做,动手去做,动手去做。重要的话说三遍。

千万不要找了一堆资源,订好了学习计划,我要留到某某天就来去做.....

千万不要这样,而是当你激情来的时候,就马上去干,千万不要留到某个放假日啊什么鬼了,很多这种想法的人,最后会啥也没做的。

也不要觉得要学习的有好多啊,不知道从哪学习起。我上面说了,可以先学习最基本的,然后刷题,刷题是一个需要长期坚持的事情,一年,两年。在刷题的过程中,可以穿插和学习其他数据结构。

最后

今天就说这么多,以上主要是我自己的学习方法,希望对你有所帮助。

最后说下我这个微#信公众号苦逼的码农(ID:di201805),我主要写【计算机网络】、【数据结构与算法】、【Java】等文章。一般90%都会是原创的,偶尔有些转载的文章,只会比我自己写的文章更好,想看我文章的可以搜索关注我下哦。

一般我会一阵子更新这个模块、一阵子更新另一个模块的方式来写文章。期待你的关注。

如果你觉得有帮助,可以分享给更多的朋友哦,这便是对我最大的支持 。

查看原文

赞 2 收藏 1 评论 0

帅地 发布了文章 · 2018-09-07

设计模式走一遍---观察者模式(下)

上篇我们讲解了观察者模式的一些知识,而且自定义观察者模式的经典代码,(传送们:设计模式走一遍---观察者模式(上))

这篇简单讲一下JDK自带的观察者模式实现代码。

对于观察者模式,JDK中提供了一个Observer接口(观察者),一个Observable类(主题对象)。

注:被观察者又被称为主题对象,目标对象。

具体我们来看下源码。

1.观察者接口

public interface Observer {
    /**
     * This method is called whenever the observed *object is changed. 
     *当被观察者发生变化时,该方法将会被调用
     * @param   o     the observable object.
     * @param   arg   an argument passed to the <code>notifyObservers</code>
     *                 method.
     */
    void update(Observable o, Object arg);
}

该接口相当于观察者,里面有一个update(Observable o, Object arg)方法,Observable参数是指主题对象,该参数指明该观察者是属于哪一个主题对象的。

arg参数可以是任意对象,假如主题对象在发送通知时,想要传递什么数据给观察者,那么就可以把数据对象传递给arg参数。

2.主题对象类(方法有点多,我就不放英文解释了)

//主题对象可以是接口、抽象类、具体类,我们上节说
//一般采用抽象类,不过JDK这里使用的是具体类
public class Observable {
    //标记主题对象的状态是否改变
    private boolean changed = false;
    //存放观察者集合,之所以用Vector而不用ArrayList
    //主要是Vector是线程安全的
    private Vector<Observer> obs;

    public Observable() {
        obs = new Vector<>();
    }

    //添加一个观察者
    public synchronized void addObserver(Observer o) {
        if (o == null)
            throw new NullPointerException();
        if (!obs.contains(o)) {
            obs.addElement(o);
        }
    }

    //删除一个观察者
    public synchronized void deleteObserver(Observer o) {
        obs.removeElement(o);
    }
    
    //标记该对象的状态是否发送了改变
    protected synchronized void setChanged() {
        changed = true;
    }

    //指示该对象不会再发生改变,或者它已经通知了
    //所有观察者
    protected synchronized void clearChanged() {
        changed = false;
    }
    
    
    //测试对象是否发生了改变。当且仅当在此对象最近
    //调用了setChange()方法
    public synchronized boolean hasChanged() {
        return changed;
    }

    //如果hasChanged()方法指示此对象发送了改变,
    //则通知所有观察者,并且调用clearChanged()方法
    //指示此对象不再改变
    public void notifyObservers() {
        notifyObservers(null);
    }

    //与上面没有参数的同名方法相同,只是如果这个方
    //法的arg参数可以接受主题对象想要传递观察者的数据对象
    public void notifyObservers(Object arg) {
        //临时保存所有观察者
        Object[] arrLocal;

        synchronized (this) {
            if (!changed)
                return;
            arrLocal = obs.toArray();
            clearChanged();
        }

        for (int i = arrLocal.length-1; i>=0; i--)
            ((Observer)arrLocal[i]).update(this, arg);
    }

    //删除所有观察者
    public synchronized void deleteObservers() {
        obs.removeAllElements();
    }

    //返回观察者的数量
    public synchronized int countObservers() {
        return obs.size();
    }
}

该具体类Observable相当于主题对象,实现的主要功能就是当自己的状态发送改变时,通知观察者,观察者再根据通知,在update方法做出相应的反应。

简单写个Demo测试下。

public class Test {
    public static void main(String[] args){
        //创建一个主题对象
        AnimalSubject animalSubject = new AnimalSubject();
        animalSubject.addObserver(new DogObsever());
        animalSubject.addObserver(new LionObsever());
        //状态发生改变
        animalSubject.setChanged();
        //通知观察者
        animalSubject.notifyObservers();
    }
}

//动物主题,弄子类方便拓展主题对象功能
class AnimalSubject extends Observable{
    //不过我就不新增代码、方法了

    //不覆盖下的话,上面的测试调用不了setChange()方法
    //为了方便测试,覆盖重写下
    @Override
    protected synchronized void setChanged() {
        super.setChanged();
    }
}
class DogObsever implements Observer{
    @Override
    public void update(Observable o, Object arg) {
        System.out.println("收到通知,小狗观察者正在做出相应处理");
    }
}

class LionObsever implements Observer{
    @Override
    public void update(Observable o, Object arg) {
        System.out.println("收到通知,狮子观察者正在做出相应处理");
    }
}

打印结果

收到通知,狮子观察者正在做出相应处理
收到通知,小狗观察者正在做出相应处理

从上面的代码中我们可以发现JDk内置的观察者模式中的主题对象是一个具体类,而不是一个抽象类或接口,而且setChange()方法还被保护起来了(被定义为protected),这就意味着,要在别的类中调用该方法,那么我们必须继承在子类中重写覆盖该方法。显然,我觉得这很不友好.....

可能这也是JDK内置的观察者模式很少被拿来使用 的原因吧,一般都是自己来自定义观察者模式。

希望大家能够动手写一下这些代码,可能会碰到一些你没想到的问题。

关注公我的众号:苦逼的码农,获取更多原创文章,后台回复礼包送你一份时下热门的资源大礼包。同时也感谢把文章介绍给更多需要的人
查看原文

赞 1 收藏 1 评论 0

帅地 发布了文章 · 2018-09-06

设计模式走一遍---观察者模式

1

红灯车过,人停;绿灯人过,车停。每天走在马路上,到处可见红绿灯指挥着我们什么时候可以过马路,什么时候不能过马路。无论是人还是车,都时刻关注着红绿灯的状态,一旦红绿灯的状态发生了改变,我们总能第一时间发现,并且做出相应的响应.....说真,红绿灯真的是个伟大的发明。

说到观察者模式,无非就是观察者被观察者之间牵扯到的一些关系。在上面的红绿灯例子中,红绿灯就如同被观察者,我们又称之为观察目标,而人行者或开着车的人就如同观察者,时刻观察着红绿灯的变化,红绿灯一旦发生变化,便会马上通知观察者,观察者也经常会做出相应的反应。

下面我们说下观察者模式的定义:

观察者模式定义了对象之间的一种一对多依赖关系,使得每当一个对象状态发生改变时,其相关依赖对象皆得到通知并被自动更新。

观察者模式的别名包括发布-订阅(Publish/Subscribe)模式、模型-视图(Model/View)模式、源-监听器(Source/Listener)模式或从属者(Dependents)模式。

上面的例子中,红绿灯就相当于,而路上的人就相当于,每次红路灯这个目标对象的状态发生变化,就会通知众多的观察者(人)。而观察者一般也会做出对象的响应

观察者模式属于行为型模式

2

观察者模式主要解决的问题:一方的状态发生了变化,依赖于这一方的观察者立即能收到通知。

例如我们平时订阅的微信公众号,一旦公众号有新的文章发布,订阅者能够立即收到新的文章推送。

这里需要注意的是,目标对象会把状态的变化通知所有观察者,而不管观察者的具体身份。自己也并不知道通知的这个人究竟是谁。

3

观察者模式一般包含如下四个角色:

  1. Subject:目标对象,一般设计成抽象类
  2. ConcreteSubject:具体目标对象,Subject的子类。
  3. Observer:观察者,一般设计为接口
  4. ConcreteObserver:具体观察者,Observer的实现者

结构图:

下面具体介绍下这四个角色:

Subject(目标):目标又被称为主题,指被观察的对象,即被观察者。一般我们会在在目标中定义一个观察者集合,用来管理观察者。一个观察目标可以接受任意数量的观察者来观察,它提供一系列方法来增加和删除观察者对象,如attach()方法与detach()方法;同时也会定义通知方法notify()。目标类可以是接口,也可以是抽象类或具体类,但一般我们设计为抽象类。

ConcreteSubject(具体目标):具体目标是目标类的子类(接口的实现者),通常它包含有经常发生改变的数据,当它的状态发生改变时,向它的各个观察者发出通知;同时它还实现了在目标类中定义的抽象业务逻辑方法

Observer(观察者):观察者角色一般是一个接口,它会有一个update方法,当目标对象的状态发生改变时,这个方法就会被调用。

ConcreteObserver(具体观察者):观察者接口的实现者,在这个角色中,将会定义目标对象状态发生变化时所要处理的逻辑。

观察者模式一般的代码实现:

1.目标对象与具体目标对象代码示例

public abstract class Subject {  
    //定义一个观察者集合用于存储所有观察者对象  
protected List<Observer> observers = new ArrayList();  

    //注册方法,用于向观察者集合中增加一个观察者  
    public void attach(Observer observer) {  
    observers.add(observer);  
}  

    //注销方法,用于在观察者集合中删除一个观察者  
    public void detach(Observer observer) {  
    observers.remove(observer);  
}  

    //声明抽象通知方法  
    public abstract void notify();  
    
    //其他方法
}  


//具体目标类ConcreteSubject是实现了抽象目标类Subject的一个具体子类
//其典型代码如下所示:

class ConcreteSubject extends Subject {  

    //实现通知方法  
    public void notify() {  
    System.out.println("目标对象状态发生变化了")
    //遍历观察者集合,调用每一个观察者的响应方法  
        for(Observer obs:observers) {  
            obs.update();  
        }  
    }     
}

2.观察者与具体观察者代码示例

interface Observer {  
    //声明响应方法  
    public void update();  
}  

//在具体观察者ConcreteObserver中实现了update()方法
//其典型代码如下所示:
class ConcreteObserver implements Observer {  
    //实现响应方法  
    public void update() {  
        System.out.println("观察者收到通知,正在做相应的处理")  
    }  
}

3.测试代码

public class Test{
    public static void main(String[] args){
        Subject sub = new ConcreteSubject();
        sub.attach(new ConcreteObserver());
        //假设状态发生了变化调用notify()方法
        sub.notify();
    }
}

4.打印结果

目标对象状态发生变化了
观察者收到通知,正在做相应的处理

4

优点:

1、从例子中我们可以看出观察者和被观察者是抽象耦合的,只有轻微的关联关系

2、建立一套触发机制。目标对象一旦发生变化,便会触发广播通知,观察者一旦收到通知,也会触发相应的响应。

缺点:

1、如果一个被观察者对象有很多的直接和间接的观察者的话,将所有的观察者都通知到会花费很多时间。

2、如果在观察者和观察目标之间有循环依赖的话,观察目标会触发它们之间进行循环调用,可能导致系统崩溃。

3、观察者模式没有相应的机制让观察者知道所观察的目标对象是怎么发生变化的,而仅仅只是知道观察目标发生了变化。

使用场景:

1.一个抽象模型有两个方面,其中一个方面依赖于另一个方面。将这些方面封装在独立的对象中使它们可以各自独立地改变和复用。

2.一个对象的改变将导致其他一个或多个对象也发生改变,而不知道具体有多少对象将发生改变,可以降低对象之间的耦合度。

3.一个对象必须通知其他对象,而并不知道这些对象是谁。

4.需要在系统中创建一个触发链,A对象的行为将影响B对象,B对象的行为将影响C对象……,可以使用观察者模式创建一种链式触发机制

最后

Java语言中也有提供了Observer接口,下一篇简单讲解使用下。

参考书籍:

1.设计模式java版。

2.Head First设计模式

3.菜鸟教程网站

关注公我的众号:苦逼的码农,获取更多原创文章,后台回复礼包送你一份特别的资源大礼包。
查看原文

赞 1 收藏 0 评论 0

帅地 发布了文章 · 2018-08-29

线程安全(上)--彻底搞懂volatile关键字

对于volatile这个关键字,相信很多朋友都听说过,甚至使用过,这个关键字虽然字面上理解起来比较简单,但是要用好起来却不是一件容易的事。

这篇文章将从多个方面来讲解volatile,让你对它更加理解。

计算机中为什么会出现线程不安全的问题

volatile既然是与线程安全有关的问题,那我们先来了解一下计算机在处理数据的过程中为什么会出现线程不安全的问题。

大家都知道,计算机在执行程序时,每条指令都是在CPU中执行的,而执行指令过程中会涉及到数据的读取和写入。由于程序运行过程中的临时数据是存放在主存(物理内存)当中的,这时就存在一个问题,由于CPU执行速度很快,而从内存读取数据和向内存写入数据的过程跟CPU执行指令的速度比起来要慢的多,因此如果任何时候对数据的操作都要通过和内存的交互来进行,会大大降低指令执行的速度。

为了处理这个问题,在CPU里面就有了高速缓存(Cache)的概念。当程序在运行过程中,会将运算需要的数据从主存复制一份到CPU的高速缓存当中,那么CPU进行计算时就可以直接从它的高速缓存读取数据和向其中写入数据,当运算结束之后,再将高速缓存中的数据刷新到主存当中。

我举个简单的例子,比如cpu在执行下面这段代码的时候,

t = t + 1;

会先从高速缓存中查看是否有t的值,如果有,则直接拿来使用,如果没有,则会从主存中读取,读取之后会复制一份存放在高速缓存中方便下次使用。之后cup进行对t加1操作,然后把数据写入高速缓存,最后会把高速缓存中的数据刷新到主存中。

这一过程在单线程运行是没有问题的,但是在多线程中运行就会有问题了。在多核CPU中,每条线程可能运行于不同的CPU中,因此每个线程运行时有自己的高速缓存(对单核CPU来说,其实也会出现这种问题,只不过是以线程调度的形式来分别执行的,本次讲解以多核cup为主)。这时就会出现同一个变量在两个高速缓存中的不一致问题了。

例如:

两个线程分别读取了t的值,假设此时t的值为0,并且把t的值存到了各自的高速缓存中,然后线程1对t进行了加1操作,此时t的值为1,并且把t的值写回到主存中。但是线程2中高速缓存的值还是0,进行加1操作之后,t的值还是为1,然后再把t的值写回主存。

此时,就出现了线程不安全问题了。

Java中的线程安全问题

上面那种线程安全问题,可能对于不同的操作系统会有不同的处理机制,例如Windows操作系统和Linux的操作系统的处理方法可能会不同。

我们都知道,Java是一种夸平台的语言,因此Java这种语言在处理线程安全问题的时候,会有自己的处理机制,例如volatile关键字,synchronized关键字,并且这种机制适用于各种平台。

Java内存模型规定所有的变量都是存在主存当中(类似于前面说的物理内存),每个线程都有自己的工作内存(类似于前面的高速缓存)。线程对变量的所有操作都必须在工作内存中进行,而不能直接对主存进行操作。并且每个线程不能访问其他线程的工作内存。

由于java中的每个线程有自己的工作空间,这种工作空间相当于上面所说的高速缓存,因此多个线程在处理一个共享变量的时候,就会出现线程安全问题。

这里简单解释下共享变量,上面我们所说的t就是一个共享变量,也就是说,能够被多个线程访问到的变量,我们称之为共享变量。在java中共享变量包括实例变量,静态变量,数组元素。他们都被存放在堆内存中。

volatile关键字

上面扯了一大堆,都没提到volatile关键字的作用,下面开始讲解volatile关键字是如何保证线程安全问题的。

可见性

什么是可见性?

意思就是说,在多线程环境下,某个共享变量如果被其中一个线程给修改了,其他线程能够立即知道这个共享变量已经被修改了,当其他线程要读取这个变量的时候,最终会去内存中读取,而不是从自己的工作空间中读取

例如我们上面说的,当线程1对t进行了加1操作并把数据写回到主存之后,线程2就会知道它自己工作空间内的t已经被修改了,当它要执行加1操作之后,就会去主存中读取。这样,两边的数据就能一致了。

假如一个变量被声明为volatile,那么这个变量就具有了可见性的性质了。这就是volatile关键的作用之一了。

volatile保证变量可见性的原理

当一个变量被声明为volatile时,在编译成会变指令的时候,会多出下面一行:

0x00bbacde: lock add1 $0x0,(%esp);

这句指令的意思就是在寄存器执行一个加0的空操作。不过这条指令的前面有一个lock(锁)前缀。

当处理器在处理拥有lock前缀的指令时:

在之前的处理中,lock会导致传输数据的总线被锁定,其他处理器都不能访问总线,从而保证处理lock指令的处理器能够独享操作数据所在的内存区域,而不会被其他处理所干扰。

但由于总线被锁住,其他处理器都会被堵住,从而影响了多处理器的执行效率。为了解决这个问题,在后来的处理器中,处理器遇到lock指令时不会再锁住总线,而是会检查数据所在的内存区域,如果该数据是在处理器的内部缓存中,则会锁定此缓存区域,处理完后把缓存写回到主存中,并且会利用缓存一致性协议来保证其他处理器中的缓存数据的一致性。

缓存一致性协议

刚才我在说可见性的时候,说“如果一个共享变量被一个线程修改了之后,当其他线程要读取这个变量的时候,最终会去内存中读取,而不是从自己的工作空间中读取”,实际上是这样的:

线程中的处理器会一直在总线上嗅探其内部缓存中的内存地址在其他处理器的操作情况,一旦嗅探到某处处理器打算修改其内存地址中的值,而该内存地址刚好也在自己的内部缓存中,那么处理器就会强制让自己对该缓存地址的无效。所以当该处理器要访问该数据的时候,由于发现自己缓存的数据无效了,就会去主存中访问。

有序性

实际上,当我们把代码写好之后,虚拟机不一定会按照我们写的代码的顺序来执行。例如对于下面的两句代码:

int a = 1;
int b = 2;

对于这两句代码,你会发现无论是先执行a = 1还是执行b = 2,都不会对a,b最终的值造成影响。所以虚拟机在编译的时候,是有可能把他们进行重排序的。

为什么要进行重排序呢?

你想啊,假如执行 int a = 1这句代码需要100ms的时间,但执行int b = 2这句代码需要1ms的时间,并且先执行哪句代码并不会对a,b最终的值造成影响。那当然是先执行int b = 2这句代码了。

所以,虚拟机在进行代码编译优化的时候,对于那些改变顺序之后不会对最终变量的值造成影响的代码,是有可能将他们进行重排序的。

更多代码编译优化可以看我写的另一篇文章:
虚拟机在运行期对代码的优化策略

那么重排序之后真的不会对代码造成影响吗?

实际上,对于有些代码进行重排序之后,虽然对变量的值没有造成影响,但有可能会出现线程安全问题的。具体请看下面的代码

public class NoVisibility{
    private static boolean ready;
    private static int number;
    
    private static class Reader extends Thread{
        public void run(){
        while(!ready){
            Thread.yield();
        }
        System.out.println(number);

    }
}
    public static void main(String[] args){
        new Reader().start();
        number = 42;
        ready = true;
    }
}

这段代码最终打印的一定是42吗?如果没有重排序的话,打印的确实会是42,但如果number = 42和ready = true被进行了重排序,颠倒了顺序,那么就有可能打印出0了,而不是42。(因为number的初始值会是0).

因此,重排序是有可能导致线程安全问题的。

如果一个变量被声明volatile的话,那么这个变量不会被进行重排序,也就是说,虚拟机会保证这个变量之前的代码一定会比它先执行,而之后的代码一定会比它慢执行。

例如把上面中的number声明为volatile,那么number = 42一定会比ready = true先执行。

不过这里需要注意的是,虚拟机只是保证这个变量之前的代码一定比它先执行,但并没有保证这个变量之前的代码不可以重排序。之后的也一样。

volatile关键字能够保证代码的有序性,这个也是volatile关键字的作用。

总结一下,一个被volatile声明的变量主要有以下两种特性保证保证线程安全。

  1. 可见性。
  2. 有序性。

volatile真的能完全保证一个变量的线程安全吗?

我们通过上面的讲解,发现volatile关键字还是挺有用的,不但能够保证变量的可见性,还能保证代码的有序性。

那么,它真的能够保证一个变量在多线程环境下都能被正确的使用吗?

答案是否定的。原因是因为Java里面的运算并非是原子操作

原子操作

原子操作:即一个操作或者多个操作 要么全部执行并且执行的过程不会被任何因素打断,要么就都不执行。

也就是说,处理器要嘛把这组操作全部执行完,中间不允许被其他操作所打断,要嘛这组操作不要执行。

刚才说Java里面的运行并非是原子操作。我举个例子,例如这句代码

int a = b + 1;

处理器在处理代码的时候,需要处理以下三个操作:

  1. 从内存中读取b的值。
  2. 进行a = b + 1这个运算
  3. 把a的值写回到内存中

而这三个操作处理器是不一定就会连续执行的,有可能执行了第一个操作之后,处理器就跑去执行别的操作的。

证明volatile无法保证线程安全的例子

由于Java中的运算并非是原子操作,所以导致volatile声明的变量无法保证线程安全。

对于这句话,我给大家举个例子。代码如下:

public class Test{
    public static volatile int t = 0;
    
    public static void main(String[] args){
    
        Thread[] threads = new Thread[10];
        for(int i = 0; i < 10; i++){
            //每个线程对t进行1000次加1的操作
            threads[i] new Thread(new Runnable(){
                @Override
                public void run(){
                    for(int j = 0; j < 1000; j++){
                        t = t + 1;
                    }
                }
            });
            threads[i].start();
        }
        
        //等待所有累加线程都结束
        while(Thread.activeCount() > 1){
            Thread.yield();
        }
        
        //打印t的值
        System.out.println(t);
    }
}

最终的打印结果会是1000 * 10 = 10000吗?答案是否定的。

问题就出现在t = t + 1这句代码中。我们来分析一下

例如:

线程1读取了t的值,假如t = 0。之后线程2读取了t的值,此时t = 0。

然后线程1执行了加1的操作,此时t = 1。但是这个时候,处理器还没有把t = 1的值写回主存中。这个时候处理器跑去执行线程2,注意,刚才线程2已经读取了t的值,所以这个时候并不会再去读取t的值了,所以此时t的值还是0,然后线程2执行了对t的加1操作,此时t =1 。

这个时候,就出现了线程安全问题了,两个线程都对t执行了加1操作,但t的值却是1。所以说,volatile关键字并不一定能够保证变量的安全性。

什么情况下volatile能够保证线程安全

刚才虽然说,volatile关键字不一定能够保证线程安全的问题,其实,在大多数情况下volatile还是可以保证变量的线程安全问题的。所以,在满足以下两个条件的情况下,volatile就能保证变量的线程安全问题:

  1. 运算结果并不依赖变量的当前值,或者能够确保只有单一的线程修改变量的值。
  2. 变量不需要与其他状态变量共同参与不变约束。

讲到这里,关于volatile关键字的就算讲完了。如果有哪里讲的不对的地方,非常欢迎你的指点。下篇应该会讲synchronize关键字。

参考书籍:

  1. 深入理解Java虚拟机(JVM高级特性与最佳实践)。
  2. Java并非编程实战
关注公众号:苦逼的码农,获取更多原创文章,后台回复"礼包"送你一份资源大礼包。
查看原文

赞 0 收藏 0 评论 0

帅地 分享了头条 · 2018-08-28

详细总结了有关字符串常量池的一些问题,相信可以帮助大家解决一些疑惑。

赞 0 收藏 2 评论 0

帅地 评论了文章 · 2018-08-28

聊一聊让我蒙蔽一晚上的各种常量池

在写之前我们先来看几个问题,假如你对这些问题已经很懂了的话,那大可不用看这篇文章,如果不大懂的话,那么可以看看我的想法。

问题1:

public static void main(String[] args){
    String t1 = new String("2");
    t1.intern();
    String t2 = "2";
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    t3.intern();
    String t4 = "22";
    System.out.println(t3 == t4);
}

答案输出:

JDK1.6是 false false

JDK1.7是 false true;

问题2(把问题1的语句调换一下位置)

public static void main(String[] args){
    String t1 = new String("2");
    String t2 = "2";
    t1.intern();
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    String t4 = "22";
    t3.intern();
    System.out.println(t3 == t4);
}

答案输出:
false false

对于这两个问题,看了几个人的博客,可谓百花齐放,越看越懵逼

问题3

public static void main(String[] args){
    Integer a = 1;
    Integer b = 2;
    Integer c = 3;
    Integer d = 3;
    Integer e = 321;
    Integer f = 321;
    Long g = 3L;
    
    System.out.println(c == d);
    System.out.Println(e == f);
    System.out.println(c == (a + b));
    System.out.println(c.equals(a+b));
    System.out.println(g == (a + b));
    System.out.println(g.equals(a + b));
}

答案输出:

true

false

true

true

true

false

问题4:

运行时常量池与字符串常量池是什么关系?包含?

在解决问题之前,我们先来简单了解一些常量池的一些知识点(大部分来源于周志明的深入Java虚拟机这本书)。

JVM中的几种常量池

1.class文件常量池

在Class文件中除了有类的版本、字段、方法、接口等描述信息外,还有一项信息是常量池(Constant Pool Table),用于存放编译期生成的各种字面量和符号引用。

这里简单解释下字面量和符号引用

字面量

字面量类似与我们平常说的常量,主要包括:

  1. 文本字符串:就是我们在代码中能够看到的字符串,例如String a = "aa"。其中"aa"就是字面量。
  2. 被final修饰的变量。

符号引用

主要包括以下常量:

  1. 类和接口和全限定名:例如对于String这个类,它的全限定名就是java/lang/String。
  2. 字段的名称和描述符:所谓字段就是类或者接口中声明的变量,包括类级别变量(static)和实例级的变量。
  3. 方法的名称和描述符。所谓描述符就相当于方法的参数类型+返回值类型

2.运行时常量池

我们上面说的class文件中的常量池,它会在类加载后进入方法区中的运行时常量池。并且需要的注意的是,运行时常量池是全局共享的,多个类共用一个运行时常量池。并且class文件中常量池多个相同的字符串在运行时常量池只会存在一份。

注意运行时常量池存在于方法区中。

3.字符串常量池

看名字我们就可以知道字符串常量池会用来存放字符串,也就是说常量池中的文本字符串会在类加载时进入字符串常量池。

那字符串常量池和运行时常量池是什么关系呢?上面我们说常量池中的字面量会在类加载后进入运行时常量池,其中字面量中有包括文本字符串,显然从这段文字我们可以知道字符串常量池存在于运行时常量池中。也就存在于方法区中。

不过在周志明那本深入java虚拟机中有说到,到了JDK1.7时,字符串常量池就被移出了方法区,转移到了里了。

那么我们可以推断,到了JDK1.7以及之后的版本中,运行时常量池并没有包含字符串常量池,运行时常量池存在于方法区中,而字符串常量池存在于中。

说了这么多,现在我们开始来解决上面提出了问题。

解决问题

问题1:

public static void main(String[] args){
    String t1 = new String("1");
    t1.intern();
    String t2 = "1";
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    t3.intern();
    String t4 = "22";
    System.out.println(t3 == t4);
}

答案输出:

JDK1.6是 false false。

JDK1.7是 false true;

在解决这个问题之前,我们先来看另外一道面试中经常会问到的问题。


String t = new String("tt");

假如程序中只有这样一行代码,那么这行代码创建了几个对象?

我们上面说过,"tt"属于字面量,那么它会在类加载之后存在于字符串常量池中,也就是说,在 String t = new String("tt")这句代码执行之前,字符串常量池就已经创建了"tt"这个字符串对象了,我们都知道,new这个关键字会在堆中创建一个对象。

所以,这段代码创建了两个对象。一个在堆中,一个在字符串常量池中。

那么下面这段代码又是创建了几个对象呢?

String t1 = new String("tt");
String t2 = new String("tt");

答是这段代码创建了三个对象,我们上面说了,字符串常量池只会保存一份内容相同的字符串。也就是说,在这两句代码执行之前,字符串常量池就已经创建了内容为"tt"的对象了。这两句代码执行之后,又在堆中创建了两个,所以一共创建了三个。

那么下面这段代码又是创建了几个对象?

String t = "tt";

答是1个,在这段代码执行之前,字符串常量池已经创建了一个"tt"的对象,但由于这行代码并非用new的方法,所以虚拟机会在字符串常量池中寻找是否有内容为"tt"的字符串对象,如果有,则直接返回这个字符串的引用,所以最终结果只创建了一个对象。

回到我们的问题,在这里我们先解释下String 的intern方法

例如我们调用了t.intern()。

在JDK1.6的时候,调用了这个方法之后,虚拟机会在字符串常量池在查找是否有内容与"tt"相等的对象,如果有,则返回这个对象,如果没有,则会在字符串常量池中添加这个对象。注意,是把这个对象添加到字符串常量池。

到了JDK1.7之后,如果调用了intern这个方法,虚拟机会在字符串常量池在查找是否有内容与"tt"相等的对象,如果有,则返回这个对象,如果没有。则会在堆中把这个对象的引用复制添加到字符串常量池中。注意,这个时候添加的是对象在堆中的引用。

现在开始来分析问题中的代码

t1 = new String("1")。

这句代码执行之前,字符串常量池中已经有"t"这个对象,执行之后会在堆中也创建一个"t"的对象,此时t1指向的是堆中的对象

t1.intern();

这句代码执行之后,会在字符串常量池寻早内容为"t"的对象,字符串常量池已经存在这个对象了,把这个对象返回(不过返回之后并没有变量来接收)。

t2 = "1"。

这句执行后会在字符串常量池查找内容为"t"的对象,字符串常量池已经有这个对象了,返回给t2,此时t2指向的是常量池中的对象

一个是常量池中的对象,一个是在堆中的对象,两者能相等吗?因此

t1 与 t2不相等。

接着下面

t3 = new String("2") + new String("2");

这段代码调用之前,字符串常量池有一个"2"的对象,执行之后,实际上会调用StringBuilder的append()方法类进行拼接,最后在堆中创建一个"22"的对象,注意,此时字面量并没有"22"这个字符串,也就是说在字符串常量池并没有"22"这个对象。此时t3指向堆中"22"这个对象

t3.intern();

执行这个方法之后

在JDK1.6的时候,它在字符串常量池中并没有找到内容为"22"的对象,所以这个时候会把这个对象添加到字符串常量池,并把这个对象返回(此时并没有变量来接收这个返回的对象)。注意添加的是对象,而并非引用。

t4 = "22"。

这句代码执行后,会返回字符串常量池中内容为"22"对象,此时t4指向的是字符串常量池中的对象

显然,一个对象在字符串常量池,一个在堆中,两个对象并非是同一个对象,因此在JDK1.6的时候,t3与t4不相等。

但是在JDK1.7的时候

t3.intern()执行之后,由于在字符串常量池在并没有内容为"22"的对象,所以会把堆中该对象的引用赋值到字符串常量池。注意此时字符串常量池保存的是堆中这个对象的引用

t4 = "22"。

执行这句代码之后,从字符串常量池返回给t4的是堆中对象的引用。此时t4指向的实际上是堆中对象的引用,也就是说,t3和t4指向的是同一个对象。

因此t3与t4相等。

不知道你明白了没有?反正我是搞了好久才明白...

问题2

至于问题2,我就只讲下半部分的代码,上半部分如果你看懂了问题1,那么问题2也差不多自然懂了。

String t3 = new String("2") + new String("2");
String t4 = "22";
t3.intern();
System.out.println(t3 == t4);

t3 = new String("2") + new String("2")。

这段代码调用之前,字符串常量池有一个"2"的对象,执行之后,实际上会调用StringBuilder的append()方法类进行拼接,最后在堆中创建一个"22"的对象。此时t3指向堆中"22"这个对象

t4 = "22"。

这句代码执行之前,字符串常量池已经存在"22"这个对象了,所有直接把这个对象返回给t4,此时t4指向的是字符串常量池中的对象.

所以t3和t4肯定不是同一个对象啊,t3.intern这句几乎可以忽略,不会给t3和t4造成任何影响。

问题3

public static void main(String[] args){
    Integer a = 1;
    Integer b = 2;
    Integer c = 3;
    Integer d = 3;
    Integer e = 321;
    Integer f = 321;
    Long g = 3L;
    
    System.out.println(c == d);
    System.out.Println(e == f);
    System.out.println(c == (a + b));
    System.out.println(c.equals(a+b));
    System.out.println(g == (a + b));
    System.out.println(g.equals(a + b));
}

对于这个问题,我简单说一下可能你就懂了。

(1). 内存中有一个java基本类型封装类的常量池。这些类包括
Byte, Short, Integer, Long, Character, Boolean。需要注意的是,Float和Double这两个类并没有对应的常量池。

(2).上面5种整型的包装类也只是在对象数值在-128~127才可以使用这些常量池。

(3). 在周志明的那本虚拟机中有这样一句话:包装类的
"=="运行符在不遇到算术运算的情况下不会自动拆箱,以及他们的equals()方法不处理数据类型的关系,可以推断出如果遇到“==”两边有算术运算是话就会自动拆箱和进行数据类型转换处理。

(4).Long的equals方法会先判断是否是Long类型。

(5).无论是Integer还是Long,他们的equals方法比较的是数值。

所以:

System.out.println(c == d)。

由于常量池的作用,c与d指向的是同一个对象(注意此时的==比较的是对象,也就是地址,而不是数值)。因此为true

System.out.println(e == f)。

由于321超过了127,因此常量池失去了作用,所以e和f数值虽然相同,但不是同一个对象,以此为false。

System.out.println(c == (a+b))。

此时==两边有算术运算,会进行拆箱,因此此时比较的是数值,而并非对象。因此为true。

System.out.println(c.equals(a+b))

c与a+b的数值相等,为true。

System.out.pirnln(g == (a + b))

由于==两边有算术运算,所以比较的是数值,因此为true。

System.out.println(g.equals(a+b))。

Long类型的equal在比较是时候,会先判断a+b是否为Long类型,显然a+b不是,因此false

问题到此就结束了,以上便是自己的理解,以上如果有不对劲的地方,非常欢迎你的指点。

关注公众号「苦逼的码农」,获取更多原创文章,后台回复「礼包」送你一份特别的大礼包
查看原文

帅地 发布了文章 · 2018-08-28

聊一聊让我蒙蔽一晚上的各种常量池

在写之前我们先来看几个问题,假如你对这些问题已经很懂了的话,那大可不用看这篇文章,如果不大懂的话,那么可以看看我的想法。

问题1:

public static void main(String[] args){
    String t1 = new String("2");
    t1.intern();
    String t2 = "2";
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    t3.intern();
    String t4 = "22";
    System.out.println(t3 == t4);
}

答案输出:

JDK1.6是 false false

JDK1.7是 false true;

问题2(把问题1的语句调换一下位置)

public static void main(String[] args){
    String t1 = new String("2");
    String t2 = "2";
    t1.intern();
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    String t4 = "22";
    t3.intern();
    System.out.println(t3 == t4);
}

答案输出:
false false

对于这两个问题,看了几个人的博客,可谓百花齐放,越看越懵逼

问题3

public static void main(String[] args){
    Integer a = 1;
    Integer b = 2;
    Integer c = 3;
    Integer d = 3;
    Integer e = 321;
    Integer f = 321;
    Long g = 3L;
    
    System.out.println(c == d);
    System.out.Println(e == f);
    System.out.println(c == (a + b));
    System.out.println(c.equals(a+b));
    System.out.println(g == (a + b));
    System.out.println(g.equals(a + b));
}

答案输出:

true

false

true

true

true

false

问题4:

运行时常量池与字符串常量池是什么关系?包含?

在解决问题之前,我们先来简单了解一些常量池的一些知识点(大部分来源于周志明的深入Java虚拟机这本书)。

JVM中的几种常量池

1.class文件常量池

在Class文件中除了有类的版本、字段、方法、接口等描述信息外,还有一项信息是常量池(Constant Pool Table),用于存放编译期生成的各种字面量和符号引用。

这里简单解释下字面量和符号引用

字面量

字面量类似与我们平常说的常量,主要包括:

  1. 文本字符串:就是我们在代码中能够看到的字符串,例如String a = "aa"。其中"aa"就是字面量。
  2. 被final修饰的变量。

符号引用

主要包括以下常量:

  1. 类和接口和全限定名:例如对于String这个类,它的全限定名就是java/lang/String。
  2. 字段的名称和描述符:所谓字段就是类或者接口中声明的变量,包括类级别变量(static)和实例级的变量。
  3. 方法的名称和描述符。所谓描述符就相当于方法的参数类型+返回值类型

2.运行时常量池

我们上面说的class文件中的常量池,它会在类加载后进入方法区中的运行时常量池。并且需要的注意的是,运行时常量池是全局共享的,多个类共用一个运行时常量池。并且class文件中常量池多个相同的字符串在运行时常量池只会存在一份。

注意运行时常量池存在于方法区中。

3.字符串常量池

看名字我们就可以知道字符串常量池会用来存放字符串,也就是说常量池中的文本字符串会在类加载时进入字符串常量池。

那字符串常量池和运行时常量池是什么关系呢?上面我们说常量池中的字面量会在类加载后进入运行时常量池,其中字面量中有包括文本字符串,显然从这段文字我们可以知道字符串常量池存在于运行时常量池中。也就存在于方法区中。

不过在周志明那本深入java虚拟机中有说到,到了JDK1.7时,字符串常量池就被移出了方法区,转移到了里了。

那么我们可以推断,到了JDK1.7以及之后的版本中,运行时常量池并没有包含字符串常量池,运行时常量池存在于方法区中,而字符串常量池存在于中。

说了这么多,现在我们开始来解决上面提出了问题。

解决问题

问题1:

public static void main(String[] args){
    String t1 = new String("1");
    t1.intern();
    String t2 = "1";
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    t3.intern();
    String t4 = "22";
    System.out.println(t3 == t4);
}

答案输出:

JDK1.6是 false false。

JDK1.7是 false true;

在解决这个问题之前,我们先来看另外一道面试中经常会问到的问题。


String t = new String("tt");

假如程序中只有这样一行代码,那么这行代码创建了几个对象?

我们上面说过,"tt"属于字面量,那么它会在类加载之后存在于字符串常量池中,也就是说,在 String t = new String("tt")这句代码执行之前,字符串常量池就已经创建了"tt"这个字符串对象了,我们都知道,new这个关键字会在堆中创建一个对象。

所以,这段代码创建了两个对象。一个在堆中,一个在字符串常量池中。

那么下面这段代码又是创建了几个对象呢?

String t1 = new String("tt");
String t2 = new String("tt");

答是这段代码创建了三个对象,我们上面说了,字符串常量池只会保存一份内容相同的字符串。也就是说,在这两句代码执行之前,字符串常量池就已经创建了内容为"tt"的对象了。这两句代码执行之后,又在堆中创建了两个,所以一共创建了三个。

那么下面这段代码又是创建了几个对象?

String t = "tt";

答是1个,在这段代码执行之前,字符串常量池已经创建了一个"tt"的对象,但由于这行代码并非用new的方法,所以虚拟机会在字符串常量池中寻找是否有内容为"tt"的字符串对象,如果有,则直接返回这个字符串的引用,所以最终结果只创建了一个对象。

回到我们的问题,在这里我们先解释下String 的intern方法

例如我们调用了t.intern()。

在JDK1.6的时候,调用了这个方法之后,虚拟机会在字符串常量池在查找是否有内容与"tt"相等的对象,如果有,则返回这个对象,如果没有,则会在字符串常量池中添加这个对象。注意,是把这个对象添加到字符串常量池。

到了JDK1.7之后,如果调用了intern这个方法,虚拟机会在字符串常量池在查找是否有内容与"tt"相等的对象,如果有,则返回这个对象,如果没有。则会在堆中把这个对象的引用复制添加到字符串常量池中。注意,这个时候添加的是对象在堆中的引用。

现在开始来分析问题中的代码

t1 = new String("1")。

这句代码执行之前,字符串常量池中已经有"t"这个对象,执行之后会在堆中也创建一个"t"的对象,此时t1指向的是堆中的对象

t1.intern();

这句代码执行之后,会在字符串常量池寻早内容为"t"的对象,字符串常量池已经存在这个对象了,把这个对象返回(不过返回之后并没有变量来接收)。

t2 = "1"。

这句执行后会在字符串常量池查找内容为"t"的对象,字符串常量池已经有这个对象了,返回给t2,此时t2指向的是常量池中的对象

一个是常量池中的对象,一个是在堆中的对象,两者能相等吗?因此

t1 与 t2不相等。

接着下面

t3 = new String("2") + new String("2");

这段代码调用之前,字符串常量池有一个"2"的对象,执行之后,实际上会调用StringBuilder的append()方法类进行拼接,最后在堆中创建一个"22"的对象,注意,此时字面量并没有"22"这个字符串,也就是说在字符串常量池并没有"22"这个对象。此时t3指向堆中"22"这个对象

t3.intern();

执行这个方法之后

在JDK1.6的时候,它在字符串常量池中并没有找到内容为"22"的对象,所以这个时候会把这个对象添加到字符串常量池,并把这个对象返回(此时并没有变量来接收这个返回的对象)。注意添加的是对象,而并非引用。

t4 = "22"。

这句代码执行后,会返回字符串常量池中内容为"22"对象,此时t4指向的是字符串常量池中的对象

显然,一个对象在字符串常量池,一个在堆中,两个对象并非是同一个对象,因此在JDK1.6的时候,t3与t4不相等。

但是在JDK1.7的时候

t3.intern()执行之后,由于在字符串常量池在并没有内容为"22"的对象,所以会把堆中该对象的引用赋值到字符串常量池。注意此时字符串常量池保存的是堆中这个对象的引用

t4 = "22"。

执行这句代码之后,从字符串常量池返回给t4的是堆中对象的引用。此时t4指向的实际上是堆中对象的引用,也就是说,t3和t4指向的是同一个对象。

因此t3与t4相等。

不知道你明白了没有?反正我是搞了好久才明白...

问题2

至于问题2,我就只讲下半部分的代码,上半部分如果你看懂了问题1,那么问题2也差不多自然懂了。

String t3 = new String("2") + new String("2");
String t4 = "22";
t3.intern();
System.out.println(t3 == t4);

t3 = new String("2") + new String("2")。

这段代码调用之前,字符串常量池有一个"2"的对象,执行之后,实际上会调用StringBuilder的append()方法类进行拼接,最后在堆中创建一个"22"的对象。此时t3指向堆中"22"这个对象

t4 = "22"。

这句代码执行之前,字符串常量池已经存在"22"这个对象了,所有直接把这个对象返回给t4,此时t4指向的是字符串常量池中的对象.

所以t3和t4肯定不是同一个对象啊,t3.intern这句几乎可以忽略,不会给t3和t4造成任何影响。

问题3

public static void main(String[] args){
    Integer a = 1;
    Integer b = 2;
    Integer c = 3;
    Integer d = 3;
    Integer e = 321;
    Integer f = 321;
    Long g = 3L;
    
    System.out.println(c == d);
    System.out.Println(e == f);
    System.out.println(c == (a + b));
    System.out.println(c.equals(a+b));
    System.out.println(g == (a + b));
    System.out.println(g.equals(a + b));
}

对于这个问题,我简单说一下可能你就懂了。

(1). 内存中有一个java基本类型封装类的常量池。这些类包括
Byte, Short, Integer, Long, Character, Boolean。需要注意的是,Float和Double这两个类并没有对应的常量池。

(2).上面5种整型的包装类也只是在对象数值在-128~127才可以使用这些常量池。

(3). 在周志明的那本虚拟机中有这样一句话:包装类的
"=="运行符在不遇到算术运算的情况下不会自动拆箱,以及他们的equals()方法不处理数据类型的关系,可以推断出如果遇到“==”两边有算术运算是话就会自动拆箱和进行数据类型转换处理。

(4).Long的equals方法会先判断是否是Long类型。

(5).无论是Integer还是Long,他们的equals方法比较的是数值。

所以:

System.out.println(c == d)。

由于常量池的作用,c与d指向的是同一个对象(注意此时的==比较的是对象,也就是地址,而不是数值)。因此为true

System.out.println(e == f)。

由于321超过了127,因此常量池失去了作用,所以e和f数值虽然相同,但不是同一个对象,以此为false。

System.out.println(c == (a+b))。

此时==两边有算术运算,会进行拆箱,因此此时比较的是数值,而并非对象。因此为true。

System.out.println(c.equals(a+b))

c与a+b的数值相等,为true。

System.out.pirnln(g == (a + b))

由于==两边有算术运算,所以比较的是数值,因此为true。

System.out.println(g.equals(a+b))。

Long类型的equal在比较是时候,会先判断a+b是否为Long类型,显然a+b不是,因此false

问题到此就结束了,以上便是自己的理解,以上如果有不对劲的地方,非常欢迎你的指点。

关注公众号「苦逼的码农」,获取更多原创文章,后台回复「礼包」送你一份特别的大礼包
查看原文

赞 4 收藏 2 评论 2

帅地 发布了文章 · 2018-08-26

JVM(2)--一文读懂垃圾回收

与其他语言相比,例如c/c++,我们都知道,java虚拟机对于程序中产生的垃圾,虚拟机是会自动帮我们进行清除管理的,而像c/c++这些语言平台则需要程序员自己手动对内存进行释放。

虽然这种自动帮我们回收垃圾的策略少了一定的灵活性,但却让代码编写者省去了很多工作,同时也提高了很多安全性。(因为像C/C++假如你创建了大量的对象,但却由于自己的疏忽忘了将他们进行释放,可能会造成内存溢出)。

何为垃圾?

刚才说了,虚拟机会自动帮助我们进行垃圾的清除,那什么样的对象我们才可以称为是垃圾对象呢?

假如你创建了一个对象

Man m = new Man();

你用一个变量指向了这个对象,显然对于这个对象,你可以用变量m对这个对象进行利用,但过了一段时间,你执行了

m = null;

并且也并没有新的变量来指向刚才创建的对象。此时对于这个没有任何变量指向的对象,你觉得它还有用处吗?

显然,对于这种没有被变量指向的对象,它是一点卵用也没有的,它只能在随风漂流。

因此,对于这样的对象,我们就可以把它称为垃圾了,它早晚会被垃圾回收器给干掉。

怎么知道它已经是垃圾对象了?

假如代码是你自己编写的,你可能知道这个对象啥时候应该被抛弃,你可以随时让它成为垃圾对象。

但是,你毕竟是你,虚拟机则没那么智能。那虚拟机是如何知道的呢?

上面已经说了,没有变量引用这个对象时,它就是垃圾对象了,基于这个原理,我们可以这样做啊:

我们可以为这个对象设置一个计数器,初始值为0,假如有一个变量指向它,那么计数器就加1,如果这个变量不在指向它了,计数器就减1。那么我们就可以判断,如果这个计数器为0的话,那它就是垃圾对象了,否则就是有用的对象。

对于这种方法,我们称之为引用计数法

好吧,我们先来夸一夸引用计数法这种方法:

  1. 实现简单。
  2. 效率高(一个if语句就能解决的问题想不高效都难)。

不好意思,接下来得说说它那个致命的缺点

实际上,对于这种引用计数的方法,假如它遇到对象互相引用的话,是很难解决的。

先看一段代码:

Man m1 = new Man();
Man m2 = new Man();
//互相引用
m1.instance = m2;//假设Man有instance这个属性
m2.instance = m1;

m1 = null;
m2 = null;
System.gc();//按道理对象应该被回收

这段代码m1和m2都指向null了,按道理两个对象已经是无用对象,应该被回收,但是,两个对象之间彼此有一个instance的属性互相牵引的对方,导致两个对象并没有被回收。

这个缺点够致命吧?

所以,虚拟机并没有采用这种引用计数的方法。

可达性分析

除了这种方法,我们还有其他的方法吗?

答案是有的,必须得有啊。这种方法就是传说中的可达性分析,(我靠,听名字是真的高级啊)。它的工作原理是这样的:

在程序开始时,会建立一个引用根节点(GC Roots),并构建一个引用图。当需要判断谁是垃圾时,我们可以从这个根节点进行遍历,如果没有被遍历到的节点则是垃圾对象,否则就是有用对象。如下图:

这个方法可以解决循环相互引用的问题,但是这个方法并没有引用计数法高效,毕竟要遍历图啊。

总结下判断是否为垃圾对象的算法:

  1. 引用计数法。
  2. 可达性分析。

何时进行垃圾回收

可能有人会觉得这个问题很奇怪,觉得看到垃圾就回收不是很好。对于这个我只能说:

  1. 看到房间有一点垃圾你会马上扫?还是等到某个时间点或者当垃圾积累到一定的数量再扫?
  2. 虚拟机可没那么智能可以马上识别这个对象是垃圾对象,它还得遍历所有对象才能知道有哪些是垃圾对象。

所以说,你总不能几秒(我们假设几秒是贼短的时间)就让虚拟机遍历一下所有对象吧?

这里先说明一下,当垃圾回收器在进行垃圾回收的时候,为了保证垃圾回收不受干扰,是会暂停所有线程的,此时程序无法对外部的请求进行响应。(因为你想啊,当你在可达性分析的时候,那些引用关系还在不断着变化,那不很难受)。

而且频繁的垃圾回收,对于有一些程序,是很影响用户体验的,例如你在玩游戏,系统动不动就停顿一下,怕你是要把这游戏给删了。

所以说,垃圾回收是会等到内存被使用了一定的比例的时候,才会触发垃圾回收。至于这个比例是多少,这可能就是人为规定的了。

怎么回收?

当我们标记好了哪些是垃圾,想要进行回收的时候,该怎么回收比较好呢?

可能有一些人就觉得奇怪,这还不简单,看见它是垃圾,直接回收不就得了。

其实这也不无道理,简单粗暴,直接回收。

是的,确实有这样的算法,看哪些是被我们标记的垃圾,看见了就直接回收。这种算法我们称之为标记--清除算法

标记-清除算法工作原理:就是先标记出所有需要回收的对象,然后在统一回收所有被标记过的对象。

不过,那些人你可别得意啊,因为这种方法虽然简单暴力,但它有个致命的缺点就是:

标记清除过后,会产生大量的不连续内存碎片,如果不连续的碎片过多的话,,可能会导致有一些大的对象存不进去。这样,会导致下面两个问题:

  1. 有些内存浪费了。
  2. 对象存不进去,会又一次触发垃圾回收。

复制算法

为了解决这种问题,另外一种算法出现了---复制算法。就是说,它会将可用的内存按容量划分成两块。然后每次只使用其中的一块,当这一块快用完的时候,就会触发垃圾回收,它会把还存活的对象全部复制到另外一块内存中去,然后把这块内存全部清理了。

这样,就不会出现碎片问题了。

居然帮我们解决了我们必须夸一下它:不仅帮我们解决了问题,而且实现上也简单、运行也高效。

但是(凡事都有个但是的),它也是有缺点的,缺点很明显,发现了没有。假如每次存活的对象都很少很少,那另外一块内存不是几乎没有用到?所以说,这种方法有可能导致另外一半内存几乎没用了。内存那么宝贵,这可是很严重的问题。

优化策略:可以告诉你,有研究显示,其实有98%的对象都是朝生夕死的,也就是说,每次存活的对象确实很少很少。既然我们都知道存活的对象很少很少了,那我们干嘛还1:1的比例来分配?所以说,HotShot虚拟机是默认按8:1的比例来分配的。这样,就不会出现很多内存没用到的问题了。

可能有人会说,万一占比为1/9的内存不够用了怎么办?不就没地方存那些活的对象?实际上,当内存不够用时,可以向其他地方借些内存来使用,例如老年代里的内存。

这里说明一下新生代和老年代:说白了,新生代就是刚刚创建不久的对象,而老年代是已经活了挺久的对象。也就是说,有一些对象是确实活的比较久的,对于这种对象,我们另外给它分配内存来养老,而且垃圾回收时,我们不用每次都来这里查找有没垃圾对象,因为这些对象是垃圾的几率会比较小。

下面在简单介绍另外两种算法:

  1. 标记-整理算法:这种算法和标记-清除算法类似,不过它把垃圾清除了之后,会让存活的对象往一个方向靠拢,以此来整理碎片。
  2. 分代收集算法:所谓分代就是把对象分成类似上面说的老年代和新生代,在新手代一般每次垃圾回收时死的对象一般都会比较多,而老年代会比较少,基于这种关系,我们就可以采取不同的算法来针对了。

总结下垃圾回收的几种算法:

  1. 标记-清除算法。
  2. 复制算法。
  3. 标记-整理算法。
  4. 分代收集算法。

最后给大家几种垃圾回收器

对于垃圾的回收,你是想一边运行程序其他代码一边进行垃圾回收?还是想把垃圾全收好再来执行程序的其他代码?虽然说最终使用cpu的时间是一样,但两种方式还是有区别的。

下面简单介绍几种垃圾回收器,看看他们都使用哪种方。

(1).Serial收集器

serial(串行),看这个英文单词就知道这是一个单线程收集器。也就是说,它在进行垃圾回收时,必须暂停其他所有线程。显然,有时垃圾回收停顿的比较久的话,这对于用户来说是很难受的。

(2).ParNew

这个收集器和Serial很类似,进行垃圾回收的时候,也是得暂停其他所有线程,不过,它可以多条线程工作进行垃圾回收。

(3).Parallel Scavenge收集器

parallel,并行的意思。也是可以多线程进行垃圾回收处理,但是它与ParNew不同。它会严格控制垃圾回收的时间与执行其他代码的时间之间的比例。我们来看一个名词:吞吐量

吞吐量 = 运行用户代码时间 / (运行用户代码时间 + 垃圾收集时间)。

也就是说,Parallet Scavenge收集器会严格控制吞吐量,至于这个吞吐量是多少,这个可以人为设置。

下面两个收集器重点介绍下

(4).CMS(Concurrent Mark Sweep)收集器

CMS收集器是基于“标记-清除”算法实现的,它的运作过程相对于前面几种收集器来说要更复杂一些,整个过程分为4个步骤,包括:

  1. 初始标记(CMS initial mark)
  2. 并发标记(CMS concurrent mark)
  3. 重新标记(CMS remark)
  4. 并发清除(CMS concurrent sweep)

其中初始标记、重新标记这两个步骤仍然需要暂停其他线程。但另外两个步骤可以和其他线程并发执行。初始标记仅仅只是标记一下GCRoots能直接关联到的对象,速度很快,并发标记阶段就是进行GC Roots Tracing的过程 (说白了就是把整个图都遍历了,找出没有的对象)

而重新标记阶段则是为了修正并发标记期间,因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录,这个阶段的停顿时间一般会比初始标记阶段稍长一些,但远比并发标记的时间短。

由于整个过程中耗时最长的并发标记和并发清除过程中,收集器线程都可以与用户线程一起工作,所以总体上来说,CMS收集器的内存回收过程几乎是与与用户线程一起并发地执行。

(5).G1收集器

这个估计是最牛的收集器了。该收集器具有如下特点:

  1. 并行与并发:G1能充分利用现代计算器多CPU,多核的硬件优势,可以使用并发或并行的方式来缩短让其他线程暂停的优势。
  2. 分代收集:就是类似像分出新生代和老年代那样处理。
  3. 空间整合:采用了复制算法+标记-整合算法的特点来回收垃圾。就是整体采用标记-整理算法,局部采用复制算法
  4. 可预测停顿:这个就牛了,就是说,它能让使用者明确指定在一个长度为M毫秒的时间片段内,消耗在垃圾收集上的时间不超过N毫秒。

它的执行过程大体如下:

  1. 初始标记。
  2. 并发标记。
  3. 最终标记。
  4. 筛选回收。

这个流程和CMS很相似,它也是在初始标记最终标记需要暂停其他线程,但其他两个过程就可以和其他线程并发执行。

刚才我们说了G1收集器哪些优点,例如可预测停顿,这也使得筛选回收,是可以预测停顿垃圾回收的时间的,也就是说,停顿的时间是用户自己可以控制的,这也使得一般情况下,在筛选回收的时候,我们会暂停其他线程的执行,把所有时间都用到筛选回收上。

本次讲解到这里。

关注公我的众号:苦逼的码农,获取更多原创文章,后台回复"礼包"送你一份特别的资源大礼包。
查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 17 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2018-06-26
个人主页被 481 人浏览