精华内容
下载资源
问答
  • 而Struts 2框架本身大致可以分为3个部分:核心控制器FilterDispatcher、业务控制器Action和用户实现的企业业务逻辑组件。3.1.1 核心控制器FilterDispatcher 核心控制器FilterDispatcher是Struts 2框架的基础,包含...

    3.1  Struts 2工作流程

    在第1章中,已经介绍了MVC设计思想和Struts 2框架的实现。而Struts 2框架本身大致可以分为3个部分:核心控制器FilterDispatcher、业务控制器Action和用户实现的企业业务逻辑组件。

    3.1.1  核心控制器FilterDispatcher

    核心控制器FilterDispatcherStruts 2框架的基础,包含了框架内部的控制流程和处理机制。业务控制器Action和业务逻辑组件是需要用户来自己实现的。用户在开发Action和业务逻辑组件的同时,还需要编写相关的配置文件,供核心控制器FilterDispatcher来使用。

    Struts 2的工作流程相对于Struts 1要简单,与WebWork框架基本相同,所以说Struts 2WebWork的升级版本。Struts 2框架按照模块来划分,可以分为Servlet FiltersStruts核心模块、拦截器和用户实现部分。Struts 2框架结构图如图3.1所示。

    3.1  Struts 2框架结构图

    一个请求在Struts 2框架中的处理大概分为以下几个步骤。

     客户端提交一个(HttpServletRequest)请求,如上文在浏览器中输入http://localhost: 8080/bookcode/ch2/Reg.action就是提交一个(HttpServletRequest)请求。

     请求被提交到一系列(主要是3层)的过滤器(Filter),如(ActionContextCleanUp、其他过滤器(SiteMesh等)、 FilterDispatcher)。注意:这里是有顺序的,先ActionContext CleanUp,再其他过滤器(Othter FiltersSiteMesh等),最后到FilterDispatcher

      FilterDispatcher是控制器的核心,就是MVCStruts 2实现中控制层(Controller)的核心。

      FilterDispatcher询问ActionMapper是否需要调用某个Action来处理这个(HttpServlet Request)请求,如果ActionMapper决定需要调用某个ActionFilterDispatcher则把请求的处理交给ActionProxy

      ActionProxy通过Configuration Managerstruts.xml)询问框架的配置文件,找到需要调用的Action类。例如,用户注册示例将找到UserReg类。

      ActionProxy创建一个ActionInvocation实例,同时ActionInvocation通过代理模式调用Action。但在调用之前,ActionInvocation会根据配置加载Action相关的所有Interceptor(拦截器)。

     一旦Action执行完毕,ActionInvocation负责根据struts.xml中的配置找到对应的返回结果result

    Struts 2的核心控制器是FilterDispatcher,有3个重要的方法:destroy()doFilter()Init(),可以在Struts 2的下载文件夹中找到源代码,如代码3.1所示。

    代码3.1  核心控制器FilterDispatcher

    public class FilterDispatcher implements StrutsStatics, Filter {

        /**

         * 定义一个Log实例

         */

    private static final Log LOG = LogFactory.getLog(FilterDispatcher.class);

    … ...

        /**

         * 存放属性文件中的.STRUTS_I18N_ENCODING

         */

        private static String encoding;

        /**

         * 定义ActionMapper实例

         */

        private static ActionMapper actionMapper;

        /**

         * 定义FilterConfig实例

         */

        private FilterConfig filterConfig;

        protected Dispatcher dispatcher;

        /**

         * 创建一个默认的dispatcher,初始化filter

         * 设置默认的packages     *

         */

        public void init(FilterConfig filterConfig) throws ServletException {

         this.filterConfig = filterConfig;

           dispatcher = createDispatcher(filterConfig);

            dispatcher.init();

            String param = filterConfig.getInitParameter("packages");

            String packages = "org.apache.struts2.static template org.apache.struts2.interceptor.debugging";

            if (param != null) {

                packages = param + " " + packages;

            }

            this.pathPrefixes = parse(packages);

        }

        //销毁filter方法

       public void destroy() {

            if (dispatcher == null) {

                LOG.warn("something is seriously wrong, Dispatcher is not initialized (null) ");

            } else {

                dispatcher.cleanup();

            }

        }

        /**

         * 处理一个Action或者资源请求

         * <p/>

         * filter尝试将请求同action mapping相匹配

         * 如果找到,将执行dispatcherserviceAction方法

         * 如果Action处理失败, doFilter将建立一个异常

         * <p/>

         * 如果请求静态资源

         * 资源将被直接复制给 response

         * <p/>

         * 如果找不到匹配Action 或者静态资源,则直接跳出

         public void doFilter(ServletRequest req, ServletResponse res, FilterChain chain) throws IOException, ServletException {

            HttpServletRequest request = (HttpServletRequest) req;

            HttpServletResponse response = (HttpServletResponse) res;

            ServletContext servletContext = getServletContext();

            String timerKey = "FilterDispatcher_doFilter: ";

            try {

                UtilTimerStack.push(timerKey);

                request = prepareDispatcherAndWrapRequest(request, response);

                ActionMapping mapping;

                try {

                    mapping=actionMapper.getMapping(request, dispatcher.getConfigurationManager());

                } catch (Exception ex) {

                    LOG.error("error getting ActionMapping", ex);

                    dispatcher.sendError(request, response, servletContext, HttpServletResponse.SC_INTERNAL_SERVER_ERROR, ex);

                    return;

                }

                if (mapping == null) {

                    String resourcePath = RequestUtils.getServletPath(request);

                    if ("".equals(resourcePath) && null != request.getPathInfo()) {

                        resourcePath = request.getPathInfo();

                    }

                    if (serveStatic && resourcePath.startsWith("/struts")) {

                        String name = resourcePath.substring("/struts".length());

                        findStaticResource(name, request, response);

                    } else {

                        //为一个普通的request, 则通过

                        chain.doFilter(request, response);

                    }

                    return;

                }

    /**

    *这个方法询问ActionMapper是否需要调用某个Action来处理这个(request)请求,

    *如果ActionMapper决定需要调用某个Action

    *FilterDispatcher则把请求的处理交给ActionProxy

                dispatcher.serviceAction(request, response, servletContext, mapping);

            } finally {

                try {

                    ActionContextCleanUp.cleanUp(req);

                } finally {

                    UtilTimerStack.pop(timerKey);

                }

            }

    }

    … …

    }

    doFilter()方法中,将调用dispatcher.serviceAction,该方法如果找到相应的Action,将把用户请求交给ActionProxyserviceAction()代码在Dispatcher.java中,如代码3.2所示。

    代码3.2  Dispatcher

    public class Dispatcher {

    ...

    /**

         * mapping加载类,并调用相应的方法或者直接返回result

         * <p/>

         * 根据用户请求的参数,建立Action上下文

         * 根据指定的Action’名称和包空间名称,加载一个Action代理 <tt>ActionProxy</tt>

         * 然后Action的相应方法将被执行,

         */

        public void serviceAction(HttpServletRequest request, HttpServletResponse response, ServletContext context, ActionMapping mapping) throws ServletException {

            Map<String, Object> extraContext = createContextMap(request, response, mapping, context);

            //如果存在一个值栈,则建立一个新的并复制以备Action使用

            ValueStack stack = (ValueStack) request.getAttribute(ServletActionContext.STRUTS_VALUESTACK_KEY);

            if (stack!= null) {

                extraContext.put(ActionContext.VALUE_STACK, ValueStackFactory.getFactory().createValueStack(stack));

            }

            String timerKey = "Handling request from Dispatcher";

            try {

                UtilTimerStack.push(timerKey);

                String namespace = mapping.getNamespace();

                String name = mapping.getName();

                String method = mapping.getMethod();

                Configuration config = configurationManager.getConfiguration();

                //FilterDispatcher把请求的处理交给ActionProxy

                ActionProxy proxy = config.getContainer().getInstance(ActionProxyFactory.class).createActionProxy(namespace, name, extraContext, true, false);

                proxy.setMethod(method);

                request.setAttribute(ServletActionContext.STRUTS_VALUESTACK_KEY, proxy.getInvocation().getStack());

                //ActionMapping 直接返回一个result

                if (mapping.getResult() != null) {

                    Result result = mapping.getResult();

                    result.execute(proxy.getInvocation());

                } else {

                    proxy.execute();

                }

                if (stack != null) {

                    request.setAttribute(ServletActionContext.STRUTS_VALUESTACK_KEY, stack);

                }

            } catch (ConfigurationException e) {

                LOG.error("Could not find action or result", e);

                sendError(request, response, context, HttpServletResponse.SC_NOT_FOUND, e);

            } catch (Exception e) {

                throw new ServletException(e);

            } finally {

                UtilTimerStack.pop(timerKey);

            }

        }

    从上面代码中可以看出来,Struts 2用于处理用户请求的Action实例,并不是用户实现的业务控制器,而是Action代理。关于Action代理相关内容,读者可以参考拦截器章节的介绍。

    提示

    前面一直在说Action可以是一个普通的Java类,与Servlet API完全分离,但是为了实现业务逻辑,Action需要使用HttpServletRequest内容。

     

    Struts 2设计的精巧之处就是使用了Action代理,Action代理可以根据系统的配置,加载一系列的拦截器,由拦截器将HttpServletRequest参数解析出来,传入Action。同样,Action处理的结果也是通过拦截器传入HttpServletResponse,然后由HttpServletRequest传给用户。

    其实,该处理过程是典型的AOP(面向切面编程)的方式,读者可以在后面详细了解到。Struts 2处理过程模型如图3.2所示。

    3.2  Struts 2处理过程模型

    说明

    拦截器是Struts 2框架的核心,通过拦截器,实现了AOP(面向切面编程)。使用拦截器,可以简化Web开发中的某些应用,例如,权限拦截器可以简化Web应用中的权限检查。

     

    3.1.2  业务控制器Action

    业务控制器Action是由开发者自己编写实现的,Action类可以是一个简单的Java类,与Servlet API完全分离。Action一般都有一个execute()方法,也可以定义其他业务控制方法,详细内容将在后面介绍。

    Actionexecute()返回一个String类型值,这与Struts 1返回的ActionForward相比,简单易懂。Struts 2提供了一个ActionSupport工具类,该类实现了Action接口和validate()方法,一般开发者编写Action可以直接继承ActionSupport类。编写Action类后,开发者还必须在配置文件中配置Action。一个Action的配置应该包含下面几个元素:

    Actionname,即用户请求所指向的URL

    Action所对应的class元素,对应Action类的位置。

    指定result逻辑名称和实际资源的定位。

    Action是业务控制器,笔者建议在编写Action的时候,尽量避免将业务逻辑放到其中,尽量减少Action与业务逻辑模块或者组件的耦合程度。

    3.1.3  业务模型组件

    业务模型组件可以是实现业务逻辑的模块,可以是EJBPOJO或者JavaBean,在实际开发中,对业务模型组件的区分和定义也是比较模糊的,实际上也超出了Struts 2框架的范围。不同的开发者或者团队,都有自己的方式来实现业务逻辑模块,Struts 2框架的目的就是使用Action来调用业务逻辑模块。例如一个银行存款的业务逻辑模块,如代码3.3所示。

    代码3.3  模拟一个银行业务的实现模块

    package ch3;

    public class Bank {

        //定义银行账户

        private String accounts;

        //定义操作金额

        private double money;

        //属性的gettersetter方法

        public String getAccounts() {

            return accounts;

        }

        public void setAccounts(String accounts) {

            this.accounts = accounts;

        }

        public double getMoney() {

            return money;

        }

        public void setMoney(double money) {

            this.money = money;

        }

        //模拟银行存款方法

        public boolean saving(String accounts, double money) {

            //调用DAO等模块读写数据库

            return dosomeing();

        }

     

    }

    上面实例在实际开发中没有任何意义,这里只是作为业务逻辑模块来说明,在执行saving(String accounts,double money)方法时,可以调用相应的数据库访问其他组件,来实现存款操作。使用Action调用该业务逻辑组件可以在execute()方法中实现,如代码3.4所示。

    代码3.4  业务控制器Bank_Saving_Action

    package ch3;

    import java.util.Map;

    import com.opensymphony.xwork2.ActionContext;

    import com.opensymphony.xwork2.ActionSupport;

     

    public class Bank_Saving_Action extends ActionSupport {

        //定义银行账户

        private String accounts;

        //定义操作金额

        private double money;

       

        public String execute() throws Exception {

            //创建Bank实例

            Bank bk=new Bank();

            //调用存款方法

            if (bk.saving(accounts, money)){

            return SUCCESS;

            }else{

            return ERROR;

            }

    }

        //属性的gettersetter方法

        public String getAccounts() {

            return accounts;

        }

     

        public void setAccounts(String accounts) {

            this.accounts = accounts;

        }

     

        public double getMoney() {

            return money;

        }

     

        public void setMoney(double money) {

            this.money = money;

        }

    Bank_Saving_Action演示了对银行存款业务逻辑组件的调用,这里是通过在Action中创建业务逻辑组件实例的方式实现的。在实际开发中,可以使用静态工厂获得业务逻辑组件的实例或者使用IoC容器来管理。Action中不实现任何业务逻辑,只是负责组织调度业务逻辑组件。调用关系如图3.3所示。

    3.3  调用业务逻辑组件

    说明

    业务控制器Action一般情况下不是直接创建业务逻辑组件实例,而是使用工厂模式或者是从Spring容器中获得业务逻辑组件实例,这样可以提高系统的性能。

     

    3.1.4  视图组件

    Struts 1只能支持JSP作为视图资源,而Struts 2的进步之处就是可以使用其他视图技术,如FreeMarkerVelocity等。通过前面的学习和示例,读者会知道Action的返回结果只是一个简单的字符串,也就是一个逻辑上的视图名称,要与实际视图资源对应,必须通过配置文件来实现。

    struts.xml配置文件中,每一个Aciton定义都有nameclass属性,同时还要指定result元素。result元素指定了逻辑视图名称和实际视图的对应关系。每个result都有一个type属性,前面介绍的struts.xml中并没有显式指定type值,即使用了默认的type类型:dispatcher,该结果类型支持JSP所谓视图资源。

    对于Struts 2的视图技术和result返回类型,后面将详细介绍。总结Strurs 2的框架工作流程,发现与WebWork基本相同,可以参考第1章关于WebWork框架的介绍和流程图(如图1.8所示)。

      
    展开全文
  • 局部性原理——各类优化的基石

    千次阅读 2019-07-28 16:38:21
    即便是非计算机行业的人,在做各种调优、提效时也不得不考虑到局部性,只不过他们不常用局部性一词。如果抽象程度再高一些,甚至可以说地球、生命、万事万物都是局部性的产物,因为这些都是宇宙中熵分布布局、局部的...

    学过计算机底层原理、了解过很多架构设计或者是做过优化的同学,应该很熟悉局部性原理。即便是非计算机行业的人,在做各种调优、提效时也不得不考虑到局部性,只不过他们不常用局部性一词。如果抽象程度再高一些,甚至可以说地球、生命、万事万物都是局部性的产物,因为这些都是宇宙中熵分布布局、局部的熵低导致的,如果宇宙中处处熵一致,有的只有一篇混沌。

    所以什么是 局部性 ?这是一个常用的计算机术语,是指处理器在访问某些数据时短时间内存在重复访问,某些数据或者位置访问的概率极大,大多数时间只访问_局部_的数据。基于局部性原理,计算机处理器在设计时做了各种优化,比如现代CPU的多级Cache、分支预测…… 有良好局部性的程序比局部性差的程序运行得更快。虽然局部性一词源于计算机设计,但在当今分布式系统、互联网技术里也不乏局部性,比如像用redis这种memcache来减轻后端的压力,CDN做素材分发减少带宽占用率……

    局部性的本质是什么?其实就是概率的不均等,这个宇宙中,很多东西都不是平均分布的,平均分布是概率论中几何分布的一种特殊形式,非常简单,但世界就是没这么简单。我们更长听到的发布叫做高斯发布,同时也被称为正态分布,因为它就是正常状态下的概率发布,起概率图如下,但这个也不是今天要说的。
    在这里插入图片描述
    其实有很多情况,很多事物有很强的头部集中现象,可以用概率论中的泊松分布来刻画,这就是局部性在概率学中的刻画形式。
    在这里插入图片描述
    在这里插入图片描述
    上面分别是泊松分布的示意图和概率计算公式,λ\lambda 表示单位时间(或单位面积)内随机事件的平均发生次数,ee表示自然常数2.71828…,k表示事件发生的次数。要注意在刻画局部性时λ\lambda表示不命中高频数据的频度,λ\lambda越小,头部集中现象越明显。

    局部性分类

    局部性有两种基本的分类, 时间局部性空间局部性 ,按Wikipedia的资料,可以分为以下五类,其实有些就是时间局部性和空间局部性的特殊情况。

    时间局部性(Temporal locality):

    如果某个信息这次被访问,那它有可能在不久的未来被多次访问。时间局部性是空间局部性访问地址一样时的一种特殊情况。这种情况下,可以把常用的数据加cache来优化访存。

    空间局部性(Spatial locality):

    如果某个位置的信息被访问,那和它相邻的信息也很有可能被访问到。 这个也很好理解,我们大部分情况下代码都是顺序执行,数据也是顺序访问的。

    内存局部性(Memory locality):

    访问内存时,大概率会访问连续的块,而不是单一的内存地址,其实就是空间局部性在内存上的体现。目前计算机设计中,都是以块/页为单位管理调度存储,其实就是在利用空间局部性来优化性能。

    分支局部性(Branch locality)

    这个又被称为顺序局部性,计算机中大部分指令是顺序执行,顺序执行和非顺序执行的比例大致是5:1,即便有if这种选择分支,其实大多数情况下某个分支都是被大概率选中的,于是就有了CPU的分支预测优化。

    等距局部性(Equidistant locality)

    等距局部性是指如果某个位置被访问,那和它相邻等距离的连续地址极有可能会被访问到,它位于空间局部性和分支局部性之间。 举个例子,比如多个相同格式的数据数组,你只取其中每个数据的一部分字段,那么他们可能在内存中地址距离是等距的,这个可以通过简单的线性预测就预测是未来访问的位置。

    实际应用

    计算机领域关于局部性非常多的利用,有很多你每天都会用到,但可能并没有察觉,另外一些可能离你会稍微远一些,接下来我们举几个例子来深入了解下局部性的应用。

    计算机存储层级结构

    极客时间
    上图来自极客时间徐文浩的《深入浅出计算机组成原理》,我们以目前常见的普通家用电脑为例 ,分别说下上图各级存储的大小和访问速度,数据来源于https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html
    在这里插入图片描述
    从最快的L1 Cache到最慢的HDD,其两者的访存时间差距达到了6个数量级,即便是和内存比较,也有几百倍的差距。举个例子,如果CPU在运算是直接从内存中读取指令和数据,执行一条指令0.3ns,然后从内存读下一条指令,等120ns,这样CPU 99%计算时间都会被浪费掉。但就是因为有局部性的存在,每一层都只有少部分数据会被频繁访问,我们可以把这部分数据从底层存储挪到高层存储,可以降低大部分的数据读取时间。
      
    可能有些人好奇,为什么不把L1 缓存做的大点,像内存那么大,直接替代掉内存,不是性能更好吗?虽然是这样,但是L1 Cache单位价格要比内存单位的价格贵好多(大概差200倍),有兴趣可以了解下DRAM和SRAM。

    我们可以通过编写高速缓存友好的代码逻辑来提升我们的代码性能,有两个基本方法 。

    1. 让最常见的情况运行的快,程序大部分的运行实际都花在少了核心函数上,而这些函数把大部分时间都花在少量循环上,把注意力放在这些代码上。
    2. 让每个循环内缓存不命中率最小。比如尽量不要列遍历二维数组。

    MemCache

    在这里插入图片描述
    MemCache在大型网站架构中经常看到。DB一般公司都会用mysql,即便是做了分库分表,数据数据库单机的压力还是非常大的,这时候因为局部性的存在,可能很多数据会被频繁访问,这些数据就可以被cache到像redis这种memcache中,当redis查不到数据,再去查db,并写入redis。
      
    因为redis的水平扩展能力和简单查询能力要比mysql强多了,查起来也快。所以这种架构设计有几个好处:

    1. 加快了数据查询的平均速度。
    2. 大幅度减少DB的压力。

    CDN

    CDN的全称是Content Delivery Network,即内容分发网络(图片来自百度百科) 。CDN常用于大的素材下发,比如图片和视频,你在淘宝上打开一个图片,这个图片其实会就近从CDN机房拉去数据,而不是到阿里的机房拉数据,可以减少阿里机房的出口带宽占用,也可以减少用户加载素材的等待时间。
    在这里插入图片描述
    CDN在互联网中被大规模使用,像视频、直播网站,电商网站,甚至是12306都在使用,这种设计对公司可以节省带宽成本,对用户可以减少素材加载时间,提升用户体验。看到这,有没有发现,CDN的逻辑和Memcache的使用很类似,你可以直接当他是一个互联网版的cache优化。

    Java JIT

    JIT全称是Just-in-time Compiler,中文名为即时编译器,是一种Java运行时的优化。Java的运行方式和C++不太一样,因为为了实现write once, run anywhere的跨平台需求,Java实现了一套字节码机制,所有的平台都可以执行同样的字节码,执行时有该平台的JVM将字节码实时翻译成该平台的机器码再执行。问题在于字节码每次执行都要翻译一次,会很耗时。
      在这里插入图片描述
    图片来自郑雨迪Introduction to Graal ,Java 7引入了tiered compilation的概念,综合了C1的高启动性能及C2的高峰值性能。这两个JIT compiler以及interpreter将HotSpot的执行方式划分为五个级别:

    • level 0:interpreter解释执行
    • level 1:C1编译,无profiling
    • level 2:C1编译,仅方法及循环back-edge执行次数的profiling
    • level 3:C1编译,除level 2中的profiling外还包括branch(针对分支跳转字节码)及receiver type(针对成员方法调用或类检测,如checkcast,instnaceof,aastore字节码)的profiling
    • level 4:C2编译

    通常情况下,一个方法先被解释执行(level 0),然后被C1编译(level 3),再然后被得到profile数据的C2编译(level 4)。如果编译对象非常简单,虚拟机认为通过C1编译或通过C2编译并无区别,便会直接由C1编译且不插入profiling代码(level 1)。在C1忙碌的情况下,interpreter会触发profiling,而后方法会直接被C2编译;在C2忙碌的情况下,方法则会先由C1编译并保持较少的profiling(level 2),以获取较高的执行效率(与3级相比高30%)。

    这里将少部分字节码实时编译成机器码的方式,可以提升java的运行效率。可能有人会问,为什么不预先将所有的字节码编译成机器码,执行的时候不是更快更省事吗?首先机器码是和平台强相关的,linux和unix就可能有很大的不同,何况是windows,预编译会让java失去夸平台这种优势。 其次,即时编译可以让jvm拿到更多的运行时数据,根据这些数据可以对字节码做更深层次的优化,这些是C++这种预编译语言做不到的,所以有时候你写出的java代码执行效率会比C++的高。

    CopyOnWrite

    CopyOnWrite写时复制,最早应该是源自linux系统,linux中在调用fork() 生成子进程时,子进程应该拥有和父进程一样的指令和数据,可能子进程会修改一些数据,为了避免污染父进程的数据,所以要给子进程单独拷贝一份。出于效率考虑,fork时并不会直接复制,而是等到子进程的各段数据需要写入才会复制一份给子进程,故此得名 写时复制
      
    在计算机的世界里,读写的分布也是有很大的局部性的,大多数情况下读远大于写, 写时复制 的方式,可以减少大量不必要的复制,提升性能。 另外这种方式也不仅仅是用在linux内核中,java的concurrent包中也提供了CopyOnWriteArrayList CopyOnWriteArraySet。像Spark中的RDD也是用CopyOnWrite来减少不必要的RDD生成。

    处理

    上面列举了那么多局部性的应用,其实还有很多很多,我只是列举出了几个我所熟知的应用,虽然上面这些例子,我们都利用局部性得到了能效、成本上的提升。但有些时候它也会给我们带来一些不好的体验,更多的时候它其实就是一把双刃剑,我们如何识别局部性,利用它好的一面,避免它坏的一面?

    识别

    文章开头也说过,局部性其实就是一种概率的不均等性,所以只要概率不均等就一定存在局部性,因为很多时候这种概率不均太明显了,非常好识别出来,然后我们对大头做相应的优化就行了。但可能有些时候这种概率不均需要做很详细的计算才能发现,最后还得核对成本才能考虑是否值得去做,这种需要具体问题具体分析了。

    如何识别局部性,很简单,看概率分布曲线,只要不是一条水平的直线,就一定存在局部性。

    利用

    发现局部性之后对我们而言是如何利用好这些局部性,用得好提升性能、节约资源,用不好局部性就会变成阻碍。而且不光是在计算机领域,局部性在非计算机领域也可以利用。

    性能优化

    上面列举到的很多应用其实就是通过局部性做一些优化,虽然这些都是别人已经做好的,但是我们也可以参考其设计思路。

    恰巧最近我也在做我们一个java服务的性能优化,利用jstack、jmap这些java自带的分析工具,找出其中最吃cpu的线程,找出最占内存的对象。我发现有个redis数据查询有问题,因为每次需要将一个大字符串解析很多个键值对,中间会产生上千个临时字符串,还需要将字符串parse成long和double。redis数据太多,不可能完全放的内存里,但是这里的key有明显的局部性,大量的查询只会集中在头部的一些key上,我用一个LRU Cache缓存头部数据的解析结果,就可以减少大量的查redis+解析字符串的过程了。

    另外也发现有个代码逻辑,每次请求会被重复执行几千次,耗费大量cpu,这种热点代码,简单几行改动减少了不必要的调用,最终减少了近50%的CPU使用。

    非计算机领域

    《高能人士的七个习惯》里提到了一种工作方式,将任务划分为重要紧急、不重要但紧急、重要但不紧急、不重要不紧急四种,这种划分方式其实就是按单位时间的重要度排序的,按单位时间的重要度越高收益越大。《The Effective Engineer》里直接用leverage(杠杆率)来衡量每个任务的重要性。这两种方法差不多是类似的,都是优先做高收益率的事情,可以明显提升你的工作效率。

    这就是工作中收益率的局部性导致的,只要少数事情有比较大的收益,才值得去做。还有一个很著名的法则__82法则__,在很多行业、很多领域都可以套用,80%的xxx来源于20%的xxx ,80%的工作收益来源于20%的工作任务,局部性给我们的启示“永远关注最重要的20%” 。

    避免

    上面我们一直在讲如何通过局部性来提升性能,但有时候我们需要避免局部性的产生。 比如在大数据运算时,时常会遇到数据倾斜、数据热点的问题,这就是数据分布的局部性导致的,数据倾斜往往会导致我们的数据计算任务耗时非常长,数据热点会导致某些单节点成为整个集群的性能瓶颈,但大部分节点却很闲,这些都是我们需要极力避免的。

    一般我们解决热点和数据切斜的方式都是提供过重新hash打乱整个数据让数据达到均匀分布,当然有些业务逻辑可能不会让你随意打乱数据,这时候就得具体问题具体分析了。感觉在大数据领域,局部性极力避免,当然如果没法避免你就得通过其他方式来解决了,比如HDFS中小文件单节点读的热点,可以通过减少加副本缓解。其本质上没有避免局部性,只增加资源缓解热点了,据说微博为应对明星出轨Redis集群也是采取这种加资源的方式。

    参考资料

    1. 维基百科局部性原理
    2. 《计算机组成与设计》 David A.Patterson / John L.Hennessy
    3. 《深入浅出计算机组成原理》 极客时间 徐文浩
    4. 《深入理解计算机系统》 Randal E.Bryant / David O’Hallaron 龚奕利 / 雷迎春(译)
    5. interactive latencies
    6. Introduction to Graal 郑雨迪
    展开全文
  • 牛逼!Java 入门精通,超全汇总版

    万次阅读 多人点赞 2021-05-06 19:40:33
    数据库索引与优化 MySQL 技术内幕:InnoDB存储引擎 MySQL技术内幕 MySQL 内核 Maven MyBatis MyBatis 入门精通 MyBatis 技术内幕 Spring Spring 揭秘 Spring 源码深度解析 Spring 技术内幕 HTTP Tomcat 深入剖析...

    文章目录


    (文末有惊喜哦!!!)

    其实学习 Java 学到什么程度算是精通,这个其实没有盖棺定论的,也不是说你拿个年薪几十万的 offer 就可以自诩精通了。另外,每当面试的时候简历上填个精通 offer 的家伙我就觉得很搞笑,没有几个熬得过开出门左拐的命运。但是我认为,如果市面上这些资料、书籍你都啃的差不多,你能在所有的 Java 程序员中跻身前 0.1% 的话,你就可以达到"精通" 这个阶段了,因为没人比你强了,你当然是精通了。

    所以,我还是选择罗列一些知识点推荐给大家,如果你都能够掌握并且真正理解这些东西的话,那你就可以到了精通这个阶段了。

    首先要学的是计算机基础知识,因为 Java 不是像 Python 那样简单,它是需要一定基础的,如果你上来直接硬肝 Java,那么 90% 的几率你会放弃。

    因为要想学好 Java ,你就得理解什么是面向对象的设计思想,而面向对象的这种设计思想又不是刚开始学习编程的新人能够熟练掌握呢?那怎么办呢?这不是死局了吗?

    其实,如果要想真正理解这种设计思想的话,你要首先学的不是 Java,而是 C 语言。

    为什么呢?因为 C 语言是面向过程的,什么是面向过程和面向对象的设计思想呢?我给你举个例子你就知道了。

    面向过程与面向对象的区别,由“如何把大象装进冰箱”来看:

    一、面向过程

    为了把大象装进冰箱,需要3个过程。

    思路:

    1、把冰箱门打开(得到打开门的冰箱)。

    2、把大象装进去(打开门后,得到里面装着大象的冰箱)。

    3、把冰箱门关上(打开门、装好大象后,获得关好门的冰箱)。

    根据上面的思路,可以看到,每个过程都有一个阶段性的目标,依次完成这些过程,就能把大象装进冰箱。

    二、面向对象

    为了把大象装进冰箱,需要做三个动作(或者叫行为)。每个动作有一个执行者,它就是对象。

    思路:

    1、冰箱,你给我把门打开。

    2、冰箱,你给我把大象装进去(或者说,大象,你给我钻到冰箱里去)。

    3、冰箱,你给我把门关上。

    依次完成这些动作,你就可以把大象装进去。

    这里我只是举个例子,可能大家还是很懵逼,这里我就要给你推荐几本入门 C 语言的视频和书籍了。

    关于书籍推荐,可以看看这篇回答

    初学C语言,有什么好书推荐?

    书一般是能够静下心来的人看的,一般初学者最大的问题就是很难静下心来编程,如果你觉得难以看得下去书的话,你可以看看这篇回答,里面的视频可以说很全了

    有哪些优秀的c语言课程视频?

    初学 C 语言周期大概是3 - 6 个月,学编程的捷径就是每天敲代码,比如 C primer plus 上面就有很多代码示例,你要对着敲,课后练习要跟着做,坚持 3 - 6 个月,你会感谢你自己的坚持。

    学到这里,你就可以说 C 语言基本入门了。

    如果 C 语言你能够坚持下来的话,那么 Java 入门,那会非常容易了,其原因有两点

    1. C 语言基本上可以说是高级语言的鼻祖,如果你 C 学得好,那么学其他语言都会非常容易。
    2. C 语言比 Java 稍微难点,而且有很多特性非常像,从一门比较难的语言 -> 一门难度中等的语言,那会变得很容易。

    好了,那么从现在开始,我们就要进入 Java 的学习环节了。

    学习 Java,我将会从三个阶段来介绍,分为初级、中级和高级

    Java 基础

    什么是初级 Java 的水平呢?我认为就是理解 Java 的语法规则、语言特性,这么说有点干瘪,直接上思维导图!

    img

    就这一张图,如果你能把图中内容都理解的差不多,那你就可以说是入门 Java 了,但是这里要注意一个概念,这并不等于说你是一个合格的初级 Java 程序员了,因为要想达到初级 Java 程序员的水平,你要会能干活,能干活的标准是你要懂框架,不要急,我们后面会说。

    有人问图中为什么没有并发或者 Java 虚拟机这些,这些属于中高级内容,刚开始学 Java 不用懂什么并发和 JVM!!!有一些人或者培训班都喜欢秀自己懂 xxx ,懂 xxx ,这不就是误导小白么。

    那么话又说回来了,如何才能学习并了解到上面这些内容呢?接下来重点来了!!!

    如果你能看到这里,我就认为你养成了每日编程的习惯,此时的你能够静下心来编程了。

    那么我首先给你推荐一本初学 Java 非常合适的一本书

    Head First Java

    《Head First Java》是本完整的面向对象(object-oriented,OO)程序设计和Java的学习指导。此书是根据学习理论所设计的,让你可以从学习程序语言的基础开始一直到包括线程、网络与分布式程序等项目。最重要的,你会学会如何像个面向对象开发者一样去思考。

    img

    书中涉及的 Swing 图形化接口和 GUI 这部分可以不用学习,或者作为简单了解,因为现在几乎很少有人 拿 Swing 开发桌面化程序。

    这本书可以说是非常适合小白的一本了,零基础就可以看,Head First 系列的书籍一般都是语言诙谐幽默,读起来不累,而且书中有非常多锻炼思维的游戏/方法,对于有经验的人来说,看这本书感觉非常弱智,但是对于零基础或者 Java 新手来说,这是一本非常适合系统学习 Java 和查漏补缺的一本书。

    Java 核心技术卷一

    有人把 Java 核心技术卷一作为入门书籍推荐,其实我觉得并不友好,虽然这也是一门基础书籍,但是对不同的人来说,这本书的接收程度不同,我推荐看完上面的 Head First Java 再看这本。

    img

    Java 编程思想

    Java 编程思想就是一本神书了,不管你是初、中还是高级程序员,你每次看这本书的时候都会有新的收获

    img

    这本书同样不适合刚开始入门 Java 的同学看,甚至前三章并不友好,因为 Java 编程思想只是讲面向对象过程的设计思想就用了很大篇幅,这本书包含很多示例代码,我强烈推荐你要学习里面的代码思想,到工作中,这些编码思想和代码规范会非常有用!!!

    所以综上所述,入门 Java 你需要掌握的基础知识有

    这里就需要区分不同的电脑类型了,一种是 Mac ,一种是 Windows,很少有直接拿 Linux 进行开发的,所以我们这里不探讨 Linux 的方式

    Mac 上的相关配置可以看这篇

    Windows 上的相关配置可以看这篇

    • 编写入门 Java 程序

    这里你需要使用集成开发工具,一种是 Eclipse 、一种是 IDE,初学者建议使用 Eclipse,因为 IDE 对新手并不友好。

    Eclipse下载与安装

    Java 入门程序编写

    好了,如果你能按照上面的步骤一步步走下来,那么恭喜你,你能够成功编写一个 Java 入门程序了。

    现在,你就可以进入到 Java 相关知识点的学习了。

    • 了解面向对象的设计思想

    首先,你需要先认识到什么是面向对象的设计思想。

    这里我推荐你看一下 《Java编程思想》 的第一章和二章

    知乎的这个回答也能帮助你理解 什么是面向对象编程思想?

    关于 Java 变量,可以参考这篇文章

    Java 中的变量有很多,很容易让初学者不知所措,这里我写了一篇 Java 变量解惑的相关文章

    Java 中到底有哪几种变量

    上面所有的内容和思维导图,都可以在这篇文中获取

    Java技术核心总结 PDF 下载

    上面都是以文章方向为主的自学流程,下面是视频方向的自学流程。

    一、Java基础 1、尚硅谷宋红康(强力推荐):

    尚硅谷宋红康Java基础教程(java入门神器、配套资料齐全)_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

    2、黑马Java基础+就业班+各种项目idea版本(推荐):

    黑马Java基础+就业班+各种项目idea版本(正在更新)_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

    3、动力节点Java零基础教程视频:

    Java零基础教程视频(适合Java 0基础,Java初学入门)_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

    4、北京尚学堂高琪(推荐):

    高淇老师应各位网友要求又更新了JAVA300集_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

    5、求知讲堂:2019求知讲堂零基础Java入门编程视频教程 高口碑 无废话 无尿点 :

    2019求知讲堂零基础Java入门编程视频教程 高口碑 无废话 无尿点_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

    6、尚硅谷Java8新特性+JUC+NIO:

    尚硅谷Java8新特性+JUC+NIO_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

    如果你能掌握上面的基础内容部分,我觉得你应该花至少 3 - 6 个月,如果你能坚持下来的话,这里我需要鼓励一下你,但是不要自满,因为这才只是最最最最基础的部分,但是现在你可以说是一只脚踏入 Java 大门了。

    设计模式

    img

    设计模式放在这里不是让你马上就要学习的(当然你也可以学习,没有人能阻碍你学习),因为设计模式涉及到你工作的方方面面。有些设计模式你可能这辈子都用不到,但是你需要了解其思想,以便写出思路严谨,条理清晰的代码。

    设计模式我给你推荐几本书,你看哪个都行。

    Head First 设计模式

    img

    这本书虽然只有 14 章,但是却介绍到了所有的二十三种设计模式,每一种设计模式都有对应的应用案例,以风趣幽默的语言描述来一步一步为你揭开设计模式的面纱,告诉你设计模式的演进过程。

    读这本书不仅仅是学习知识,而是在学习一种思考的方法,学习一种认知的技巧,学习一种成长的阶梯。总之,用你闲暇的时间来读这本书,并不亚于你专注的工作或学习。

    图解设计模式

    img

    设计模式更多是一种思想,而不是一种固定的代码编写方式,千万不要局限于这些条条框框。日本人的书写的就是非常通俗易懂,适合小白。194张图表 + Java示例代码 = 轻松理解 GoF 的23种设计模式。

    本书以浅显易懂的语言逐一说明了 GoF 的 23 种设计模式。在讲解过程中,不仅搭配了丰富的图片,而且理论结合实例,用 Java 语言编写代码实现了设计模式的程序,让程序真正地运行起来,并提供了运用模式解决具体问题的练习题和答案。除此以外,本书在必要时还对 Java 语言的功能进行补充说明,以加深读者对 Java 的理解,在学习设计模式的同时也在复习 Java。

    上面这两本书非常适合初学者学习设计模式

    设计模式

    img

    这本书结合设计实作例从面向对象的设计中精选出23个设计模式,总结了面向对象设计中最有价值的经验,并且用简洁可复用的形式表达出来。书中分类描述了一组设计良好、表达清楚的软件设计模式,这些模式在实用环境下特别有用。此书适合大学计算机专业的学生、研究生及相关人员参考。

    这本书并不适合初学者,因为这本书是用C++ 写的,如果你没有对 C++ 语法有了解的话,不容易看懂。下面这段评价我觉得非常合适。

    img

    重学 Java 设计模式

    img

    给大家推荐一下我的朋友 小傅哥 写的重学 Java 设计模式,这本书是彩印的,作者写设计模式大概花了两年的时间,非常用心。书中包含大量的图示和例子。

    本书从六大设计原则入手,警示我们在日常开发过程中需要注意代码的编写原则。同时,本书列举了大量生动形象的例子,在遇到相关业务场景时可以把代码写得非常漂亮。原则既是规范,也是日常开发过程中要遵守的约定;设计模式是在业务场景下能够使用的工具。遵守原则并在合适的场景下用合适的工具,你的代码将无懈可击!

    设计模式不用看视频,就研读上面这几本就够了。

    设计模式并不适合一口气读完,因为你看完几个设计模式就会容易混,相信我,你可以一周熟悉一个设计模式,这样在工作中你也可以使用。一口气看完所有,就会记住最后一个设计模式,相信我,亲身实践。。。。。。

    Java 进阶

    Java 进阶需要学习的东西就有很多了,内容涉及许多方面,我们接下来就来和你聊聊

    注意:当你学会这些 Java 进阶的内容后,不代表你就是一个中级程序员了,恰恰相反,你需要把这些知识融会贯通并运用到项目/实践中去。掌握多少就看你自己了。

    首先是 Java 多线程,这里我先列出来多线程应该掌握知识的大纲

    img

    这里有个我小伙伴整理的一个多线程思维导图,不知道对你有没有帮助,获取地址如下

    搞懂这 10 张脑图后,我膨胀了。

    或者微信搜索「程序员cxuan」,回复「秋招」有很多更优质的思维脑图。

    img

    那么先抛开这张脑图不看,我先给你推荐几本关于 Java 并发方面的书。

    Java 并发编程实战

    不要犹豫了,这本书就是并发编程界的王者,也是你必看的一本书。

    img

    外版书籍不会和你讨论什么源码啥的,他们只看思想,思想有了,实现也就轻而易举。所以并发编程实战讨论更多的是思想,这本书同时也罗列了很多伪代码和应用场景来验证这些思想。

    这本书并不完全适合国内互联网现状,因为在八股文、背书如此盛行的今天,想要进大厂,成为"高级程序员",你还要懂一些八股文。

    Java 并发编程艺术

    所以如果你想要在国内找工作的话,那么下面这本书,更适合你。不要为我为什么,阿里人写的。

    img

    这些书罗列出来的一些知识点,其实都是大厂所经常问到的,所以这本书值得你仔细研读。

    Java 并发编程之美

    这本书比较适合初学者,我虽然没有系统看过,但是也翻了一下,这也是学习 Java 并发编程一本不错的书,可以当作查漏补缺或者巩固的一本。

    img

    图解Java多线程设计模式

    不得不说,日本人写的书就是通俗易懂,充满趣味性,这点不得不佩服,这本 Java 多线程设计模式,就是了解多线程中使用设计模式一本非常好的书籍。本书通过具体的Java 程序,以浅显易懂的语言逐一说明了多线程和并发处理中常用的12 种设计模式,帮助读者加深对多线程和并发处理的理解,并掌握其使用技巧。

    img

    书籍看这几本就差不多了,而且 Java 并发这块我不推荐你看视频,最好是亲自验证,视频这个东西毕竟也是别人吃过的剩下的,最主要的还是要穿一手鞋,亲自验证。

    说到这里,那么 Java 并发这块你应该掌握的知识点都有哪些呢?划重点划重点了!!!

    线程池这部分内容的思维导图

    img

    锁这部分内容我也汇总了一个思维导图

    img

    对了,我这里也总结了一本 《深入浅出 Java 多线程》,你可以在 太赞了!阿里几位工程师重写了 《Java 并发编程》 下载

    上面的内容如果你能理解,那么你 Java 这部分已经可以算是高级水平了,你去大厂面试问一些八股文,多线程这块问题不大了。

    JVM

    Java 虚拟机也叫做 JVM ,这部分是判断一个 Java 程序员分水岭的关键,如果你想要达到中高级 Java 程序员的层次,那么 JVM 是你必须要突破和提高的一个点。下面我就来和大家聊一下 JVM 都需要了解哪些内容。

    还是照例先给大家介绍几本了解 JVM 非常优秀的书籍

    深入理解 Java 虚拟机

    这本书是你必看的一本,而且作者是我们国内的周志明,国内作者一般讲实现比较多,专业术语比较少,这本书讲的更是通俗易懂,虽然有许多概念,不过周志明大佬都给出了示例和解释

    img

    豆瓣能给出国内作者 9.5 的评分,可知这本书写的有多好了,这本书是了解 JVM 非常经典的一本书,五星强烈推荐。

    Java 虚拟机规范

    img

    Java 虚拟机规范同样也是周志明大佬参与翻译的一本,这本书的权威性不容置疑,其实就是按照 Java 官方文档来写的,可以说看完这一本在面试的时候聊到 JVM 你都能够给出 “官方” 回答,大大增加你的面试通过几率。

    按理说学习 JVM 掌握上面两本书就 OK 了,但是这里我还是给喜欢学习的小伙伴们一些拓展书籍推荐。

    HotSpot 实战

    img

    深入浅出地讲解了 HotSpot 虚拟机的工作原理,将隐藏在它内部的本质内容逐一呈现在读者面前。本书适合于已具有一定 Java 编程基础的读者,以及在 Java 或基于 JVM 的编程语言平台下进行各类软件开发的开发人员、测试人员和运维人员。对于 JVM 和编程语言爱好者来说,《HotSpot 实战》也具有一定的学习参考价值。

    自己动手写 Java 虚拟机

    我们大家都知道,学习编程最好的方式就是动手实践,幸好 JVM 我们也能自己写了。

    img

    自己动手写 Java 虚拟机是《自己动手系列》中的一本,这个系列有很多硬核的书籍,给大家看一下。

    img

    如果大家有时间的话,我推荐大家按着书中的内容写一个虚拟机,对于掌握理解其运行原理有非常大的帮助。

    学习 JVM 我同样也不推荐大家看视频,看书就够了,学习 JVM 在于让你去想去思考,你如果非要让我推荐一个视频的话,那我也愿意双手奉上

    尚硅谷JVM全套教程,百万播放,全网巅峰(宋红康详解java虚拟机)

    JVM 所涉及到的一些内容

    img

    获取地址如下

    搞懂这 10 张脑图后,我膨胀了。

    主要涉及内容

    img

    这是一本揭示 JVM 字节码“黑科技”的著作,它从原理和应用两个维度深入剖析了 JVM 字节码。书中内容涉及 JVM 字节码的大部分应用场景,如 Java 性能优化、软件防护与破解、APM 等,通过大量实战案例讲解了它在这些场景中的实操技巧。

    这里再给大家推荐几篇不错的字节码文章

    字节码增强技术探索

    JVM基础系列第5讲:字节码文件结构 - 陈树义 - 博客园

    轻松看懂Java字节码

    到现在为止,Java 语言这条线算是走通了,虽然上面关于并发和 JVM 我列出了学习路线,但是这个学习路线并不是说只能学了并发才学 JVM,其实上这两个掺杂着一起学效果会更好,因为并发会涉及到对于 volatile synchronized 和 内存模型的关系,内存模型又是 JVM 中的内容,所以这两块其实是相辅相成的。而且没必要学并发和 JVM 的时候就要一股脑把东西全看明白,这些内容是中高级的东西,你可以一周看一篇都行。

    上面这些内容真正掌握起码要花 2 - 3 年的时间,也不是说这三年你就学上面这些东西,你可以学习其他的,我下面推荐的这些,就是在这个时间段内你应该掌握的。

    MySQL

    MySQL 其实要和 Java 基础以及 Java 并发、JVM 一起学习,甚至要比并发和 JVM 还要早,也就是说,你学完 Java 基础就可以学 MySQL 了。

    此时的 MySQL 我指的是 MySQL 基础,因为 MySQL 博大精深,想要深入理解 MySQL 不容易,而且我们一般 Java 开发把 MySQL 掌握到中级水平就可以了。

    MySQL 初级水平就是要求你会写 MySQL ,这里推荐几本书,由初级到高级,大家可以根据自己的水平和能力看对应的书籍。

    MySQL 基础教程

    img

    这本书是日本公认的 MySQL 入门首选教程,原版长销13年,好评如潮,非常详细。

    SQL 基础教程

    又是日本人写的一本高分书。

    img

    这本书介绍了关系数据库以及用来操作关系数据库的 SQL 语言的使用方法。书中通过丰富的图示、大量示例程序和详实的操作步骤说明,让读者循序渐进地掌握 SQL 的基础知识和使用技巧,切实提高编程能力。每章结尾设置有练习题,帮助读者检验对各章内容的理解程度。另外,本书还将重要知识点总结为“法则”,方便读者随时查阅。

    深入浅出 MySQL

    这本书是零基础学习 MySQL 非常好的一本书,由浅入深,文字通俗易懂。

    img

    但是这本书非常厚,涵盖的内容非常多,不容易把握重点。

    MySQL 必知必会

    相对来说,这本书就比较薄了。

    img

    同样也是入门 MySQL 非常值得看的一本。书中从介绍简单的数据检索开始,逐步深入一些复杂的内容,包括联结的使用、子查询、正则表达式和基于全文本的搜索、存储过程、游标、触发器、表约束,等等。通过重点突出的章节,条理清晰、系统而扼要地讲述了读者应该掌握的知识,使他们不经意间立刻功力大增。

    SQL 必知必会

    SQL 语法简洁,使用方式灵活,功能强大,已经成为当今程序员不可或缺的技能。

    img

    这本书是深受世界各地读者欢迎的 SQL 经典畅销书,内容丰富,文字简洁明快,针对 Oracle、SQL Server、MySQL、DB2、PostgreSQL、SQLite 等各种主流数据库提供了大量简明的实例。与其他同类图书不同,它没有过多阐述数据库基础理论,而是专门针对一线软件开发人员,直接从SQL SELECT 开始,讲述实际工作环境中最常用和最必需的 SQL 知识,实用性极强。通过本书,读者能够从没有多少SQL经验的新手,迅速编写出世界级的 SQL!

    上面推荐了一些 MySQL 的基础书籍,把上面任意 1 - 2 本啃会了之后,那么你的 CRUD 的功力就初步具备了。恭喜你离初级 Java 程序员又近了一步。

    下面我会推荐一些中高级内容,这些内容会一直伴随着你的整个开发生涯,是的你没听错,如果你做开发,那么下面这些书中的内容,真的会伴随着你整个开发生涯,不论任何语言。

    高性能 MySQL

    img

    这本书太优秀了!这本书是 MySQL 领域的经典之作,拥有广泛的影响力。我之前和出版社联系给读者送了 20 本书,超过一半的人都要的是 高性能MySQL,由此可见这个影响力!

    原文链接:cxuan 给大家送 20 本书!!!

    img

    MySQL 是怎样运行的

    img

    这本书是去年刚出的,小孩子大佬非常牛批,之前在掘金写了一篇小册,好像是购买人数最多的课程,这本书就是小册的汇总,非常硬核。

    本书采用诙谐幽默、通俗易懂的写作风格,针对上面这些问题给出了相应的解答方案。尽管本书的表达方式与司空见惯的学术派、理论派IT图书有显著区别,但本书的确是相当正经的专业技术图书,内容涵盖了使用 MySQL 的同学在求职面试和工作中常见的一些核心概念。无论是身居 MySQL专家身份的技术人员,还是技术有待进一步提升的 DBA,甚至是刚投身于数据库行业的“萌新”人员,本书都是他们彻底了解 MySQL 运行原理的优秀图书。

    数据库索引与优化

    这本书大家可能听的比较少,但这是很好的关于索引介绍的书,提供了估计查询支行时间和方法,并解释了索引对于查询效率的影响方式,对实践和指导意义。而且数据库的索引和优化是 MySQL必问的重点。

    img

    上面推荐的这些算是进阶篇,而我们下面推荐的这几本就算是 MySQL 的高级内容了。

    MySQL 技术内幕:InnoDB存储引擎

    img

    作为 MySQL 5.5 之后的首选存储引擎,InnoDB 存储引擎到底有哪些特别之处?这本书会给你详细介绍一波。这本书从源代码的角度深度解析了 InnoDB 的体系结构、实现原理、工作机制,并给出了大量最佳实践,能帮助你系统而深入地掌握 InnoDB,更重要的是,它能为你设计管理高性能、高可用的数据库系统提供绝佳的指导

    MySQL技术内幕

    img

    《MySQL技术内幕(第5版)》是MySQL方面名副其实的经典著作,全面介绍MySQL的基础知识以及MySQL有别于其他数据库系统的独特功能,书中特别关注如何高效地使用和管理MySQL。 《MySQL技术内幕(第5版)》由4个部分组成:第一部分集中介绍与数据库使用相关的一些基本概念,第二部分重点关注的是自己如何动手编写和使用 MySQL 的程序,第三部分主要是面向那些负责数据库管理的读者,第四部分提供了一些参考附录。书中包含大量示例,详尽地演示了MySQL的各项功能特性。此外,本书还为使用C语言、PHP语言和Perl语言开发数据库应用的读者提供了相关内容。 《MySQL技术内幕(第5版)》不仅适合MySQL初学者阅读,也适合想要深入了解 MySQL 的数据库管理人员和开发人员参考。

    MySQL 内核

    img

    非常优秀的一本书,这本书在 InnoDB 介绍性图书的基础之上,更深入地介绍InnoDB存储引擎的内核,例如latch、B+树索引、事务、锁等,从源代码的角度深度解析了InnoDB的体系结构、实现原理、工作机制,并给出了大量最佳实践,希望通过《MySQL内核:InnoDB存储引擎 卷1》帮助用户真正了解一个数据库存储引擎的开发。

    好了,推荐了这么多本 MySQL 的书籍,那么有没有 MySQL 的视频推荐呢?啊?MySQL 还用看视频吗?MySQL 不好讲呀,初级的直接对着命令敲就可以了,高级的内容,很多讲师也讲不清楚,更别提内核这块了,所以大家还是看书把,看书就够了!

    那么关于 MySQL ,内容其实是很多的,不过为了这个回答能作为一个标准回答来解释,我耐着性子给大家把所要学习的内容罗列一下,读者朋友们如果觉得我的付出是值得的,不妨给这篇文章点个赞哟!

    img

    那么 MySQL ,走你!

    • MySQL 基础入门

      • SQL 基础使用

      • 查询语言分类

        • DDL 语句
        • DML 语句
        • DQL 语句
        • DCL 语句
      • 如何使用 MySQL 帮助文档

        • 按层次查询
        • 快速查阅
    • MySQl 数据类型

      • 数值类型

        • 整数
        • 小数
        • 位类型
      • 日期类型

        • YEAR
        • TIME
        • DATE
        • DATETIME
        • TIMESTAMP
      • 字符串类型

        • CHAR 和 VARCHAR
        • BINARY 和 VARBINARY
        • BLOB
        • TEXT
        • ENUM
        • SET
    • MySQL 运算符

      • 算数运算符
      • 比较运算符
      • 逻辑运算符
      • 位运算符
    • MySQL 常用函数

      • 字符串函数
      • 数值函数
      • 日期和时间函数
      • 流程函数
      • 其他函数

    上面这些内容都可以在这篇文章中找到,我自己写的关于 MySQL 的实战入门总结

    138 张图带你 MySQL 入门

    MySQL 开发中应该掌握哪些知识点

    • MySQL 存储引擎

      • 存储引擎概述

      • 存储引擎特性

        • MyISAM
        • InnoDB
        • MEMORY
        • MERGE
      • 选择合适的存储引擎

    • MySQL 字符集

    • 索引的设计和使用

      • 索引概述
      • 索引设计原则
    • 视图

      • 什么是视图

      • 对视图的操作

        • 创建或者修改视图
    • 存储过程

      • 存储过程使用

        • 创建存储过程
        • 删除存储过程
        • 查看存储过程
      • 变量的使用

        • 用户变量
        • 全局变量
        • 会话变量
        • 局部变量
      • MySQL 流程介绍

    • 触发器

      • 创建触发器
      • 删除触发器
      • 查看触发器
      • 触发器的作用

    上面这些内容,可以在我自己写的 MySQL 开发中找到

    47 张图带你 MySQL 进阶!!!

    MySQL 高级内容,主要包括

    • 事务控制和锁定语句

      • 锁定语句
      • 解锁语句
    • 事务控制

      • 自动提交

      • 手动提交

        • 事务表和非事务表
    • SQL 安全问题

      • SQL Mode 解决问题
      • SQL Mode 三种作用域
    • SQL 正则表达式

    • 常见 SQL 技巧

      • RAND 函数
      • GROUD BY + WITH ROLLUP 语句
      • 数据库名、表名大小写问题
      • 外键问题
    • MySQL 常用函数

      • 字符串函数
      • 数值函数
      • 日期和时间函数
      • 流程函数
      • 其他函数

    上面这些内容,你可以在我自己写的关于 MySQL 高级部分找到

    炸裂!MySQL 82 张图带你飞!

    以上这些 MySQL 内容都是偏重日常开发和使用,没有深入到 MySQL 架构和底层,所以下面我们介绍的这些内容,会涉及到 MySQL 架构和底层的相关内容,这些内容,也是你在 CRUD 的背后,需要下的功夫。

    这些内容我也在学习,因为我是 MySQL 新手,所以这部分内容应该不是特别全,大家可以追更这个答案,我会在后面更新这个回答。

    这里再提醒大家一点,MySQL 高级内容是你在工作中慢慢掌握的,如果你想要成为初级 Java 程序员,当下不需要掌握这些内容,把我写的几篇文章看完,并且跟着敲下来,那么就可以说你的 MySQL 已经达到入门水准了,可以进行下面的学习了!!

    138 张图带你 MySQL 入门

    47 张图带你 MySQL 进阶!!!

    炸裂!MySQL 82 张图带你飞!

    Maven

    在学习框架前,我建议你先了解一下什么是 Maven,以及项目为什么要使用 Maven,狼哥的这个 Maven 系列可以了解下。

    Maven学习总结

    市面上关于 maven 的书不多,你可以看下这本

    img

    Maven 对于初学者来说,只做为了解即可,但是 Maven 这个优秀的架构是如何简化代码的,如何让我们更方便的使用,以及 Maven 中的一些不为人知的秘密,你都可以在这本书中找到。

    下面该学啥了?终于到了框架了!!! 作为一门开发,框架就是你的武器!!!就是玩儿!在抗美援朝的时候,志愿军使用轻武器加迫击炮照样干翻米国骑兵第一师和陆战第一师这种王牌军队。

    框架要学习的就是 SpringMVC 、Spring 、MyBatis,SSH 框架已经不行了,至于为什么不行,可以看一下这篇回答

    JAVA的三大框架是什么?

    框架首先要学的就是 MyBatis

    MyBatis

    MyBatis 入门,看一本书就够了。

    MyBatis 从入门到精通

    img

    这本书是我刚开始学 MyBatis 的时候看的,书中的内容我对照着都敲了一遍,可以说是非常有参考价值的一本。

    《MyBatis从入门到精通》中从一个简单的MyBatis查询入手,搭建起学习MyBatis的基础开发环境。通过全面的示例代码和测试讲解了在MyBatis XML方式和注解方式中进行增、删、改、查操作的基本用法,介绍了动态SQL在不同方面的应用以及在使用过程中的最佳实践方案。针对MyBatis高级映射、存储过程和类型处理器提供了丰富的示例,通过自下而上的方法使读者更好地理解和掌握MyBatis的高级用法,同时针对MyBatis的代码生成器提供了详细的配置介绍。

    深入理解 MyBatis ,你可以参考

    MyBatis 技术内幕

    img

    嗯,这本书其实可以说是把 MyBatis 的一些核心特性和核心组件说完了,《MyBatis 技术内幕》旨在为读者理解 MyBatis 的设计原理、阅读 MyBatis 源码、扩展 MyBatis 功能提供帮助和指导,让读者更加深入地了解 MyBatis 的运行原理、设计理念。希望《MyBatis 技术内幕》能够帮助读者全面提升自身的技术能力,让读者在设计业务系统时,可以参考 MyBatis的 优秀设计,更好地应用MyBatis。

    这本书我还是强烈推荐给大家的。

    另外,你也可以去看 MyBatis 官方文档 mybatis - MyBatis 3

    英文版的看不懂,汉化的也给你安排了。mybatis - MyBatis 3

    MyBatis 这部分内容可以去看一些视频

    【狂神说Java】Mybatis最新完整教程IDEA版通俗易懂

    2020最新MyBatis教程【IDEA版】-MyBatis从入门到精通

    那么 MyBatis 都应该掌握哪些内容呢?当然你要会用 MyBatis 了,用法直接参见官网或者 MyBatis 从入门到精通这本书就可以了。

    我上面给出的这些连接,都是让你在工作中逐步掌握的,MyBatis 要是达到能够开发的程度,你只需要看完 MyBatis 从入门到精通或者一门视频课程就可以了。

    Spring

    在学完 MyBatis ,就该学习我们的核心框架 Spring 了,Spring 能风靡到现在一定有他的道理,等你到工作中再慢慢体会它的精髓。

    学习 Spring ,我首先给你推荐的一本书就是 Spring 实战,也就是 Spring In Action,这本书我认为即使学习 Spring 最好的一本,没有之一了。

    img

    这个评价我认为是有些低了,还有评价说是什么不注重思想的,这只是一本实战书诶,又不是讲思想的,不能要求一本书能够涵盖所有的内容吧,只要这本书能够给出实战案例,代码示例,清楚的讲明白逻辑,我觉得就是好的。

    Spring 揭秘

    img

    这本书和上面的 Spring 实战一起学习,那么 Spring 你就能击败大部分选手了,这两本书是绝配。这本书更多讲解的是方案和思想。这本书没有教程似的训导,更多的是说故事般的娓娓道来,本书是作者在多年的工作中积累的第一手 Spring 框架使用经验的总结,深入剖析了 Spring 框架各个模块的功能、出现的背景、设计理念和设计原理,揭开了 Spring 框架的神秘面纱,使你“知其然,更知其所以然”。每部分的扩展篇帮助读者活学活用 Spring 框架的方方面面,同时可以触类旁通,衍生出新的思路和解决方案。

    关于 Spring 基础的视频,我推荐下面几个

    【狂神说Java】Spring5最新完整教程IDEA版通俗易懂

    尚硅谷-Spring5框架最新版教程(idea版)

    作为进阶学习,我推荐宁看看官网

    Core Technologies

    Spring 官网的权威性不用我多说了吧,但是官网有个特点,这个不只是 Spring 特有的,几乎所有的外国官网都不会带你分析源码,所以如果你想要了解设计思想和理论精髓,还是要撸源码。

    撸源码当然很费劲了,这里推荐给你两本书可以搭配着看下,网上对这两本书的褒贬不一,我不强烈推荐任何一本。。。。。。

    Spring 源码深度解析

    img

    这本书我看了一些,以我目前的能力水平可能还无法完全看懂这本书,里面的内容非常深奥,不过如果你对 Spring 源码有一些研究的话,可以看看。

    Spring 技术内幕

    img

    这本书和上面一样,代码比较多,但是解释相对较少,适合对 Spring 源码有一些了解的同学看。

    推荐给你几个 Spring 源码的视频

    这可能是B站讲的最好的SPRING源码教程(2021年最新版)

    尚硅谷Spring注解驱动教程(雷丰阳源码级讲解)

    当然,Spring 你终究还是要看源码的,所以还是硬着头皮啃源码吧,骚年们~

    关于 Spring,有哪些需要学习的东西呢?

    Spring 单独拿来使用的场景非常少,更多是作为框架的整合来用,Spring 最主要的特点就是两个:IOC 容器和 Aop,IOC 容器就是 Spring 和 各种资源整合的基础,可以说有了 IOC 的这个特点,才会有 bean 的装配,自动装配等等特性,而 Aop 就是减少业务耦合性的一种技术,让我们能够以"切面"的方式来看到业务关联性。最主要的就是这两项技术,把这两项技术弄懂了 Spring 就差不多了。

    HTTP

    再继续往下学习之前,我们先聊聊 HTTP 协议,HTTP 协议可以说是我们 Java 开发打交道最多的协议了,关于 HTTP 协议,我们这里不讲述太多,大家可以参考一下我的这篇文章,里面有详细的 HTTP 教程。

    想深入了解 HTTP 协议,有哪些值得推荐的书籍?

    Tomcat

    我刚开始接触 Tomcat 之前也有这个疑问,这个 Tomcat 是啥。。。。。。听起来很别扭,但是你可以通过这篇文章了解一下什么是 Tomcat

    Tomcat(一) Tomcat是什么:Tomcat与Java技术 Tomcat与Web应用 以及 Tomcat基本框架及相关配置

    牧酱:什么是TOMCAT

    Tomcat 我推荐你看看这几本书

    img

    这本书是一本万能工具,其主题涵盖了Apache Tomcat这一广受欢迎的开源servlet、JSP容器和高性能的web server。《Tomcat权威指南》对管理员和web站点管理员而言,具有较强的参考价值;对在开发或产品中要使用 Tomcat 作为 web 应用程序服务器的开发者而言,这是一本有用的指南书;对 Tomcat 感兴趣的人而言,这是一本优秀的介绍工具。

    但是这本书翻译好像比较糟糕,大家可以看看英文版

    http://index-of.co.uk/Misc/O’Reilly%20Tomcat%20The%20Definitive%20Guide%20(2nd%20Edition).pdf

    深入剖析 Tomcat

    另外一本就是深入剖析 Tomcat

    img

    这本书会揭示 Tomcat 的工作原理,通过学习本书,你将可以自行开发 Tomcat 组件,或者扩展已有的组件,甚至可以让你自制一个 Tomcat 服务器。

    关于 Tomcat 学习有多深,这个没有一个明确的定论,对于初级 Java 开发而言,你知道 Tomcat 是干什么的,能够起到什么作用就可以了,如果你想要达到中高级 Java 程序员的水平,那么任何深入的学习都是不为过的。

    Tomcat 架构解析

    img

    本书全面介绍了Tomcat的架构、各组件的实现方案以及使用方式。包括Tomcat的基础组件架构以及工作原理,Tomcat各组件的实现方案、使用方式以及详细配置说明,Tomcat与Web服务器集成以及性能优化,Tomcat部分扩展特性介绍等。读者可以了解应用服务器的架构以及工作原理,学习Tomcat的使用、优化以及详细配置。

    这本书和深入剖析 Tomcat 差不多,都是带你深入理解 Tomcat 的一本书,我认为你看哪本都可。

    Servlet/JSP 技术

    下面要聊的不是框架了,而是一项非常古老的技术:Servlet 和 JSP 技术,这两项技术很多人说不用在学习了,说这话的人有两点考量:1. 他认为老的技术都不用学了;2. 他自己根本就不懂。

    在没有前后端分离前,我们的项目架构都是单体,也就是各种 JSP 页面直接耦合进去,Servlet 负责前端和后端的交互,这个时候项目非常冗余,很多文件都扔在一个项目中,导致逻辑混乱,文件类型庞杂。后来随着技术的发展,出现了 SpringMVC ,封装了 Servlet,让我们不用再管理 HttpServletRequest 和 HttpServletResponse,直接让 SpringMVC 把这事干了,我们只用遵照其要求的风格 — restFul 格式,我们就能够把前后端的接口"标准化",随着 HTML5 等动态页面的发展,从而出现了后面我们说的前后端分离的项目架构,也就是前端是一个项目,后端是一个项目。

    但是他们的核心还是 Servlet 和 JSP。

    这里我又开始推荐书了

    Head First Servlet/JSP

    img

    Head First 系列的书就是幽默,通俗易懂,用轻松愉快的语言,通过做游戏的方式就把知识点给你讲明白了。讲述了关于如何编写 servlets 和 JSP 代码,如何使用 JSP 表达式语言,如何部署 Web 应用,如何开发定制标记,以及会话状态、包装器、过滤器、企业设计模式等方面的知识,以一种轻松、幽默而又形象的方式让你了解、掌握 servlets 和 JSP,并将其运用到你的项目中去。

    这本书 cxuan 强烈推荐

    这里给大家推荐一个学习 Servlet 的网站

    Servlet/JSP Gossip

    这同时也是一本书

    img

    作者是台湾人,除了语言有点没有那么痛快之外,其他技术点的讲解还不错。

    Servlet & JSP 核心编程

    img

    这也是一本基础书籍,条理清晰。对于初学者来说是一本不可多得的入门书籍。

    Servlet 和 JSP 的视频,我给你推荐

    尚硅谷最新版JavaWeb全套教程,java web零基础入门完整版

    这个其实也包括了前端 HTML CSS JavaScript Servlet JSP 部分

    JavaWeb视频教程(JSP/Servlet/上传/下载/分页/MVC/三层架构/Ajax)

    这两个视频都是 Web 整合的,单独的 Servlet 可以看看

    【千锋】Servlet教程-Servlet入门

    2020最新servlet教程-Servlet全解和案例实操_

    Spring MVC

    SpringMVC 终于来了!!!!为什么最后再说 SpringMVC,因为Spring MVC 其实就是 Servlet 的一种封装,而且 Spring MVC 打交道的对象是 HTTP 协议,所以你需要先掌握上面知识再学 Spring MVC。

    学习 SpringMVC,我推荐你看

    SpringMVC 学习指南

    img

    本书重在讲述如何通过 Spring MVC 来开发基于 Java 的 Web 应用。全书共计12章,分别从 Spring框架、模型2和 MVC模式、Spring MVC 介绍、控制器、数据绑定和表单标签库、传唤器和格式化、验证器、表达式语言、JSTL、国际化、上传文件、下载文件多个角度介绍了Spring MVC。除此之外,本书还配有丰富的示例以供读者练习和参考。

    看透 SpringMVC

    img

    全面介绍 Spring MVC 的架构、原理、核心概念和操作,通过案例完整呈现 Tomcat 的实现,系统总结 Spring MVC 九大组件的处理以及常用的技巧和实践。

    这两本书看完,SpringMVC 就差不多了,如果觉得还有遗漏的话,不妨看看官网。

    Web on Servlet Stack

    视频可以看看这个

    2020最新SpringMVC教程【IDEA版】

    那么关于 SpringMVC 都需要掌握哪些内容呢?

    Stop. Stop. Stop

    当你从 Java 基础 -> MySQL基础 -> MyBatis -> Spring -> HTML/CSS -> Servlert/JSP -> SpringMVC 学完之后,我觉得你应该需要花 1 - 2 年左右的时间,此时的你应该能够具备完成一个小型 SSM 项目的能力了,现在先不忘下面继续学习了,你应该把你的知识进行整合,你可以按照书中的内容搭建小型项目,或者完成一些 SSM 项目等,很多 Java 方向的毕业设计也就到这里就能完事儿了。

    这里给你推荐一些整合资源

    Java SSM练手小项目-手把手带你搭建一个基于SSM框架的人力资源管理后台系统

    liddhome/yosebook-ssm

    ZhongFuCheng3y/910convenienceSite

    学生管理系统(SSM简易版)总结

    https://github.com/saysky/ForestBlog

    或者看一下尚硅谷的整合教程

    尚硅谷SSM框架实战,ssm整合教程

    此时的你,可以说能够具备一个初级 Java 开发的基本素质了,但是你可能还找不到工作,为什么?因为现阶段最最最流行的框架你还没有接触,下面有请大名鼎鼎的 SpringBoot 大佬登场。

    SpringBoot

    SpringBoot 可以说是当今 Java 领域最火的框架了,那么 SpringBoot 为什么这么火呢?

    从设计理念谈起

    要说到 Spring Boot 为什么这么火,就必须得聊聊 Spring Boot 的设计理念,正是此设计理念奠基了Spring Boot 开发设计的基准,让 Spring Boot 走到了今天。

    那 Spring Boot 的设计理念是什么呢?它就是约定优于配置(convention over configuration)。

    约定优于配置并不是一个新概念,它是一种软件设计范式,很早就应用在软件架构设计中,它的作用是减少软件开发人员需做决定的数量,获得简单的好处,而又不失灵活性。

    只是 Spring Boot 让这个设计理念上升了一个层次,Spring Boot 不止在某个功能上实现此设计理念,而是整个软件体系都在践行约定优于配置。

    Spring Boot 体系将约定优于配置的思想展现得淋淋尽致,小到配置文件,中间件的默认配置,大到内置容器、生态中的各种 Starters 无不遵循此设计规则。

    Spring Boot Jpa 80% 大部分查询功能都以约定的方式给与提供,另外 20% 复杂的场景,提供另外的技术手段来解决,典型的约定优于配置的实现。

    Spring Boot Starter ,在项目启动的时候,根据约定信息对组件进行加载、初始化。因此项目中引入了对于的 Starter 之后,就可以到达开箱即用的效果。

    甚至 Spring Cloud 的设计,也借鉴了约定优于配置的思想,很多组件都是在启动时,默认提供了其相关的功能,可以让我们的使用到达很少配置或者零配置。

    Spring Boot 的 Starter 机制

    Spring Boot Starter 是 Spring Boot 的 星辰大海。

    正是因为丰富的 Spring Boot Starter ,让 Spring Boot 征服了使用各个开源软件的开发者,只要 Spring Boot Starter 指向哪个开源软件,就会让某个开源软件变得异常好用。

    这真的是这样,有一种神笔马良的感觉(夸张了一点)。

    那什么是 Spring Boot Starter 呢?

    在 Spring Boot 中,Starter 是为快速应用开发提供“一站式服务”的依赖(Dependency)。Starter 使得开发人员在开始编写新的模块时不需要拷贝样板式的配置文件、编写样板式的代码,只需要提供最简单的配置即可开始编程。

    Spring Boot Starter 有两个核心组件:自动配置代码和提供自动配置模块及其它有用的依赖。也就意味着当我们项目中引入某个 Starter ,即拥有了此软件的默认使用能力,除非我们需要特定的配置,一般情况下我仅需要少量的配置或者不配置即可使用组件对应的功能。

    Spring Boot 由众多 Starter 组成,随着版本的推移 Starter 家族成员也与日俱增。在传统 Maven 项目中通常将一些层、组件拆分为模块来管理,以便相互依赖复用,在 Spring Boot 项目中我们则可以创建自定义 Spring Boot Starter 来达成该目的。

    Spring Boot Starter 统一了使用不同软件的编程体验。

    在没有使用 Spring Boot Starter 之前,我们需要按照每个开源软件的特性,将对应的组件包集成到我们的开发项目中,因为每个组件的设计理念和开发团队都不一致,因此会有很多不同的调用风格在我们的项目中。

    Spring Boot 强大到很多技术社区都主动提供了对应的 Starter 组件,比如 MyBatis 、Apache Camel、Apache CXF 等等。随着 Spring Boot 的发展 Starter 组件会越来越多。

    Spring Boot 非常强大的原因之一就是提供了大量的 Spring Boot Starter ,如此多的“开箱即用” 的依赖模块,让我们在日常开发中“拿来即用”,以便更加快速和高效专注于业务开发。

    Spring Boot 的豪华开发团队

    我们经常会看到在介绍 Spring Boot 的时候有这么一句:Spring Boot 是由 Pivotal 团队提供的全新框架。由此我们得知 Spring Boot 是由 Pivotal 团队所研发,那么 Pivotal 团队到底是一个什么样的团队呢?其实这里的 Pivotal 团队是指 Pivotal 公司。

    Pivotal 公司介绍:致力于“改变世界构造软件的方式(We are transforming how the world builds software)”,提供云原生应用开发 PaaS 平台及服务,帮助企业客户采用敏捷软件开发方法论,从而提高软件开发人员工作效率、减少运维成本,实现数字化转型、IT 创新,并最终实现业务创新。

    Pivotal 公司可谓是大牛云集,公司研发的产品有: Spring 以及衍生框架、缓存中间件 Redis、消息队列框架 RabbitMQ、数据引擎产品 Greenplum,还有 Tomcat、Groovy 里的一些顶级开发者,DevOps 理论的提出者都在这个公司。

    2016 年风靡全球的云原生理念亦是 Pivotal 公司提出,美国硅谷著名的精益化创业书籍的作者 Eric Ries 也加入了 Pivotal公司。Spring Boot 为什么如此的优秀,正是因为背后有这些全球的顶级开发者。

    Pivotal 公司的背后其实是一场商业并购大片,有很多著名的公司在其身后,戴尔、Spring、EMC、VMware 等等,详情大家开源看这篇文章:《是时候给大家介绍 Spring Boot/Cloud 背后豪华的研发团队了》

    有个好干爹

    Spring Boot 的干爹是谁呢?毫无疑问就是 Spring 了。有图为证,看下面:

    img

    Spring Boot 完全依赖 Spring 来开发,发明 Spring Boot 也是为了让大家更好的使用 Spring,而不是消灭 Spring ,所以说没有 Spring 这个干爹,就没有 Spring Boot 。

    当然 Spring Boot 不仅是基于 Spring 开发这么简单,Spring Boot 完全继承了 Spring 干爹的声誉,说实话如果没有 Spring 这个老干爹十多年来打拼下来的天气,哪有 Spring Boot 今天来的风光。

    2002 年的时候, Rod Johnson 可能也没有想到自己开创的一个小开源软件,可以发展到今天这么辉煌的一刻。到了今天,如果一个 Java 程序员说自己不知道 Spring ,那估计会把他当作外星人吧。

    Spirng 当时以 IoC 和 Aop 开始发家,一开始的目标只是想干掉 EJB 这个庞然大物,但是随着时间的发展,Spring 开始了一路的逆袭之路,在2010年的时候 Spring 还是 SSH 三大框架之一,到了今天 Spring 要说自己是老二,还这没有人敢说自己是第一。

    正是因为 Spring 在 Java 社区中有如此强大的影响力,所以在 Spring Boot 一出生的时候,就受到了广大社区爱好者的关注、使用、写教程、贡献代码、提 Bug。正是因为庞大的开源爱好者,才一起反铺 Spring Boot ,让 Spring Boot 发展这么快,这么好。

    上面这段内容转载自 Spring Boot 为什么这么火?

    所以你只需要再学习完 SpringBoot ,就能够完成一个初级 Java 开发的用人需求了。所以你必须要学好 SpringBoot,之前看很多大咖推荐 SpringBoot 实战这本书,我觉得这本书并不好,反正我看这本书的时候找不到头绪和思路

    img

    很多人认为是基础入门书籍,但是我觉得学习 SpringBoot ,看这几个 github 就行了

    Github点赞接近 100k 的Spring Boot学习教程+实战项目推荐!

    推荐以 Spring Boot 教程与 Spring Cloud 教程的详细开源项目 SpringBoot-Learning 此项目内容为 Spring Boot 教程程序样例,对于 Spring Boot 的初学者来说非常有用,文末也列出了Spring 相关开源项目,供大家交流学习。

    1. SpringBoot-Learning 部分样例:
    快速入门

    工程配置

    Web开发

    数据访问、日志管理等等,项目地址:程序猿DD/SpringBoot-Learning - 码云 Gitee.com

    1. 项目名称:spring boot 实践学习案例 springboot-learning-example
      项目结构:
      a. 『 基础 - 入门篇 』

    b. 『 基础 - Web 业务开发篇 』

    c. 『 基础 – 数据存储篇 』

    d. 『 基础 – 数据缓存篇 』

    e. 『 其他篇 』

    Spring Data ES 篇

    项目地址:泥沙砖瓦浆木匠/springboot-learning-example - 码云 Gitee.com

    Spring 相关项目推荐:

    1. 项目名称:基于Spring+SpringMVC+Mybatis分布式敏捷开发系统架构

    img

    项目内容:基于Spring+SpringMVC+Mybatis分布式敏捷开发系统架构,提供整套公共微服务服务模块:集中权限管理(单点登录)、内容管理、支付中心、用户管理(支持第三方登录)、微信平台、存储系统、配置中心、日志分析、任务和通知等,支持服务治理、监控和追踪,努力为中小型企业打造全方位J2EE企业级开发解决方案。
    项目地址:shuzheng/zheng - 码云 Gitee.com

    1. 项目名称:模块化开发系统 ybg-spring-fast
      项目简介:以SpringBoot 为中心,模块化开发系统,用户可以随意删减除权限框架外 任意的系统模块。复用,组装性强主要应用技术:spring Security+Ehcache+quartz+swagger2+Mysql5.6+springjdbc+druid+spring social+spring session + layerui+vue.js等。

    img

    项目地址:YYDeament/ybg-spring-fast - 码云 Gitee.com

    1. 项目名称:JAVA分布式快速开发平台 iBase4J

    img

    **项目内容:**JAVA分布式快速开发平台:SpringBoot,SpringMVC,Mybatis,mybatis-plus,motan/dubbo分布式,Redis缓存,Shiro权限管理,Spring-Session单点登录,Quartz分布式集群调度,Restful服务,QQ/微信登录,App token登录,微信/支付宝支付;日期转换、数据类型转换、序列化、汉字转拼音、身份证号码验证、数字转人民币、发送短信、发送邮件、加密解密、图片处理、excel导入导出、FTP/SFTP/fastDFS上传下载、二维码、XML读写、高精度计算、系统配置工具类等等。
    项目地址:iBase4J/iBase4J - 码云 Gitee.com

    **4. 项目名称:**Java EE(J2EE)快速开发框架 ThinkGem
    **项目内容:**Java EE(J2EE)快速开发框架,基于经典技术组合(Spring MVC、Apache Shiro、MyBatis、Bootstrap UI),包括核心模块如:组织机构、角色用户、权限授权、数据权限、内容管理、工作流等。虽说很长时间没有大的更新了,但它的架构精良易于扩展深受大家喜爱,依然是中小企业的首选,它的功能设计、底层架构也非常具有参考意义、是学习入门的首选。关注我ThinkGem开源中国博客了解4.0最新动态。
    项目地址:ThinkGem/JeeSite - 码云 Gitee.com

    **5. 项目名称:**Java快速开发平台 MCMS

    img

    项目内容:完整开源,Java快速开发平台。基于Spring、SpringMVC、Mybatis架构,MStore提供更多好用的插件与模板(文章、商城、微信、论坛、会员、评论、支付、积分、工作流、任务调度等,同时提供上百套免费模板任意选择),价值源自分享!铭飞系统不仅一套简单好用的开源系统、更是一整套优质的开源生态内容体系。
    项目地址:铭飞/MCMS - Gitee

    1. 项目名称:基于Spring Cloud微服务化开发平台 AG-Admin

    img

    项目内容:AG-Admin是国内首个基于Spring Cloud微服务化开发平台,具有统一授权、认证后台管理系统,其中包含具备用户管理、资源权限管理、网关API管理等多个模块,支持多业务系统并行开发,可以作为后端服务的开发脚手架。代码简洁,架构清晰,适合学习和直接项目中使用。核心技术采用Eureka、Fegin、Ribbon、Zuul、Hystrix、JWT Token、Mybatis等主要框架和中间件,前端采用vue-element-admin组件。
    项目地址:老A/AG-Admin - 码云 Gitee.com

    1. 项目名称:轻量级的Spring Boot快速开发平台 renren-fast
      项目简介:renren-fast是一个轻量级的Spring Boot快速开发平台,其设计目标是开发迅速、学习简单、轻量级、易扩展;使用Spring Boot、Shiro、MyBatis、Redis、Bootstrap、Vue2.x等框架,包含:管理员列表、角色管理、菜单管理、定时任务、参数管理、代码生成器、日志管理、云存储、API模块(APP接口开发利器)、前后端分离等。
      项目地址:人人开源/renren-fast - 码云 Gitee.com

    作者:Gitee 链接:https://www.zhihu.com/question/53729800/answer/255785661

    其实你学了一段时间就会发现,SpringBoot 就完全是个脚手架,方便我们快速搭建一个项目,简化了配置,不用再让你写繁杂的 XML 表达式,相反的而是用 注解 来实现,他们的原理类似,只不过使用注解能让你的项目更加简洁。

    最后再推荐一下 SpringBoot 的官网

    https://docs.spring.io/spring-boot/docs/2.3.10.RELEASE/reference/htmlsingle/

    Spring Cloud

    Spring Cloud 是以 SpringBoot 为基础的微服务项目架构,现在大多数互联网公司甚至一些传统行业都开始用 Spring Cloud 为基础架构,有些是因为业务需求,有些是为了装 B,反正不管怎样,面试官问起你会不会 Spring Cloud,你说不会的话,那么你的印象分估计会降低,所以初级程序员,或多或少要了解一下 Spring Cloud ,所以我给你推荐几本书和 Github 作为基础和练习。

    我刚开始学 Spring Cloud 是看的这本书,当然现在这个书中的版本有些好了,不过作为了解,你也应该看一下这本书

    img

    《Spring Cloud 微服务实战》从时下流行的微服务架构概念出发,详细介绍了 Spring Cloud 针对微服务架构中几大核心要素的解决方案和基础组件。对于各个组件的介绍,《Spring Cloud 微服务实战》主要以示例与源码结合的方式来帮助读者更好地理解这些组件的使用方法以及运行原理。同时,在介绍的过程中,还包含了作者在实践中所遇到的一些问题和解决思路,可供读者在实践中作为参考。

    这本书的作者翟永超(DD)也建了一个网站

    https://blog.didispace.com/spring-cloud-learning/

    反正学习 Spring Cloud 跟着 D 总没错的。

    可以看下 Spring Cloud 大致都要学习哪些东西

    Brixton 版本

    img

    Dalston 版本

    img

    Edgware 版本

    img

    Finchley 版本

    img

    还有各种套件的选择

    img

    img

    顺便把阿里巴巴开源框架 Spring Cloud Alibaba 学了

    img

    除了上述内容之外,还可以看看到底什么是微服务

    img

    本书全面介绍了微服务的建模、集成、测试、部署和监控,通过一个虚构的公司讲解了如何建立微服务架构。主要内容包括认识微服务在保证系统设计与组织目标统一上的重要性,学会把服务集成到已有系统中,采用递增手段拆分单块大型应用,通过持续集成部署微服务,等等。

    什么是微服务设计模式,微服务设计模式都有哪些,以及微服务的拆分策略等。

    img

    估计很多人可能会把集群、微服务和分布式搞混了,下面来解惑下

    集群是个物理形态,分布式是个工作方式。
    1.分布式:一个业务分拆多个子业务,部署在不同的服务器上
    2.集群:同一个业务,部署在多个服务器上
    分布式是指将不同的业务分布在不同的地方。而集群指的是将几台服务器集中在一起,实现同一业务。

    分布式中的每一个节点,都可以做集群。而集群并不一定就是分布式的。
    举例:就比如新浪网,访问的人多了,他可以做一个集群,前面放一个响应服务器,后面几台服务器完成同一业务,如果有业务访问的时候,响应服务器看哪台服务器的负载不是很重,就将给哪一台去完成。
    而分布式,从窄意上理解,也跟集群差不多,但是它的组织比较松散,不像集群,有一个组织性,一台服务器垮了,其它的服务器可以顶上来。
    分布式的每一个节点,都完成不同的业务,一个节点垮了,那这个业务就不可访问了。
    简单说,分布式是以缩短单个任务的执行时间来提升效率的,而集群则是通过提高单位时间内执行的任务数来提升效率。
    例如:如果一个任务由 10 个子任务组成,每个子任务单独执行需 1 小时,则在一台服务器上执行该任务需 10 小时。
    采用分布式方案,提供 10 台服务器,每台服务器只负责处理一个子任务,不考虑子任务间的依赖关系,执行完这个任务只需一个小时。(这种工作模式的一个典型代表就是 Hadoop 的 Map/Reduce 分布式计算模型)
    而采用集群方案,同样提供 10 台服务器,每台服务器都能独立处理这个任务。假设有 10 个任务同时到达,10 个服务器将同时工作,1 小时后,10 个任务同时完成,这样,整体来看,还是 1 小时内完成一个任务!
    好的设计应该是分布式和集群的结合,先分布式再集群,具体实现就是业务拆分成很多子业务,然后针对每个子业务进行集群部署,这样每个子业务如果出了问题,整个系统完全不会受影响。
    另外,还有一个概念和分布式比较相似,那就是微服务。
    **微服务是一种架构风格,一个大型复杂软件应用由一个或多个微服务组成。**系统中的各个微服务可被独立部署,各个微服务之间是松耦合的。每个微服务仅关注于完成一件任务并很好地完成该任务。在所有情况下,每个任务代表着一个小的业务能力。

    区别:
    1.分布式

    img

    将一个大的系统划分为多个业务模块,业务模块分别部署到不同的机器上,各个业务模块之间通过接口进行数据交互。区别分布式的方式是根据不同机器不同业务。
    上面:service A、B、C、D 分别是业务组件,通过API Geteway进行业务访问。
    注:分布式需要做好事务管理。
    分布式事务可参考:微服务架构的分布式事务解决方案

    2.集群模式

    img

    集群模式是不同服务器部署同一套服务对外访问,实现服务的负载均衡。区别集群的方式是根据部署多台服务器业务是否相同。
    注:集群模式需要做好session共享,确保在不同服务器切换的过程中不会因为没有获取到session而中止退出服务。
    一般配置Nginx的负载容器实现:静态资源缓存、Session共享可以附带实现,Nginx支持5000个并发量。

    分布式是否属于微服务?
    答案是肯定的。微服务的意思也就是将模块拆分成一个独立的服务单元通过接口来实现数据的交互。

    微服务架构
    微服务的设计是为了不因为某个模块的升级和BUG影响现有的系统业务。微服务与分布式的细微差别是,微服务的应用不一定是分散在多个服务器上,他也可以是同一个服务器。

    img

    分布式和微服的架构很相似,只是部署的方式不一样而已。

    链接:https://www.jianshu.com/p/1f9455139a31
    作者:mayiwoaini

    然后我就要推荐给你一本分布式方向的神书了

    img

    有些人认为这是数据处理方向的人看的书,但是里面涉及 NoSQL, 大数据,最终一致性,CAP,MapReduce,流处理确实 Java 程序员也需要知道和了解的,这本书讲的比较高深,适合在工作中慢慢研究,不太适合 Java 方向的初学者。

    img

    综上所述,我上面推荐的三本书都适合中高级 Java 程序员来看的,初学者把 D 总的文章搞懂了就行,或者可以做做下面的 github

    macrozheng/springcloud-learning

    Dubbo

    说完了 Spring Cloud,怎能少的了 Dubbo?

    先来了解一下 Spring Cloud 和 Dubbo 的区别是什么,如何做技术选型?

    Java 微服务框架选型(Dubbo 和 Spring Cloud?)

    Dubbo 的书籍感觉一般,我没有看过,不过大家感兴趣可以了解一下

    img

    《深入理解Apache Dubbo与实战》首先介绍Dubbo的简史、后续的规划和整体架构大图;接着介绍Dubbo环境配置,并基于Dubbo开发第一款应用程序;然后介绍Dubbo内置的常用注册中心的实现原理,Dubbo扩展点加载的原理和实现,Dubbo的启动、服务暴露、服务消费和优雅停机的机制,Dubbo中RPC协议细节、编解码和服务调用实现原理,Dubbo集群容错、路由和负载均衡机制,Dubbo的扩展点相关知识,Dubbo高级特性的实现和原理,Dubbo常用的Filter的实现原理,Dubbo中新增etcd3注册中心的实战内容和Dubbo服务治理平台的相关知识;最后介绍Dubbo未来生态和Dubbo Mesh的相关知识。

    官网文档走起! Apache Dubbo

    Dubbo 的 Github apache/dubbo

    Redis

    Redis 可以说是最流行的 NoSQL 数据库了,你可能不知道 Redis 是干什么用的,我先给你普及一下。

    缓存数据库目前最常用的两种就是 Redis 和 Memcached,与 Memcached 相比 Redis 其一大特点是支持丰富的数据类型(Memcached 只能用 string 类型)。Redis 因为其丰富的数据结构因此应用范围不局限于缓存,有很多场景用 Redis 来实现可以大大减少工作量。

    关于 Redis 的使用场景,可以看一下

    Redis能用来做什么

    深入分析Redis特点及应用场景

    这里给大家推荐两本 Redis 入门的经典书籍

    Redis 实战

    img

    这本书一共由三个部分组成。第一部分对Redis进行了介 绍,说明了Redis的基本使用方法、它拥有的5种数据结构以及操作这5种数据结构的命令,并讲解了如何使用Redis去构建文章展示网站、cookie、购物车、网页缓存、数据库行缓存等一系列程序。第二部分对Redis命令进行了更详细的介绍,并展示了如何使用Redis去构建更为复杂的辅助工具和应用程序,并在最后展示了如何使用Redis去构建一个简单的社交网站。第三部分对Redis用户经常会遇到的一些问题进行了介绍,讲解了降低Redis内存占用的方法、扩展Redis性能的方法以及使用Lua语言进行脚本编程的方法。这

    Redis 设计与实现

    img

    这本书强烈推荐,系统而全面地描述了 Redis 内部运行机制,图示丰富,描述清晰,并给出大量参考信息,是 NoSQL 数据库开发人员的案头必备。

    这本书和上面的 Redis 实战,一个讲实现,一个讲思想,正所谓理论和实践相结合。

    Redis 开发与运维

    img

    这本书也是学习 Redis 很好的一本,也针对于初学者,适合零基础的童鞋。这本书全面讲解 Redis 基本功能及其应用,并结合线上开发与运维监控中的实际使用案例,深入分析并总结了实际开发运维中遇到的“陷阱”,以及背后的原因, 包含大规模集群开发与管理的场景、应用案例与开发技巧,为高效开发运维提供了大量实际经验和建议。

    Redis 深度历险:核心原理与应用实践

    img

    Redis 深度历险是老钱写的,老钱最开始在掘金开了一门掘金小册,受到广泛好评,所以这本书也是如此。Redis 深度历险适合对于 Redis 有一定基础了解的程序员阅读,渴望深度掌握 Redis 技术原理的中高级后端开发者;渴望成功进入大型互联网企业研发部的中高级后端开发者;需要支撑公司 Redis 中间件运维工作的初中级运维工程师;对 Redis 中间件技术好奇的中高级前端技术研究者。

    学习 Redis 基本上上面几本书看完就差不多了,当然官网是必不可少的

    Redis

    关于 Redis 相关知识,你需要了解

    Kafka

    我刚开始听到 Kafka 的时候,还以为是写《变形记》的那位呢 哈哈哈,其实不是,Kafka 是一个优秀的消息流平台。

    img

    Kafka学习之路 (一)Kafka的简介

    就介绍一些 kafka 的基本内容显然不够,更多内容你可以参考

    Kafka 权威指南

    img

    我当时入门看的是这本书,所以强烈推荐一下。这本书是 O’ RELLY 出版的,作者为 LinkedIn 的 Kafka 核心作者和一线技术人员共同执笔写成的,可以说是非常权威。

    这本书详细介绍了如何部署Kafka集群、开发可靠的基于事件驱动的微服务,以及基于 Kafka 平台构建可伸缩的流式应用程序。通过详尽示例,你将会了解到 Kafka 的设计原则、可靠性保证、关键API,以及复制协议、控制器和存储层等架构细节。

    Apache Kafka实战

    img

    这本书的作者是胡夕老师,胡夕老师对 Kafka 有非常深入的理解,他也在极客时间开了一门 Kafka 的课程,我是通过课程认识他的,胡夕老师对 Kafka 源码有很深的研究,所以这本 Apache Kafka 实战,是一本涵盖 Apache Kafka 各方面的具有实践指导意义的工具书和参考书。作者结合典型的使用场景,对 Kafka 整个技术体系进行了较为全面的讲解,以便读者能够举一反三,直接应用于实践。同时,本书还对 Kafka 的设计原理及其流式处理组件进行了较深入的探讨,并给出了翔实的案例。

    深入理解Kafka:核心设计与实践原理

    img

    这本书适合对 Kafka 有一定程度了解的童鞋,这本书从基础概念入手,循序渐进地转入对其内部原理的剖析。

    最后,官网压轴

    Apache Kafka

    kafka 的学习视频,大家看看尚硅谷的就可以了。

    尚硅谷Kafka教程(kafka框架快速入门)

    Kafka 一般会涉及如下内容

    ZooKeeper

    Kafka 的底层是使用 ZooKeeper 来保证可靠性的,那么 ZooKeeper 是什么呢?

    ZooKeeper 介绍

    ZooKeeper 一个中心化的服务, 用于维护配置信息, 命名服务(naming), 提供分布式同步和集群服务(group services)。

    它是一个开源的分布式应用程序协调服务, 作为 Google Chubby 的一个开源实现, 是 Hadoop 和 Hbase 的重要组件。 ZooKeeper 的目标是封装好复杂易出错的关键服务, 暴露简单易用、高效、稳定的接口给用户, 提供 java 和 C 接口。

    设计目标

    简单
    ZooKeeper 允许分布式的进程之间通过一个共享的层级命名空间(hierarchinal namespace, 和文件系统类似)进行协调。
    ZK 实现了高性能、高可用和严格顺序访问, 是的它可以用于大规模分布式系统, 无单点故障问题, 和复杂的同步原语。
    复制的(replicated)
    ZooKeeper 和其它的分布式进程一样, 也是一个集群的主机作为一个整体。结构如下图

    img

    组成 ZooKeeper 服务的所有服务器必须指向相互之间的存在, 并在内存中维护一张状态图和事务日志, 以及永久储存的快照。 只要服务器中的一个多数(majority)保持可用, ZooKeeper 就可以继续提供服务。
    客户端连接到一个单一的(single) ZooKeeper 服务器, 通过 TCP 连接来发送请求、获取响应、观察的事件和发送心跳。 如果 TCP 连接断开了, 客户端则连接到其它服务器。

    有序(ordered)
    ZooKeeper 用一个数字表示每一次的更新, 以反映所有 ZooKeeper 事务的顺序。后续可以利用这个顺序来实现诸如同步原语之类的高级抽象。

    快速(fast)
    ZK 在读多写少的负载中性能尤其高, 读写比例大概处于 10:1 时表现最好。

    数据模型和层级命名空间(hierarchinal namespace)
    命名空间

    img

    名字是一个用斜杆(/)分隔的路径元素序列, ZK 中每一个节点(znode)都用路径标识。

    节点和临时节点(ephemeral nodes)
    和文件系统不同, ZK 中的节点可以拥有数据和子节点。ZK 被设计来存储协调数据: 状态信息、配置、位置信息等, 所以数据通常很小(byte 到 kilobyte 之间)。
    znode 维护了一个状态结构体(stat structure), 结构体包含数据修改的版本, ACL(Access Control List) 变化, 时间戳。 每次数据修改, 版本号加一。
    znode 中的数据读取都是原子的, 读写都是整个节点所有数据进行读写, 并且通过 ACL 进行访问控制。
    临时节点表示只在 session 存续的期间存在的节点, 在实现[tbd]时很有用。

    条件更新和观察(watches)
    当一个 znode 改变时会触发一个观察, 且删除 watch。客户端可以通过 watch 来接收到通知, 如果客户端和 ZK 的连接断开了会受到一个本地通知。

    保证(Guarantees)

    1. 顺序一致性(Sequential Consistency) - 从一个客户端来的更新会按照发送的顺序应用
    2. 原子性(atomicity) -
    3. 单系统镜像(Signle System Image) - 不管客户端连到的是哪一个 ZK 服务器, 看到的都是同样一个 view
    4. 可靠性(Reliability) -
    5. 及时性(Timeliness) - 在一定的时间范围内(within a certain time bound), 客户端看到服务器 view 保证是最新的

    简单 API
    简单的编程接口

    • create
    • delete
    • exists
    • get data
    • set data
    • get children
    • sync

    实现

    img

    除了 Reqeust Processor 以外, 组成 ZK 服务的每一台服务器拥有所有组件的一份本地拷贝。Replicated Database 是一个内存数据库, 而每一个更新操作都会先序列化到磁盘, 然后才会应用到内存数据库。

    • 读请求 - ZK 服务器根据的本地 Replicated Database 响应
    • 写请求 - ZK 服务器会将来自客户端的所有写请求转发到角色为 leader 的 ZK 服务器(leader 只有一个, 其它称为 follower) 来写, 然后同步给 follower

    ZK 使用一个自定义的原子消息协议。

    性能

    img

    测试环境

    • ZooKeeper release 3.2
    • 服务器 双核 2GHz Xeon, 两块 15K RPM 的 SATA, 一块作为 ZK 的日志, 快照写到系统盘
    • 读写请求都是 1K
    • “Servers” 表示提供服务的 ZK 服务器数量
    • 接近 30 台其它服务器用来模拟客户端
    • leader 配置成不接受客户端连接

    可靠性

    img

    图中 1-5 表示如下五个事件:

    1. 一个 follower 失效和恢复
    2. 另外一个 follower 失效和恢复
    3. leader 失效
    4. 两个 follower 失效和恢复
    5. 另外一个 leader 失效

    ZK 服务器组由 7 台服务器组成, 写请求的比例保持在 30%。
    几个观察到的现象

    • follower 失效和恢复足够快的话, ZK 能够保持高吞吐
    • leader 失效性能影响较大
    • 花了不到 200ms 来选举一个新的 leader
    • follower 恢复后, 吞吐能够提升回来

    更多关于 ZooKeeper 的内容,可以参考下

    从 Paxos 到 Zookeeper

    img

    这本书从分布式一致性的理论出发,向读者简要介绍几种典型的分布式一致性协议,以及解决分布式一致性问题的思路,其中重点讲解了 Paxos 和 ZAB 协议。同时,本书深入介绍了分布式一致性问题的工业解决方案——ZooKeeper,并着重向读者展示这一分布式协调框架的使用方法、内部实现及运维技巧,旨在帮助读者全面了解 ZooKeeper,并更好地使用和运维 ZooKeeper。

    ZooKeeper : 分布式过程协同技术详解

    img

    这本书内容非常好,但是翻译属实有些不忍直视了。

    一般市面上关于 ZooKeeper 的书非常少,只找到了这两本,推荐读者读一下 《从 Paxos 到 ZooKeeper》 这本书,我看过一遍,内容还是写的非常容易理解。

    关于 ZooKeeper 的视频,我还是推荐你尚硅谷的

    尚硅谷Zookeeper教程(zookeeper框架精讲)

    关于 ZooKeeper ,你需要掌握的有

    Nginx

    Nginx 基础知识

    Nginx 是什么?

    Nginx 是一个 web 服务器,主要处理客户端和服务器的请求分发。

    特点和优势

    1. 高并发
    2. 热部署
    3. 低功耗
    4. 热部署

    使用和扩展

    开源免费的Nginx与商业版Nginx Plus,与之对应的是免费OpenResty与商业版OpenResty

    Nginx 正向代理与反向代理

    为了便于理解,首先先来了解一下一些基础知识,nginx是一个高性能的反向代理服务器那么什么是反向代理呢?

    代理是在服务器和客户端之间假设的一层服务器,代理将接收客户端的请求并将它转发给服务器,然后将服务端的响应转发给客户端。

    不管是正向代理还是反向代理,实现的都是上面的功能。

    如果你对OSI 七层模型与 TCP/IP 四层模型不是很熟悉可以再回顾下

    img

    正向代理

    正向代理(forward)意思是一个位于客户端和原始服务器 (origin server) 之间的服务器,为了从原始服务器取得内容,客户端向代理发送一个请求并指定目标 (原始服务器),然后代理向原始服务器转交请求并将获得的内容返回给客户端。

    正向代理是为我们服务的,即为客户端服务的,客户端可以根据正向代理访问到它本身无法访问到的服务器资源。

    正向代理对我们是透明的,对服务端是非透明的,即服务端并不知道自己收到的是来自代理的访问还是来自真实客户端的访问。

    反向代理

    反向代理(Reverse Proxy)方式是指以代理服务器来接受 internet 上的连接请求,然后将请求转发给内部网络上的服务器,并将从服务器上得到的结果返回给 internet 上请求连接的客户端,此时代理服务器对外就表现为一个反向代理服务器。

    反向代理是为服务端服务的,反向代理可以帮助服务器接收来自客户端的请求,帮助服务器做请求转发,负载均衡等。

    反向代理对服务端是透明的,对我们是非透明的,即我们并不知道自己访问的是代理服务器,而服务器知道反向代理在为他服务。

    Nginx 基本配置

    安装nginx时通常需要编译自己需要的模块,可以使用 rpmbuild 制作 Nginx 的 RPM 包

    main                                # 全局配置
    
    events {                            # nginx工作模式配置
    }
    
    http {                                # http设置
        ....
    
        server {                        # 服务器主机配置
            ....
            location {                    # 路由配置
                ....
            }
    
            location path {
                ....
            }
    
            location otherpath {
                ....
            }
        }
    
        server {
            ....
    
            location {
                ....
            }
        }
    
        upstream name {                    # 负载均衡配置
            ....
        }
    }
    

    如果想要生成nginx规范配置,可以参考nginxconfig.io

    下面是 nginx 一些配置中常用的内置全局变量,你可以在配置的任何位置使用它们。

    | 变量名 | 功能 | | — | — | | $host | 请求信息中的 Host,如果请求中没有 Host 行,则等于设置的服务器名 | | $request_method | 客户端请求类型,如 GETPOST | | $remote_addr | 客户端的 IP 地址 | | $args | 请求中的参数 | | $content_length | 请求头中的 Content-length 字段 | | $http_user_agent | 客户端 agent 信息 | | $http_cookie | 客户端 cookie 信息 | | $remote_addr | 客户端的 IP 地址 | | $remote_port | 客户端的端口 | | $server_protocol | 请求使用的协议,如 HTTP/1.0HTTP/1.1\ | | $server_addr | 服务器地址 | | $server_name | 服务器名称 | | $server_port | 服务器的端口号 |

    img

    Nginx 负载均衡

    Upstream 指定后端服务器地址列表,在 server 中拦截响应请求,并将请求转发到 Upstream 中配置的服务器列表。

    upstream balanceServer {
        server 10.1.22.33:12345;
        server 10.1.22.34:12345;
        server 10.1.22.35:12345;
    }
    
    server {
        server_name  fe.server.com;
        listen 80;
        location /api {
            proxy_pass http://balanceServer;
        }
    }
    

    上面的配置只是指定了 nginx 需要转发的服务端列表,并没有指定分配策略。

    默认情况下采用的是轮询策略,将所有客户端请求轮询分配给服务端。这种策略是可以正常工作的,但是如果其中某一台服务器压力太大,出现延迟,会影响所有分配在这台服务器下的用户。

    Nginx常用命令

    # 快速关闭Nginx,可能不保存相关信息,并迅速终止web服务
    nginx -s stop
    # 平稳关闭Nginx,保存相关信息,有安排的结束web服务
    nginx -s quit
    # 因改变了Nginx相关配置,需要重新加载配置而重载
    nginx -s reload
    # 重新打开日志文件
    nginx -s reopen
    # 为 Nginx 指定一个配置文件,来代替缺省的
    nginx -c filename
    # 不运行,而仅仅测试配置文件。nginx 将检查配置文件的语法的正确性,并尝试打开配置文件中所引用到的文件
    nginx -t
    #  显示 nginx 的版本
    nginx -v
    # 显示 nginx 的版本,编译器版本和配置参数
    nginx -V
    # 格式换显示 nginx 配置参数
    2>&1 nginx -V | xargs -n1
    2>&1 nginx -V | xargs -n1 | grep lua
    

    上面只是一些 Nginx 的基础知识,如果想要了解更多的 Nginx 内容,你可以参考

    深入理解 Nginx

    img

    学习 Nginx ,跟着陶辉老师就够了,这本书首先通过介绍官方 Nginx 的基本用法和配置规则,帮助读者了解一般 Nginx 模块的用法,然后重点介绍了如何开发 HTTP 模块(含 HTTP 过滤模块)来得到定制化的 Nginx,其中包括开发—个功能复杂的模块所需要了解的各种知识,并对内存池的实现细节及 TCP 协议进行了详细介绍;接着,综合 Nginx 框架代码分析了 Nginx 架构的设计理念和技巧,此外,还新增了如何在模块中支持 HTTP变量,以及与 slab 共享内存等相关的内容,相信通过完善,可进一步帮助读者更好地开发出功能丰富、性能—流的 Nginx 模块。

    如果大家有兴趣,陶辉老哥在极客时间开了一门关于 Nginx 的课程,大家可以详细了解下。

    Nginx 是需要你在工作中逐渐掌握的,它涉及内容如下

    Netty

    Netty 是一个利用 Java 的高级网络的能力,隐藏其背后的复杂性而提供一个易于使用的 API 的客户端/服务器框架。
    Netty 是一个广泛使用的 Java 网络编程框架(Netty 在 2011 年获得了Duke’s Choice Award,见https://www.java.net/dukeschoice/2011)。它活跃和成长于用户社区,像大型公司 Facebook 和 Instagram 以及流行 开源项目如 Infinispan, HornetQ, Vert.x, Apache Cassandra 和 Elasticsearch 等,都利用其强大的对于网络抽象的核心代码。

    大家可以看看这篇文章 Netty入门教程——认识Netty

    Netty 推荐一本书

    Netty 实战

    img

    这一本书循序渐进的为你介绍了 Netty 各个方面内容,本书共分为4个部分:第一部分详细地介绍Netty 的相关概念以及核心组件,第二部分介绍自定义协议经常用到的编解码器,第三部分介绍Netty 对于应用层高级协议的支持,会覆盖常见的协议及其在实践中的应用,第四部分是几个案例研究。此外,附录部分还会简单地介绍 Maven,以及如何通过使用 Maven编译和运行本书中的示例。

    ES

    ES 的全称是 Elasticsearch,这个名字挺难拼写的,关于 ES 是干啥的以及 ES 入门汇总,你可以参考这一篇

    Elasticsearch入门,这一篇就够了

    更多关于 ES 的内容,你可以看这本书

    Elasticsearch 实战

    img

    全书共分两个部分,第一部分解释了核心特性,内容主要涉及 Elasticsearch 的介绍,数据的索引、更新和删除,数据的搜索,数据的分析,使用相关性进行搜索,使用聚集来探索数据,文档间的关系等;第二部分介绍每个特性工作的更多细节及其对性能和可扩展性的影响,以便对核心功能进行产品化,内容主要涉及水平扩展和性能提升等。

    Elasticsearch 源码解析与优化实战

    img

    《Elasticsearch源码解析与优化实战》介绍了Elasticsearch的系统原理,旨在帮助读者了解其内部原理、设计思想,以及在生产环境中如何正确地部署、优化系统。系统原理分两方面介绍,一方面详细介绍主要流程,例如启动流程、选主流程、恢复流程;另一方面介绍各重要模块的实现,以及模块之间的关系,例如 gateway 模块、allocation 模块等。本书的最后一部分介绍如何优化写入速度、搜索速度等大家关心的实际问题,并提供了一些诊断问题的方法和工具供读者参考。

    我刚开始学 ES 的时候,竟然不知道 ELK 是什么。。。。。。那么 ELK 是啥,为啥要搞 ELK ?

    为什么用到ELK:
    一般我们需要进行日志分析场景:直接在日志文件中 grep、awk 就可以获得自己想要的信息。但在规模较大的场景中,此方法效率低下,面临问题包括日志量太大如何归档、文本搜索太慢怎么办、如何多维度查询。需要集中化的日志管理,所有服务器上的日志收集汇总。常见解决思路是建立集中式日志收集系统,将所有节点上的日志统一收集,管理,访问。
    一般大型系统是一个分布式部署的架构,不同的服务模块部署在不同的服务器上,问题出现时,大部分情况需要根据问题暴露的关键信息,定位到具体的服务器和服务模块,构建一套集中式日志系统,可以提高定位问题的效率。
    一个完整的集中式日志系统,需要包含以下几个主要特点:

    • 收集-能够采集多种来源的日志数据
    • 传输-能够稳定的把日志数据传输到中央系统
    • 存储-如何存储日志数据
    • 分析-可以支持 UI 分析
    • 警告-能够提供错误报告,监控机制

    ELK提供了一整套解决方案,并且都是开源软件,之间互相配合使用,完美衔接,高效的满足了很多场合的应用。目前主流的一种日志系统。

    ELK简介:
    ELK是三个开源软件的缩写,分别表示:Elasticsearch , Logstash, Kibana , 它们都是开源软件。新增了一个FileBeat,它是一个轻量级的日志收集处理工具(Agent),Filebeat占用资源少,适合于在各个服务器上搜集日志后传输给Logstash,官方也推荐此工具。
    Elasticsearch是个开源分布式搜索引擎,提供搜集、分析、存储数据三大功能。它的特点有:分布式,零配置,自动发现,索引自动分片,索引副本机制,restful风格接口,多数据源,自动搜索负载等。
    Logstash 主要是用来日志的搜集、分析、过滤日志的工具,支持大量的数据获取方式。一般工作方式为c/s架构,client端安装在需要收集日志的主机上,server端负责将收到的各节点日志进行过滤、修改等操作在一并发往elasticsearch上去。
    Kibana 也是一个开源和免费的工具,Kibana可以为 Logstash 和 ElasticSearch 提供的日志分析友好的 Web 界面,可以帮助汇总、分析和搜索重要数据日志。
    Filebeat隶属于Beats。目前Beats包含四种工具:

      1. Packetbeat(搜集网络流量数据)
      2. Topbeat(搜集系统、进程和文件系统级别的 CPU 和内存使用情况等数据)
      3. Filebeat(搜集文件数据)
      4. Winlogbeat(搜集 Windows 事件日志数据)

    官方文档:
    Filebeat:
    https://www.elastic.co/cn/products/beats/filebeat
    https://www.elastic.co/guide/en/beats/filebeat/5.6/index.html
    Logstash:
    https://www.elastic.co/cn/products/logstash
    https://www.elastic.co/guide/en/logstash/5.6/index.html
    Kibana:
    https://www.elastic.co/cn/products/kibana
    https://www.elastic.co/guide/en/kibana/5.5/index.html
    Elasticsearch:
    https://www.elastic.co/cn/products/elasticsearch
    https://www.elastic.co/guide/en/elasticsearch/reference/5.6/index.html
    elasticsearch中文社区:
    https://elasticsearch.cn/

    ELK架构图:
    架构图一:

    img

    这是最简单的一种ELK架构方式。优点是搭建简单,易于上手。缺点是Logstash耗资源较大,运行占用CPU和内存高。另外没有消息队列缓存,存在数据丢失隐患。
    此架构由Logstash分布于各个节点上搜集相关日志、数据,并经过分析、过滤后发送给远端服务器上的Elasticsearch进行存储。Elasticsearch将数据以分片的形式压缩存储并提供多种API供用户查询,操作。用户亦可以更直观的通过配置Kibana Web方便的对日志查询,并根据数据生成报表。

    架构图二:

    img

    此种架构引入了消息队列机制,位于各个节点上的Logstash Agent先将数据/日志传递给Kafka(或者Redis),并将队列中消息或数据间接传递给Logstash,Logstash过滤、分析后将数据传递给Elasticsearch存储。最后由Kibana将日志和数据呈现给用户。因为引入了Kafka(或者Redis),所以即使远端Logstash server因故障停止运行,数据将会先被存储下来,从而避免数据丢失。

    架构图三:

    img

    此种架构将收集端logstash替换为beats,更灵活,消耗资源更少,扩展性更强。同时可配置Logstash 和Elasticsearch 集群用于支持大集群系统的运维日志数据监控和查询。

    Filebeat工作原理:
    Filebeat由两个主要组件组成:prospectors 和 harvesters。这两个组件协同工作将文件变动发送到指定的输出中。

    img

    **Harvester(收割机):**负责读取单个文件内容。每个文件会启动一个Harvester,每个Harvester会逐行读取各个文件,并将文件内容发送到制定输出中。Harvester负责打开和关闭文件,意味在Harvester运行的时候,文件描述符处于打开状态,如果文件在收集中被重命名或者被删除,Filebeat会继续读取此文件。所以在Harvester关闭之前,磁盘不会被释放。默认情况filebeat会保持文件打开的状态,直到达到close_inactive(如果此选项开启,filebeat会在指定时间内将不再更新的文件句柄关闭,时间从harvester读取最后一行的时间开始计时。若文件句柄被关闭后,文件发生变化,则会启动一个新的harvester。关闭文件句柄的时间不取决于文件的修改时间,若此参数配置不当,则可能发生日志不实时的情况,由scan_frequency参数决定,默认10s。Harvester使用内部时间戳来记录文件最后被收集的时间。例如:设置5m,则在Harvester读取文件的最后一行之后,开始倒计时5分钟,若5分钟内文件无变化,则关闭文件句柄。默认5m)。

    **Prospector(勘测者):**负责管理Harvester并找到所有读取源。
    filebeat.prospectors: - input_type: log paths: - /apps/logs/*/info.log
    Prospector会找到/apps/logs/*目录下的所有info.log文件,并为每个文件启动一个Harvester。Prospector会检查每个文件,看Harvester是否已经启动,是否需要启动,或者文件是否可以忽略。若Harvester关闭,只有在文件大小发生变化的时候Prospector才会执行检查。只能检测本地的文件。

    Filebeat如何记录文件状态:
    将文件状态记录在文件中(默认在/var/lib/filebeat/registry)。此状态可以记住Harvester收集文件的偏移量。若连接不上输出设备,如ES等,filebeat会记录发送前的最后一行,并再可以连接的时候继续发送。Filebeat在运行的时候,Prospector状态会被记录在内存中。Filebeat重启的时候,利用registry记录的状态来进行重建,用来还原到重启之前的状态。每个Prospector会为每个找到的文件记录一个状态,对于每个文件,Filebeat存储唯一标识符以检测文件是否先前被收集。

    Filebeat如何保证事件至少被输出一次:
    Filebeat之所以能保证事件至少被传递到配置的输出一次,没有数据丢失,是因为filebeat将每个事件的传递状态保存在文件中。在未得到输出方确认时,filebeat会尝试一直发送,直到得到回应。若filebeat在传输过程中被关闭,则不会再关闭之前确认所有时事件。任何在filebeat关闭之前为确认的时间,都会在filebeat重启之后重新发送。这可确保至少发送一次,但有可能会重复。可通过设置shutdown_timeout 参数来设置关闭之前的等待事件回应的时间(默认禁用)。

    Logstash工作原理:
    Logstash事件处理有三个阶段:inputs → filters → outputs。是一个接收,处理,转发日志的工具。支持系统日志,webserver日志,错误日志,应用日志,总之包括所有可以抛出来的日志类型。

    img

    Input:输入数据到logstash。
    一些常用的输入为:
    file:从文件系统的文件中读取,类似于tail -f命令
    syslog:在514端口上监听系统日志消息,并根据RFC3164标准进行解析
    redis:从redis service中读取
    beats:从filebeat中读取

    Filters:数据中间处理,对数据进行操作。
    一些常用的过滤器为:
    grok:解析任意文本数据,Grok 是 Logstash 最重要的插件。它的主要作用就是将文本格式的字符串,转换成为具体的结构化的数据,配合正则表达式使用。内置120多个解析语法。
    官方提供的grok表达式:https://github.com/logstash-plugins/logstash-patterns-core/tree/master/patterns
    grok在线调试:https://grokdebug.herokuapp.com/
    mutate:对字段进行转换。例如对字段进行删除、替换、修改、重命名等。
    drop:丢弃一部分events不进行处理。
    clone:拷贝 event,这个过程中也可以添加或移除字段。
    geoip:添加地理信息(为前台kibana图形化展示使用)

    **Outputs:outputs是logstash处理管道的最末端组件。**一个event可以在处理过程中经过多重输出,但是一旦所有的outputs都执行结束,这个event也就完成生命周期。
    一些常见的outputs为:
    elasticsearch:可以高效的保存数据,并且能够方便和简单的进行查询。
    file:将event数据保存到文件中。
    graphite:将event数据发送到图形化组件中,一个很流行的开源存储图形化展示的组件。

    Codecs:codecs 是基于数据流的过滤器,它可以作为input,output的一部分配置。Codecs可以帮助你轻松的分割发送过来已经被序列化的数据。
    一些常见的codecs:
    json:使用json格式对数据进行编码/解码。
    multiline:将汇多个事件中数据汇总为一个单一的行。比如:java异常信息和堆栈信息。

    来源:博客园
    作者:Mr.Ares
    原文:https://www.cnblogs.com/aresxin/p/8035137.html

    关于 ELK 看官网文档就行了,市面上没有什么好的可以借鉴的书籍。

    Git

    Git 是一款优秀的分布式版本控制平台,代码协作通常用于团队或者多人共同开发一个项目的情况,刚开始接触代码协作可能无法理解,就是说你和你的同事共同开发一个项目的话,你们的代码也要放在一起,你提交的代码对方能够看到,对方提交的代码你也能够看到。不用在说什么我改了代码我发给你,一方面你知道你改过内容可能会有遗漏,有一些人说那记录好改了哪些文件不就行了吗?但是你这样工作量多大?而且假如你和你同事改的是同一个文件呢?还要记住同一个文件中有多少内容是改没改过的嘛?这太麻烦而且低效了,所以 Git 就是用于解决这种情况的,Git 目前是大多数企业的选择,但是仍旧还有一些传统的软件公司使用 SVN,SVN 也是代码协作平台,下面具体介绍一下 Git

    Git 是分布式的,SVN 是集中式的

    Git是分布式的,SVN是集中式的

    这是 Git 和 SVN 最大的区别。若能掌握这个概念,两者区别基本搞懂大半。因为 Git 是分布式的,所以 Git 支持离线工作,在本地可以进行很多操作,包括接下来将要重磅推出的分支功能。而 SVN 必须联网才能正常工作。

    Git 复杂概念多,SVN 简单易上手

    所有同时掌握 Git 和 SVN 的开发者都必须承认,Git 的命令实在太多了,日常工作需要掌握add,commit,status,fetch,push,rebase等,若要熟练掌握,还必须掌握rebasemerge的区别,fetchpull的区别等,除此之外,还有cherry-picksubmodulestash等功能,仅是这些名词听着都很绕。

    在易用性这方面,SVN 会好得多,简单易上手,对新手很友好。但是从另外一方面看,Git 命令多意味着功能多,若我们能掌握大部分 Git 的功能,体会到其中的奥妙,会发现再也回不去 SVN 的时代了。

    Git 分支廉价,SVN 分支昂贵

    在版本管理里,分支是很常使用的功能。在发布版本前,需要发布分支,进行大需求开发,需要 feature 分支,大团队还会有开发分支,稳定分支等。在大团队开发过程中,常常存在创建分支,切换分支的需求。

    Git 分支是指针指向某次提交,而 SVN 分支是拷贝的目录。这个特性使 Git 的分支切换非常迅速,且创建成本非常低。

    而且 Git 有本地分支,SVN 无本地分支。在实际开发过程中,经常会遇到有些代码没写完,但是需紧急处理其他问题,若我们使用 Git,便可以创建本地分支存储没写完的代码,待问题处理完后,再回到本地分支继续完成代码。

    学习 Git 的方式有很多种,但是最主要的还是你动手实践,不管是看书也好还是根据教程进行实操,你都需要实践一遍,那么 Git 的使用你就差不多了。

    Git 也有一些书籍,我推荐给你。

    Pro Git

    首推的肯定是大部分程序员入门的《Pro Git》,该书由 GitHub 的两名早期员工 Scott Chacon 和 Ben Straub 编写而成。这本书可以说是最早期,也是现今知名度最高的 Git 入门教程了。
    通过该教程你可以快速了解到 Git 与 GitHub 的基础使用,内容覆盖面广,一些知识点也都讲得较为通透,所以也有不少人拿该这本书当 Git 的使用手册,遇到不懂的问题还会跑回来查阅。
    同时该书还配套了 视频教程 供读者观看。

    img

    或者 Pro Git 中文版 Pro Git(中文版)

    Git 版本控制管理

    img

    O’Reilly 的一贯风格,清晰明了,特点是讲授了 GIT 的内部原理,而不是简单列举命令操作。使用很多例子和示意图,一目了然。

    Git 的资料有很多,这里给大家推荐几个口碑非常好的

    廖雪峰的 Git 教程可以说是做到简单清晰明了了,可以说是最好的 Git 入门指南

    Git教程

    Github Docs 的官方文档也是学习 Git 的好方式

    快速入门 - GitHub Docs
    Git 工作流程(阮一峰):http://www.ruanyifeng.com/blog/2015/12/git-workflow.html
    菜鸟教程-Git简明教程:http://www.runoob.com/manual/git-guide/
    Git Book:https://git-scm.com/book/zh/v2

    上面这些内容,如果你能够真正掌握,我觉得你已经可以吊打 95% 以上的程序员了,上面这些内容你真正掌握可能会花 5 - 10 年的时间,不同层次的程序员掌握框架的层次不同,比如对于 Kafka 这个消息中间件来说,初级程序员可能知道 Kafka 是用来干什么的,知道 Kafka 有哪些组件,会安装搭建就可以了,对于中级程序员来说,你可能需要懂一些 Kafka 的配置和参数,知道 Kafka 的架构,Kafka 和其他消息中间件的区别等。如果你是高级程序员,可能要求你会监控 Kafka,Kafka 调优,有没有研究过 Kafka 的源码,某个细节点的内部实现原理等。如果你认真研究某个领域五年以上,那么你可以称之为领域内的专家了,我说的是研究,而不是你知道了某个框架五年以上就是专家了,这个概念是完全不一样的,研究是真正去一行一行看其内部实现源码,了解它的设计思想和痛点。

    上面的这些内容可以说是针对非科班的程序员的,因为非科班程序员和科班程序员的侧重点不同,非科班程序员侧重点就是能上手干活,解决问题,科班程序员侧重点在于思路,算法等,因为他们在大学期间会仔细研究,认真打磨计算机基础。这也不是说非科班程序员不用学习计算机基础了,你在能上手干活的同时也要打牢基础,这样你才能够和科班的去竞争,去内卷,去弥补差距。

    计算机基础是内功,内功在任何时期和阶段都是需要修炼的。

    计算机基础

    计算机基础都包括哪些呢?

    计算机组成原理、操作系统、计算机网络、数据结构与算法。

    计算机组成原理

    先说计算机组成原理,这部分内容主要涉及

    • 计算机系统概述
    • 数据与运算
    • CPU 概述
    • 存储子系统概述
    • 总线和 IO 概述

    这些内容可以在 MOOC 大学上找到

    计算机组成原理_电子科技大学_中国大学MOOC(慕课)

    大家也可以看一下这本书

    img

    虽然国内教授/专家写的书不及国外,但是在国内来说已经算是不错的了,而且这本书还是颇为具有指导意义的。

    还有一本

    img

    这本书看的人比较少,但是不失为一本好书,计算机组成原理,了解汇编层的代码运行。计算机是如何执行二进制命令的。本书基于 arm 指令集架构。

    操作系统

    关于操作系统,我写了一篇如何学习的文章

    如何学好操作系统原理这门课?

    计算机网络

    关于计算机网络,我也写了一篇关于如何学习的文章,你可以参考

    计算机网络该怎么学?

    数据结构和算法

    算法书籍推荐:市面上有很多关于算法的书籍,最近非常火的《labuladong 的算法小抄》,通俗易懂的《小灰的算法之旅》等等,不过我这里只说两本最经典的算法书:《算法导论》和《算法第四版》

    关于算法如何学习,可以参考下这个回答

    如何系统地学习算法?

    关于学习的意见和建议,可以参考

    程序员cxuan:编程从入门到精通,2021小白版

    这篇回答会持续完善下,欢迎读者追更,点赞喜欢关注就是对我的爱。

    这是第一版内容,部分技术栈和知识点整理的不是很全面,这个我承认,不过如果这篇文章能够对你产生帮助,就是他的价值。

    我把这篇文章汇总成为了 PDF 版本,链接如下

    获取 PDF 链接 密码: atsg

    展开全文
  • java数据结构与算法之顺序表与链表深入分析

    万次阅读 多人点赞 2016-11-05 16:24:30
    接下来将以下几点出发分析线性表的设计与实现。 线性表抽象数据类型概述 线性表的顺序存储设计与实现顺序表 1 顺序存储结构的设计原理概要 2 顺序存储结构的实现分析 3 顺序存储结构的效率分析 线性表的链式存

    转载请注明出处(万分感谢!):
    http://blog.csdn.net/javazejian/article/details/52953190
    出自【zejian的博客】

    关联文章:

    java数据结构与算法之顺序表与链表设计与实现分析
    java数据结构与算法之双链表设计与实现
    java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedList(带Iterator迭代器与fast-fail机制)
    java数据结构与算法之栈(Stack)设计与实现
    java数据结构与算法之队列(Queue)设计与实现
    java数据结构与算法之递归思维(让我们更通俗地理解递归)
    java数据结构与算法之树基本概念及二叉树(BinaryTree)的设计与实现
    java数据结构与算法之平衡二叉查找树(AVL树)的设计与实现

      数据结构与算法这门学科虽然在大学期间就已学习过了,但是到现在确实也忘了不少,因此最近又重新看了本书-《数据结构与算法分析》加上之前看的《java数据结构》也算是对数据结构的进一步深入学习了,于是也就打算写一系列的数据结构的博文以便加深理解,这些博文涵盖了自己对数据结构与算法的理解也包含了这类书籍的基础内容,所以博文中会包含书中的一些概念的引用段落,看到时也不必惊讶,本篇是开篇,主要涵盖顺序表与链表的知识点,关于顺序表与链表将会分两篇博文记录,而本篇将从以下几点出发分析线性表的设计与实现。

    1.线性表抽象数据类型概述

      首先来说明一下什么是抽象数据类型,我们都知道java在默认情况下,所有的基本数据类型(int,float,boolean等)都支持基本运算,如加减法,这是因为系统已帮我们实现了这些基本数据类型的的基本运算。而对于自定义的数据类型(如类)也需要定义相应的运算,但在实际使用这些自定义的数据类型的运算时需要自己实现相关的运算,也就是说用户自定义的数据类型的运算需要我们自己利用系统提供的基本运算来定义和实现。这些自定义了数据结构(如自定义类)和包含相关运算组合实现的数据类型就称其为抽象数据类型(ADT,Abstract Data Type),因此一个ADT会包含数据声明和运算声明。常用的ADT包含链表、栈、队列、优先队列、二叉树、散列表、图等,所以接下来我们要分析的顺序表和链表也属于ADT范畴。下面引用自java数据结构一书对线性表的定义:

      线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,an-1组成的有限的序列,在数学中记作(a0,a1,…,an-1),其中ai的数据类型可以是基本数据类型(int,float等)、字符或类。n代表线性表的元素个数,也称其为长度(Length)。若n=0,则为空表;若n > 0,则ai(0 < i < n-1)有且仅有一个前驱(Predecessor)元素ai-1和一个后继(Successor)元素ai+1,a0没有前驱元素,ai没有后继元素。

    以上便是对线性表抽象数据类型概述,下面我们开始分别针对顺序表和链表进行深入分析。

    2.线性表的顺序存储设计与实现(顺序表)

    2.1 顺序存储结构的设计原理概要

      顺序存储结构底层是利用数组来实现的,而数组可以存储具有相同数据类型的元素集合,如int,float或者自定义类型等,当我们创建一个数组时,计算机操作系统会为该数组分配一块连续的内存块,这也就意味着数组中的每个存储单元的地址都是连续的,因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址,就如下图所示:
    这里写图片描述
      通过上图可以发现为了访问一个数组元素,该元素的内存地址需要计算其距离数组基地址的偏移量,即用一个乘法计算偏移量然后加上基地址,就可以获得数组中某个元素的内存地址。其中c代表的是元素数据类型的存储空间大小,而序号则为数组的下标索引。整个过程需要一次乘法和一次加法运算,因为这两个操作的执行时间是常数时间,所以我们可以认为数组访问操作能再常数时间内完成,即时间复杂度为O(1),这种存取任何一个元素的时间复杂度为O(1)的数据结构称之为随机存取结构。而顺序表的存储原理正如上图所示,因此顺序表的定义如下(引用):

      线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a0到an-1的数据元素(a0,a1,…,an-1),将ai(0< i <> n-1)存放在数组的第i个元素,使得ai与其前驱ai-1及后继ai+1的存储位置相邻,因此数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。

    2.2 顺序存储结构的实现分析

      接着我们来分析一下顺序表的实现,先声明一个顺序表接口类ISeqList<T>,然后实现该接口并实现接口方法的代码,ISeqList接口代码如下:

    package com.zejian.structures.LinkedList;
    
    /**
     * Created by zejian on 2016/10/30.
     * 顺序表顶级接口
     */
    public interface ISeqList<T> {
    
        /**
         * 判断链表是否为空
         * @return
         */
        boolean isEmpty();
    
        /**
         * 链表长度
         * @return
         */
        int length();
    
        /**
         * 获取元素
         * @param index
         * @return
         */
        T get(int index);
    
        /**
         * 设置某个元素的值
         * @param index
         * @param data
         * @return
         */
        T set(int index, T data);
    
        /**
         * 根据index添加元素
         * @param index
         * @param data
         * @return
         */
        boolean add(int index, T data);
    
        /**
         * 添加元素
         * @param data
         * @return
         */
        boolean add(T data);
    
        /**
         * 根据index移除元素
         * @param index
         * @return
         */
        T remove(int index);
    
        /**
         * 根据data移除元素
         * @param data
         * @return
         */
        boolean remove(T data);
    
        /**
         * 根据data移除元素
         * @param data
         * @return
         */
        boolean removeAll(T data);
    
        /**
         * 清空链表
         */
        void clear();
    
        /**
         * 是否包含data元素
         * @param data
         * @return
         */
        boolean contains(T data);
    
        /**
         * 根据值查询下标
         * @param data
         * @return
         */
        int indexOf(T data);
    
        /**
         * 根据data值查询最后一个出现在顺序表中的下标
         * @param data
         * @return
         */
        int lastIndexOf(T data);
    
        /**
         * 输出格式
         * @return
         */
        String toString();
        }
    }

      代码中声明了一个Object数组,初始化数组大小默认为64,存储的元素类型为泛型T,length则为顺序表的长度,部分方法实现比较简单,这里不过多分析,我们主要分析get(int index)、set(int index, T data)、add(int index, T data)、remove(int index)、removeAll(T data)、indexof(T data)等方法的实现。

    • get(int index) 实现分析
      从顺序表中获取值是一种相当简单的操作并且效率很高,这是由于顺序表内部采用了数组作为存储数据的容器。因此只要根据传递的索引值,然后直接获取数组中相对应下标的值即可,代码实现如下:

      public T get(int index){
         if (index>=0 && index<this.length)
             return (T) this.table[index];         
         return null;
      }
    • set(int index, T data) 实现分析
      在顺序表中替换值也是非常高效和简单的,只要根据传递的索引值index找到需要替换的元素,然后把对应元素值替换成传递的data值即可,代码如下:

      public T set(int index, T data){
         if (index>=0 && index<this.length&& data!=null)
           {
               T old = (T)this.table[index];
               this.table[index] = data;
               return old;
           }
           return null;
       }
    • add(int index, T data)实现分析
      在顺序表中执行插入操作时,如果其内部数组的容量尚未达到最大值时,可以归结为两种情况,一种是在头部插入或者中间插入,这种情况下需要移动数组中的数据元素,效率较低,另一种是在尾部插入,无需移动数组中的元素,效率高。但是当顺序表内部数组的容量已达到最大值无法插入时,则需要申请另一个更大容量的数组并复制全部数组元素到新的数组,这样的时间和空间开销是比较大的,也就导致了效率更为糟糕了。因此在插入频繁的场景下,顺序表的插入操作并不是理想的选择。下面是顺序表在数组容量充足下头部或中间插入操作示意图(尾部插入比较简单就不演示了):
      这里写图片描述
      顺序表在数组容量不充足的情况下头部或中间插入操作示意图:

      理解了以上几种顺序表的插入操作后,我们通过代码来实现这个插入操作如下,注释很清晰就过多分析了:

      /**
         * 根据index插入元素
         * @param index 插入位置的下标,0作为起始值
         * @param data 插入的数据
         * @return
         */
        public boolean add(int index, T data){                                        
           if (data==null)
               return false;
      
           //插入下标的容错判断,插入在最前面
           if (index<0)                             
               index=0;
      
           //插入下标的容错判断,插入在最后面
           if (index>this.length)
               index = this.length;
      
           //判断内部数组是否已满
           if (this.length==table.length)              
           {
               //把原数组赋值给临时数组
               Object[] temp = this.table;
      
               //对原来的数组进行成倍拓容,并把原数组的元素复制到新数组
               this.table = new Object[temp.length*2];   
      
               //先把原数组下标从0到index-1(即插入位置的前一个位置)复制到新数组
               for (int i=0; i<index; i++) {
                   this.table[i] = temp[i];
               }
           }
      
           //从原数组的最后一个元素开始直到index位置,都往后一个位置
           // 最终腾出来的位置就是新插入元素的位置了
           for (int j=this.length-1; j>=index; j--) {
               this.table[j + 1] = this.table[j];
           }
           //插入新值
           this.table[index] = data;
           //长度加一
           this.length++;
           //插入成功
           return true;
        }
    • remove(int index) 实现分析
      顺序表的删除操作和前的插入操作情况是类似的,如果是在中间或者头部删除顺序表中的元素,那么在删除位置之后的元素都必须依次往前移动,效率较低,如果是在顺序表的尾部直接删除的话,则无需移动元素,此情况下删除效率高。如下图所示在顺序表中删除元素ai时,ai之后的元素都依次往前移动:
      这里写图片描述
      删除操作的代码实现如下:

      /**
        * 根据index删除元素
        * @param index 需要删除元素的下标
        * @return
        */
       public T remove(int index)
       {
           if (this.length!=0 && index>=0 && index<this.length)
           {
               //记录删除元素的值并返回
               T old = (T)this.table[index];
      
               //从被删除的元素位置开,其后的元素都依次往前移动
               for (int j=index; j<this.length-1; j++) {
                   this.table[j] = this.table[j + 1];
               }
               //设置数组元素对象为空
               this.table[this.length-1]=null;
               //顺序表长度减1
               this.length--;
               return old;                         
           }
           return null;
       }
    • removeAll(T data) 实现分析
      在顺序表中根据数据data找到需要删除的数据元素和前面分析的根据index删除顺序表中的数据元素是一样的道理,因此我们只要通过比较找到与data相等的数据元素并获取其下标,然后调用前面实现的remove(int index)方法来移除即可。代码实现如下:

      @Override
      public boolean removeAll(T data) {
          boolean done=false;
          if (this.length!=0 && data!=null)
          {
              int i=0;
              while (i<this.length)
                  //找出数据相同的选项
                  if (data.equals(this.table[i]))
                  {
                      this.remove(i);//根据下标删除
                      done = true;
                  }
                  else
                      i++;//继续查找
          }
          return done;
      }
    • indexOf(T data) 实现分析
      要根据data在顺序表中查找第一个出现的数据元素的下标,只需要通过对比数据项是否相等,相等则返回下标,不相等则返回-1,indexOf和lastIndexOf方法实现如下:

      /**
       * 根据数据查询下标
       * @param data
       * @return
       */
      @Override
      public int indexOf(T data)
      {
          if (data!=null)
              for (int i=0; i<this.length; i++) {
                  //相当则返回下标
                  if (this.table[i].equals(data))
                      return i;
              }
          return -1;
      }
      
      /**
       * 根据data查询最后一个出现在顺序表中的下标
       * @param data
       * @return
       */
      @Override
      public int lastIndexOf(T data)
      {
          if (data!=null)
              for (int i=this.length-1; i>=0; i--)
                  if (data.equals(this.table[i]))
                      return i;
          return -1;
      }

      以上便是顺序表的主要的操作方法,当然顺序表中还可以实现其他操作,如在初始化构造函数时传入数组来整体初始化顺序表,比较两个信息表是否相等、是否包含某个数据等。这里贴一下传入数据构建顺序表构造方法实现,其他实现代码我们这里就不贴了,稍后实现源码都会上传gitHub提供给大家:

    /**
    * 传入一个数组初始化顺序表
    * @param array
    */
    public SeqList(T[] array){
      if (array==null){
          throw new NullPointerException("array can\'t be empty!");
      }
      //创建对应容量的数组
      this.table = new Object[array.length];
    //复制元素
      for (int i=0;i<array.length;i++){
          this.table[i]=array[i];
      }
    
      this.length=array.length;
    }

    2.3 顺序存储结构的效率分析

      通过上述的分析,我们对顺序表的实现已有了比较清晰的认识,接下来看一下顺序表的执行效率问题,主要针对获取、插入、修改、删除等主要操作。前面分析过,由于顺序表内部采用了数组作为存储容器,而数组又是随机存取结构的容器,也就是说在创建数组时操作系统给数组分配的是一块连续的内存空间,数组中每个存储单元的地址都是连续的,所以在知道数组基地址后可以通过一个简单的乘法和加法运算即可计算出其他存储单元的内存地址(实际上计算机内部也就是这么做的),这两个运算的执行时间是常数时间,因此可以认为数组的访问操作能在常数时间内完成,即顺序表的访问操作(获取和修改元素值)的时间复杂为O(1)。
      对于在顺序表中插入或者删除元素,从效率上则显得不太理想了,由于插入或者删除操作是基于位置的,需要移动数组中的其他元素,所以顺序表的插入或删除操作,算法所花费的时间主要是用于移动元素,如在顺序表头部插入或删除时,效率就显得相当糟糕了。若在最前插入或删除,则需要移动n(这里假设长度为n)个元素;若在最后插入或删除,则需要移动的元素为0。这里我们假设插入或删除值为第i(0<i<=n)个元素,其概率为pi,则插入或删除一个元素的平均移动次数求和为:

    p1(n1)+p2(n2)+...+pi(ni)+...+pn11+pn0=i=1n(pi(ni))

    如果在各个位置插入元素的概率相同即 pi=1n+1 (n+1个插入位置任意选择一个的概率)则有:

    i=1n(pi(ni))=1n+1i=1n(ni)=1n+1n(n+1)2=n2=O(n)

      也就是说,在等概率的情况下,插入或者删除一个顺序表的元素平均需要移动顺序表元素总量的一半,其时间复杂度是O(n)。当然如果在插入时,内部数组容量不足时,也会造成其他开销,如复制元素的时间开销和新建数组的空间开销。
      因此总得来说顺序表有以下优缺点:

    • 优点

      • 使用数组作为内部容器简单且易用

      • 在访问元素方面效率高

      • 数组具有内存空间局部性的特点,由于本身定义为连续的内存块,所以任何元素与其相邻的元素在物理地址上也是相邻的。

    • 缺点

      • 内部数组大小是静态的,在使用前必须指定大小,如果遇到容量不足时,需动态拓展内部数组的大小,会造成额外的时间和空间开销

      • 在内部创建数组时提供的是一块连续的空间块,当规模较大时可能会无法分配数组所需要的内存空间

      • 顺序表的插入和删除是基于位置的操作,如果需要在数组中的指定位置插入或者删除元素,可能需要移动内部数组中的其他元素,这样会造成较大的时间开销,时间复杂度为O(n)

    3.线性表的链式存储设计与实现(链表)

    3.1 链表的链式存储结构设计原理概要

      通过前面对线性顺序表的分析,我们知道当创建顺序表时必须分配一块连续的内存存储空间,而当顺序表内部数组的容量不足时,则必须创建一个新的数组,然后把原数组的的元素复制到新的数组中,这将浪费大量的时间。而在插入或删除元素时,可能需要移动数组中的元素,这也将消耗一定的时间。鉴于这种种原因,于是链表就出场了,链表在初始化时仅需要分配一个元素的存储空间,并且插入和删除新的元素也相当便捷,同时链表在内存分配上可以是不连续的内存,也不需要做任何内存复制和重新分配的操作,由此看来顺序表的缺点在链表中都变成了优势,实际上也是如此,当然链表也有缺点,主要是在访问单个元素的时间开销上,这个问题留着后面分析,我们先通过一张图来初步认识一下链表的存储结构,如下:

      从图可以看出线性链表的存储结构是用若干个地址分散的存储单元存放数据元素的,逻辑上相邻的数据元素在物理位置上不一定相邻,因此每个存储单元中都会有一个地址指向域,这个地址指向域指明其后继元素的位置。在链表中存储数据的单元称为结点(Node),从图中可以看出一个结点至少包含了数据域和地址域,其中数据域用于存储数据,而地址域用于存储前驱或后继元素的地址。前面我们说过链表的插入和删除都相当便捷,这是由于链表中的结点的存储空间是在插入或者删除过程中动态申请和释放的,不需要预先给单链表分配存储空间的,从而避免了顺序表因存储空间不足需要扩充空间和复制元素的过程,提高了运行效率和存储空间的利用率。

    3.2 单链表的储结构实现分析

    到此我们已初步了解了链表的概念和存储结构,接下来,开始分析链表的实现,这里先从单链表入手。同样地,先来定义一个顶级的链表接口:ILinkedList和存储数据的结点类Node,该类是代表一个最基本的存储单元,Node代码如下:

    /**
     * Created by zejian on 2016/10/21.
     * 单向链表节点
     */
    public class Node<T> {
        public T data;//数据域
        public Node<T> next;//地址域
    
        public Node(T data){
            this.data=data;
        }
    
        public Node(T data,Node<T> next){
            this.data=data;
            this.next=next;
        }
    }

    接着顶级的链表接口ILinkedList,该接口声明了我们所有需要实现的方法。

    /**
     * Created by zejian on 2016/10/21.
     * 链表顶级接口
     */
    public interface ILinkedList<T> {
        /**
         * 判断链表是否为空
         * @return
         */
        boolean isEmpty();
    
        /**
         * 链表长度
         * @return
         */
        int length();
    
        /**
         * 获取元素
         * @param index
         * @return
         */
        T get(int index);
    
        /**
         * 设置某个结点的的值
         * @param index
         * @param data
         * @return
         */
        T set(int index, T data);
    
        /**
         * 根据index添加结点
         * @param index
         * @param data
         * @return
         */
        boolean add(int index, T data);
    
        /**
         * 添加结点
         * @param data
         * @return
         */
        boolean add(T data);
    
        /**
         * 根据index移除结点
         * @param index
         * @return
         */
        T remove(int index);
    
        /**
         * 根据data移除结点
         * @param data
         * @return
         */
        boolean removeAll(T data);
    
        /**
         * 清空链表
         */
        void clear();
    
        /**
         * 是否包含data结点
         * @param data
         * @return
         */
        boolean contains(T data);
    
          /**
         * 输出格式
         * @return
         */
        String toString();
    }

    创建一个单链表SingleILinkedList并实现ILinkedList接口,覆盖其所有方法,声明一个单链表的头结点head,代表链表的开始位置,如下:

    public class SingleILinkedList<T> implements ILinkedList<T> {
       protected Node<T> headNode; //带数据头结点
    
       public SingleILinkedList(Node<T> head) {
           this.headNode = head;
       }
       //其他代码先省略
       .....
    }
    • boolean isEmpty()实现分析
      需要判断链表是否为空的依据是头结点head是否为null,当head=null时链表即为空链表,因此我们只需判断头结点是否为空即可,isEmpty方法实现如下:

      /**
       * 判断链表是否为空
       * @return
       */
      @Override
      public boolean isEmpty() {
          return this.head==null;
      }
    • int length()实现分析
      由于单链表的结点数就是其长度,因此我们只要遍历整个链表并获取结点的数量即可获取到链表的长度。遍历链表需要从头结点HeadNode开始,为了不改变头结点的存储单元,声明变量p指向当前头结点和局部变量length,然后p从头结点开始访问,沿着next地址链到达后继结点,逐个访问,直到最后一个结点,每经过一个结点length就加一,最后length的大小就是链表的大小。实现代码如下:

      @Override
      public int length() {
         int length=0;//标记长度的变量
         Node<T> p=head;//变量p指向头结点
         while (p!=null){
             length++;
             p=p.next;//后继结点赋值给p,继续访问
         }
         return length;
      }
    • T get(int index)实现分析
      在单链表中获取某个元素的值是一种比较费时间的操作,需要从头结点开始遍历直至传入值index指向的位置,其中需要注意的是index是从0开始计算,也就是说传递的index=3时,查找的是链表中第4个位置的值。其查询获取值的过程如下图所示:
      这里写图片描述
      代码实现如下:

      /**
       * 根据index索引获取值
       * @param index 下标值起始值为0
       * @return
       */
      @Override
      public T get(int index) {
      
          if(this.head!=null&&index>=0){
              int count=0;
              Node<T> p=this.head;
              //找到对应索引的结点
              while (p!=null&&count<index){
                  p=p.next;
                  count++;
              }
      
              if(p!=null){
                  return p.data;
              }
          }
          return null;
      }

      通过上图和代码,我们就可以很容易理解链表中取值操作的整个过程了。

    • T set(int index, T data)实现分析
      根据传递的index查找某个值并替换其值为data,其实现过程的原理跟get(int index)是基本一样的,先找到对应值所在的位置然后删除即可,不清晰可以看看前面的get方法的图解,这里直接给出代码实现:

      /**
       * 根据索引替换对应结点的data
       * @param index 下标从0开始
       * @param data
       * @return 返回旧值
       */
      @Override
      public T set(int index, T data) {
      
          if(this.head!=null&&index>=0&&data!=null){
              Node<T> pre=this.head;
              int count=0;
              //查找需要替换的结点
              while (pre!=null&&count<index){
                  pre=pre.next;
                  count++;
              }
              //不为空直接替换
              if (pre!=null){
                  T oldData=pre.data;
                  pre.data=data;//设置新值
                  return oldData;
              }
      
          }
          return null;
      }
    • add(int index, T data)实现分析
      单链表的插入操作分四种情况:
      a.空表插入一个新结点,插语句如下:

      head=new Node<T>(x,null);

      这里写图片描述

      b.在链表的表头插入一个新结点(即链表的开始处),此时表头head!=null,因此head后继指针next应该指向新插入结点p,而p的后继指针应该指向head原来的结点,代码如下:

      //创建新结点
      Node<T> p =new Node<T>(x,null);
      //p的后继指针指向head原来的结点
      p.next=head;
      //更新head
      head=p;

      以上代码可以合并为如下代码:

      //创建新结点,其后继为head原来的结点,head的新指向为新结点
      head=new Node<T>(x,head);

      执行过程如下图:

      这里写图片描述

      c.在链表的中间插入一个新结点p,需要先找到给定插入位置的前一个结点,假设该结点为front,然后改变front的后继指向为新结点p,同时更新新结点p的后继指向为front原来的后继结点,即front.next,其执行过程如下图所示:
      这里写图片描述
      代码实现如下:

      //新结点p
      Node<T> p =new Node<T>(x,null);
      //更新p的后继指向
      p.next=front.next;
      //更新front的后继指向
      front.next=p;

      以上三句代码合并为一句简洁代码:

      front.next=new Node<T>(x,front.next);

      d.在链表的表尾插入一个新结点(链表的结尾)在尾部插入时,同样需要查找到插入结点P的前一个位置的结点front(假设为front),该结点front为尾部结点,更改尾部结点的next指针指向新结点P,新结点P的后继指针设置为null,执行过程如下:

      其代码语句如下:

      //front的next指针指向新结点,新结点的next指针设置为null
      front.next=new Node<T>(x,null);

        到此我们也就可以发现单向链表中的中间插入和尾部插入其实可以合并为一种情况。最后这里给出该方法整体代码实现,从代码实现上来看中间插入和尾部插入确实也视为同种情况处理了。

        /**
           * 根据下标添加结点
           * 1.头部插入
           * 2.中间插入
           * 3.末尾插入
           * @param index 下标值从0开始
           * @param data
           * @return
           */
          @Override
          public boolean add(int index, T data) {
      
              if (data==null){
                  return false;
              }
              //在头部插入
              if (this.head==null||index<=1){
                  this.head = new Node<T>(data, this.head);
              }else {
                  //在尾部或中间插入
                  int count=0;
                  Node<T> front=this.head;
                  //找到要插入结点位置的前一个结点
                  while (front.next!=null&&count<index-1){
                      front=front.next;
                      count++;
                  }
                  //尾部添加和中间插入属于同种情况,毕竟当front为尾部结点时front.next=null
                  front.next=new Node<T>(data,front.next);
              }
              return true;
          }
    • T remove(int index) 删除结点实现分析
      在单向链表中,根据传递index位置删除结点的操作分3种情况,并且删除后返回被删除结点的数据:
      a.删除链表头部(第一个)结点,此时需要删除头部head指向的结点,并更新head的结点指向,执行图示如下:
      这里写图片描述
      代码实现如下:

      //头部删除,更新head指向
      head=head.next;

      b.删除链表的中间结点,与添加是同样的道理,需要先找到要删除结点r(假设要删除的结点为r)位置的前一个结点front(假设为front),然后把front.next指向r.next即要删除结点的下一个结点,执行过程如下:
      这里写图片描述
      代码语句如下:

      Node<T> r =front.next;
      //更新结点指针指向
      front.next=r.next;
      r=null;

      c.删除链表的最后一个结点,通过遍历操作找到最后一个结点r的前一个结点front,并把front.next设置为null,即可。执行过程如下:

      代码如下:

      front.next=null;
      r=null;

      我们把中间删除和尾部删除合并为如下代码:

      Node<T> r =front.next;
      //如果不是尾部结点,更新结点front指针指向
      if(r=!null){
          front.next=r.next;
          r=null;
      }

      该方法整体代码实现如下:

      /**
           * 根据索引删除结点
           * @param index
           * @return
           */
          @Override
          public T remove(int index) {
      
              T old=null;
      
              if (this.head!=null&&index>=0){
      
                  //直接删除的是头结点
                  if(index==0){
                      old=this.head.data;
                      this.head=this.head.next;
                  }else {
      
                      Node<T> front = this.head;
                      int count = 0;
                      //查找需要删除结点的前一个结点
                      while (front.next != null && count < index - 1) {
                          front = front.next;
                          count++;
                      }
      
                      //获取到要删除的结点
                      Node<T> r = front.next;
      
                      if ( r!= null) {
                          //获取旧值
                          old =r.data;
                          //更改指针指向
                          front.next=r.next;
                          //释放
                          r=null;
                      }
                  }
              }
              return old;
          }

      当然还有如下更简洁的代码写法:

      @Override
        public T remove(int index) {
      
            T old=null;
      
            if (this.head!=null&&index>=0){
      
                //直接删除的是头结点
                if(index==0){
                    old=this.head.data;
                    this.head=this.head.next;
                }else {
      
                    Node<T> front = this.head;
                    int count = 0;
                    //查找需要删除结点的前一个结点
                    while (front.next != null && count < index - 1) {
                        front = front.next;
                        count++;
                    }
      
                    if ( front.next!= null) {
                        //获取旧值
                        old =front.next.data;
                        //更改指针指向
                        front.next=front.next.next;
                    }
                }
            }
            return old;
        }
    • void clear() 实现分析
      清空链表是一件非常简单的事,只需让head=null即可;代码如下:

      /**
       * 清空链表
       */
      @Override
      public void clear() {
          this.head=null;
      }

      ok~,到此单链表主要的添加、删除、获取值、设置替换值、获取长度等方法已分析完毕,其他未分析的方法都比较简单这里就不一一分析了,单链表的整体代码最后会分享到github给大家。

    3.3 带头结点的单链表以及循环单链表的实现

    带头结点的单链表

    前面分析的单链表是不带特殊头结点的,所谓的特殊头结点就是一个没有值的结点即:

    //没有带值的头结点
    Node<T> head= new Node<T>(null,null);

    此时空链表的情况如下:

    那么多了头结点的单向链表有什么好处呢?通过对没有带头结点的单链表的分析,我们可以知道,在链表插入和删除时都需要区分操作位,比如插入操作就分头部插入和中间或尾部插入两种情况(中间或尾部插入视为一种情况对待即可),如果现在有不带数据的头结点,那么对于单链表的插入和删除不再区分操作的位置,也就是说头部、中间、尾部插入都可以视为一种情况处理了,这是因为此时头部插入和头部删除无需改变head的指向了,头部插入如下所示:

    接着再看看在头部删除的情况:

    带头结点遍历从head.next开始:

    因此无论是插入还是删除,在有了不带数据的头结点后,在插入或者删除时都无需区分操作位了,好~,到此我们来小结一下带头结点的单链表特点:

    • a.空单链表只有一个结点,head.next=null。
    • b.遍历的起点为p=head.next。
    • c.头部插入和头部删除无需改变head的指向。

      同时为了使链表在尾部插入时达到更加高效,我们可在链表内增加一个尾部指向的结点rear,如果我们是在尾部添加结点,那么此时只要通过尾部结点rear进行直接操作即可,无需从表头遍历到表尾,带尾部结点的单链表如下所示:

    从尾部直接插入的代码实现如下:

    /**
     * 尾部插入
     * @param data
     * @return
     */
    @Override
    public boolean add(T data) {
        if (data==null)
            throw new NullPointerException("data can\'t be empty!");
    
        this.rear.next = new Node<T>(data);
        //更新末尾指针的指向
        this.rear = this.rear.next;
        return true;
    }


      从代码和图示看来确实只要获取当前的尾部指向的结点rear并把新结点赋值给rear.next,最后更新rear结点的值即可,完全不用遍历操作,但是如果是根据index来插入的还,遍历部分结点还是少不了的,下面看看根据index插入的代码实现,由于有了头结点,头部、中间、尾部插入无需区分操作位都视为一种情况处理。

    /**
     * 根据下标添加结点
     * 1.头部插入
     * 2.中间插入
     * 3.末尾插入
     * @param index 该值从0开始,如传4就代表插入在第5个位置
     * @param data
     * @return
     */
    @Override
    public boolean add(int index, T data) {
    
        if (data==null){
            throw new NullPointerException("data can\'t be empty!");
        }
    
        if(index<0)
            throw new NullPointerException("index can\'t less than 0");
    
        //无需区分位置操作,中间/头部/尾部插入
        int j=0;
        Node<T> pre=this.headNode;
        //查找到插入位置即index的前一个结点
        while (pre.next!=null&&j<index){
            pre=pre.next;
            j++;
        }
    
        //将新插入的结点的后继指针指向pre.next
        Node<T> q=new Node<T>(data,pre.next);
        //更改指针指向
        pre.next=q;
    
        //如果是尾部指针
        if (pre==this.rear)
            this.rear=q;
    
        return true;
    }

      最后在看看删除的代码实现,由于删除和插入的逻辑和之前不带头结点的单链表分析过的原理的是一样的,因此我们这里不重复了,主要注意遍历的起始结点变化就行。

     /**
         * 根据索引删除结点
         * @param index
         * @return
         */
        @Override
        public T remove(int index) {
            T old=null;
    
            //无需区分头删除或中间删除或尾部删除的情况
            if (index>=0){
                Node<T> pre = this.headNode;
                int j = 0;
                //查找需要删除位置的前一个结点
                while (pre.next != null && j < index) {
                    pre = pre.next;
                    j++;
                }
    
                //获取到要删除的结点
                Node<T> r = pre.next;
    
                if (r != null) {
                    //获取旧值
                    old =r.data;
                    //如果恰好是尾部结点,则更新rear的指向
                    if (r==this.rear){
                        this.rear=pre;
                    }
                    //更改指针指向
                    pre.next=r.next;
                }
    
            }
            return old;
        }

    ok~,关于带头结点的单向链表就分析到这,这里贴出实现源码,同样地,稍后在github上也会提供:

    package com.zejian.structures.LinkedList.singleLinked;
    
    import com.zejian.structures.LinkedList.ILinkedList;
    
    /**
    * Created by zejian on 2016/10/22.
    * 带头结点并含有尾指针的链表
    */
    public class HeadSingleILinkedList<T> implements ILinkedList<T> {
    
       protected Node<T> headNode; //不带数据头结点
       protected Node<T> rear;//指向尾部的指针
    
       public HeadSingleILinkedList() {
           //初始化头结点与尾指针
           this.headNode =rear= new Node<>(null);
       }
    
       public HeadSingleILinkedList(Node<T> head) {
           this();
           this.headNode.next =rear.next= head;
           rear=rear.next;//更新末尾指针指向
       }
    
       /**
        * 传入一个数组,转换成链表
        * @param array
        */
       public HeadSingleILinkedList(T[] array)
       {
           this();
           if (array!=null && array.length>0)
           {
               this.headNode.next = new Node<T>(array[0]);
               rear=this.headNode.next;
               int i=1;
               while (i<array.length)
               {
                   rear.next=new Node<T>(array[i++]);
                   rear = rear.next;
               }
           }
       }
    
       /**
        * 通过传入的链表构造新的链表
        * @param list
        */
       public HeadSingleILinkedList(HeadSingleILinkedList<T> list) {
           this();
           if (list!=null && list.headNode.next!=null)
           {
               this.headNode.next = new Node(list.headNode.data);
               Node<T> p = list.headNode.next;
               rear = this.headNode.next;
               while (p!=null)
               {
                   rear.next = new Node<T>(p.data);
                   rear = rear.next;
                   p = p.next;
               }
           }
       }
    
    
       /**
        * 判断链表是否为空
        * @return
        */
       @Override
       public boolean isEmpty() {
           return this.headNode.next==null;
       }
    
       @Override
       public int length() {
           int length=0;
           Node<T> currentNode=headNode.next;
           while (currentNode!=null){
               length++;
               currentNode=currentNode.next;
           }
           return length;
       }
    
       /**
        * 根据index索引获取值
        * @param index 下标值起始值为0
        * @return
        */
       @Override
       public T get(int index) {
    
           if(index>=0){
               int j=0;
               Node<T> pre=this.headNode.next;
               //找到对应索引的结点
               while (pre!=null&&j<index){
                   pre=pre.next;
                   j++;
               }
    
               if(pre!=null){
                   return pre.data;
               }
    
           }
           return null;
       }
    
       /**
        * 根据索引替换对应结点的data
        * @param index 下标从0开始
        * @param data
        * @return 返回旧值
        */
       @Override
       public T set(int index, T data) {
    
           if(index>=0&&data!=null){
               Node<T> pre=this.headNode.next;
               int j=0;
               while (pre!=null&&j<index){
                   pre=pre.next;
                   j++;
               }
    
               if (pre!=null){
                   T oldData=pre.data;
                   pre.data=data;//设置新值
                   return oldData;
               }
    
           }
           return null;
       }
    
       /**
        * 根据下标添加结点
        * 1.头部插入
        * 2.中间插入
        * 3.末尾插入
        * @param index 该值从0开始,如传4就代表插入在第5个位置
        * @param data
        * @return
        */
       @Override
       public boolean add(int index, T data) {
    
           if (data==null){
               throw new NullPointerException("data can\'t be empty!");
           }
    
           if(index<0)
               throw new NullPointerException("index can\'t less than 0");
    
           //无需区分位置操作,中间/头部/尾部插入
           int j=0;
           Node<T> pre=this.headNode;
           while (pre.next!=null&&j<index){
               pre=pre.next;
               j++;
           }
    
           //将新插入的结点的后继指针指向pre.next
           Node<T> q=new Node<T>(data,pre.next);
           //更改指针指向
           pre.next=q;
    
           //如果是未指针
           if (pre==this.rear)
               this.rear=q;
    
           return true;
       }
    
       /**
        * 尾部插入
        * @param data
        * @return
        */
       @Override
       public boolean add(T data) {
           if (data==null)
               throw new NullPointerException("data can\'t be empty!");
    
           this.rear.next = new Node<T>(data);
           //更新末尾指针的指向
           this.rear = this.rear.next;
           return true;
       }
    
       /**
        * 根据索引删除结点
        * @param index
        * @return
        */
       @Override
       public T remove(int index) {
           T old=null;
    
           //包含了头删除或中间删除或尾部删除的情况
           if (index>=0){
    
               Node<T> pre = this.headNode;
               int j = 0;
               //查找需要删除位置的前一个结点
               while (pre.next != null && j < index) {
                   pre = pre.next;
                   j++;
               }
    
               //获取到要删除的结点
               Node<T> r = pre.next;
    
               if (r != null) {
                   //获取旧值
                   old =r.data;
                   //如果恰好是尾部结点,则更新rear的指向
                   if (r==this.rear){
                       this.rear=pre;
                   }
                   //更改指针指向
                   pre.next=r.next;
               }
    
           }
           return old;
       }
    
       /**
        * 根据data移除所有数据相同的结点
        * @param data
        * @return
        */
       @Override
       public boolean removeAll(T data) {
    
           boolean isRemove=false;
    
           if(data!=null){
               //用于记录要删除结点的前一个结点
               Node<T> front=this.headNode;
               //当前遍历的结点
               Node<T> pre=front.next;
               //查找所有数据相同的结点并删除
               while (pre!=null){
                   if(data.equals(pre.data)){
                       //如果恰好是尾部结点,则更新rear的指向
                       if(data.equals(rear.data)){
                           this.rear=front;
                       }
                       //相等则删除pre并更改指针指向
                       front.next=pre.next;
                       pre =front.next;
                       isRemove=true;
                   }else {
                       front=pre;
                       pre=pre.next;
                   }
               }
           }
           return isRemove;
       }
    
       /**
        * 清空链表
        */
       @Override
       public void clear() {
           this.headNode.next=null;
           this.rear=this.headNode;
       }
    
       /**
        * 判断是否包含某个值
        * @param data
        * @return
        */
       @Override
       public boolean contains(T data) {
    
           if(data!=null){
               Node<T> pre=this.headNode.next;
               while (pre!=null){
                   if(data.equals(pre.data)){
                       return true;
                   }
                   pre=pre.next;
               }
           }
           return false;
       }
    
       /**
        * 从末尾连接两个链表
        * @param list
        */
       public void concat(HeadSingleILinkedList<T> list)
       {
           if (this.headNode.next==null) {
               this.headNode.next = list.headNode.next;
           } else {
               Node<T> pre=this.headNode.next;
               while (pre.next!=null)
                   pre = pre.next;
              pre.next=list.headNode.next;
               //更新尾部指针指向
               this.rear=list.rear;
           }
       }
    
       @Override
       public String toString() {
           String str="(";
           Node<T> pre = this.headNode.next;
           while (pre!=null)
           {
               str += pre.data;
               pre = pre.next;
               if (pre!=null)
                   str += ", ";
           }
           return str+")";
       }
    
       public static void main(String[] args){
    
           String[] letters={"A","B","C","D","E","F"};
           HeadSingleILinkedList<String> list=new HeadSingleILinkedList<>(letters);
    
           System.out.println("list.get(3)->"+list.get(3));
           System.out.println("list:"+list.toString());
    
           System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
           System.out.println("list:"+list.toString());
           System.out.println("list.add(Z)—>"+list.add("Z"));
           System.out.println("list:"+list.toString());
    
    
           System.out.println("list.contains(Z)->"+list.contains("Z"));
           System.out.println("list.set(4,P)-->"+list.set(4,"P"));
           System.out.println("list:"+list.toString());
    
           System.out.println("list.remove(Z)->"+list.removeAll("Z"));
           System.out.println("list.remove(4)-->"+list.remove(4));
           System.out.println("list:"+list.toString());
       }
    }

    循环单链表

      有上述的分析基础,循环单链表(Circular Single Linked List)相对来说就比较简单了,所谓的循环单链表是指链表中的最后一个结点的next域指向了头结点head,形成环形的结构,我们通过图示来理解:

    此时的循环单链表有如下特点:
    a.当循环链表为空链表时,head指向头结点,head.next=head。
    b.尾部指向rear代表最后一个结点,则有rear.next=head。
    在处理循环单链表时,我们只需要注意在遍历循环链表时,避免进入死循环即可,也就是在判断循环链表是否到达结尾时,由之前的如下判断

    Node<T> p=this.head;
    while(p!=null){
         p=p.next;
    }

    在循环单链表中改为如下判断:

    Node<T> p=this.head;
    while(p!=this.head){
         p=p.next;
    }

    因此除了判断条件不同,其他操作算法与单链表基本是一样的,下面我们给出循环单链表的代码实现:

    package com.zejian.structures.LinkedList.singleLinked;
    
    import com.zejian.structures.LinkedList.ILinkedList;
    
    
    /**
     * Created by zejian on 2016/10/25.
     * 循环单链表
     */
    public class CircularHeadSILinkedList<T> implements ILinkedList<T> {
    
        protected Node<T> head; //不带数据头结点
        protected Node<T> tail;//指向尾部的指针
    
    
        public CircularHeadSILinkedList() {
            //初始化头结点与尾指针
            this.head= new Node<T>(null);
            this.head.next=head;
            this.tail=head;
        }
    
    
        public CircularHeadSILinkedList(T[] array)
        {
            this();
            if (array!=null && array.length>0)
            {
                this.head.next = new Node<>(array[0],head);
                tail=this.head.next;
                int i=1;
                while (i<array.length)
                {
                    tail.next=new Node<>(array[i++]);
                    tail.next.next=head;
                    tail = tail.next;
                }
            }
        }
    
    
        @Override
        public boolean isEmpty() {
            return this.head.next==head;
        }
    
        @Override
        public int length() {
    
            int length=0;
            Node<T> p=this.head.next;
            while (p!=head){
                p=p.next;
                length++;
            }
    
            return length;
        }
    
        @Override
        public T get(int index) {
    
            if (index>=0)
            {
                int j=0;
                Node<T> pre=this.head.next;
                while (pre!=null && j<index)
                {
                    j++;
                    pre=pre.next;
                }
                if (pre!=null)
                    return pre.data;
            }
            return null;
        }
    
        @Override
        public T set(int index, T data) {
    
            if (data==null){
                return null;
            }
    
            if(index>=0){
                int j=0;
                Node<T> p=this.head.next;
    
                while (p!=head&&j<index){
                    j++;
                    p=p.next;
                }
    
                //如果不是头结点
                if(p!=head){
                    T old = p.data;
                    p.data=data;
    
                    return old;
                }
            }
            return null;
        }
    
        @Override
        public boolean add(int index, T data) {
            int size=length();
            if(data==null||index<0||index>=size)
                return false;
    
            int j=0;
            Node<T> p=this.head;
            //寻找插入点的位置的前一个结点
            while (p.next!=head&&j<index){
                p=p.next;
                j++;
            }
    
            //创建新结点,如果index=3,那么插入的位置就是第4个位置
            Node<T> q=new Node<>(data,p.next);
            p.next=q;
            //更新尾部指向
            if(p==tail){
                this.tail=q;
            }
            return true;
        }
    
        @Override
        public boolean add(T data) {
            if(data==null){
                return false;
            }
    
            Node<T> q=new Node<>(data,this.tail.next);
            this.tail.next=q;
            //更新尾部指向
            this.tail=q;
    
            return true;
        }
    
        @Override
        public T remove(int index) {
            int size=length();
            if(index<0||index>=size||isEmpty()){
                return null;
            }
    
            int j=0;
            Node<T> p=this.head.next;
    
            while (p!=head&&j<index){
                j++;
                p=p.next;
            }
    
            if(p!=head){
                T old =p.next.data;
    
                if(tail==p.next){
                    tail=p;
                }
                p.next=p.next.next;
    
                return old;
            }
    
            return null;
        }
    
        @Override
        public boolean removeAll(T data) {
            boolean isRemove=false;
            if(data==null){
                return isRemove;
            }
    
            //用于记录要删除结点的前一个结点
            Node<T> front=this.head;
            //当前遍历的结点
            Node<T> pre=front.next;
            //查找所有数据相同的结点并删除
            while (pre!=head){
                if(data.equals(pre.data)){
                    //如果恰好是尾部结点,则更新rear的指向
                    if(data.equals(tail.data)){
                        this.tail=front;
                    }
                    //相等则删除pre并更改指针指向
                    front.next=pre.next;
                    pre =front.next;
                    isRemove=true;
                }else {
                    front=pre;
                    pre=pre.next;
                }
            }
    
    
            return isRemove;
        }
    
        @Override
        public void clear() {
            this.head.next=head;
            this.tail=head;
        }
    
        @Override
        public boolean contains(T data) {
            if (data==null){
                return false;
            }
    
            Node<T> p=this.head.next;
    
            while (p!=head){
                if(data.equals(p.data)){
                    return true;
                }
    
                p=p.next;
            }
    
            return false;
        }
    
        @Override
        public String toString()
        {
            String str="(";
            Node<T> p = this.head.next;
            while (p!=head)
            {
                str += p.data.toString();
                p = p.next;
                if (p!=head)
                    str += ", ";
            }
            return str+")";
        }
    
        public static void main(String[] args){
    
            String[] letters={"A","B","C","D","E","F"};
            CircularHeadSILinkedList<String> list=new CircularHeadSILinkedList<>(letters);
    
            System.out.println("list.get(3)->"+list.get(3));
            System.out.println("list:"+list.toString());
    
            System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
            System.out.println("list:"+list.toString());
            System.out.println("list.add(Z)—>"+list.add("Z"));
            System.out.println("list:"+list.toString());
    
    
            System.out.println("list.contains(Z)->"+list.contains("Z"));
            System.out.println("list.set(4,P)-->"+list.set(4,"P"));
            System.out.println("list:"+list.toString());
    
            System.out.println("list.removeAll(Z)->"+list.removeAll("Z"));
            System.out.println("list.remove(4)-->"+list.remove(4));
            System.out.println("list:"+list.toString());
        }
    }

    3.4 单链表的效率分析

      由于单链表并不是随机存取结构,即使单链表在访问第一个结点时花费的时间为常数时间,但是如果需要访问第i(0<i<n)个结点,需要从头结点head开始遍历部分链表,进行i次的p=p.next操作,这点从上述的图文分析我们也可以看出,这种情况类似于前面计算顺序表需要平均移动元素的总数,因此链表也需要平均进行n2次的p=p.next操作,也就是说get(i)和set(i,x)的时间复杂度都为O(n)。
      由于链表在插入和删除结点方面十分高效的,因此链表比较适合那些插入删除频繁的场景使用,单纯从插入操作来看,我们假设front指向的是单链表中的一个结点,此时插入front的后继结点所消耗的时间为常数时间O(1),但如果此时需要在front的前面插入一个结点或者删除结点自己时,由于front并没有前驱指针,单凭front根本无法知道前驱结点,所以必须从链表的表头遍历至front的前一个结点再执行插入或者删除操作,而这个查询操作所消耗的时间为O(n),因此在已知front结点需要插入前驱结点或者删除结点自己时,消耗的时间为O(n)。当然这种情况并不是无法解决的,后面我们要分析到的双链表就可以很好解决这个问题,双链表是每个结点都同时拥有前后继结点的链表,这样的话上面的问题就迎刃而解了。上述是从已知单链表中front结点的情况下讨论的单链表的插入删除效率。
      我们可能会有个疑问,从前面单链表的插入删除的代码实现上来说,我们并不知道front结点的,每次插入和删除结点,都需要从表头开始遍历至要插入或者删除结点的前一个结点,而这个过程所花费的时间和访问结点所花费的时间是一样的,即O(n),
    也就是说从实现上来说确实单链表的插入删除操作花费时间也是O(n),而顺序表插入和删除的时间也是O(n),那为什么说单链表的插入和删除的效率高呢?这里我们要明白的是链表的插入和删除之所以是O(N),是因为查询插入点所消耗的,找到插入点后插入操作消耗时间只为O(1),而顺序表查找插入点的时间为O(1),但要把后面的元素全部后移一位,消耗时间为O(n)。问题是大部分情况下查找所需时间比移动短多了,还有就是链表不需要连续空间也不需要扩容操作,因此即使时间复杂度都是O(n),所以相对来说链表更适合插入删除操作。

      以上便是本篇对象顺序表与单链表的分析,如有误处,欢迎留言,我们一起探讨学习。下篇会是双链表的知识点,欢迎持续关注,下面丢出github的地址:
    GITHUB博文源码下载地址

    关联文章:

    java数据结构与算法之顺序表与链表设计与实现分析
    java数据结构与算法之双链表设计与实现
    java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedList(带Iterator迭代器与fast-fail机制)

    如果您喜欢我写的博文,读后觉得收获很大,不妨小额赞助我一下,让我有动力继续写出高质量的博文,感谢您的赞赏!支付宝、微信


    SouthEast         SouthEast

    展开全文
  • 逻辑思维

    千次阅读 2017-09-25 16:05:07
    逻辑思维,又称抽象思维,是人的理性认识阶段,人运用概念、判断、推理等思维类型反映事物本质与规律的认识过程。
  • 逻辑 &nbsp; &nbsp;&nbsp;&nbsp;逻辑一词在定义的时候有狭义和广义之...广义的概念不仅仅指思维方面,还指事物客观规律、形式上又分为形式逻辑和辩证逻辑等等,说的更具体一些逻辑是事物的因果规...
  • 在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用 变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生变化(可以增加或删除元素)。 对于这种...
  • 这篇继续结合例子来深入了解下Method组件动态变更...那么我们也基本可以知道,同ClassVisitor改变类成员一样,MethodVIsistor如果需要改变方法成员,注入逻辑,也可以通过继承MethodVisitor,来编写一个MethodXXXAdapte
  • 13 万字C语言保姆级教程,入门精通。
  • 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,... 这节学习的是逻辑回归(Logistic Regression),也算进入了比较正统的机器学习算法。啥叫正统呢?我概念里面机器学
  • 小程序入门快速开发小程序项目

    万次阅读 多人点赞 2018-08-19 21:39:39
    Page.prototype.setData(Object data, Function callback):setData 函数用于将数据从逻辑层发送视图层(异步),同时改变对应的 this.data 的值(同步)。 Object 以 key: value 的形式表示,将 this.data 中...
  • 深度学习:卷积神经网络入门精通

    万次阅读 多人点赞 2019-03-28 23:30:12
    全面介绍各种卷积神经网络的模型、算法及应用,指导读者把握其形成和演变的基本脉络,以帮助读者在较短的时间内入门达到精通的水平。有兴趣的读者可以本书开始,通过图像分类、识别、检测和分割的案例,逐步深入...
  • FPGA组合逻辑训练-三八译码器

    千次阅读 2020-03-12 17:16:54
    而时序逻辑从电路特征上看来,其特点为任意时刻的输出不仅取决于该时刻的输入,而且还和电路原来的状态有关。 组合逻辑电路在电路结构上,不涉及对信号跳变沿的处理,无存储电路,也没有反馈电路,通常可以通过真值...
  • 善用性能工具进行SQL整体优化

    千次阅读 2017-07-06 22:30:01
    SQL优化是一个复杂的工程,首先要讲究从整体到局部。今天我们首先学习关于数据库整体优化都有哪些性能工具,接着分析这些工具的特点,并结合案例进行探索,最后再进行总结和思考。 总体学习思路如下图所示: ...
  • Logistic Regression(逻辑回归)简介

    千次阅读 2014-12-16 15:32:46
    在求职过程中发现各大互联网公司凡是涉及广告工程师的岗位面试几乎都会问到逻辑回归,因此在这里作一个总结。 1.什么是逻辑回归 Logistic Regression 是基于Sigmoid函数(又叫“S型函数”)的有监督二类分类模型。...
  • 操作系统概念逻辑线(下)

    千次阅读 2019-12-22 17:49:56
    书接上回,上次我们讲逻辑线讲了进程和线程的管理调度。 上文说,只有一个程序被装入和内存才能够执行,并被称为进程,可问题来了,内存就这么大,我们如何讲一个程序装入内存呢? 这里,就是上文我们所讲的...
  • 微信小程序逻辑层视图层解析

    千次阅读 2018-08-06 15:39:03
    框架提供了自己的视图层描述语言 WXML 和 WXSS,以及基于JavaScript的逻辑层框架,并在视图层与逻辑层间提供了数据传输和事件系统,让开发者能够专注于数据与逻辑 响应的数据绑定 框架的核心是一个响应的数据绑定...
  • 一、整体式结构 以模块为基本单位构建 特点: 模块设计、编码、调试独立 模块调用自由 模块通信多以全局变量完成 缺点 信息传递随意、维护和更新困难 二、层次式结构 分层结构的操作系统 所有功能模块按照调用...
  • K近邻算法、距离度量谈KD树、SIFT+BBF算法

    万次阅读 多人点赞 2012-11-20 16:31:35
    K近邻算法、距离度量谈KD树、SIFT+BBF算法前言 前两日,在微博上说:“今天为止,我至少亏欠了3篇文章待写:1、KD树;2、神经网络;3、编程艺术第28章。你看到,blog内的文章与你于别处所见的任何都不同。于是...
  • 在回收的时候将对象一个小堆区复制另一个小堆区,这意味着G1在回收垃圾的时候同时完成了堆的部分内存压缩,相对于CMS的优势而言就是内存碎片的产生率大大降低。 heap被划分为一系列大小相等的“小堆区”,...
  • 数据结构顺序表和链表的实现原理

    千次阅读 2018-07-07 16:38:32
    java数据结构与算法之顺序表与链表深入分析2016年11月05日 16:24:30阅读数:14829 转载请注明出处(万分感谢!): http://blog.csdn.net/javazejian/article/details/52953190 出自【zejian的博客】关联文章:java...
  • UML-逻辑视图-类图

    万次阅读 2018-06-27 09:07:09
    【代码表现】:局部变量、方法的参数或者对静态方法的调用 【箭头及指向】:带箭头的虚线,指向被使用者 各种关系的强弱顺序: 泛化 = 实现 > 组合 > 聚合 > 关联 > 依赖 下面这张UML图,比较形象地展示了各种类图...
  • 决策树&逻辑回归

    千次阅读 2014-08-11 17:54:08
    一种是决策树分析中找出数据局部结构,作为在逻辑回归中构建依变量(interaction)的依据。 另一种是在需要对预测因子进行离散化处理时,利用决策树分析决定最佳切分点。 还有一种是把决策树分类的最终结果...
  • 逻辑回归-logistic regression 详解

    万次阅读 2016-10-02 23:46:27
    线性分类器谈起  给定一些数据集合,他们分别属于两个不同的类别。例如对于广告数据来说,是典型的二分类问题,一般将被点击的数据称为正样本,没被点击的数据称为负样本。现在我们要找到一个线性分类器,将这些...
  • 优缺点 优点 顺序性,它支持顺序性,可以做到局部有序,在单线程内使用该生产者发送的消息按照发送的顺序到达服务器并存储,并按照相同顺序被消费,但前提是这些消息发往同一服务器的同一个分区 实时性:采取长轮询...
  • 数据结构、逻辑结构和物理结构

    千次阅读 2009-12-12 16:18:00
    什么是数据结构数据结构是在...逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式,其目的是为了提高
  • 逻辑模型的工具-数据流图DFD

    千次阅读 2010-04-08 11:03:00
    逻辑模型的工具——只反映信息在系统中流动和处理情况的图称为数据流图,它是描述系统逻辑模型的工具之一。数据流图(Data Flow Diagram,简称DFD)是便于用户理解系统数据流程的图形表示。它能精确地在逻辑上描述系统...
  • 本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,一篇文章足够。能换你一个收藏了吧?
  • 初看Xgboost,翻了多篇博客发现关于xgboost原理的描述实在难以忍受,缺乏逻辑性,写一篇供讨论。——以下是抛砖引玉。 观其大略,而后深入细节,一开始扎进公式反正我是觉得效率不高,还容易打消人的积极性。首先说...
  • MySQL整体总结

    千次阅读 2018-10-29 16:28:32
    设置自增属性(AUTO_INCREMENT)的时候,还可以指定第一条插入记录的自增字段的值,这样新插入的记录的自增字段值初始值开始 递增, 如在tb_emp中插入第一条记录,同时 指定id值为5,则以后插入的记录的id值就会...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,539
精华内容 15,015
关键字:

从整体到局部的逻辑顺序