• 程序兵法:插入排序算法 Java 源版

    《程序兵法: Java 源码的插入排序算法 (二)》

    文章工程:

    一、前言

    上一讲《程序兵法:Java String 源码的排序算法(一)》讲了什么是选择问题,什么是比较能力。

    选择问题,是假设一组 N 个数,要确定其中第 K 个最大值者。算法是为求解一个问题。

    那什么是算法?
    算法是某种集合,是简单指令的集合,是被指定的简单指令集合。确定该算法重要的指标:

    • 第一是否能解决问题;
    • 第二算法运行时间,即解决问题出结果需要多少时间;
    • 还有所需的空间资源,比如内存等。

    很多时候,写一个工作程序并不够。因为遇到大数据下,运行时间就是一个重要的问题。

    算法性能用大 O 标记法表示。大 O 标记法是标记相对增长率,精度是粗糙的。比如 2N 和 3N 2 ,都是 O(N)。也就是常说的线性增长,还有常说的指数增长等

    典型的增长率

    file

    典型的提供性能做法是分治法,即分支 divide and conquer 策略:

    1. 将问题分成两个大致相等的子问题,递归地对它们求解,这是分的部分;
    2. 治阶段将两个子问题的解修补到一起,并可能再做些少量的附加工作,最后得到整个问题的解。

    file

    二、排序

    file

    排序问题,是古老,但一直流行的问题。从 ACM 接触到现在工作,每次涉及算法,或品读 JDK 源码中一些算法,经常会有排序的算法出现。

    排序算法是为了将一组数组(或序列)重新排列,排列后数据符合从大到小(或从小到大)的次序。这样数据从无序到有序,会有什么好处?

    • 应用层面:解决问题。
      • 最简单的是可以找到最大值或者最小值
      • 解决"一起性"问题,即相同标志元素连在一起
      • 匹配在两个或者更多个文件中的项目
      • 通过键码值查找信息
    • 系统层面:减少系统的熵值,增加系统的有序度
      (Donald Knuth 的经典之作《计算机程序设计艺术》(The Art of Computer Programming)的第三卷)

    通过维基百科查阅资料得到:
    在主内存中完成的排序叫做,内部排序。那需要在磁盘等其他存储完成的排序,叫做外部排序 external sorting。资料地址:https://en.wikipedia.org/wiki/External_sorting

    上一篇《程序兵法:Java String 源码的排序算法(一)》,讲到了 java.lang.Comparable 接口。那么接口是一个抽象类型,是抽象方法(compareTo)的集合,用 interface 来声明。因此被排序的对象属于 Comparable 类型,即实现 Comparable 接口,然后调用对象实现的 compareTo 方法进行比较后排序。

    在这些条件下的排序,叫作基于比较的排序(comparison-based sorting)

    三、插入排序

    白话文:熊大(一)、熊二、熊三… 按照身高从低到高排队(排序)。这时候熊 N 加入队伍,它从队伍尾巴开始比较。如果它比前面的熊身高低,则与被比较的交换位置,依次从尾巴到头部进行比较 & 交换位置。最终换到了应该熊 N 所在的位置。这就是插入排序的原理。

    插入排序(insertion sort)

    • 最简单的排序之一。ps: 冒泡排序看看就好,不推荐学习
    • 由 N - 1 次排序过程组成。
      • 如果被排序的这样一个元素,就不需要排序。即 N =1 (1 - 1 = 0)
      • 每一次排序保证,从第一个位置到当前位置的元素为已排序状态。
    • 如图:每个元素往前进行比较,并终止于自己所在的位置

    file

    /**
     * 插入排序案例
     * <p>
     * Created by 泥瓦匠@bysocket.com on 19/5/15.
     */
    public class InsertionSortingDemo {
        
        /**
         * 插入排序
         *
         * @param arr 能比较的对象数组
         * @param <T> 已排序的对象数组
         */
        public static <T extends Comparable> void insertionSort(T[] arr) {
            int j;
            
            // 从数组第二个元素开始,向前比较
            for (int p = 1; p < arr.length; p  ) {
                T tmp = arr[p];
                // 循环,向前依次比较
                // 如果比前面元素小,交换位置
                for (j = p; (j > 0) && (tmp.compareTo(arr[j - 1]) < 0); j--) {
                    arr[j] = arr[j - 1];
                }
                // 如果比前面元素大或者相等,那么这就是元素的位置,交换
                arr[j] = tmp;
            }
        }
        
        public static void main(String[] args) {
            Integer[] intArr = new Integer[] {2, 3, 1, 4, 3};
            
            System.out.println(Arrays.toString(intArr));
            insertionSort(intArr);
            System.out.println(Arrays.toString(intArr));
        }
    }
    

    代码解析如下:

    • 从数组的第二个元素,向前开始比较。比第一个元素小,则交换位置
    • 如果第二个元素比较完毕,那就第三个,第四个… 以此类推
    • 比较到最后一个元素时,完成排序

    时间复杂度是 O(N^2),最好情景的是排序已经排好的,那就是 O(N),因为满足不了循环的判断条件;最极端的是反序的数组,那就是 O(N^2)。所以该算法的时间复杂度为 O(N^2)

    运行 main 方法,结果如下:

    [2, 3, 1, 4, 3]
    [1, 2, 3, 3, 4]
    

    再考虑考虑优化,会怎么优化呢?
    插入排序优化版 不是往前比较 。往前的一半比较,二分比较会更好。具体代码,可以自行试试

    四、Array.sort 源码中的插入排序

    上面用自己实现的插入算法进行排序,其实 JDK 提供了 Array.sort 方法,方便排序。案例代码如下:

    /**
     * Arrays.sort 排序案例
     * <p>
     * Created by 泥瓦匠@bysocket.com on 19/5/28.
     */
    public class ArraysSortDemo {
        
        public static void main(String[] args) {
        
            Integer[] intArr = new Integer[] {2, 3, 1, 4, 3};
        
            System.out.println(Arrays.toString(intArr));
            Arrays.sort(intArr);
            System.out.println(Arrays.toString(intArr));
        }
    }
    

    运行 main 方法,结果如下:

    [2, 3, 1, 4, 3]
    [1, 2, 3, 3, 4]
    

    那 Arrays.sort 是如何实现的呢?JDK 1.2 的时候有了 Arrays ,JDK 1.8 时优化了一版 sort 算法。大致如下:

    • 如果元素数量小于 47,使用插入排序
    • 如果元素数量小于 286,使用快速排序
    • Timsort 算法整合了归并排序和插入排序

    file

    源码中我们看到了 mergeSort 里面整合了插入排序算法,跟上面实现的异曲同工。这边就不一行一行解释了。

    五、小结

    算法是解决问题的。所以不一定一个算法解决一个问题,可能多个算法一起解决一个问题。达到问题的最优解。插入排序,这样就这么简单

    资料:

    展开全文
  • 参考书籍:《实战JAVA高并发程序设计》本文仅用于自己参考 一、概念 同步(Synchronous)和异步(Asynchronous) 并发(Concurrency)和并行(Parallelism) 临界区 临界区用来表示一种公共资源或者说是共享数据...

    参考书籍:《实战JAVA高并发程序设计》本文仅用于自己参考
    一、概念

    • 同步(Synchronous)和异步(Asynchronous)
      在这里插入图片描述
    • 并发(Concurrency)和并行(Parallelism)
      在这里插入图片描述
    • 临界区
      临界区用来表示一种公共资源或者说是共享数据,可以被多个线程使用。但是每一次,只能有一个线程使用它,一旦临界区资源被占用,其他线程想要使用这个资源就必须等待。
    • 阻塞(Blocking)和非阻塞(Non-Blocking)
      在这里插入图片描述
    • 死锁(DeadLock)、饥饿(Starvation)和活锁(Livelock)
      死锁就是多个线程之间,相互占用对方需要的资源而都不进行释放,导致彼此之间相互等待对方释放资源,产生无限制等待的现象。
      在这里插入图片描述

    二、Java并行程序基础
    1、线程就是轻量级的进程,是程序执行的最小单位,使用多线程而不是用多线程去进行兵法程序的设计,是因为线程间的切换和调度的成本远远小于进程。
    在这里插入图片描述

    2、wait()和notify()的工作流程细节
    在这里插入图片描述

    3、volatile与java内存模型
    java内存模型具有原子性、有序性、可见性。
    通过关键字volatile来修饰的变量为共享变量,有不断被修改的风险。

    4、synchronized
    关键字synchronized的作用是实现线程间的同步,他的工作是对同步的代码加锁,使得每一次只能有一个线程进入同步块,从而保证线程间的安全性。
    关键字sychronized的用法

    • 指定加锁对象:对给定对象加锁,进入同步代码前要获得给定对象的锁
    • 直接作用于实例方法:相当于对当前实例加锁,进入同步代码前要获得当前实例的锁
    • 直接作用于静态方法:相当于对当前类加锁,进入同步代码前要获取当前类的锁

    5、ArrayList与Vector
    多线程情况下,ArrayList会导致程序出错,因为ArrayList是一个线程不安全的容器
    使用Vecotr代替ArrayList即可

    6、HashMap与ConcurrentHashMap
    HashMap同样不是线程安全的
    使用ConcurrentHashMap代替HashMap

    7、加锁问题
    多线程间,对于在变的对象加锁,会导致对临界区代码控制出现问题。
    synchronized加锁在Integer等变量上,会产生诡异问题,原因是Integer不能改变值,参考valueOf等方法,都是通过new Integer()返回的,所以针对加锁问题,应该加在同一个对象上。

    8、线程复用:线程池
    线程池中提供一定数量的线程,外部调用需要创建线城时,从线程池中获取空闲的线程;当外部使用线程完成后需要关闭线程时,只需要把线程放回线程池。JDK提供了一套Executor框架对线程进行有效的控制。java.util.concurrent包中,是JDK并发包的核心类

    三、JDK并发包
    java.util.concurrent包中
    ConcurrentHashMap:这是一个高效的并发HashMap,是一个线程安全的HashMap;
    CopyOnWriteArrayList:这是一个List,读多写少的场合,这个List性能非常好,远远好于Vector;
    ConcurrentLinkedQueue:高效的并发队列,使用链表实现,可以看做是线程安全的LinkedList;
    BlockingQueue:这是一个接口,JDK内部通过链表、数组等方式实现了这个接口,标识阻塞队列,非常适合用于作为数据共享的通道;
    ConcurrentSkipListMap:跳表的实现,这是一个map,使用跳表的数据结构进行快速查找。
    1、HashMap
    如果需要一个线程安全的HashMap,可以通过Collections.synchronizedMap()方法实现,产生一个名为SynchronizedMap的map,它使用托管,将自己所有Map相关的功能交给传入的hashMap实现,而自己则主要负责保证线程安全。
    public static Map map = Collections.synchronizedMap(new HashMap());

    一个更加专业的并发HashMap是ConcurrentHashMap,专门为并发进行了性能优化,跟适合多线程场景。

    2、List
    ArrayList 和Vector都是使用数组作为其内部实现,不同的是,Vector是线程安全的。
    LinkedList使用链表的数据结构实现了List,但也不是线程安全的,但可以通过Collections.synchonizedList()方式实现线程安全。

    3、ConcurrentLinkedQueue
    队列Queue也是常用的数据结构之一,ConcurrentLinkedQueue是用来实现高并发的队列,使用链表数据结构。

    4、CopyOnWriteArrayList
    很多场景中,读操作可能会远远大于写操作,读操作是安全的,但遇见写-写操作或者读-写操作时,并发量大的情况下就会有不一致的情况产生。CopyOnWriteArrayList类读取是完全不加锁的,写入也不会阻塞读取操作,只有写入-写入之间需要同步等待。因为在写入操作时,会进行一次自我复制。写完之后,再将复制替换原来的数据,其他线程读取会立刻察觉,因为array变量是volatile类型。

    四、并行模式与算法
    1、单例模式:一种创建对象的模式,用于产生一个对象的具体实例。确保系统中一个类只产生一个实例。
    好处1:对于频繁的使用对象,可以省略new操作花费的时间,这对于重量级对象而言,节省了一笔很可观的开销。
    好处2:由于new操作的减少,对系统内存的使用频率也会降低,这将减轻GC的压力,缩短GC停顿时间。

    不变模型:类似String类、基础类型的封装类型,使用final关键字对类进行修饰
    final修饰属性,确保属性只有一次赋值后就永远不会发生改变;
    对class进行修饰,确保了类不会有子类。

    2、生产者-消费者模式
    核心是共享内存缓存区,是生产者和消费者之间的桥梁,避免两者直接通信,对两者进行解耦。

    3、算法:
    搜索:二分法
    排序:冒泡排序(冒泡迭代排序、奇偶交换排序)、希尔排序 import java.util.concurrent.CountDownLatch;
    public class bubbleSort {

    //方法一
    public static int[] bubbleSort(int[] array) {
        Long begin = System.currentTimeMillis();
        for (int i = array.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        System.out.println(System.currentTimeMillis() - begin);
        return array;
    }
    
    //方法二:【串行】奇偶交换排序exchFlag:记录当前迭代是否发生了数据交换;start记录是奇交换还是偶交换
    public static int[] oddEventSort(int[] arr) {
        Long begin = System.currentTimeMillis();
        int exchFlag = 1, start = 0;
        while (exchFlag == 1 || start == 1) {
            exchFlag = 0;
            for (int i = start; i < arr.length - 1; i += 2) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    exchFlag = 1;
                }
            }
            if (start == 0) {
                start = 1;
            } else {
                start = 0;
            }
    
        }
        System.out.println(System.currentTimeMillis() - begin);
    
        return arr;
    }
    
    //希尔排序
    public static int[] insertSort(int[] arr){
        int length = arr.length ;
        int i , j , key ;
        for(i = 1 ; i < length ; i++){
           key = arr[i];
           j = i-1 ;
           while (j >= 0 && arr[j] > key){
               arr[j + 1] = arr[j];
               j-- ;
           }
           arr[j+1] = key ;
        }
        return arr ;
    }
    

    }

    展开全文
  • 摘要: 原创出处 ... 这是泥瓦匠的第103篇原创 《程序兵法Java String 源码的排序算法(一)》 文章工程: * JDK 1.8 * 工程名:algorithm-core-learning # StringComparisonDemo * 工程地址:https://...

    摘要: 原创出处 https://www.bysocket.com 「公众号:泥瓦匠BYSocket 」欢迎关注和转载,保留摘要,谢谢!

    这是泥瓦匠的第103篇原创

    《程序兵法:Java String 源码的排序算法(一)》

    文章工程:
    * JDK 1.8
    * 工程名:algorithm-core-learning # StringComparisonDemo
    * 工程地址:https://github.com/JeffLi1993/algorithm-core-learning

    一、前言

    Q:什么是选择问题?
    选择问题,是假设一组 N 个数,要确定其中第 K 个最大值者。比如 A 与 B 对象需要哪个更大?又比如:要考虑从一些数组中找出最大项?

    解决选择问题,需要对象有个能力,即比较任意两个对象,并确定哪个大,哪个小或者相等。找出最大项问题的解决方法,只要依次用对象的比较(Comparable)能力,循环对象列表,一次就能解决。

    那么 JDK 源码如何实现比较(Comparable)能力的呢?

    二、java.lang.Comparable 接口

     

    Comparable 接口,从 JDK 1.2 版本就有了,历史算悠久。Comparable 接口强制了实现类对象列表的排序。其排序称为自然顺序,其 compareTo 方法,称为自然比较法。

    该接口只有一个方法 public int compareTo(T o); ,可以看出

    • 入参 T o :实现该接口类,传入对应的要被比较的对象
    • 返回值 int:正数、负数和 0 ,代表大于、小于和等于

    对象的集合列表(Collection List)或者数组(arrays) ,也有对应的工具类可以方便的使用:

    • java.util.Collections#sort(List) 列表排序
    • java.util.Arrays#sort(Object[]) 数组排序

    那 String 对象如何被比较的?

    三、String 源码中的算法

    String 源码中可以看到 String JDK 1.0 就有了。那么应该是 JDK 1.2 的时候,String 类实现了 Comparable 接口,并且传入需要被比较的对象是 String。对象如图:

     

    String 是一个 final 类,无法从 String 扩展新的类。从 114 行,可以看出字符串的存储结构是字符(Char)数组。先可以看看一个字符串比较案例,代码如下:

    /**
     * 字符串比较案例
     *
     * Created by bysocket on 19/5/10.
     */
    public class StringComparisonDemo {
    
        public static void main(String[] args) {
            String foo = "ABC";
    
            // 前面和后面每个字符完全一样,返回 0
            String bar01 = "ABC";
            System.out.println(foo.compareTo(bar01));
    
            // 前面每个字符完全一样,返回:后面就是字符串长度差
            String bar02 = "ABCD";
            String bar03 = "ABCDE";
            System.out.println(foo.compareTo(bar02)); // -1 (前面相等,foo 长度小 1)
            System.out.println(foo.compareTo(bar03)); // -2 (前面相等,foo 长度小 2)
    
            // 前面每个字符不完全一样,返回:出现不一样的字符 ASCII 差
            String bar04 = "ABD";
            String bar05 = "aABCD";
            System.out.println(foo.compareTo(bar04)); // -1  (foo 的 'C' 字符 ASCII 码值为 67,bar04 的 'D' 字符 ASCII 码值为 68。返回 67 - 68 = -1)
            System.out.println(foo.compareTo(bar05)); // -32 (foo 的 'A' 字符 ASCII 码值为 65,bar04 的 'a' 字符 ASCII 码值为 97。返回 65 - 97 = -32)
    
            String bysocket01 = "泥瓦匠";
            String bysocket02 = "瓦匠";
            System.out.println(bysocket01.compareTo(bysocket02));// -2049 (泥 和 瓦的 Unicode 差值)
        }
    }
    
    

    运行结果如下:

    0
    -1
    -2
    -1
    -32
    -2049
    
    

    可以看出, compareTo 方法是按字典顺序比较两个字符串。具体比较规则可以看代码注释。比较规则如下:

    • 字符串的每个字符完全一样,返回 0
    • 字符串前面部分的每个字符完全一样,返回:后面就是两个字符串长度差
    • 字符串前面部分的每个字符存在不一样,返回:出现不一样的字符 ASCII 码的差值
      • 中文比较返回对应的 Unicode 编码值(Unicode 包含 ASCII)
      • foo 的 ‘C’ 字符 ASCII 码值为 67
      • bar04 的 ‘D’ 字符 ASCII 码值为 68。
      • foo.compareTo(bar04),返回 67 – 68 = -1
      • 常见字符 ASCII 码,如图所示

    file

    再看看 String 的 compareTo 方法如何实现字典顺序的。源码如图:

     

    源码解析如下:

    • 第 1156 行:获取当前字符串和另一个字符串,长度较小的长度值 lim
    • 第 1161 行:如果 lim 大于 0 (较小的字符串非空),则开始比较
    • 第 1164 行:当前字符串和另一个字符串,依次字符比较。如果不相等,则返回两字符的 Unicode 编码值的差值
    • 第 1169 行:当前字符串和另一个字符串,依次字符比较。如果均相等,则返回两个字符串长度的差值

    所以要排序,肯定先有比较能力,即实现 Comparable 接口。然后实现此接口的对象列表(和数组)可以通过 Collections.sort(和 Arrays.sort)进行排序。

    还有 TreeSet 使用树结构实现(红黑树),集合中的元素进行排序。其中排序就是实现 Comparable 此接口

    另外,如果没有实现 Comparable 接口,使用排序时,会抛出 java.lang.ClassCastException 异常。详细看《Java 集合:三、HashSet,TreeSet 和 LinkedHashSet比较》https://www.bysocket.com/archives/195

    四、小结

    上面也说到,这种比较其实有一定的弊端:

    • 默认 compareTo 不忽略字符大小写。如果需要忽略,则重新自定义 compareTo 方法
    • 无法进行二维的比较决策。比如判断 2 * 1 矩形和 3 * 3 矩形,哪个更大?
    • 比如有些类无法实现该接口。一个 final 类,也无法扩展新的类。其也有解决方案:函数对象(Function Object)

    方法参数:定义一个没有数据只有方法的类,并传递该类的实例。一个函数通过将其放在一个对象内部而被传递。这种对象通常叫做函数对象(Funtion Object)

    在接口方法设计中, T execute(Callback callback) 参数中使用 callback 类似。比如在 Spring 源码中,可以看出很多设计是:聚合优先于继承或者实现。这样可以减少很多继承或者实现。类似 SpringJdbcTemplate 场景设计,可以考虑到这种 Callback 设计实现。

    代码示例

    本文示例读者可以通过查看下面仓库的中: StringComparisonDemo 字符串比较案例案例:

    如果您对这些感兴趣,欢迎 star、follow、收藏、转发给予支持!

    参考资料

    • 《数据结构与算法分析:Java语言描述(原书第3版)》
    • https://en.wikipedia.org/wiki/Unicode
    • https://www.cnblogs.com/vamei/tag/%E7%AE%97%E6%B3%95/
    • https://www.bysocket.com/archives/2314/algorithm

    以下专题教程也许您会有兴趣

     
    (关注微信公众号,领取 Java 精选干货学习资料) 
    (添加我微信:bysocket01。加入纯技术交流群,成长技术)

    展开全文
  • 面试兵法——备战(二) 在上一篇文章当中,强调了备战面试需要收集的一些信息。在文章的最后,特别的强调了一下要注意招聘岗位的需求,在本文当中就让我们分析两个招聘需求,找出公司这些需求当中的要点。 案例一...

    面试兵法——备战(二)

    在上一篇文章当中,强调了备战面试需要收集的一些信息。在文章的最后,特别的强调了一下要注意招聘岗位的需求,在本文当中就让我们分析两个招聘需求,找出公司这些需求当中的要点。

    案例一:

    1)计算机或相关专业,本科及以上学历,一年以上开发经验。

    2)熟悉JspJavaJ2EEJavaScriptStrutsSpringHibernate等技术。

    3)熟悉OracleDB2sybaseinformix等大型关系型数据库的相关技术。

    4)具备良好自学能力和独立的解决问题能力,能承受一定的工作压力。

    5)具有良好而规范的编程习惯和技术文挡编写习惯。

    6)具有强烈的工作责任心、有良好的沟通能力和团队合作精神。

    7)入职地点郑州,可以接受出差安排(不能适应者勿投)。

    上面的内容是一家主营金融系统的公司所提出的“初级程序员”招聘需求。我们基本上可以讲这个招聘需求分成三个部分:

    1.     硬件条件:这个部分通常都是对学历、外语水平和开发经验的要求。如果说是应届生参见面试,最大的问题是开发经验。其实如果在需求当中要求的是一至两年的开发经验,基本可以无视。否则得话,你可能会发现没有任何的岗位适合你;

    2.     技术条件:作为Java初级程序员来说,常见的技术条件在本需求当中基本上都已经列出来了。针对这些技术,如果你有超过一半都比较熟练,那么面试时相对就比较从容了。如果大部分你听都没有听说过,那还是买些书回家好好啃吧;

    3.     软性条件:这个部分应该是最扑朔迷离的,特别是针对第一次找工作的人,更是看不明白,觉得这些需求太虚,没有什么实质性的东西。但是对于有经验的人来说,往往可以通过这些软性条件看出该公司的用人倾向。以本需求为例,从第4条和第5条来看,这个职位的人很可能要进行现场开发,也就是到客户工作的地方去完成开发任务。这样的开发工作,往往是要求程序员能够和客户进行良好的沟通,这样才能充分的理解客户的需求。同时还需要有较强的学习能力,以便能够快速的掌握客户公司当中的业务处理方法,进而使用程序来实现这些业务。有了这样的认知,就不难理解该需求当中的内容了;

    分析了这个需求之后,我们就可以制定相应面试策略。第一,重点强调自己的沟通能力。但是仅仅说自己沟通能力强还是不够的,需求拿出切实的证据。比如说可以介绍一下自己以前参加过的社会活动。例如做家教或者是在卖场进行促销工作,并强调自己在这些工作当中学习到的沟通技巧。第二,强调自己在学习能力方面的优势。比如说可以介绍自己是如何通过自学,来快速的掌握Java编程的相关知识等等。要说明自己有一套完善的自学方法,以及有持之以恒的学习耐心,这样面试官才会对你另眼相看。不能仅仅是说一句“我有很强的学习能力”,没人相信的。

    有了一定的技术作为基础,再加上适当的面试策略,就可以大大的提升面试的成功率。其实指定面试策略的方法非常简单,首先“换位思考”,分析出用人单位的需求。然后在“投其所好”,整合自己的优点,有针对性的回答面试问题。

    好了,今天就到这里吧。“休息,休息一下”!

    展开全文
  • 从数据来源或者说是操作对象角度来看,IO类可以分为: 1、文件(file): FileInputStream 、 FileOutputStream 、 FileReader、 FileWriter 2、数组([]): 2.1、 字节数组(byte[]):ByteArrayInputStream、...

    在这里插入图片描述
    从数据来源或者说是操作对象角度来看,IO类可以分为:

    • 1、文件(file): FileInputStream 、 FileOutputStream 、 FileReader、
      FileWriter
    • 2、数组([]):
    • 2.1、 字节数组(byte[]):ByteArrayInputStream、ByteArrayOutputStream
    • 2.2、字符数组(char[]):CharArrayReader、CharArrayWriter
    • 3、管道操作:PipedInputStream、PipedOutputStream、PipedReader、PipedWrited
    • 4、基本数据类型:DataInputStream、DataOutputStream
    • 、缓冲操作:BufferedInputStream、BufferdOutputStream、BufferdReader、BufferedWriter
    • 6、打印:PrintStream、PrintWriter
    • 7、对象序列化反序列化:ObjectInputStream、ObjectOutputStream
    • 8、转换:InputStreamReader、OutputStreamWriter

    从数据传输方式或者说是运输方式角度看,可以将IO类分为:

    • 1、字节流
    • 2、字符流
      字节流是以一个字节单位来运输的,比如一杯一杯的取水。而字符流是以多个字节来运输的,比如一桶一桶的取水,一桶水又可以分为几杯水。

    字节流和字符流的区别:
    字节流读取单个字节,字符流读取单个字符(一个字符根据编码的不同,对应的字节也不同,如UTF-8编码是3个字节,中文编码是2个字节。)字节流用来处理二进制文件(图片、MP3、视频文件),字符流用来处理文本文件(可以看作是特殊的额二进制文件,使用了某种编码,人可以阅读)。简而言之,字节是给计算机看的,字符才是给人看的。
    在这里插入图片描述

    IO类和相关方法
    IO类虽然很多,但最基本的是4个抽象类:InputStream、OutputStream、Reader、Writer。最基本的方法就是读read()方法,写write()方法。方法的具体实现要看继承者四个抽象类的子类。我们平时使用的也是子类对象。这些类中的一些方法都是(native)本地方法,所以没有Java源代码。

    InputStream类
    在这里插入图片描述
    在这里插入图片描述

    OutputStream类
    在这里插入图片描述

    Reader类
    在这里插入图片描述

    Writer类
    在这里插入图片描述

    使用多线程的目的是更好的利用Cpu资源。

    • 多线程:指的是这个程序(一个进程)运行时产生了不止一个线程

    • 并行与并发:

    • 并行:多个cpu实例或者多台机器同时执行一段处理逻辑,是真正的同时。

    • 并发:通过cpu调度算法,让用户看上去同时执行,实际上从cpu操作层面不是真正的同时。并发往往在场景中有公用的资源,那么针对这个公用的资源往往产生瓶颈,我们会用TPS或者QPS来反应这个系统的处理能力。
      /*
      QPS:Queries Per Second意思是“每秒查询率”,是一台服务器每秒能够相应的查询次数,是对一个特定的查询服务器在规定时间内所处理流量多少的衡量标准。
      TPS:是Transactions Per Second的缩写,也就是事务数/秒。它是软件测试结果的测量单位。一个事务是指一个客户机向服务器发送请求然后服务器做出反应的过程。客户机在发送请求时开始计时,收到服务器响应后结束计时,以此来计算使用的时间和完成的事务个数。
      */

    • 线程安全:经常用来秒回一段代码。指在并发的情况之下,该代码经过多线程使用,线程的调度顺序不会影响任何结果。在这个时候使用多线程,我们只需要关住系统的内存,cpu是不是够用即可。反过来,线程不安全就意味着线程的调度顺序会影响最终结果。

    • 同步:Java中的同步指的是通过人为的控制和调度,保证共享资源的多线程访问成为线程安全,来保证结果的尊去。在保证结果准确的同时,提高性能,才是优秀的程序。线程安全的优先级高于性能。

    线程状态:
    在这里插入图片描述

    线程状态转换:
    1.调用join()和sleep()方法,sleep()时间结束或被打断,join()中断,IO完成都会回到Runnable状态,等待JVM的调度。
    2.调用wait(),使该线程处于等待池(wait blocked pool),知道notify()/notifyAll(),线程被唤醒放到锁定池(lock blocked pool),释放同步锁线程回到可运行状态(Runnable)
    3.对Running状态的线程加同步锁(Synchronized)使其进入(lock blocked pool),同步锁被释放进入可运行状态(Runnable)
    此外,在runnable状态的线程是处于被调度的线程,此时的调度顺序是不一定的。Thread类中的yield方法可以让每一个running状态的线程转入runnable。

    Synchronized,wait,notify是任何对象都具有的同步工具。
    在这里插入图片描述
    Monitor
    他们是应用于同步问题的人工线程调度工具。讲其本质,首先要明确monitor的概念,Java的每个对象都有一个监视器,来监测并发代码的重入。在非多线程编码时该监视器不发挥作用,反之如果在synchronize范围内,监视器发挥作用。
    Wait/notify必须存在于synchronize块中。并且,这三个关键字针对的是同一个监视器(某对象的监视器)。这意味着wait之后,其他线程可以进入同步块执行。
    当某代码并不持有监视器的使用权时,(如图中5的状态,即脱离同步块)去wait或notify,会抛出java.lang.illegalMonitorStateException。也包括在synchronize块中去调用另一个对象的wait/notify,因为不同对象的监视器不同,同样会抛出此异常。

    Volatile
    多线程的内存模型:main memory(主存)、working memory(线程栈)、在处理数据时,线程会把值从主存load到本地栈,完成操作后再save回去(volatile关键词的作用:每次针对该变量的操作都激发一次load and save)
    在这里插入图片描述

    针对多线程使用的变量如果不是volatile或者final修饰的,很有可能产生不可预知的结果(另一个线程修改了这个值,但是之后再某线程看到的是修改之前的值)。其实道理上讲同一实例的同一属性本身只有一个副本。但是多线程是会缓存值的,本质上,volatile就是不去缓存,直接取值。在线程安全的情况下加volatile会牺牲性能。

    基本线程类:
    基本线程类指的是Thread类,Runnable接口,Callable接口

    Thread类相关方法:
    Thread类的相关方法:
    //当前线程可转让cpu控制权,让别的就绪状态线程运行(切换)
    Thread.yield()
    //暂停一段时间
    Thread.sleep()
    //在一个线程中调用other.join(),将等待执行完后才继续本线程
    Join()
    //后两个函数皆可被打断
    Interrupt()

    关于中断:
    它并不像stop方法那样会中断一个正在运行的线程。线程会不时地检测中断标志位,以判断线程是否应该被中断,中断只会影响到wait状态、sleep状态和join状态。被打断的线程会抛出InterruptedException。
    Thread.interrupted()检查当前线程是否发生中断,返回boolean
    Synchronize在获锁的过程中是不能被中断的。

    中断是一个状态!Interrupt()方法只是将这个状态置为true而已。所以说正常运行的程序不去检测状态,就不会终止,而wait等阻塞方法会检查并抛出异常。如果在正常运行的程序中添加while(!Thread.interruptd()),则同样在中断后离开代码体。

    Runnable
    与Thread类似

    Callable
    Future模式:并发music的一种,可以有两种形式,即无阻塞和阻塞,分别是isDone和get。其中Future对象用来存放该线程的返回值以及状态。
    在这里插入图片描述

    高级多线程控制类
    1.ThreadLocal类
    用处:保存线程的独立变量。对一个线程类(继承自Thread)
    当使用ThreadLocal维护变量时,ThreadLocal为每个使用该变量的线程提供独立的变量副本,所以每一个线程都可以独立地改变自己的副本,而不会影响其它线程所对应的副本。常用于用户登录控制,如记录session信息。
    实现:每个Thread都持有一个TreadLocalMap类型的变量(该类是一个轻量级的Map,功能与map一样,区别是桶里放的是entry而不是entry的链表。功能还是一个map。)以本身为key,以目标为value。
    主要的方法是get()和set(T a),set之后再map里维护一个threadLocal->,get时将a返回。ThreadLocal是一个特殊的容器。
    2.原子类(AtomicIntegr、AtomicBoolean…)
    如果使用atomic wrapper class如atomicInteger,或者使用自己保证原子的操作,则等同于synchronize

    在这里插入图片描述

    该方法可用于实现乐观锁,考虑文中最初提到的如下场景:a给b付款10元,a扣了10元,b要加10元。此时c给b2元,但是b加十元代码约为:
    在这里插入图片描述
    AtomicReference
    对于AtomicReference来讲,也许对象会出现,属性丢失的情况,即oldObject==current,但是OldObject.getPropertyA != current.getPropertyA。

    3.Lock类
    Lock:在java.util.concurrent包内。共有三个实现。
    ReentrantLock
    ReentrantReadWriteLock.ReadLock
    ReentrantReadWriteLock.WriteLock
    主要目的是和synchronize一样,两者都是为了解决同步问题,处理资源争端而产生的技术。功能类似但有一些区别。
    lock更灵活,可以自由定义多把锁的加锁解锁顺序(synchronized要按照先加的后解顺序)
    提供多种加锁方案,lock 阻塞式, trylock 无阻塞式, lockInterruptily 可打断式, 还有trylock的带超时时间版本。
    本质上和监视器锁(即synchronized是一样的)
    能力越大,责任越大,必须控制好加锁和解锁,否则会导致灾难。
    和Condition类的结合。
    性能更高,对比如下图:
    在这里插入图片描述
    Synchronize和Lock的性能对比

    ReentrantLock
    可重入的意义在于持有锁的线程可以继续持有,并且要释放对等的次数后才真正释放该锁。
    使用方法是:
    1.先new一个实例
    Static ReentrantLock r = new ReentrantLock();
    2.加锁
    r.lock() 或r.lockInterruptibly();
    此处也是个不同。当a线程lock后,b线程阻塞,此时如果是lockInterruptibly,那么在
    调用b.interrupt()之后,b线程退出阻塞,并放弃对资源的争抢,进入catch块。(如果使用后者,必须throw interruptable exception 或catch)
    3.释放锁
    r.unlock()
    必须做!要放在finally中,以防止异常跳出了正常流程,导致灾难。这里补充一个小知识点,finally是可以信任的:经过测试,哪怕是发生了OutofMemoryError,finally中的语句执行也能够得到保证。
    ReentrantReadWriteLock
    可重入读写锁(读写锁的一个实现)
    ReentrantReadWriterLock lock = new ReentrantReadWriterLock()
    ReadLock r = lock.readLock()
    WriteLock w = lock。WriteLock()
    两者都有lqock,unlock方法。写写,写读互斥;读读补互斥,可以实现兵法读的高效线程安全代码。
    4.容器类
    常用的两个:BlockingQueue、ConcurentHashMap
    BlockingQueue
    阻塞队列。该类是java.util.concurrent包下的重要类,通过对Queue的学习可以得知,这个queue是单向队列,可以在队列头添加元素和在队尾删除或取出元素。类似于一个管道,特别适用于先进先出策略的一些应用场景。
    BlockingQueue在队列基础上添加了多线程协作的功能。
    在这里插入图片描述
    除了传统的queue功能(表格左边的两列)之外,还提供了阻塞接口put和take,带超时功能的阻塞接口offer和poll。Put会在队列满的时候阻塞,知道有空间时被唤醒;take在队列空的时候阻塞,直到有东西拿的时候才被唤醒。
    常见的阻塞队列有:
    ArrayListBlockingQueue、LinkListBlockingQueue、DelayQueue、SynchronousQueue

    5.管理类
    管理类的概念比较泛,用于管理线程,本身不是多线程,但提供了一些机制来利用上述的工具做一些封装。
    ThreadPoolExecutor
    如果不了解该类,应该先了解ExecutorService。开启自己的线程池十分方便。
    ExecutorService e = Executors.newCachedThreadPool();
    ExecutorService e = Executors.newSingleThreadExecutor();
    ExecutorService e = Executors.newFixedThreadPool(3);
    // 第一种是可变大小线程池,按照任务数来分配线程,
    // 第二种是单线程池,相当于FixedThreadPool(1)
    // 第三种是固定大小线程池。
    // 然后运行
    e.execute(new MyRunnableImpl());
    该类内部是通过ThreadPoolExecutor实现的,掌握该类有助于理解线程池的管理,本质上,他们都是ThreadPoolExecutor类的各种实现版本。

    Java 高级特性-反射
    Java反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意方法和属性;这种动态获取信息以及动态调用对象方法的功能称为java语言的反射机制。
    用途:在日常的第三方应用开发过程中,经常会遇到某个类的某个成员变量、方法或是属性是私有的或是只对系统应用开放,这时候就可以利用Java的反射机制通过反射来获取所需的的私有成员或是方法。当然,也不是所有的都适合反射。对于没有权限的应用返回值是没有意义的缺省值,否则返回实际值起到保护用户的隐私目的。

    反射机制的相关类
    与Java反射相关的类如下:
    在这里插入图片描述

    Class类
    Class代表类的实体,在运行的Java应用程序中表示类和接口。在这个类中提供了很多有用的方法,这里对他们简单的分类介绍

    • 获取类相关的方法
      在这里插入图片描述
    • 获得类中属性相关的方法

    在这里插入图片描述

    • 获得类中注解相关的方法
      在这里插入图片描述
    • 获得类中构造器相关的方法
      在这里插入图片描述
    • 获取类中方法相关的方法
      在这里插入图片描述
    • 类中其他重要的方法
      在这里插入图片描述
      Filed类
      Field代表类的成员变量(成员变量也称为类的属性)
      在这里插入图片描述

    Method类
    Method代表类的方法
    在这里插入图片描述

    Constructor类
    Constructor代表类的构造方法
    在这里插入图片描述

    展开全文
  • 第一章初识Java1.写出Java领域的相关技术在计算机软件应用领域中,一种是安装和运行在本机上桌面程序,另一种是通过浏览器访问的面向lnternet的应用程序。2.简述Java程序中注释的作用及类型在java中常用的注释有两种...
  • java高级交流群【329019348】更多Java高级交流文章 2018/03/01 zipkin使用介绍 Spring Boot 2.0正式发布,新特性解读 区块链3.0:超越货币、经济和市场的公正应用 分布式锁的实现 架构师之路17年精选80篇 ...
  • 声明:由于学习环境为JDK1.8,所有有关Java的代码均在JDK1.8环境中测试通过,若环境发生变换,代码可能会发生错误。 本周的学习难度较上周有明显提升,今天所学习的排序算法有很多需要理解的地方,今后还需多加练习...
  • 这一年,职业生涯中的最大变化,是从.net到java的直接跨越,是从平台架构到解决方案的不断完善。 砥砺前行 初出茅庐,天下无敌。再学三年,寸步难行。很多时候不是别人太强,真的是自己太弱,却不自知。 时间从来...
  • 注:已经延期好久好久了,从去年11月份到...孙子兵法>,掌握之,能打胜仗也,今有<23种设计模式代码案列大全>,学习之,能敲出骇世惊俗的代码;不信吗,若不信的话,那是你没有真正掌握其中的思想精髓; ...
  • 在时隔一年多重新开始写博客后,我翻阅了一下以往写的博客,发现了一个非常神奇的事情——我的博客...由于我的博客是以源码阅读、设计模式等内容为主的,所以这篇文章简单谈一谈我在java的设计、抽象等方面的一点...
  • Struts2_实战演练(上) 三个准备: 1.导入Struts2库(jar包) 2.添加核心配置文件struts.xml 3.配置properties文件   准备二,配置struts2核心filter Web.xml xml version="1.0" ...
  • Android(安卓)培训 Java培训 本人信息安全专业,两年工作经验。现从事安卓应用开发。学习与从事Java语言开发4年。可帮助想学习android或者在android方面有所发展的朋友学习android,一对一教学。 与其在外面的...
  • Java语言基础一、黄蓉难倒瑛姑的数学题 看过《射雕英雄传》的朋友,一定被黄蓉的机灵鬼怪、冰雪聪明深深打动。比如黄蓉遇上神算子瑛姑,给她出的三道题目中有一题是这样的:今有物不知其数,三三数之剩二,五五数之...
  • 本文转载自公众号 码出高效面试的程序媛来源:码出高效面试文章工程:JDK 1.8工程名:algorithm-core-learning工程地址:https://gith...
1 2 3 4 5 ... 20
收藏数 733
精华内容 293
热门标签