排序查找算法

冒泡排序

对要进行排序的数据中相邻的数据进行两两比较，将较大的数据放在后面，依次对所有的数据进行操作，直至所有数据按要求完成排序
如果有n个数据进行排序，总共需要比较n-1趟

每一趟比较完毕，下一次的比较就会少一个数据参与

/*
  冒泡排序：
      一种排序的方式，对要进行排序的数据中相邻的数据进行两两比较，将较大的数据放在后面，
      依次对所有的数据进行操作，直至所有数据按要求完成排序
*/
public class ArrayDemo {
  public static void main(String[] args) {
      //定义一个数组
      int[] arr = {7, 6, 5, 4, 3};
      System.out.println("排序前：" + Arrays.toString(arr));
      // 这里减1，是控制每轮比较的次数
      for (int x = 0; x < arr.length - 1; x++) {
          // -1是为了避免索引越界，-x是为了调高比较效率
          for (int i = 0; i < arr.length - 1 - x; i++) {
              if (arr[i] > arr[i + 1]) {
                  int temp = arr[i];
                  arr[i] = arr[i + 1];
                  arr[i + 1] = temp;
              }
          }
      }
      System.out.println("排序后：" + Arrays.toString(arr));
  }
}

冒泡排序第一次优化

public class ArrayDemo {
  public static void main(String[] args) {
      //定义一个数组
      int[] arr = {7, 6, 5, 4, 3};
      System.out.println("排序前：" + Arrays.toString(arr));
      // 这里减1，是控制每轮比较的次数
      for (int x = 0; x < arr.length - 1; x++) {
          // -1是为了避免索引越界，-x是为了调高比较效率
          int flag = 1;
          for (int i = 0; i < arr.length - 1 - x; i++) {
              if (arr[i] > arr[i + 1]) {
                  int temp = arr[i];
                  arr[i] = arr[i + 1];
                  arr[i + 1] = temp;
                  flag = 0;  //发生交换，标志位置为0
              }
          }
          if (flag == 1) {//如果没有交换过元素，则已经有序
               return;
          }
      }
      System.out.println("排序后：" + Arrays.toString(arr));
  }
}

选择排序

选中数组的某个元素,其后面的元素依次和选中的元素进行两两比较，将较大的数据放在后面，依次从前到后选中每个元素，直至所有数据按要求完成排序
如果有n个数据进行排序，总共需要比较n-1次

每一次比较完毕，下一次的比较就会少一个数据参与

/*
  选择排序：
      另外一种排序的方式，选中数组的某个元素,其后面的元素依次和选中的元素进行两两比较，将较大的数据放在后面，依次从前到后选中每个元素，直至所有数据按要求完成排序
*/
public class ArrayDemo {
  public static void main(String[] args) {
      //定义一个数组
      int[] arr = {7, 6, 5, 4, 3};
      System.out.println("排序前：" + Arrays.toString(arr));
        // 这里减1，是控制比较的轮数
      for (int x = 0; x < arr.length - 1; x++) {
          // 从x+1开始,直到最后一个元素
          for (int i = x+1; i < arr.length; i++) {
              if (arr[x] > arr[i]) {
                  int temp = arr[x];
                  arr[x] = arr[i];
                  arr[i] = temp;
              }
          }
      }
      System.out.println("排序后：" + Arrays.toString(arr));
  }
}

选择排序优化

//优化选择排序
  //（每次遍历只会出现一次交换，性能更好）当找到拿到的数与下一个数小的时候，再
  // 把下一个数直接和后面的数进行比较，如果有更小的，则交换位置
  private static void selectSort(int[] a){
      int k,temp; //在循环之前定义，不用每次循环的时候都要分配栈空间
      for (int i=0; i<a.length; i++){
          k = i; //假设找到当前最小的数，位置为i 
          for(int j=k+1; k<a.length; j++){ //j往后找比i更小的数
              if(a[j] < a[k]){ //如有后面的数有比拿到的数还要小的数
                  k = j; //则交换位置
              }
          }
          //如果从后面找到的数与当前最小的数不相等，则交换位置
          if(k != i){
              temp = a[i];
              a[i] = a[k];
              a[k] = temp;
          }
      }
  }

二分查找

原理：遍历数组，获取每一个元素，然后判断当前遍历的元素是否和要查找的元素相同，如果相同就返回该元素的索引。如果没有找到，就返回一个负数作为标识(一般是-1)
如果不相同，就比较中间元素和要查找的元素的值；
如果中间元素的值大于要查找的元素，说明要查找的元素在左侧，那么就从左侧按照上述思想继续查询(忽略右侧数据)；
如果中间元素的值小于要查找的元素，说明要查找的元素在右侧，那么就从右侧按照上述思想继续查询(忽略左侧数据)；

注意：二分查找对数组是由要求的，数组必须已经排好序

public static void main(String[] args) {
      int[] arr = {10, 14, 21, 38, 45, 47, 53, 81, 87, 99};
      int index = binarySerach(arr, 38);
      System.out.println(index);
  }
  /**
   * 二分查找方法
   * @param arr 查找的目标数组
   * @param number 查找的目标值
   * @return 找到的索引,如果没有找到返回-1
   */
  public static int binarySerach(int[] arr, int number) {
      int start = 0;
      int end = arr.length - 1;
      while (start <= end) {
          int mid = (start + end) / 2;
          if (number == arr[mid]) {
              return mid ;
          } else if (number < arr[mid]) {
              end = mid - 1;
          } else if (number > arr[mid]) {
              start = mid + 1;
          }
      }
      return -1;  //如果数组中有这个元素，则返回
  }

单例设计

饿汉单例

public class Singleton {
  // 1.将构造方法私有化，使其不能在类的外部通过new关键字实例化该类对象。
  private Singleton() {}
  // 2.在该类内部产生一个唯一的实例化对象，并且将其封装为private static类型的成员变量。
  private static final Singleton instance = new Singleton();
  // 3.定义一个静态方法返回这个唯一对象。
  public static Singleton getInstance() {
      return instance;
  }
}

懒汉单例

懒汉单例设计模式就是调用getInstance()方法时实例才被创建，先不急着实例化出对象，等要用的时候才实例化出对象。不着急，故称为“懒汉模式”
注意：懒汉单例设计模式在多线程环境下可能会实例化出多个对象，不能保证单例的状态，所以加上关键字：synchronized，保证其同步安全

//在方法上面加synchronized
public class Singleton {
  // 2.在该类内部产生一个唯一的实例化对象，并且将其封装为private static类型的成员变量。
  private static Singleton instance;
  // 1.将构造方法私有化，使其不能在类的外部通过new关键字实例化该类对象。
  private Singleton() {}
  // 3.定义一个静态方法返回这个唯一对象。要用的时候才例化出对象
  public static synchronized Singleton getInstance() {
      if(instance == null) {
          instance = new Singleton();
      }
      return instance;
  }
}
//双检锁
public class Singleton {
  // 2.在该类内部产生一个唯一的实例化对象，并且将其封装为private static类型的成员变量。
  private static Singleton instance;
  // 1.将构造方法私有化，使其不能在类的外部通过new关键字实例化该类对象。
  private Singleton() {}
  // 3.定义一个静态方法返回这个唯一对象。要用的时候才例化出对象
  public static Singleton getInstance() {
      if(instance == null) {
          synchronized (Singleton.class){
              if(instance==null){
                  instance = new Singleton();
              }
          }
      }
      return instance;
  }
}

HashMap底层原理

HashMap通过key经过抖动函数获取hash值，然后通过（n-1）&hash判断当前元素所在的位置，如果存在就判断key和hash值是否相等，相等就直接覆盖，不相等再通过拉链法解决冲突

抖动函数：就是HashMap的hash方法，防止一些实现比较差的 hashCode() 方法，目的就是使用抖动函数减少碰撞

拉链法：创建一个新的链表数组，数组中的每一格存储链表，遇到哈希冲突九江冲突的值加到链表中

# 树化的前提
  数组的初始长度为16 当链表的长度大于阈值（默认是8）的时候，如果数组的长度没有超过64，是直接扩容的，直到数组的长度为64，这时在向链表长度为8的hash码地方添加值，就会树化
  注：在扩容的过程中，再次往相同的hash码添加值时，链表的长度会超过8 
  红黑树是一种不正常的情况（只是为了避免DOS恶意攻击会造成链表超长）
  一般情况下链表长度是不会超过8的
  为什么是8（为了让树化几率足够小），在负载因子0.75的情况下，长度超过8的链表出现概率是亿分之6
# 加载因子
  loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。
  loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
  给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。
# 退化为链表
  1.在扩容时如果拆分树时，树元素个数<=6就会退化
  2.删除树节点时，如根节点、左孩子、右孩子、左孙子有一个为null  就会退化
      这里会有一个检测机制，移除之前如果存在，即使移除了 也不会退化

JavaEE-多线程 - 图1

多线程

什么是线程？为什么使用多线程？

# 什么是线程
  单个进程中执行中每个任务就是一个线程。线程是进程中执行运算的最小单位，每个线程都拥有单独的栈内存用来存储本地数据
# 为什么使用多线程
  提高程序的效率：当任务到达时，任务可以不需要等待
  降低资源消耗：通过重复利用已经创建的线程降低线程创建和销毁造成的消耗
# 多线程使用场景
  任务量大，通过多线程来提高效率
  需要异步处理  ： 记录日志 发送短信 ， 统计结果
  占用系统资源，造成阻塞的工作时，
  并发量高的场景---项目中 文章点赞 异步线程

获取线程的几种方式

# 获取线程的四种方式
  1.继承Thread类 重写run方法创建线程，但是不能在继承其他类
  2.实现Runnable接口 重写run方法，避免了单线程局限性，常用
  3.实现Callable接口 重写call方法，可以获取线程执行结果的返回值，并且可以抛出异常
  4.线程池
# Runnable 和 Callable 的区别
  Runnable 接口 run方法没有返回值， Callable接口call方法有返回值，支持泛型
  Runnable 接口 run方法只能抛出运行时异常，无法捕获；Callable接口call方法可以抛也可以捕获
# 如何启动一个新线程、调用start和run方法的区别
  run方法是不开启线程的，只是对象调用方法
  调用start方法开启线程，使线程进入就绪状态 并且调用run方法执行
# 线程唤醒（notify）
  Object 类中的 notify() 方法，唤醒在此对象监视器上等待的单个线程
  notifyAll() ，唤醒在此监视器上等待的所有线程
# wait()与sleep()区别
  1. 来自不同的类
      wait():来自Object类；
      sleep():来自Thread类；
  2.关于锁的释放：
      wait():在等待的过程中会释放锁；
      sleep():在等待的过程中不会释放锁
  3.使用的范围：
      wait():必须在同步代码块中使用；
      sleep():可以在任何地方使用；
  4.是否需要捕获异常
      wait():不需要捕获异常；
      sleep():需要捕获异常；

线程的生命周期

# 线程的几种状态以及各种状态之间的转换
  1、新建状态(New)：新创建了一个线程对象。 　　
  2、就绪状态(Runnable)：线程对象创建后，其他线程调用了该对象的start()方法。该状态的线程位于        可运行线程池中，变得可运行，等待获取CPU的使用权。 　　
  3、运行状态(Running)：就绪状态的线程获取了CPU，执行程序代码。 　　
  4、阻塞状态(Blocked)：阻塞状态是线程因为某种原因放弃CPU使用权，暂时停止运行。直到线程进入就        绪状态，才有机会转到运行状态。
  5、死亡状态(Dead)：线程执行完了或者因异常退出了run()方法，该线程结束生命周期。等待被销毁。
  阻塞状态
      计时等待 ：通过调用线程的wait() 方法，让线程等待某工作的完成
      无线等待 ：通过调用线程的sleep() 或join()或发出了I/O请求时，线程会进入到阻塞状态，
      当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入就绪状态
      同步阻塞：线程在获取synchronized同步锁失败(因为锁被其它线程所占用)，
      它会进入同步阻塞状态

线程优先级

# 线程优先级
  通过提高线程的优先级来最大程度的改善线程获取时间片的几率
  线程的优先级被划分为10级,值分别为1-10,其中1最低,10最高。
  线程提供了3个常量来表示最低,最高,以及默认优先级:
  Thread.MIN_PRIORITY   1
  Thread.MAX_PRIORITY   10
  Thread.NORM_PRIORITY   5
  void setPriority(int priority):设置线程的优先级。

线程池的原理

# 线程池的原理
  当任务进来时，
  线程池首先会判断核心线程池中的线程是否已经满了，不满就创建线程执行任务
  满了，就判断任务队列是否满了，不满就放进任务队列中
  满了，判断线程池里的线程是否都在执行任务，不是就创建一个新的工作栈执行
  满了就需要执行拒绝策略

线程池的分类以及核心参数

# 线程池的分类
  1.newCachedThreadPool：创建一个可进行缓存重复利用的线程池
  2.newFixedThreadPool：创建一个可重用固定线程数的线程池，
  以共享的无界队列方式来运行这些线程，线程池中的线程处于一定的量，可以很好的控制线程的并发量
  3.newSingleThreadExecutor：创建一个使用单个 worker 线程的Executor ，
  以无界队列方式来运行该线程。线程池中最多执行一个线程，之后提交的线程将会排在队列中以此执行
  4.newSingleThreadScheduledExecutor：创建一个单线程执行程序，
  它可安排在给定延迟后运行命令或者定期执行
  5.newScheduledThreadPool：创建一个线程池，它可安排在给定延迟后运行命令或者定期的执行
  6.newWorkStealingPool：创建一个带并行级别的线程池，
  并行级别决定了同一时刻最多有多少个线程在执行，如不传并行级别参数，将默认为当前系统的CPU个数
# 线程池的核心参数
  corePoolSize：核心线程池的大小
  maximumPoolSize：线程池最大线程数
  keepAliveTime：线程空闲时存货时间
  unit：时间单位
  workQueue：任务队列：保存任务的阻塞队列
  threadFactory：创建线程的工程类
  handler：拒绝策略
# 拒绝策略
  ThreadPoolExecutor.AbortPolicy（系统默认）：丢弃任务抛异常
  ThreadPoolExecutor.DiscardPolicy：丢弃任务不抛异常
  ThreadPoolExecutor.DiscardOldestPolicy：丢弃队列中最前面的任务，然后重复执行任务
  ThreadPoolExecutor.CallerRunsPolicy：不抛弃任务不抛出异常

反射

```markdown what：反射是一种机制，利用该机制可以在程序运行过程中对类进行解剖并操作类中所有成员（成员变量，成员方法，构造方法）简单来说就是：在程序运行时操作类 why: 主要为后面的动态代理，和框架做铺垫

   作用：解耦

how:

  1. 使用反射操作类成员的前提：要获得该类字节码文件对象，就是Class对象
      Class对象的获取方式(三种方式)
          I.通过类名.class获取
              // 获得Student类对应的Class对象
              Class c1 = Student.class;
          II.通过对象名.getclass()获得
              // 创建学生对象
              Student stu = new Student();
                 // 通过getClass方法
              Class c2 = stu.getClass();
          III.通过Class类的静态方法获取：static  Class forName("类全名") 
                  每一个类的Class对象都只有一个
                   // 通过Class类的静态方法获得： static Class forName("类全名")
                   Class c3 = Class.forName("com.itheima._03反射.Student");
   2.Class类常用方法
       String getSimpleName(); 获得类名字符串：类名
       String getName();  获得类全名：包名+类名
       T newInstance() ;  创建Class对象关联类的对象

     3.反射之操作构造方法 (重要)
     4.反射之操作成员方法（重要）
     5.反射之操作成员变量

<a name="39d8ec08"></a>
# 动态代理
```markdown
动态代理（dynamic proxy）
    what: 
        1.动态：在运行时动态创建代理类对象
        2.代理：代理模式/装饰模式
          动态和静态的区别：
            I.静态代理的静态：代理类在代码运行之前写好的
            II.动态代理的动态：(反射) 代理类在代码运行时写的
          对比
            I.能用动态代理写的，都能用静态代理写
                反之，不一定成立，动态代理基于接口的
                静态代理可以基于接口，也可以基于抽象类
            II.在很多场景下，动态代理比静态代理简洁（因为程序员无需提前写代理类）
        #3.动态代理
            底层：反射
                1). 类加载器：将字节码加载进内存，jvm依次常见class
     why:
         1.装饰模式/代理模式
          在不改变原有类的前提下,增强这个类的功能
          接口 : obj和proxy要实现要相同的接口
          被代理类 obj : 实际干活的对象
          代理类 proxy : 包装obj,增强obj,实际底层操作obj干活
         2.动态代理
           Object proxy = Proxy.newProxyInstance(loader,interfaces,invocationHandler);
               1. loader 类加载器
               2. interfaces 代理类实现的接口（要跟被代理类相同）
               3. invocationHandler 代理对象被调用之后执行的方法
               return 代理类对象
      HOW：见下

动态代理如何使用

//举例：
     public static void main(String[] args) {
        //1. 创建被代理类对象 客户
        UserServiceImpl3 kehu = new UserServiceImpl3();
        /*#java代码
                 源码    ->    编译    ->   运行
                 (java类)     (class文件)    (Class对象)
                         编译器       类加载器      JVM
            1. jvm底层创建一个类,实现 interfaces 接口  (中介和代理要具备相同的父接口)
            2. 重写接口中的所有抽象方法,每个方法都调用h.invoke方法,这样一个类就写完了,生成的是字节码
            3. 最后通过loader,将字节码加载到jvm内存中,产生Class对象
            4. 最后的最后, 通过反射创建了Class对象的实例
        */
        //2. 创建代理
        /*
            原理的第一步：loader + interfaces (继承 + 反射)
                运行时：jvm底层会定义一个类，去实现interfaces中的接口
                    这个字节码是在运行时动态创建的
                loader此时加载这个字节码，jvm依次创建代理类的Class对象
                总结：loader + interfaces -> 代理类Class对象
            原理的第二步 ： InvocationHandler h (多态 + 反射)
                问题： jvm能创建类实现接口，无法预知业务重写方法
                    重写方法还是需要交给我们来实现
        */
            //被代理类对象获取自己的类加载器
        ClassLoader loader = kehu.getClass().getClassLoader();
            //获取被代理类实现的接口
        Class<?>[] interfaces = kehu.getClass().getInterfaces();
        InvocationHandler h = new InvocationHandler() {
            /*
       invoke 方法: 代理对象每调用一次方法(无论什么方法),invoke就会执行一次!!!（接口中所有的方法抽取）
             */
            /*
                代理类调用任意方法都执行invoke (接口所有方法的抽取)
                1. proxy : 当前中介,没用
                2. method : 中介当前调用的方法
                3. args : 中介当前调用方法传入的参数
                返回值 : 中介当前调用方法的返回值
             */
            @Override
            public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
                //开启事务
                SqlSession session = SqlSessionUtil.getSession(false);
                Object result = null;
                try {
                    UserDao dao = session.getMapper(UserDao.class);
                    //业务代码 (不一样)
                    // kehu.deleteUser(userId);
                    result = method.invoke(kehu, args);
                    //成功提交
                    SqlSessionUtil.commitAndClose(session);
                } catch (NumberFormatException e) {
                    SqlSessionUtil.rollbackAndClose(session);
                }
                return result;
            }
        };
        UserService proxy = (UserService) Proxy.newProxyInstance(loader, interfaces, h);
//        proxy.deleteUser("3");
//        proxy.query(null);
    };
  }