深入理解Java虚拟机(一)

准备利用空闲看一些技术书,先从深入理解java虚拟及开始,希望可以从中收获一些东西,顺便也记录一些东西。

一、

JRE: Java Runtime Environment
JDK:Java Development Kit

JRE即Java运行环境,可以理解为Java运行环境 。

JDK即Java开发工具包,Java开发人员使用的工具包,包括Java运行环境和开发环境等,JDK包括JRE。

二、

Java栈-存放基本数据类型和对象的引用

Java堆-存放对象实例

方法区-各个线程共享的内存区域,存储虚拟机加载的类信息、常量、静态变量、编译后的代码等。

运行时常量池-存放编译期生成的各种字面量和符号引用

对象的创建-在对象的创建过程中,即new;首先去检查这个指令的参数是否能在常量池中定位到一个类的符号引用,并且检查这个符号引用代表的类是否已被加载、解析和初始化过。上面我们知道堆存放对象实例,也就是new对象的时候会使用堆内存。

内存分配方式:1、指针碰撞-假设Java堆中内存是绝对规整的,所有用过的内存放在一边,空闲的内存放在另一边,中间放着一个指针作为分界点的指示器,所分配的内存就仅仅是把那个指针向空闲空间那边挪动一段与对象大小相等的距离,这种方式就叫指针碰撞。

2、空闲列表-如果Java堆中的内存并不是规整的,已使用的内存和空闲的内存相互交错,那就没有办法简单的进行指针碰撞了,虚拟机就必须维护一个列表,记录上哪些内存是可用的,在分配的时候从列表中找到一块足够大的空间划分给对象实例,并更新列表上的记录,这种分配方式称为空闲列表。

以上内容为18.7.22号写的,现在更新一下。

=================================================================

image.png

上图是Java虚拟机运行时数据区的图示

链接:https://www.nowcoder.com/questionTerminal/8e62ee8f66284ea3ac407197acc18a39

来源:牛客网

1、程序计数器: 线程私有,是当前线程所执行的字节码的行号指示器,如果线程正执行一个java方法,计数器记录正在执行的虚拟机字节码指令的地址,如果线程正在执行的是Native方法,则计数器值为空;

2、虚拟机栈: 即栈区, 线程私有 ,为虚拟机执行 Java 方法(字节码)服务,每个方法在执行的时会创建一个栈帧用于存放局部变量表、操作数栈、动态链接和方法出口等信息,每个方法的调用直至执行完成对应于栈帧的入栈和出栈;

3、本地方法栈: 为虚拟机使用的 N ative 方法服务,也是 线程私有 ;

4、Java 堆: 在虚拟机启动时创建, 线程共享 ,唯一目的是存放对象实例,是垃圾收集器管理的主要区域——” GC 堆“,可以细分为新生代和老年代,新生代又可以细分为 Eden 空间、 From Survivor 空间和 To Survivor 空间;物理上可以不连续,但逻辑上连续,可以选择固定大小或者扩展;

5、方法区: 线程共享 ,用于存储被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。被称为“永久代”,是因为 H otSpot 虚拟机的设计团队把 GC 分代收集扩展到方法区,即使用永久代来实现方法区,像 GC 管理 Java 堆一样管理方法区,从而省去专门为方法区编写内存管理代码,内存回收目标是针对常量池的回收和堆类型的卸载;

6、运行时常量池: 线程共享 ,是方法区的一部分, C lass 文件中存放编译期生成的各种字面量和符号引用,类加载后进入方法区的运行时常量池中。

image.png

Java学习之反射

反射机制是Java语言中一个非常重要的特性,它允许程序在运行时进行自我检查,同时也允许对其内部的成员进行操作。

反射机制的主要功能有:1.得到一个对象所属的类;

                                 2.获取一个类的所有成员变量和方法;

                                 3.在运行时创建对象;

                                 4.在运行时调用对象的方法

1、Class类的使用

万物皆对象。类也是对象,类是java.lang.Class类的实例对象,这个对象我们称之为该类的类类型。

那么我们该如何获取Class类的实例对象呢?下面我们来演示一下:

package com.wjy329;
/**
 * @description:
 *
 * @author: wjy329
 * @create: 2018-10-31 15:32
 **/
public class ClassDemo {
    public static void main(String[] args) {
        //Test的实例对象test
        Test test = new Test();

        //Test类是一个实例对象,是Class的实例对象
        //下面用三种方式表达

        //第一种方式
        Class c1 = Test.class;

        //第二种方式,已知该类的对象,通过getClass()方法
        Class c2 = test.getClass();

        Class c3 = null;
        //第三种方式
        try {
             c3 = Class.forName("com.wjy329.Test");
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
        //返回true
        System.out.println(c1 == c2);
        //返回true,这就说明一个类只可能是Class类的一个实例对象
        System.out.println(c2 == c3);

        //通过该 类类型创建该类的实例对象
        try {
            Test test1 = (Test) c1.newInstance();
        } catch (InstantiationException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
    }
}

class Test{}

通过上面的代码我们可以总结出三个获取类类型的方法:

  1. 类名.class;         

  2. 实例.getClass();

  3. Class.forName("类的路径")

而且无论通过何种方式获取到的类类型对象都是相同的,并且可以通过类类型创建类的实例对象。

2、反射功能的演示

package com.wjy329;

import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;

/**
 * @Author wjy329
 * @Time 2018/10/314:03 PM
 * @description
 */

public class ReflectTest {
    public static void main(String[] args) {
        //新建一个list对象
        List<String> list = new ArrayList<>();
        //1.得到一个对象所属的类
        Class listClass = list.getClass();
        System.out.println("list所属的类为:"+listClass.getName());

        System.out.println("===================================================");

        //2.获取一个类的所有成员变量和方法
        /**
         * A:获得类的成员变量 数组:
           1、getFields(公共类的)
           2、getDeclaredFields(所有类型的)
          B:获得类的单个成员变量:
           1、getField (公共类的)
           2、getDeclaredField (所有类型的)
         获取方法也是类似的......
         * */
        Field[] listFields = listClass.getDeclaredFields();
        for(Field field : listFields){
            System.out.println("list所属类的成员变量为:"+field);
        }

        Method[] listMethods = listClass.getDeclaredMethods();
        for(Method method : listMethods){
            System.out.println("list所属类的方法为:"+method);
        }

        System.out.println("===================================================");

    }
}

上面演示了获取一个对象所属的类和获取一个类的成员变量和方法的功能。运行效果如下:

image.png

在运行时创建对象和在运行时获取对象的方法也是很容易理解的,我们一般在编译时创建对象就是直接new一个对象出来,这时候如果我们的类不存在,那么创建的对象就是失败,编译也会失败(一般不会有这种情况,仅用于解释),那么就会导致后面即使有其他的对象也无法运行,利用反射就可以动态的创建对象,不存在的类不影响其他类的编译和运行。

部分内容学习于:《反射,Java高级开发必须懂的》—慕课网

Java学习之List接口下的subList(int fromIndex,int toIndex)方法

最近遇到了subList(int fromIndex,int toIndex),就总结一下吧。

subList(int fromIndex,int toIndex)是List接口中的一个方法,它用来返回list从[fromIndex,toIndex)之间这一部分的视图;之所以称之为视图,是因为返回的list是以原来的list为支撑的,对原来的list和返回的list做“非结构性修改”,都会影响彼此。

非结构性修改:不涉及list的大小改变

结构性修改:改变了list的大小

如果发生结构性修改的是返回的list,那么原来的list的大小也会发生改变;如果发生结构性修改的是原来的list,那么就会抛出异常。

API文档连接:https://docs.oracle.com/javase/8/docs/api/

image.png

下面用一个例子来演示:

package servlet;/**
 * @Author wjy329
 * @Time 2018/10/306:36 PM
 * @description
 */

import java.util.ArrayList;
import java.util.List;

/**

 * @description:
 *
 * @author: wjy329
 * @param:
 * @return:
 * @create: 2018-10-30 18:36
 **/
public class testSub {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        List subList = list.subList(0,2);
        //输出结果是:  [a, b, c, d]
        System.out.println(list);
        //返回的是list的视图,从索引0到索引2(不包含索引2)  : [a, b]
        System.out.println(subList);


        subList.add("www");
        //返回的sublist添加www元素,list中也添加了相关元素  :  [a, b, www, c, d]
        System.out.println(list);
        //返回的sublist添加www元素     [a, b, www]
        System.out.println(subList);


        subList.clear();
        //清空返回的sublist,list中也删除相应的元素    [c,d]
        System.out.println(list);
        //清空sublist     []
        System.out.println(subList);

        //下面来修改原来的list,让其发生大小的改变
        subList.add("w");
        subList.add("j");
        subList.add("y");
        //添加元素   [w, j, y, c, d]
        System.out.println(list);
        //   [w, j, y]
        System.out.println(subList);
        //修改原来list(包括添加,删除等改变list大小的操作,都会导致subList抛出异常)
        list.add("aaaa");
        // 返回[w, j, y, c, d, aaaa]
        System.out.println(list);
        // subList 抛出异常 java.util.ConcurrentModificationException
        System.out.println(subList);

    }
}

控制台输出的结果:

image.png该方法常用来删除list的某个片段,比如删除2-5的元素可以这么写:

list.subList(2,5).clear();   

Java学习之JDBC Statement的相关知识点

摘自:牛客网       链接:https://www.nowcoder.com/questionTerminal/d29b742b521743118a741d01fcdc0b96pos=131&mutiTagIds=570&orderByHotValue=1

1、Statement、PreparedStatement和CallableStatement都是接口(interface)。 
2、Statement继承自Wrapper、PreparedStatement继承自Statement、CallableStatement继承自PreparedStatement。 
3、Statement接口提供了执行语句和获取结果的基本方法; 
     PreparedStatement接口添加了处理 IN 参数的方法; 
     CallableStatement接口添加了处理 OUT 参数的方法。 
4、a.Statement: 
        普通的不带参的查询SQL;支持批量更新,批量删除; 
    b.PreparedStatement: 
        可变参数的SQL,编译一次,执行多次,效率高; 
        安全性好,有效防止Sql注入等问题; 
        支持批量更新,批量删除; 
    c.CallableStatement: 
        继承自PreparedStatement,支持带参数的SQL操作; 
        支持调用存储过程,提供了对输出和输入/输出参数(INOUT)的支持; 
5、Statement每次执行sql语句,数据库都要执行sql语句的编译 , 最好用于仅执行一次查询并返回结果的情形,效率高于PreparedStatement。 
6、PreparedStatement是预编译的,使用PreparedStatement有几个好处 :
    1. 在执行可变参数的一条SQL时,PreparedStatement比Statement的效率高,因为DBMS预编译一条SQL当然会比多次编译一条SQL的效率         要高。 
    2. 安全性好,有效防止Sql注入等问题。 
    3. 对于多次重复执行的语句,使用PreparedStament效率会更高一点,并且在这种情况下也比较适合使用batch; 
    4. 代码的可读性和可维护性。

Java学习之Servlet

  • 什么是Servlet

  • Tomcat容器等级

  • 手写一个Servlet

  • Servlet的执行流程和生命周期

  • Tomcat装载Servlet的三种情况

1、什么是Servlet

Servlet是在服务器上运行的小程序。一个Servlet就是一个Java类,并且可以通过“请求-响应”编程模型来访问的这个驻留在服务器内存里的Servlet程序。

2、Tomcat容器等级

Tomcat容器分为4个等级,Servlet的容器管理Context容器,一个Context对应一个web工程。

image.png3、手写一个Servlet

image.png

从上图可以看出,HttpServlet的父类是一个GenericServlet抽象类,GenericServlet抽象类实现了Servlet接口,所以自定义的servlet需要继承HttpServlet并且重写doGet和doPost方法。

编写servlet的步骤为

1、继承HttpServlet

2、重写doGet()或者doPost()方法,取决于用户提交请求的方式

3、在web.xml中注册Servlet

下面我们来实际操作一下:

我这里使用IntelliJ IDEA,如图所示,新建Java项目,选择JavaEE,勾选Web Application,再勾选下面的web.xml,完毕。

image.png

新建完成之后的目录结构如下:

image.png

然后右击项目,选择Open Module Settings -> 然后点击下面的加号,然后点击 2 Library 选择Tomcat,将Tomcat的相关包添加进去。

image.png

首先编写我们的index.jsp,如下:

<%--
  Created by IntelliJ IDEA.
  User: wjy329
  Date: 2018/10/30
  Time: 3:39 PM
  To change this template use File | Settings | File Templates.
--%>
<%@ page language="java" import="java.util.*" contentType="text/html; charset=utf-8"%>
<%
  String path = request.getContextPath();
  String basePath = request.getScheme()+"://"+request.getServerName()+":"+request.getServerPort()+path+"/";
%>
<html>
  <head>
    <title>servlet</title>
  </head>
  <body>
  <h1>第一个servlet</h1>
  <hr>
  <a href="servlet/HelloServlet">Get方式请求HelloServlet</a>
  </body>
</html>

添加一个超链接,连接的路径就是之后的servlet的路径,后面会接着介绍。

然后我们在src目录下新建一个名为servlet的包,里面再新建一个HelloServlet.java文件,如下:

image.png

package servlet;

import javax.servlet.ServletException;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.io.IOException;
import java.io.PrintWriter;

/**
 * @Author wjy329
 * @Time 2018/10/303:46 PM
 * @description
 */

//继承HttpServlet
public class HelloServlet extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        System.out.println("处理Get()请求...");
        PrintWriter out = response.getWriter();
        out.println("Hello Servlet");
    }

    @Override
    protected void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        super.doPost(request, response);
    }
}

上面就是自定义serlvlet的主要代码,和之前学习的一样,我们需要继承HttpServlet类,然后重写doGet()和doPost()方法,这里我们jsp中的跳转是get请求,所以这里只重写doGet()方法,doPost()是一样的道理。

这里doGet()方法我们在控制台输出“处理Get()请求”的文字,然后返回给浏览器"Hello Servlet";

有了servlet,我们还需要在web.xml中配置一下,才可以访问到:

<?xml version="1.0" encoding="UTF-8"?>
<web-app xmlns="http://xmlns.jcp.org/xml/ns/javaee"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://xmlns.jcp.org/xml/ns/javaee http://xmlns.jcp.org/xml/ns/javaee/web-app_3_1.xsd"
         version="3.1">
    <servlet>
        <servlet-name>HelloServlet</servlet-name>
        <servlet-class>servlet.HelloServlet</servlet-class>
    </servlet>
    
    <servlet-mapping>
        <servlet-name>HelloServlet</servlet-name>
        <url-pattern>/servlet/HelloServlet</url-pattern>
    </servlet-mapping>
    
</web-app>

上面就是配置的主要内容,我们需要两个主要的标签,<servlet></servlet><servlet-mapping></servlet-mapping><servlet></servlet>中又包含两个标签,<servlet-name></servlet-name>表示servlet的名字,<servlet-class></servlet-class>中是我们上面写的servlet的路径;<servlet-mapping></servlet-mapping>中的两个标签分别是<servlet-name></servlet-name>它与上面我们写的servlet的名字是对应的,<url-pattern></url-pattern>中是表示将要访问servlet的路径,我们之前在jsp中写的那个路径就是。

至此,一个小的servlet的demo就完成了,然后我们在tomcat容器中运行。

控制台效果:

image.png

网页点击效果:

image.png

点击以后,跳转成功。

4、Servlet的执行流程和生命周期

4.1 执行流程

1.Get方式请求HelloServlet —>  2.用户点击url<a href="servlet/HelloServlet"> —>3.在servlet映射中寻找路径<url-pattern>/servlet/HelloServlet</url-pattern> —> 4.根据映射路径找到servlet映射名字为HelloServlet —> 5.然后在servlet标签中找到名字为HelloServlet的servlet,然后找到类的路径—> 6.然后根据用户请求方式执行doGet()/doPost()方法。

4.2 生命周期

  1. 初始化阶段,调用init()方法

  2. 响应客户端请求阶段,调用service()方法。由service()方法根据提交方式选择执行doGet()或者doPost()方法

  3. 终止阶段,调用destroy()方法

    image.png

5、Tomcat装载Servlet的三种情况

  • Servlet容器启动时自动装载某些Servlet,实现它只需要在web.xml文件中的<servlet></servlet>之间添加如下代码:<loadon-startup>1</loadon-startup>,数字越小表示优先级别越高。

  • 在Servlet容器启动后,客户首次向servlet发送请求

  • servlet类文件被更新后,重新装载servlet

Docker学习(二)运行一个镜像

国内有很多优秀的镜像中心,这里使用网易云的镜像:https://c.163yun.com/hub#/m/home/

搜索nginx,然后点开,复制下载地址到linux;

image.png

运行命令后,用docker images 命令查看镜像

image.png

docker run -p 8080:80 -d hub.c.163.com/library/nginx 命令运行镜像。image.png

这个命令后面的参数 p 8080:80 表明将docker的80端口映射到linux的8080端口,d 表明是在后台运行。

然后访问测试:

image.png

这样运行一个简单的镜像就成功了。

Docker学习(一)介绍与安装

1、什么是Docker

Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。容器是完全使用沙箱机制,相互之间不会有任何接口。—百度百科

我觉得上面的解释还是很容易理解的,就是把开发好的应用丢到里面,然后应用就能提供服务了,当然这中间的流程,我们之后还会介绍。

2、Docker安装

系统准备:CentOS 7  (64位内核版本3.10以上

注意红字,这是必须满足的条件;

查看内核:

uname -r

image.png

安装必要系统工具:

sudo yum install -y yum-utils device-mapper-persistent-data lvm2

添加源信息:

sudo yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo

更新yum缓存:

sudo yum makecache fast

安装Docker:

sudo yum -y install docker-ce

启动Docker后台服务:

sudo systemctl start docker

这就ok了,安装完成了,输入docker查看是否安装成功。

image.png

Java学习之线程的状态

Java线程在运行的生命周期中可能处于6种不同的状态,在给定的一个时刻,线程只能处于其中一个状态。这6中状态分别为NEW(初始状态)、RUNNABLE(运行状态)、BLOCKED(阻塞状态)、WAITING(等待状态)、TIME_WAITING(超时等待状态)、TERMINATED(终止状态),下面我们用一个表格来详细的说明这6中状态;

状态名称 说明
NEW
初始状态,线程被构建,但是还没有调用start()方法
RUNNABLE 运行状态,Java线程将操作系统中的就绪和运行两种状态笼统地称作“运行中”
BLOCKED 阻塞状态,表示线程阻塞于锁
WAITING 等待状态,表示线程进入等待状态,进入该状态表示当前线程需要等待其他线程做出一些特定动作(通知或中断)
TIME_WAITING 超时等待状态,该状态不同于WAITING,它是可以在指定的时间自行返回的
TERMINATED 终止状态,表示当前线程已经执行完毕

线程在自身的生命周期中,并不是固定地处于某个状态,而是随着代码的执行在不同的状态之间进行切换,Java线程状态变迁如图:

image.png

由图可以看到,线程创建之后,调用start()方法开始运行。当线程执行wait()方法之后,线程进入等待状态。进入等待状态的线程需要依靠其他线程的通知才能够返回到运行状态,而超时等待状态相当于在等待状态的基础上增加了超时限制,也就是超时时间到达时会返回到运行状态。当线程调用同步方法时,在没有获取到锁的情况下,线程将会进入到阻塞状态。线程在执行Runnable的run()方法之后将会进入到终止状态。

注意:Java将操作系统中的运行和就绪两个状态合并称为运行状态。阻塞状态是线程阻塞在进入synchronized关键字修饰的方法或代码块(获取锁)时的状态,但是阻塞在java.concurrent包中Lock接口的线程状态却是等待状态,因为java.concurrent包中Lock接口对于阻塞的实现均使用了LockSupport类中的相关方法。

数据结构(六)集合和映射

1、集合

集合(Set)最大的特点就是元素不重复;上篇博客中二分搜索树也是不重复的,这篇我们就用上节实现的二分搜索树来作为集合的底层;

我们先来定义一个集合的接口:

package com.wjy329;

/**
 * @Author wjy329
 * @Time 2018/10/1610:03 AM
 * @description
 */
public interface Set<E> {
    //添加元素
    void add(E e);
    //删除元素
    void remove(E e);
    //判断是否包含
    boolean contains(E e);
    //获得元素个数
    int getSize();
    //判断是否为空
    boolean isEmpty();
}

基于二分搜索树的集合实现:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/1610:25 AM
 * @description 以二分搜索树为底层的集合
 */

public class BSTSet<E extends Comparable<E>> implements Set<E> {

    private BST<E> bst;

    public BSTSet(){
        bst = new BST<>();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public int getSize() {
        return bst.size();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty() ;
    }
}

基于链表实现集合:

链表在之前的博客中写了 数据结构(四)链表  

package com.wjy329;
/**
 * @description: 基于链表的集合实现
 * @create: 2018-10-16 10:58
 **/
public class LinkedListSet<E> implements Set<E>{

    private LinkedList<E> list;

    public LinkedListSet(){
        list = new LinkedList<>();
    }

    @Override
    public void add(E e) {
        if(!list.contains(e)){
            list.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        list.removeElement(e);
    }

    @Override
    public boolean contains(E e) {
        return list.contains(e);
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
}

上面就是有关集合的一些实现,集合有有序集合和无序集合,有序集合中的元素具有顺序性,它是基于搜索树实现,而无序集合中的元素不具有顺序性,它基于哈希表实现;

2、映射

映射(Map)是存储(键,值)数据对的数据结构(Key,Value) ,可以根据键(Key),寻找值(Value),这里我们可以使用链表或者二分搜索树实现;

和上面一样,我们先定义一个映射的接口:

package com.wjy329;

/**
 * @Author wjy329
 * @Time 2018/10/162:43 PM
 * @description
 */
public interface Map<K,V> {
    //添加元素
    void add(K key,V value);
    //移除元素
    V remove(K key);
    //是否包含输入的key
    boolean contains(K key);
    //获取输入key的值
    V get(K key);
    //给key指定新的值
    void set(K key,V newValue);
    //获取有几个键值对
    int getSize();
    //判断是否为空
    boolean isEmpty();
}

链表为底层的映射:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/162:47 PM
 * @description 以链表为底层的映射类
 */


public class LinkedListMap<K,V> implements Map<K,V>{

    private class Node{
        public K key;
        public V value;
        public Node next;

        public Node(K key,V value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(K key){
            this(key,null,null);
        }

        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString(){
            return key.toString()+" : "+value.toString();
        }

    }

    //虚拟头指针
    private Node dummyHead;
    private int size;

    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    private Node getNode(K key){
        Node cur = dummyHead.next;
        while (cur != null){
            if(cur.key.equals(key)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if(node == null){
            dummyHead.next = new Node(key,value,dummyHead.next);
            size++;
        }else{
            node.value = value;
        }
    }

    @Override
    public V remove(K key) {
        Node pre = dummyHead;
        while (pre.next != null){
            if(pre.next.key.equals(key)){
                break;
            }
            pre = pre.next;
        }

        if(pre.next != null){
            Node delNode = pre.next;
            pre.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(key);
        if(node ==null){
            throw new IllegalArgumentException(key + "doesn't exist");
        }
        node.value = newValue;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size ==0;
    }
}

二分搜索树为底层的映射:

package com.wjy329;/**
 * @Author wjy329
 * @Time 2018/10/163:17 PM
 * @description
 */

public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> {

    private class Node{
        public K key;
        public V value;
        public Node left,right;

        public Node(K key,V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap(){
        root = null;
        size = 0;
    }

    @Override
    public void add(K key,V value){
        root = add(root,key,value);
    }

    private Node add(Node node,K key,V value){
        if(node == null){
            size++;
            return new Node(key, value);
        }
        if(key.compareTo(node.key)<0){
            node.left = add(node.left,key,value);
        }else if(key.compareTo(node.key)>0){
            node.right = add(node.right,key,value);
        }else{
            node.value = value;
        }
        return node;
    }

    private Node getNode(Node node,K key){
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key) == 0){
            return node;
        }else if(key.compareTo(node.key) < 0){
            return getNode(node.left,key);
        }else{
            return getNode(node.right,key);
        }
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root,key);
        if(node != null){
            root = remove(root,key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node,K key){
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key) < 0){
            node.left = remove(node.left,key);
            return node;
        }else if(key.compareTo(node.key) > 0){
            node.right = remove(node.right,key);
            return node;
        }else{
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right =null;
            return successor;
        }
    }

    //返回最小的元素
    public V minimum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty!!!");
        }
        return minimum(root).value;
    }
    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }
    //返回最大的元素
    public V maximum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty!!!");
        }
        return maximum(root).value;
    }
    private Node maximum(Node node){
        if(node.right == null){
            return node;
        }
        return maximum(node.right);
    }

    //删除最小的元素
    public V removeMin(){
        V ret = minimum();
        root = removeMin(root);
        return ret;
    }
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left =  removeMin(node.left);
        return node;
    }

    //删除最大的元素
    public V removeMax(){
        V ret = maximum();
        root = removeMax(root);
        return ret;
    }
    private Node removeMax(Node node){
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right =  removeMax(node.right);
        return node;
    }


    @Override
    public boolean contains(K key) {
        return getNode(root,key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(root,key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(root,key);
        if(node == null){
            throw new IllegalArgumentException(key + "doesn't exist");
        }
        node.value = newValue;
    }

    @Override
    public int getSize() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }
}

数据结构(五)二分搜索树

1、二叉树

image.png 

如上图所示就是二叉树,如同链表一样,是动态的数据结构;

class Node{
    E e;
    Node left;
    Node right;
}
  • 二叉树具有唯一的根节点

  • 二叉树每个节点最多有两个孩子

  • 二叉树每个节点最多有一个父亲

  • 二叉树具有天然的递归结构

            (1)每个节点的左子树也是二叉树

            (2)每个节点的右子树也是二叉树

2、二分搜索树

  • 二分搜索树是二叉树

  • 二分搜索树每个节点的值:

        (1)大于其左子树的所有节点的值

        (2)小于其右子树的所有节点的值

  • 每一棵子树也是二分搜索树

  • 存储的元素必须具有可比较性

下面我们来看二分搜索树的代码表现形式:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/152:02 PM
 * @description
 */

//继承Comparable使元素具有可比较性
public class BST<E extends Comparable<E>>{
    //节点类
    private class Node{
        //元素的值
        public E e;
        //左右节点
        public Node left,right;

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }
    //根节点
    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

3、二分搜索树添加新元素

我们设计的二分搜索树不包含重复元素;直接上代码;

//向二分搜索树中添加元素
public void add(E e){
   root = add(root,e);
}

private Node add(Node node,E e){
    if(node == null){
        size++;
        return new Node(e);
    }
    if(e.compareTo(node.e)<0){
        node.left = add(node.left,e);
    }else if(e.compareTo(node.e)>0){
        node.right = add(node.right,e);
    }
    return node;
}

上面的方式是一个递归的方式,我们来分析一下:

我们看私有的add()方法,首先我们判断节点是否为空,如果为空的话,直接new一个新的值为e的节点即可,如果不为空的话,需要我们比较值来添加,我们之前也学习了二叉搜索树的特点,那就是左子树小于父节点,右子树大于父节点,所以我们用传进来的e和父节点的值比较,如果比父节点的值小,就需要查入到左子树,此时,需要判断左子树是否为空,左子树为空直接new,左子树不为空需要再次判断大小插入,这是一个递归的过程,所以我们有了node.left = add(node.left,e),右子树也是一样的道理;

4、查询元素

//查询元素
public boolean contains(E e){
    return contains(root,e);
}

private boolean contains(Node node,E e){
    if(node == null){
        return false;
    }
    if(e.compareTo(node.e) == 0){
        return true;
    }else if(e.compareTo(node.e) < 0){
        return contains(node.left,e);
    }else{
        return contains(node.right,e);
    }
}

上面的查询算法也是递归的操作,结合上面的理解即可;

5、遍历

5.1 前序遍历

前序遍历,也叫先序遍历、先根遍历,即先访问根节点然后遍历左子树,在遍历右子树。

//前序遍历
public void preOrder(){
    preOrder(root);
}
private void preOrder(Node node ){
    if(node == null){
        return;
    }
    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}

5.2 中序遍历

中序遍历,先遍历左子树,然后访问根节点,最后遍历右子树。

//中序遍历
public void inOrder(){
    inOrder(root);
}
private void inOrder(Node node ){
    if(node == null){
        return;
    }
    inOrder(node.left);
    System.out.println(node.e);
    inOrder(node.right);
}

中序遍历的结果是顺序的。

5.3 后序遍历

后序遍历,先遍历左子树,再遍历右子树,最后访问根节点。

//后序遍历
public void postOrder(){
    postOrder(root);
}
private void postOrder(Node node ){
    if(node == null){
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.e);
}

5.4 层序遍历

思路:应用了队列,根节点先入队,然后出队,出队完成后,再将左右子树的根节点分别入队,然后左节点出队,出队时候,再将左右节点入队,以此类推……

//层次遍历
public void levelOrder(){
    Queue<Node> q = new LinkedList<Node>();
    q.add(root);
    while (!q.isEmpty()){
        Node cur = q.remove();
        System.out.println(cur.e);
        if(cur.left != null){
            q.add(cur.left);
        }
        if(cur.right != null){
            q.add(cur.right);
        }
    }
}

意义:更快的找到问题的解;算法设计-最短路径;图中的深度优先遍历和广度优先遍历;

6、删除节点

6.1 获取最小值和最大值

//返回最小的元素
public E minimum(){
    if(size == 0){
        throw new IllegalArgumentException("BST is empty!!!");
    }
    return minimum(root).e;
}
private Node minimum(Node node){
    if(node.left == null){
        return node;
    }
    return minimum(node.left);
}
//返回最大的元素
public E maximum(){
    if(size == 0){
        throw new IllegalArgumentException("BST is empty!!!");
    }
    return maximum(root).e;
}
private Node maximum(Node node){
    if(node.right == null){
        return node;
    }
    return maximum(node.right);
}

6.2 删除最小值和最大值

思路:由之前所学,我们知道最小的元素就是不停的访问左子树中的左节点,如果正好是叶子节点,那么我们删除即可;如果该节点还有右子树,那么我们将右子树的父节点作为该节点的父节点的新的左子树即可;删除最大的元素正好相反,即不停的访问右子树的右节点,如果正好是叶子节点,删除即可;如果该节点还有左子树,那么我们将左子树的父节点作为该节点的父节点的新的右子树即可。

//删除最小的元素
public E removeMin(){
    E ret = minimum();
    root = removeMin(root);
    return ret;
}
private Node removeMin(Node node){
    if(node.left == null){
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
    }
    node.left =  removeMin(node.left);
    return node;
}

//删除最大的元素
public E removeMax(){
    E ret = maximum();
    root = removeMax(root);
    return ret;
}
private Node removeMax(Node node){
    if(node.right == null){
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
    }
    node.right =  removeMax(node.right);
    return node;
}

6.3 删除任意的元素

思路:删除任意元素时,需要我们进行判断,如果删除的元素没有左子树,那么删除后将它的右子树作为它的替代即可;如果删除的元素没有右子树,那么删除后将它的左子树作为它的替代即可;如果该元素同时有左右子树,那么找到它右子树中最小的元素来代替它,它的左子树作为新节点的左子树即可,新节点的右子树是原右子树删除新节点的树;

//删除元素e
public void remove(E e){
    root = remove(root,e);
}
private Node remove(Node node,E e){
    if(node == null){
        return null;
    }
    if(e.compareTo(node.e) < 0){
        node.left = remove(node.left,e);
        return node;
    }else if(e.compareTo(node.e) > 0){
        node.right = remove(node.right,e);
        return node;
    }else{
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        Node successor = minimum(node.right);
        successor.right = removeMin(node.right);
        successor.left = node.left;
        node.left = node.right =null;
        return successor;
    }
}