精华内容
下载资源
问答
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的数据结构: 在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针...

    发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全,希望对大家有帮助哈~

    本套Java面试题大全,全的不能再全,哈哈~

    博主已将以下这些面试题整理成了一个Java面试手册,是PDF版的。

    关注博主的微信公众号:Java团长,然后回复“面试手册”即可获取~

    一、Java 基础

    1. JDK 和 JRE 有什么区别?

    • JDK:Java Development Kit 的简称,java 开发工具包,提供了 java 的开发环境和运行环境。
    • JRE:Java Runtime Environment 的简称,java 运行环境,为 java 的运行提供了所需环境。

    具体来说 JDK 其实包含了 JRE,同时还包含了编译 java 源码的编译器 javac,还包含了很多 java 程序调试和分析的工具。简单来说:如果你需要运行 java 程序,只需安装 JRE 就可以了,如果你需要编写 java 程序,需要安装 JDK。

    2. == 和 equals 的区别是什么?

    == 解读

    对于基本类型和引用类型 == 的作用效果是不同的,如下所示:

    • 基本类型:比较的是值是否相同;
    • 引用类型:比较的是引用是否相同;

    代码示例:

    String x = "string";
    String y = "string";
    String z = new String("string");
    System.out.println(x==y); // true
    System.out.println(x==z); // false
    System.out.println(x.equals(y)); // true
    System.out.println(x.equals(z)); // true

    代码解读:因为 x 和 y 指向的是同一个引用,所以 == 也是 true,而 new String()方法则重写开辟了内存空间,所以 == 结果为 false,而 equals 比较的一直是值,所以结果都为 true。

    equals 解读

    equals 本质上就是 ==,只不过 String 和 Integer 等重写了 equals 方法,把它变成了值比较。看下面的代码就明白了。

    首先来看默认情况下 equals 比较一个有相同值的对象,代码如下:

    class Cat {
        public Cat(String name) {
            this.name = name;
        }
    
        private String name;
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    }
    
    Cat c1 = new Cat("王磊");
    Cat c2 = new Cat("王磊");
    System.out.println(c1.equals(c2)); // false

    输出结果出乎我们的意料,竟然是 false?这是怎么回事,看了 equals 源码就知道了,源码如下:

    public boolean equals(Object obj) {
        return (this == obj);
    }

    原来 equals 本质上就是 ==。

    那问题来了,两个相同值的 String 对象,为什么返回的是 true?代码如下:

    String s1 = new String("老王");
    String s2 = new String("老王");
    System.out.println(s1.equals(s2)); // true

    同样的,当我们进入 String 的 equals 方法,找到了答案,代码如下:

    public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

    原来是 String 重写了 Object 的 equals 方法,把引用比较改成了值比较。

    总结 :== 对于基本类型来说是值比较,对于引用类型来说是比较的是引用;而 equals 默认情况下是引用比较,只是很多类重新了 equals 方法,比如 String、Integer 等把它变成了值比较,所以一般情况下 equals 比较的是值是否相等。

    3. 两个对象的 hashCode()相同,则 equals()也一定为 true,对吗?

    不对,两个对象的 hashCode()相同,equals()不一定 true。

    代码示例:

    String str1 = "通话";
    String str2 = "重地";
    System.out.println(String.format("str1:%d | str2:%d",  str1.hashCode(),str2.hashCode()));
    System.out.println(str1.equals(str2));

    执行的结果:

    str1:1179395 | str2:1179395

    false

    代码解读:很显然“通话”和“重地”的 hashCode() 相同,然而 equals() 则为 false,因为在散列表中,hashCode()相等即两个键值对的哈希值相等,然而哈希值相等,并不一定能得出键值对相等。

    4. final 在 java 中有什么作用?

    • final 修饰的类叫最终类,该类不能被继承。
    • final 修饰的方法不能被重写。
    • final 修饰的变量叫常量,常量必须初始化,初始化之后值就不能被修改。

    5. java 中的 Math.round(-1.5) 等于多少?

    等于 -1,因为在数轴上取值时,中间值(0.5)向右取整,所以正 0.5 是往上取整,负 0.5 是直接舍弃。

    6. String 属于基础的数据类型吗?

    String 不属于基础类型,基础类型有 8 种:byte、boolean、char、short、int、float、long、double,而 String 属于对象。

    7. java 中操作字符串都有哪些类?它们之间有什么区别?

    操作字符串的类有:String、StringBuffer、StringBuilder。

    String 和 StringBuffer、StringBuilder 的区别在于 String 声明的是不可变的对象,每次操作都会生成新的 String 对象,然后将指针指向新的 String 对象,而 StringBuffer、StringBuilder 可以在原有对象的基础上进行操作,所以在经常改变字符串内容的情况下最好不要使用 String。

    StringBuffer 和 StringBuilder 最大的区别在于,StringBuffer 是线程安全的,而 StringBuilder 是非线程安全的,但 StringBuilder 的性能却高于 StringBuffer,所以在单线程环境下推荐使用 StringBuilder,多线程环境下推荐使用 StringBuffer。

    8. String str="i"与 String str=new String("i")一样吗?

    不一样,因为内存的分配方式不一样。String str="i"的方式,java 虚拟机会将其分配到常量池中;而 String str=new String("i") 则会被分到堆内存中。

    9. 如何将字符串反转?

    使用 StringBuilder 或者 stringBuffer 的 reverse() 方法。

    示例代码:

    // StringBuffer reverse
    StringBuffer stringBuffer = new StringBuffer();
    stringBuffer.append("abcdefg");
    System.out.println(stringBuffer.reverse()); // gfedcba
    // StringBuilder reverse
    StringBuilder stringBuilder = new StringBuilder();
    stringBuilder.append("abcdefg");
    System.out.println(stringBuilder.reverse()); // gfedcba

    10. String 类的常用方法都有那些?

    • indexOf():返回指定字符的索引。
    • charAt():返回指定索引处的字符。
    • replace():字符串替换。
    • trim():去除字符串两端空白。
    • split():分割字符串,返回一个分割后的字符串数组。
    • getBytes():返回字符串的 byte 类型数组。
    • length():返回字符串长度。
    • toLowerCase():将字符串转成小写字母。
    • toUpperCase():将字符串转成大写字符。
    • substring():截取字符串。
    • equals():字符串比较。

    11. 抽象类必须要有抽象方法吗?

    不需要,抽象类不一定非要有抽象方法。

    示例代码:

    abstract class Cat {
        public static void sayHi() {
            System.out.println("hi~");
        }
    }

    上面代码,抽象类并没有抽象方法但完全可以正常运行。

    12. 普通类和抽象类有哪些区别?

    • 普通类不能包含抽象方法,抽象类可以包含抽象方法。
    • 抽象类不能直接实例化,普通类可以直接实例化。

    13. 抽象类能使用 final 修饰吗?

    不能,定义抽象类就是让其他类继承的,如果定义为 final 该类就不能被继承,这样彼此就会产生矛盾,所以 final 不能修饰抽象类,如下图所示,编辑器也会提示错误信息:

    14. 接口和抽象类有什么区别?

    • 实现:抽象类的子类使用 extends 来继承;接口必须使用 implements 来实现接口。
    • 构造函数:抽象类可以有构造函数;接口不能有。
    • main 方法:抽象类可以有 main 方法,并且我们能运行它;接口不能有 main 方法。
    • 实现数量:类可以实现很多个接口;但是只能继承一个抽象类。
    • 访问修饰符:接口中的方法默认使用 public 修饰;抽象类中的方法可以是任意访问修饰符。

    15. java 中 IO 流分为几种?

    按功能来分:输入流(input)、输出流(output)。

    按类型来分:字节流和字符流。

    字节流和字符流的区别是:字节流按 8 位传输以字节为单位输入输出数据,字符流按 16 位传输以字符为单位输入输出数据。

    16. BIO、NIO、AIO 有什么区别?

    • BIO:Block IO 同步阻塞式 IO,就是我们平常使用的传统 IO,它的特点是模式简单使用方便,并发处理能力低。
    • NIO:New IO 同步非阻塞 IO,是传统 IO 的升级,客户端和服务器端通过 Channel(通道)通讯,实现了多路复用。
    • AIO:Asynchronous IO 是 NIO 的升级,也叫 NIO2,实现了异步非堵塞 IO ,异步 IO 的操作基于事件和回调机制。

    17. Files的常用方法都有哪些?

    • Files.exists():检测文件路径是否存在。
    • Files.createFile():创建文件。
    • Files.createDirectory():创建文件夹。
    • Files.delete():删除一个文件或目录。
    • Files.copy():复制文件。
    • Files.move():移动文件。
    • Files.size():查看文件个数。
    • Files.read():读取文件。
    • Files.write():写入文件。

    二、容器

    18. java 容器都有哪些?

    常用容器的图录:

    19. Collection 和 Collections 有什么区别?

    • java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式,其直接继承接口有List与Set。
    • Collections则是集合类的一个工具类/帮助类,其中提供了一系列静态方法,用于对集合中元素进行排序、搜索以及线程安全等各种操作。

    20. List、Set、Map 之间的区别是什么?

    21. HashMap 和 Hashtable 有什么区别?

    • hashMap去掉了HashTable 的contains方法,但是加上了containsValue()和containsKey()方法。
    • hashTable同步的,而HashMap是非同步的,效率上逼hashTable要高。
    • hashMap允许空键值,而hashTable不允许。

    22. 如何决定使用 HashMap 还是 TreeMap?

    对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。

    23. 说一下 HashMap 的实现原理?

    HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 

    HashMap的数据结构: 在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。

    当我们往Hashmap中put元素时,首先根据key的hashcode重新计算hash值,根绝hash值得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放入链尾.如果数组中该位置没有元素,就直接将该元素放到数组的该位置上。

    需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

    24. 说一下 HashSet 的实现原理?

    • HashSet底层由HashMap实现
    • HashSet的值存放于HashMap的key上
    • HashMap的value统一为PRESENT

    25. ArrayList 和 LinkedList 的区别是什么?

    最明显的区别是 ArrrayList底层的数据结构是数组,支持随机访问,而 LinkedList 的底层数据结构是双向循环链表,不支持随机访问。使用下标访问一个元素,ArrayList 的时间复杂度是 O(1),而 LinkedList 是 O(n)。

    26. 如何实现数组和 List 之间的转换?

    • List转换成为数组:调用ArrayList的toArray方法。
    • 数组转换成为List:调用Arrays的asList方法。

    27. ArrayList 和 Vector 的区别是什么?

    • Vector是同步的,而ArrayList不是。然而,如果你寻求在迭代的时候对列表进行改变,你应该使用CopyOnWriteArrayList。 
    • ArrayList比Vector快,它因为有同步,不会过载。 
    • ArrayList更加通用,因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。

    28. Array 和 ArrayList 有何区别?

    • Array可以容纳基本类型和对象,而ArrayList只能容纳对象。 
    • Array是指定大小的,而ArrayList大小是固定的。 
    • Array没有提供ArrayList那么多功能,比如addAll、removeAll和iterator等。

    29. 在 Queue 中 poll()和 remove()有什么区别?

    poll() 和 remove() 都是从队列中取出一个元素,但是 poll() 在获取元素失败的时候会返回空,但是 remove() 失败的时候会抛出异常。

    30. 哪些集合类是线程安全的?

    • vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用。在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的。
    • statck:堆栈类,先进后出。
    • hashtable:就比hashmap多了个线程安全。
    • enumeration:枚举,相当于迭代器。

    31. 迭代器 Iterator 是什么?

    迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。

    32. Iterator 怎么使用?有什么特点?

    Java中的Iterator功能比较简单,并且只能单向移动:

    (1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。

    (2) 使用next()获得序列中的下一个元素。

    (3) 使用hasNext()检查序列中是否还有元素。

    (4) 使用remove()将迭代器新返回的元素删除。

    Iterator是Java迭代器最简单的实现,为List设计的ListIterator具有更多的功能,它可以从两个方向遍历List,也可以从List中插入和删除元素。

    33. Iterator 和 ListIterator 有什么区别?

    • Iterator可用来遍历Set和List集合,但是ListIterator只能用来遍历List。 
    • Iterator对集合只能是前向遍历,ListIterator既可以前向也可以后向。 
    • ListIterator实现了Iterator接口,并包含其他的功能,比如:增加元素,替换元素,获取前一个和后一个元素的索引,等等。

     三、多线程

    35. 并行和并发有什么区别?

    • 并行是指两个或者多个事件在同一时刻发生;而并发是指两个或多个事件在同一时间间隔发生。
    • 并行是在不同实体上的多个事件,并发是在同一实体上的多个事件。
    • 在一台处理器上“同时”处理多个任务,在多台处理器上同时处理多个任务。如hadoop分布式集群。

    所以并发编程的目标是充分的利用处理器的每一个核,以达到最高的处理性能。

    36. 线程和进程的区别?

    简而言之,进程是程序运行和资源分配的基本单位,一个程序至少有一个进程,一个进程至少有一个线程。进程在执行过程中拥有独立的内存单元,而多个线程共享内存资源,减少切换次数,从而效率更高。线程是进程的一个实体,是cpu调度和分派的基本单位,是比程序更小的能独立运行的基本单位。同一进程中的多个线程之间可以并发执行。

    37. 守护线程是什么?

    守护线程(即daemon thread),是个服务线程,准确地来说就是服务其他的线程。

    38. 创建线程有哪几种方式?

    ①. 继承Thread类创建线程类

    • 定义Thread类的子类,并重写该类的run方法,该run方法的方法体就代表了线程要完成的任务。因此把run()方法称为执行体。
    • 创建Thread子类的实例,即创建了线程对象。
    • 调用线程对象的start()方法来启动该线程。

    ②. 通过Runnable接口创建线程类

    • 定义runnable接口的实现类,并重写该接口的run()方法,该run()方法的方法体同样是该线程的线程执行体。
    • 创建 Runnable实现类的实例,并依此实例作为Thread的target来创建Thread对象,该Thread对象才是真正的线程对象。
    • 调用线程对象的start()方法来启动该线程。

    ③. 通过Callable和Future创建线程

    • 创建Callable接口的实现类,并实现call()方法,该call()方法将作为线程执行体,并且有返回值。
    • 创建Callable实现类的实例,使用FutureTask类来包装Callable对象,该FutureTask对象封装了该Callable对象的call()方法的返回值。
    • 使用FutureTask对象作为Thread对象的target创建并启动新线程。
    • 调用FutureTask对象的get()方法来获得子线程执行结束后的返回值。

    39. 说一下 runnable 和 callable 有什么区别?

    有点深的问题了,也看出一个Java程序员学习知识的广度。

    • Runnable接口中的run()方法的返回值是void,它做的事情只是纯粹地去执行run()方法中的代码而已;
    • Callable接口中的call()方法是有返回值的,是一个泛型,和Future、FutureTask配合可以用来获取异步执行的结果。

    40. 线程有哪些状态?

    线程通常都有五种状态,创建、就绪、运行、阻塞和死亡。

    • 创建状态。在生成线程对象,并没有调用该对象的start方法,这是线程处于创建状态。
    • 就绪状态。当调用了线程对象的start方法之后,该线程就进入了就绪状态,但是此时线程调度程序还没有把该线程设置为当前线程,此时处于就绪状态。在线程运行之后,从等待或者睡眠中回来之后,也会处于就绪状态。
    • 运行状态。线程调度程序将处于就绪状态的线程设置为当前线程,此时线程就进入了运行状态,开始运行run函数当中的代码。
    • 阻塞状态。线程正在运行的时候,被暂停,通常是为了等待某个时间的发生(比如说某项资源就绪)之后再继续运行。sleep,suspend,wait等方法都可以导致线程阻塞。
    • 死亡状态。如果一个线程的run方法执行结束或者调用stop方法后,该线程就会死亡。对于已经死亡的线程,无法再使用start方法令其进入就绪   

    41. sleep() 和 wait() 有什么区别?

    sleep():方法是线程类(Thread)的静态方法,让调用线程进入睡眠状态,让出执行机会给其他线程,等到休眠时间结束后,线程进入就绪状态和其他线程一起竞争cpu的执行时间。因为sleep() 是static静态的方法,他不能改变对象的机锁,当一个synchronized块中调用了sleep() 方法,线程虽然进入休眠,但是对象的机锁没有被释放,其他线程依然无法访问这个对象。

    wait():wait()是Object类的方法,当一个线程执行到wait方法时,它就进入到一个和该对象相关的等待池,同时释放对象的机锁,使得其他线程能够访问,可以通过notify,notifyAll方法来唤醒等待的线程。

    42. notify()和 notifyAll()有什么区别?

    • 如果线程调用了对象的 wait()方法,那么线程便会处于该对象的等待池中,等待池中的线程不会去竞争该对象的锁。
    • 当有线程调用了对象的 notifyAll()方法(唤醒所有 wait 线程)或 notify()方法(只随机唤醒一个 wait 线程),被唤醒的的线程便会进入该对象的锁池中,锁池中的线程会去竞争该对象锁。也就是说,调用了notify后只要一个线程会由等待池进入锁池,而notifyAll会将该对象等待池内的所有线程移动到锁池中,等待锁竞争。
    • 优先级高的线程竞争到对象锁的概率大,假若某线程没有竞争到该对象锁,它还会留在锁池中,唯有线程再次调用 wait()方法,它才会重新回到等待池中。而竞争到对象锁的线程则继续往下执行,直到执行完了 synchronized 代码块,它会释放掉该对象锁,这时锁池中的线程会继续竞争该对象锁。

    43. 线程的 run()和 start()有什么区别?

    每个线程都是通过某个特定Thread对象所对应的方法run()来完成其操作的,方法run()称为线程体。通过调用Thread类的start()方法来启动一个线程。

    start()方法来启动一个线程,真正实现了多线程运行。这时无需等待run方法体代码执行完毕,可以直接继续执行下面的代码; 这时此线程是处于就绪状态, 并没有运行。 然后通过此Thread类调用方法run()来完成其运行状态, 这里方法run()称为线程体,它包含了要执行的这个线程的内容, Run方法运行结束, 此线程终止。然后CPU再调度其它线程。

    run()方法是在本线程里的,只是线程里的一个函数,而不是多线程的。 如果直接调用run(),其实就相当于是调用了一个普通函数而已,直接待用run()方法必须等待run()方法执行完毕才能执行下面的代码,所以执行路径还是只有一条,根本就没有线程的特征,所以在多线程执行时要使用start()方法而不是run()方法。

    44. 创建线程池有哪几种方式?

    ①. newFixedThreadPool(int nThreads)

    创建一个固定长度的线程池,每当提交一个任务就创建一个线程,直到达到线程池的最大数量,这时线程规模将不再变化,当线程发生未预期的错误而结束时,线程池会补充一个新的线程。

    ②. newCachedThreadPool()

    创建一个可缓存的线程池,如果线程池的规模超过了处理需求,将自动回收空闲线程,而当需求增加时,则可以自动添加新线程,线程池的规模不存在任何限制。

    ③. newSingleThreadExecutor()

    这是一个单线程的Executor,它创建单个工作线程来执行任务,如果这个线程异常结束,会创建一个新的来替代它;它的特点是能确保依照任务在队列中的顺序来串行执行。

    ④. newScheduledThreadPool(int corePoolSize)

    创建了一个固定长度的线程池,而且以延迟或定时的方式来执行任务,类似于Timer。

    45. 线程池都有哪些状态?

    线程池有5种状态:Running、ShutDown、Stop、Tidying、Terminated。

    线程池各个状态切换框架图:

    46. 线程池中 submit()和 execute()方法有什么区别?

    • 接收的参数不一样
    • submit有返回值,而execute没有
    • submit方便Exception处理

    47. 在 java 程序中怎么保证多线程的运行安全?

    线程安全在三个方面体现:

    • 原子性:提供互斥访问,同一时刻只能有一个线程对数据进行操作,(atomic,synchronized);
    • 可见性:一个线程对主内存的修改可以及时地被其他线程看到,(synchronized,volatile);
    • 有序性:一个线程观察其他线程中的指令执行顺序,由于指令重排序,该观察结果一般杂乱无序,(happens-before原则)。

    48. 多线程锁的升级原理是什么?

    在Java中,锁共有4种状态,级别从低到高依次为:无状态锁,偏向锁,轻量级锁和重量级锁状态,这几个状态会随着竞争情况逐渐升级。锁可以升级但不能降级。

    锁升级的图示过程: 

    49. 什么是死锁?

    死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。是操作系统层面的一个错误,是进程死锁的简称,最早在 1965 年由 Dijkstra 在研究银行家算法时提出的,它是计算机操作系统乃至整个并发程序设计领域最难处理的问题之一。

    50. 怎么防止死锁?

    死锁的四个必要条件:

    • 互斥条件:进程对所分配到的资源不允许其他进程进行访问,若其他进程访问该资源,只能等待,直至占有该资源的进程使用完成后释放该资源
    • 请求和保持条件:进程获得一定的资源之后,又对其他资源发出请求,但是该资源可能被其他进程占有,此事请求阻塞,但又对自己获得的资源保持不放
    • 不可剥夺条件:是指进程已获得的资源,在未完成使用之前,不可被剥夺,只能在使用完后自己释放
    • 环路等待条件:是指进程发生死锁后,若干进程之间形成一种头尾相接的循环等待资源关系

    这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之 一不满足,就不会发生死锁。

    理解了死锁的原因,尤其是产生死锁的四个必要条件,就可以最大可能地避免、预防和 解除死锁。

    所以,在系统设计、进程调度等方面注意如何不让这四个必要条件成立,如何确 定资源的合理分配算法,避免进程永久占据系统资源。

    此外,也要防止进程在处于等待状态的情况下占用资源。因此,对资源的分配要给予合理的规划。

    51. ThreadLocal 是什么?有哪些使用场景?

    线程局部变量是局限于线程内部的变量,属于线程自身所有,不在多个线程间共享。Java提供ThreadLocal类来支持线程局部变量,是一种实现线程安全的方式。但是在管理环境下(如 web 服务器)使用线程局部变量的时候要特别小心,在这种情况下,工作线程的生命周期比任何应用变量的生命周期都要长。任何线程局部变量一旦在工作完成后没有释放,Java 应用就存在内存泄露的风险。

    52.说一下 synchronized 底层实现原理?

    synchronized可以保证方法或者代码块在运行时,同一时刻只有一个方法可以进入到临界区,同时它还可以保证共享变量的内存可见性。

    Java中每一个对象都可以作为锁,这是synchronized实现同步的基础:

    • 普通同步方法,锁是当前实例对象
    • 静态同步方法,锁是当前类的class对象
    • 同步方法块,锁是括号里面的对象

    53. synchronized 和 volatile 的区别是什么?

    • volatile本质是在告诉jvm当前变量在寄存器(工作内存)中的值是不确定的,需要从主存中读取; synchronized则是锁定当前变量,只有当前线程可以访问该变量,其他线程被阻塞住。
    • volatile仅能使用在变量级别;synchronized则可以使用在变量、方法、和类级别的。
    • volatile仅能实现变量的修改可见性,不能保证原子性;而synchronized则可以保证变量的修改可见性和原子性。
    • volatile不会造成线程的阻塞;synchronized可能会造成线程的阻塞。
    • volatile标记的变量不会被编译器优化;synchronized标记的变量可以被编译器优化。

    54. synchronized 和 Lock 有什么区别?

    • 首先synchronized是java内置关键字,在jvm层面,Lock是个java类;
    • synchronized无法判断是否获取锁的状态,Lock可以判断是否获取到锁;
    • synchronized会自动释放锁(a 线程执行完同步代码会释放锁 ;b 线程执行过程中发生异常会释放锁),Lock需在finally中手工释放锁(unlock()方法释放锁),否则容易造成线程死锁;
    • 用synchronized关键字的两个线程1和线程2,如果当前线程1获得锁,线程2线程等待。如果线程1阻塞,线程2则会一直等待下去,而Lock锁就不一定会等待下去,如果尝试获取不到锁,线程可以不用一直等待就结束了;
    • synchronized的锁可重入、不可中断、非公平,而Lock锁可重入、可判断、可公平(两者皆可);
    • Lock锁适合大量同步的代码的同步问题,synchronized锁适合代码少量的同步问题。

    55. synchronized 和 ReentrantLock 区别是什么?

    synchronized是和if、else、for、while一样的关键字,ReentrantLock是类,这是二者的本质区别。既然ReentrantLock是类,那么它就提供了比synchronized更多更灵活的特性,可以被继承、可以有方法、可以有各种各样的类变量,ReentrantLock比synchronized的扩展性体现在几点上: 

    • ReentrantLock可以对获取锁的等待时间进行设置,这样就避免了死锁 
    • ReentrantLock可以获取各种锁的信息
    • ReentrantLock可以灵活地实现多路通知 

    另外,二者的锁机制其实也是不一样的:ReentrantLock底层调用的是Unsafe的park方法加锁,synchronized操作的应该是对象头中mark word。

    56. 说一下 atomic 的原理?

    Atomic包中的类基本的特性就是在多线程环境下,当有多个线程同时对单个(包括基本类型及引用类型)变量进行操作时,具有排他性,即当多个线程同时对该变量的值进行更新时,仅有一个线程能成功,而未成功的线程可以向自旋锁一样,继续尝试,一直等到执行成功。

    Atomic系列的类中的核心方法都会调用unsafe类中的几个本地方法。我们需要先知道一个东西就是Unsafe类,全名为:sun.misc.Unsafe,这个类包含了大量的对C代码的操作,包括很多直接内存分配以及原子操作的调用,而它之所以标记为非安全的,是告诉你这个里面大量的方法调用都会存在安全隐患,需要小心使用,否则会导致严重的后果,例如在通过unsafe分配内存的时候,如果自己指定某些区域可能会导致一些类似C++一样的指针越界到其他进程的问题。


    四、反射

    57. 什么是反射?

    反射主要是指程序可以访问、检测和修改它本身状态或行为的一种能力

    Java反射:

    在Java运行时环境中,对于任意一个类,能否知道这个类有哪些属性和方法?对于任意一个对象,能否调用它的任意一个方法

    Java反射机制主要提供了以下功能:

    • 在运行时判断任意一个对象所属的类。
    • 在运行时构造任意一个类的对象。
    • 在运行时判断任意一个类所具有的成员变量和方法。
    • 在运行时调用任意一个对象的方法。 

    58. 什么是 java 序列化?什么情况下需要序列化?

    简单说就是为了保存在内存中的各种对象的状态(也就是实例变量,不是方法),并且可以把保存的对象状态再读出来。虽然你可以用你自己的各种各样的方法来保存object states,但是Java给你提供一种应该比你自己好的保存对象状态的机制,那就是序列化。

    什么情况下需要序列化:

    a)当你想把的内存中的对象状态保存到一个文件中或者数据库中时候;
    b)当你想用套接字在网络上传送对象的时候;
    c)当你想通过RMI传输对象的时候;

    59. 动态代理是什么?有哪些应用?

    动态代理:

    当想要给实现了某个接口的类中的方法,加一些额外的处理。比如说加日志,加事务等。可以给这个类创建一个代理,故名思议就是创建一个新的类,这个类不仅包含原来类方法的功能,而且还在原来的基础上添加了额外处理的新类。这个代理类并不是定义好的,是动态生成的。具有解耦意义,灵活,扩展性强。

    动态代理的应用:

    • Spring的AOP
    • 加事务
    • 加权限
    • 加日志

    60. 怎么实现动态代理?

    首先必须定义一个接口,还要有一个InvocationHandler(将实现接口的类的对象传递给它)处理类。再有一个工具类Proxy(习惯性将其称为代理类,因为调用他的newInstance()可以产生代理对象,其实他只是一个产生代理对象的工具类)。利用到InvocationHandler,拼接代理类源码,将其编译生成代理类的二进制码,利用加载器加载,并将其实例化产生代理对象,最后返回。


    五、对象拷贝

    61. 为什么要使用克隆?

    想对一个对象进行处理,又想保留原有的数据进行接下来的操作,就需要克隆了,Java语言中克隆针对的是类的实例。

    62. 如何实现对象克隆?

    有两种方式:

    1). 实现Cloneable接口并重写Object类中的clone()方法;

    2). 实现Serializable接口,通过对象的序列化和反序列化实现克隆,可以实现真正的深度克隆,代码如下:

    
    import java.io.ByteArrayInputStream;
    import java.io.ByteArrayOutputStream;
    import java.io.ObjectInputStream;
    import java.io.ObjectOutputStream;
    import java.io.Serializable;
    
    public class MyUtil {
    
        private MyUtil() {
            throw new AssertionError();
        }
    
        @SuppressWarnings("unchecked")
        public static <T extends Serializable> T clone(T obj) throws Exception {
            ByteArrayOutputStream bout = new ByteArrayOutputStream();
            ObjectOutputStream oos = new ObjectOutputStream(bout);
            oos.writeObject(obj);
    
            ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
            ObjectInputStream ois = new ObjectInputStream(bin);
            return (T) ois.readObject();
    
            // 说明:调用ByteArrayInputStream或ByteArrayOutputStream对象的close方法没有任何意义
            // 这两个基于内存的流只要垃圾回收器清理对象就能够释放资源,这一点不同于对外部资源(如文件流)的释放
        }
    }

    下面是测试代码:

    
    import java.io.Serializable;
    
    /**
     * 人类
     * @author nnngu
     *
     */
    class Person implements Serializable {
        private static final long serialVersionUID = -9102017020286042305L;
    
        private String name;    // 姓名
        private int age;        // 年龄
        private Car car;        // 座驾
    
        public Person(String name, int age, Car car) {
            this.name = name;
            this.age = age;
            this.car = car;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        public Car getCar() {
            return car;
        }
    
        public void setCar(Car car) {
            this.car = car;
        }
    
        @Override
        public String toString() {
            return "Person [name=" + name + ", age=" + age + ", car=" + car + "]";
        }
    
    }
    
    /**
     * 小汽车类
     * @author nnngu
     *
     */
    class Car implements Serializable {
        private static final long serialVersionUID = -5713945027627603702L;
    
        private String brand;       // 品牌
        private int maxSpeed;       // 最高时速
    
        public Car(String brand, int maxSpeed) {
            this.brand = brand;
            this.maxSpeed = maxSpeed;
        }
    
        public String getBrand() {
            return brand;
        }
    
        public void setBrand(String brand) {
            this.brand = brand;
        }
    
        public int getMaxSpeed() {
            return maxSpeed;
        }
    
        public void setMaxSpeed(int maxSpeed) {
            this.maxSpeed = maxSpeed;
        }
    
        @Override
        public String toString() {
            return "Car [brand=" + brand + ", maxSpeed=" + maxSpeed + "]";
        }
    
    }
    class CloneTest {
    
        public static void main(String[] args) {
            try {
                Person p1 = new Person("郭靖", 33, new Car("Benz", 300));
                Person p2 = MyUtil.clone(p1);   // 深度克隆
                p2.getCar().setBrand("BYD");
                // 修改克隆的Person对象p2关联的汽车对象的品牌属性
                // 原来的Person对象p1关联的汽车不会受到任何影响
                // 因为在克隆Person对象时其关联的汽车对象也被克隆了
                System.out.println(p1);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    注意:基于序列化和反序列化实现的克隆不仅仅是深度克隆,更重要的是通过泛型限定,可以检查出要克隆的对象是否支持序列化,这项检查是编译器完成的,不是在运行时抛出异常,这种是方案明显优于使用Object类的clone方法克隆对象。让问题在编译的时候暴露出来总是好过把问题留到运行时。

    63. 深拷贝和浅拷贝区别是什么?

    • 浅拷贝只是复制了对象的引用地址,两个对象指向同一个内存地址,所以修改其中任意的值,另一个值都会随之变化,这就是浅拷贝(例:assign())
    • 深拷贝是将对象及值复制过来,两个对象修改其中任意的值另一个值不会改变,这就是深拷贝(例:JSON.parse()和JSON.stringify(),但是此方法无法复制函数类型)

    六、Java Web

    64. jsp 和 servlet 有什么区别?

    1. jsp经编译后就变成了Servlet.(JSP的本质就是Servlet,JVM只能识别java的类,不能识别JSP的代码,Web容器将JSP的代码编译成JVM能够识别的java类)
    2. jsp更擅长表现于页面显示,servlet更擅长于逻辑控制。
    3. Servlet中没有内置对象,Jsp中的内置对象都是必须通过HttpServletRequest对象,HttpServletResponse对象以及HttpServlet对象得到。
    4. Jsp是Servlet的一种简化,使用Jsp只需要完成程序员需要输出到客户端的内容,Jsp中的Java脚本如何镶嵌到一个类中,由Jsp容器完成。而Servlet则是个完整的Java类,这个类的Service方法用于生成对客户端的响应。

    65. jsp 有哪些内置对象?作用分别是什么?

    JSP有9个内置对象:

    • request:封装客户端的请求,其中包含来自GET或POST请求的参数;
    • response:封装服务器对客户端的响应;
    • pageContext:通过该对象可以获取其他对象;
    • session:封装用户会话的对象;
    • application:封装服务器运行环境的对象;
    • out:输出服务器响应的输出流对象;
    • config:Web应用的配置对象;
    • page:JSP页面本身(相当于Java程序中的this);
    • exception:封装页面抛出异常的对象。

    66. 说一下 jsp 的 4 种作用域?

    JSP中的四种作用域包括page、request、session和application,具体来说:

    • page代表与一个页面相关的对象和属性。
    • request代表与Web客户机发出的一个请求相关的对象和属性。一个请求可能跨越多个页面,涉及多个Web组件;需要在页面显示的临时数据可以置于此作用域。
    • session代表与某个用户与服务器建立的一次会话相关的对象和属性。跟某个用户相关的数据应该放在用户自己的session中。
    • application代表与整个Web应用程序相关的对象和属性,它实质上是跨越整个Web应用程序,包括多个页面、请求和会话的一个全局作用域。

    67. session 和 cookie 有什么区别?

    • 由于HTTP协议是无状态的协议,所以服务端需要记录用户的状态时,就需要用某种机制来识具体的用户,这个机制就是Session.典型的场景比如购物车,当你点击下单按钮时,由于HTTP协议无状态,所以并不知道是哪个用户操作的,所以服务端要为特定的用户创建了特定的Session,用用于标识这个用户,并且跟踪用户,这样才知道购物车里面有几本书。这个Session是保存在服务端的,有一个唯一标识。在服务端保存Session的方法很多,内存、数据库、文件都有。集群的时候也要考虑Session的转移,在大型的网站,一般会有专门的Session服务器集群,用来保存用户会话,这个时候 Session 信息都是放在内存的,使用一些缓存服务比如Memcached之类的来放 Session。
    • 思考一下服务端如何识别特定的客户?这个时候Cookie就登场了。每次HTTP请求的时候,客户端都会发送相应的Cookie信息到服务端。实际上大多数的应用都是用 Cookie 来实现Session跟踪的,第一次创建Session的时候,服务端会在HTTP协议中告诉客户端,需要在 Cookie 里面记录一个Session ID,以后每次请求把这个会话ID发送到服务器,我就知道你是谁了。有人问,如果客户端的浏览器禁用了 Cookie 怎么办?一般这种情况下,会使用一种叫做URL重写的技术来进行会话跟踪,即每次HTTP交互,URL后面都会被附加上一个诸如 sid=xxxxx 这样的参数,服务端据此来识别用户。
    • Cookie其实还可以用在一些方便用户的场景下,设想你某次登陆过一个网站,下次登录的时候不想再次输入账号了,怎么办?这个信息可以写到Cookie里面,访问网站的时候,网站页面的脚本可以读取这个信息,就自动帮你把用户名给填了,能够方便一下用户。这也是Cookie名称的由来,给用户的一点甜头。所以,总结一下:Session是在服务端保存的一个数据结构,用来跟踪用户的状态,这个数据可以保存在集群、数据库、文件中;Cookie是客户端保存用户信息的一种机制,用来记录用户的一些信息,也是实现Session的一种方式。

    68. 说一下 session 的工作原理?

    其实session是一个存在服务器上的类似于一个散列表格的文件。里面存有我们需要的信息,在我们需要用的时候可以从里面取出来。类似于一个大号的map吧,里面的键存储的是用户的sessionid,用户向服务器发送请求的时候会带上这个sessionid。这时就可以从中取出对应的值了。

    69. 如果客户端禁止 cookie 能实现 session 还能用吗?

    Cookie与 Session,一般认为是两个独立的东西,Session采用的是在服务器端保持状态的方案,而Cookie采用的是在客户端保持状态的方案。但为什么禁用Cookie就不能得到Session呢?因为Session是用Session ID来确定当前对话所对应的服务器Session,而Session ID是通过Cookie来传递的,禁用Cookie相当于失去了Session ID,也就得不到Session了。

    假定用户关闭Cookie的情况下使用Session,其实现途径有以下几种:

    1. 设置php.ini配置文件中的“session.use_trans_sid = 1”,或者编译时打开打开了“--enable-trans-sid”选项,让PHP自动跨页传递Session ID。
    2. 手动通过URL传值、隐藏表单传递Session ID。
    3. 用文件、数据库等形式保存Session ID,在跨页过程中手动调用。

    70. spring mvc 和 struts 的区别是什么?

    • 拦截机制的不同

    Struts2是类级别的拦截,每次请求就会创建一个Action,和Spring整合时Struts2的ActionBean注入作用域是原型模式prototype,然后通过setter,getter吧request数据注入到属性。Struts2中,一个Action对应一个request,response上下文,在接收参数时,可以通过属性接收,这说明属性参数是让多个方法共享的。Struts2中Action的一个方法可以对应一个url,而其类属性却被所有方法共享,这也就无法用注解或其他方式标识其所属方法了,只能设计为多例。

    SpringMVC是方法级别的拦截,一个方法对应一个Request上下文,所以方法直接基本上是独立的,独享request,response数据。而每个方法同时又何一个url对应,参数的传递是直接注入到方法中的,是方法所独有的。处理结果通过ModeMap返回给框架。在Spring整合时,SpringMVC的Controller Bean默认单例模式Singleton,所以默认对所有的请求,只会创建一个Controller,有应为没有共享的属性,所以是线程安全的,如果要改变默认的作用域,需要添加@Scope注解修改。

    Struts2有自己的拦截Interceptor机制,SpringMVC这是用的是独立的Aop方式,这样导致Struts2的配置文件量还是比SpringMVC大。

    • 底层框架的不同

    Struts2采用Filter(StrutsPrepareAndExecuteFilter)实现,SpringMVC(DispatcherServlet)则采用Servlet实现。Filter在容器启动之后即初始化;服务停止以后坠毁,晚于Servlet。Servlet在是在调用时初始化,先于Filter调用,服务停止后销毁。

    • 性能方面

    Struts2是类级别的拦截,每次请求对应实例一个新的Action,需要加载所有的属性值注入,SpringMVC实现了零配置,由于SpringMVC基于方法的拦截,有加载一次单例模式bean注入。所以,SpringMVC开发效率和性能高于Struts2。

    • 配置方面

    spring MVC和Spring是无缝的。从这个项目的管理和安全上也比Struts2高。

    71. 如何避免 sql 注入?

    1. PreparedStatement(简单又有效的方法)
    2. 使用正则表达式过滤传入的参数
    3. 字符串过滤
    4. JSP中调用该函数检查是否包函非法字符
    5. JSP页面判断代码

    72. 什么是 XSS 攻击,如何避免?

    XSS攻击又称CSS,全称Cross Site Script  (跨站脚本攻击),其原理是攻击者向有XSS漏洞的网站中输入恶意的 HTML 代码,当用户浏览该网站时,这段 HTML 代码会自动执行,从而达到攻击的目的。XSS 攻击类似于 SQL 注入攻击,SQL注入攻击中以SQL语句作为用户输入,从而达到查询/修改/删除数据的目的,而在xss攻击中,通过插入恶意脚本,实现对用户游览器的控制,获取用户的一些信息。 XSS是 Web 程序中常见的漏洞,XSS 属于被动式且用于客户端的攻击方式。

    XSS防范的总体思路是:对输入(和URL参数)进行过滤,对输出进行编码。

    73. 什么是 CSRF 攻击,如何避免?

    CSRF(Cross-site request forgery)也被称为 one-click attack或者 session riding,中文全称是叫跨站请求伪造。一般来说,攻击者通过伪造用户的浏览器的请求,向访问一个用户自己曾经认证访问过的网站发送出去,使目标网站接收并误以为是用户的真实操作而去执行命令。常用于盗取账号、转账、发送虚假消息等。攻击者利用网站对请求的验证漏洞而实现这样的攻击行为,网站能够确认请求来源于用户的浏览器,却不能验证请求是否源于用户的真实意愿下的操作行为。

    如何避免:

    1. 验证 HTTP Referer 字段

    HTTP头中的Referer字段记录了该 HTTP 请求的来源地址。在通常情况下,访问一个安全受限页面的请求来自于同一个网站,而如果黑客要对其实施 CSRF
    攻击,他一般只能在他自己的网站构造请求。因此,可以通过验证Referer值来防御CSRF 攻击。

    2. 使用验证码

    关键操作页面加上验证码,后台收到请求后通过判断验证码可以防御CSRF。但这种方法对用户不太友好。

    3. 在请求地址中添加token并验证

    CSRF 攻击之所以能够成功,是因为黑客可以完全伪造用户的请求,该请求中所有的用户验证信息都是存在于cookie中,因此黑客可以在不知道这些验证信息的情况下直接利用用户自己的cookie 来通过安全验证。要抵御 CSRF,关键在于在请求中放入黑客所不能伪造的信息,并且该信息不存在于 cookie 之中。可以在 HTTP 请求中以参数的形式加入一个随机产生的 token,并在服务器端建立一个拦截器来验证这个 token,如果请求中没有token或者 token 内容不正确,则认为可能是 CSRF 攻击而拒绝该请求。这种方法要比检查 Referer 要安全一些,token 可以在用户登陆后产生并放于session之中,然后在每次请求时把token 从 session 中拿出,与请求中的 token 进行比对,但这种方法的难点在于如何把 token 以参数的形式加入请求。
    对于 GET 请求,token 将附在请求地址之后,这样 URL 就变成 http://url?csrftoken=tokenvalue。
    而对于 POST 请求来说,要在 form 的最后加上 <input type="hidden" name="csrftoken" value="tokenvalue"/>,这样就把token以参数的形式加入请求了。

    4. 在HTTP 头中自定义属性并验证

    这种方法也是使用 token 并进行验证,和上一种方法不同的是,这里并不是把 token 以参数的形式置于 HTTP 请求之中,而是把它放到 HTTP 头中自定义的属性里。通过 XMLHttpRequest 这个类,可以一次性给所有该类请求加上 csrftoken 这个 HTTP 头属性,并把 token 值放入其中。这样解决了上种方法在请求中加入 token 的不便,同时,通过 XMLHttpRequest 请求的地址不会被记录到浏览器的地址栏,也不用担心 token 会透过 Referer 泄露到其他网站中去。


    七、异常

    74. throw 和 throws 的区别?

    throws是用来声明一个方法可能抛出的所有异常信息,throws是将异常声明但是不处理,而是将异常往上传,谁调用我就交给谁处理。而throw则是指抛出的一个具体的异常类型。

    75. final、finally、finalize 有什么区别?

    • final可以修饰类、变量、方法,修饰类表示该类不能被继承、修饰方法表示该方法不能被重写、修饰变量表示该变量是一个常量不能被重新赋值。
    • finally一般作用在try-catch代码块中,在处理异常的时候,通常我们将一定要执行的代码方法finally代码块中,表示不管是否出现异常,该代码块都会执行,一般用来存放一些关闭资源的代码。
    • finalize是一个方法,属于Object类的一个方法,而Object类是所有类的父类,该方法一般由垃圾回收器来调用,当我们调用System的gc()方法的时候,由垃圾回收器调用finalize(),回收垃圾。 

    76. try-catch-finally 中哪个部分可以省略?

    答:catch 可以省略

    原因:

    更为严格的说法其实是:try只适合处理运行时异常,try+catch适合处理运行时异常+普通异常。也就是说,如果你只用try去处理普通异常却不加以catch处理,编译是通不过的,因为编译器硬性规定,普通异常如果选择捕获,则必须用catch显示声明以便进一步处理。而运行时异常在编译时没有如此规定,所以catch可以省略,你加上catch编译器也觉得无可厚非。

    理论上,编译器看任何代码都不顺眼,都觉得可能有潜在的问题,所以你即使对所有代码加上try,代码在运行期时也只不过是在正常运行的基础上加一层皮。但是你一旦对一段代码加上try,就等于显示地承诺编译器,对这段代码可能抛出的异常进行捕获而非向上抛出处理。如果是普通异常,编译器要求必须用catch捕获以便进一步处理;如果运行时异常,捕获然后丢弃并且+finally扫尾处理,或者加上catch捕获以便进一步处理。

    至于加上finally,则是在不管有没捕获异常,都要进行的“扫尾”处理。

    77. try-catch-finally 中,如果 catch 中 return 了,finally 还会执行吗?

    答:会执行,在 return 前执行。

    代码示例1:

    
    /*
     * java面试题--如果catch里面有return语句,finally里面的代码还会执行吗?
     */
    public class FinallyDemo2 {
        public static void main(String[] args) {
            System.out.println(getInt());
        }
    
        public static int getInt() {
            int a = 10;
            try {
                System.out.println(a / 0);
                a = 20;
            } catch (ArithmeticException e) {
                a = 30;
                return a;
                /*
                 * return a 在程序执行到这一步的时候,这里不是return a 而是 return 30;这个返回路径就形成了
                 * 但是呢,它发现后面还有finally,所以继续执行finally的内容,a=40
                 * 再次回到以前的路径,继续走return 30,形成返回路径之后,这里的a就不是a变量了,而是常量30
                 */
            } finally {
                a = 40;
            }
    
    //      return a;
        }
    }

    执行结果:30

    代码示例2:

    
    package com.java_02;
    
    /*
     * java面试题--如果catch里面有return语句,finally里面的代码还会执行吗?
     */
    public class FinallyDemo2 {
        public static void main(String[] args) {
            System.out.println(getInt());
        }
    
        public static int getInt() {
            int a = 10;
            try {
                System.out.println(a / 0);
                a = 20;
            } catch (ArithmeticException e) {
                a = 30;
                return a;
                /*
                 * return a 在程序执行到这一步的时候,这里不是return a 而是 return 30;这个返回路径就形成了
                 * 但是呢,它发现后面还有finally,所以继续执行finally的内容,a=40
                 * 再次回到以前的路径,继续走return 30,形成返回路径之后,这里的a就不是a变量了,而是常量30
                 */
            } finally {
                a = 40;
                return a; //如果这样,就又重新形成了一条返回路径,由于只能通过1个return返回,所以这里直接返回40
            }
    
    //      return a;
        }
    }

    执行结果:40

    78. 常见的异常类有哪些?

    • NullPointerException:当应用程序试图访问空对象时,则抛出该异常。
    • SQLException:提供关于数据库访问错误或其他错误信息的异常。
    • IndexOutOfBoundsException:指示某排序索引(例如对数组、字符串或向量的排序)超出范围时抛出。 
    • NumberFormatException:当应用程序试图将字符串转换成一种数值类型,但该字符串不能转换为适当格式时,抛出该异常。
    • FileNotFoundException:当试图打开指定路径名表示的文件失败时,抛出此异常。
    • IOException:当发生某种I/O异常时,抛出此异常。此类是失败或中断的I/O操作生成的异常的通用类。
    • ClassCastException:当试图将对象强制转换为不是实例的子类时,抛出该异常。
    • ArrayStoreException:试图将错误类型的对象存储到一个对象数组时抛出的异常。
    • IllegalArgumentException:抛出的异常表明向方法传递了一个不合法或不正确的参数。
    • ArithmeticException:当出现异常的运算条件时,抛出此异常。例如,一个整数“除以零”时,抛出此类的一个实例。 
    • NegativeArraySizeException:如果应用程序试图创建大小为负的数组,则抛出该异常。
    • NoSuchMethodException:无法找到某一特定方法时,抛出该异常。
    • SecurityException:由安全管理器抛出的异常,指示存在安全侵犯。
    • UnsupportedOperationException:当不支持请求的操作时,抛出该异常。
    • RuntimeExceptionRuntimeException:是那些可能在Java虚拟机正常运行期间抛出的异常的超类。

    八、网络

    79. http 响应码 301 和 302 代表的是什么?有什么区别?

    答:301,302 都是HTTP状态的编码,都代表着某个URL发生了转移。

    区别: 

    • 301 redirect: 301 代表永久性转移(Permanently Moved)。
    • 302 redirect: 302 代表暂时性转移(Temporarily Moved )。 

    80. forward 和 redirect 的区别?

    Forward和Redirect代表了两种请求转发方式:直接转发和间接转发。

    直接转发方式(Forward),客户端和浏览器只发出一次请求,Servlet、HTML、JSP或其它信息资源,由第二个信息资源响应该请求,在请求对象request中,保存的对象对于每个信息资源是共享的。

    间接转发方式(Redirect)实际是两次HTTP请求,服务器端在响应第一次请求的时候,让浏览器再向另外一个URL发出请求,从而达到转发的目的。

    举个通俗的例子:

    直接转发就相当于:“A找B借钱,B说没有,B去找C借,借到借不到都会把消息传递给A”;

    间接转发就相当于:"A找B借钱,B说没有,让A去找C借"。

    81. 简述 tcp 和 udp的区别?

    • TCP面向连接(如打电话要先拨号建立连接);UDP是无连接的,即发送数据之前不需要建立连接。
    • TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保证可靠交付。
    • Tcp通过校验和,重传控制,序号标识,滑动窗口、确认应答实现可靠传输。如丢包时的重发控制,还可以对次序乱掉的分包进行顺序控制。
    • UDP具有较好的实时性,工作效率比TCP高,适用于对高速传输和实时性有较高的通信或广播通信。
    • 每一条TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信。
    • TCP对系统资源要求较多,UDP对系统资源要求较少。

    82. tcp 为什么要三次握手,两次不行吗?为什么?

    为了实现可靠数据传输, TCP 协议的通信双方, 都必须维护一个序列号, 以标识发送出去的数据包中, 哪些是已经被对方收到的。 三次握手的过程即是通信双方相互告知序列号起始值, 并确认对方已经收到了序列号起始值的必经步骤。

    如果只是两次握手, 至多只有连接发起方的起始序列号能被确认, 另一方选择的序列号则得不到确认。

    83. 说一下 tcp 粘包是怎么产生的?

    ①. 发送方产生粘包

    采用TCP协议传输数据的客户端与服务器经常是保持一个长连接的状态(一次连接发一次数据不存在粘包),双方在连接不断开的情况下,可以一直传输数据;但当发送的数据包过于的小时,那么TCP协议默认的会启用Nagle算法,将这些较小的数据包进行合并发送(缓冲区数据发送是一个堆压的过程);这个合并过程就是在发送缓冲区中进行的,也就是说数据发送出来它已经是粘包的状态了。

    ②. 接收方产生粘包

    接收方采用TCP协议接收数据时的过程是这样的:数据到底接收方,从网络模型的下方传递至传输层,传输层的TCP协议处理是将其放置接收缓冲区,然后由应用层来主动获取(C语言用recv、read等函数);这时会出现一个问题,就是我们在程序中调用的读取数据函数不能及时的把缓冲区中的数据拿出来,而下一个数据又到来并有一部分放入的缓冲区末尾,等我们读取数据时就是一个粘包。(放数据的速度 > 应用层拿数据速度) 

    84. OSI 的七层模型都有哪些?

    1. 应用层:网络服务与最终用户的一个接口。
    2. 表示层:数据的表示、安全、压缩。
    3. 会话层:建立、管理、终止会话。
    4. 传输层:定义传输数据的协议端口号,以及流控和差错校验。
    5. 网络层:进行逻辑地址寻址,实现不同网络之间的路径选择。
    6. 数据链路层:建立逻辑连接、进行硬件地址寻址、差错校验等功能。
    7. 物理层:建立、维护、断开物理连接。

    85. get 和 post 请求有哪些区别?

    • GET在浏览器回退时是无害的,而POST会再次提交请求。
    • GET产生的URL地址可以被Bookmark,而POST不可以。
    • GET请求会被浏览器主动cache,而POST不会,除非手动设置。
    • GET请求只能进行url编码,而POST支持多种编码方式。
    • GET请求参数会被完整保留在浏览器历史记录里,而POST中的参数不会被保留。
    • GET请求在URL中传送的参数是有长度限制的,而POST么有。
    • 对参数的数据类型,GET只接受ASCII字符,而POST没有限制。
    • GET比POST更不安全,因为参数直接暴露在URL上,所以不能用来传递敏感信息。
    • GET参数通过URL传递,POST放在Request body中。

    86. 如何实现跨域?

    方式一:图片ping或script标签跨域

    图片ping常用于跟踪用户点击页面或动态广告曝光次数。 
    script标签可以得到从其他来源数据,这也是JSONP依赖的根据。 

    方式二:JSONP跨域

    JSONP(JSON with Padding)是数据格式JSON的一种“使用模式”,可以让网页从别的网域要数据。根据 XmlHttpRequest 对象受到同源策略的影响,而利用 <script>元素的这个开放策略,网页可以得到从其他来源动态产生的JSON数据,而这种使用模式就是所谓的 JSONP。用JSONP抓到的数据并不是JSON,而是任意的JavaScript,用 JavaScript解释器运行而不是用JSON解析器解析。所有,通过Chrome查看所有JSONP发送的Get请求都是js类型,而非XHR。 

    缺点:

    • 只能使用Get请求
    • 不能注册success、error等事件监听函数,不能很容易的确定JSONP请求是否失败
    • JSONP是从其他域中加载代码执行,容易受到跨站请求伪造的攻击,其安全性无法确保

    方式三:CORS

    Cross-Origin Resource Sharing(CORS)跨域资源共享是一份浏览器技术的规范,提供了 Web 服务从不同域传来沙盒脚本的方法,以避开浏览器的同源策略,确保安全的跨域数据传输。现代浏览器使用CORS在API容器如XMLHttpRequest来减少HTTP请求的风险来源。与 JSONP 不同,CORS 除了 GET 要求方法以外也支持其他的 HTTP 要求。服务器一般需要增加如下响应头的一种或几种:

    Access-Control-Allow-Origin: *
    Access-Control-Allow-Methods: POST, GET, OPTIONS
    Access-Control-Allow-Headers: X-PINGOTHER, Content-Type
    Access-Control-Max-Age: 86400

    跨域请求默认不会携带Cookie信息,如果需要携带,请配置下述参数:

    "Access-Control-Allow-Credentials": true
    // Ajax设置
    "withCredentials": true

    方式四:window.name+iframe

    window.name通过在iframe(一般动态创建i)中加载跨域HTML文件来起作用。然后,HTML文件将传递给请求者的字符串内容赋值给window.name。然后,请求者可以检索window.name值作为响应。

    • iframe标签的跨域能力;
    • window.name属性值在文档刷新后依旧存在的能力(且最大允许2M左右)。

    每个iframe都有包裹它的window,而这个window是top window的子窗口。contentWindow属性返回<iframe>元素的Window对象。你可以使用这个Window对象来访问iframe的文档及其内部DOM。

    <!-- 
     下述用端口 
     10000表示:domainA
     10001表示:domainB
    -->
    
    <!-- localhost:10000 -->
    <script>
      var iframe = document.createElement('iframe');
      iframe.style.display = 'none'; // 隐藏
    
      var state = 0; // 防止页面无限刷新
      iframe.onload = function() {
          if(state === 1) {
              console.log(JSON.parse(iframe.contentWindow.name));
              // 清除创建的iframe
              iframe.contentWindow.document.write('');
              iframe.contentWindow.close();
              document.body.removeChild(iframe);
          } else if(state === 0) {
              state = 1;
              // 加载完成,指向当前域,防止错误(proxy.html为空白页面)
              // Blocked a frame with origin "http://localhost:10000" from accessing a cross-origin frame.
              iframe.contentWindow.location = 'http://localhost:10000/proxy.html';
          }
      };
    
      iframe.src = 'http://localhost:10001';
      document.body.appendChild(iframe);
    </script>
    
    <!-- localhost:10001 -->
    <!DOCTYPE html>
    ...
    <script>
      window.name = JSON.stringify({a: 1, b: 2});
    </script>
    </html>
    

    方式五:window.postMessage()

    HTML5新特性,可以用来向其他所有的 window 对象发送消息。需要注意的是我们必须要保证所有的脚本执行完才发送 MessageEvent,如果在函数执行的过程中调用了它,就会让后面的函数超时无法执行。

    下述代码实现了跨域存储localStorage

    <!-- 
     下述用端口 
     10000表示:domainA
     10001表示:domainB
    -->
    
    <!-- localhost:10000 -->
    <iframe src="http://localhost:10001/msg.html" name="myPostMessage" style="display:none;">
    </iframe>
    
    <script>
      function main() {
          LSsetItem('test', 'Test: ' + new Date());
          LSgetItem('test', function(value) {
              console.log('value: ' + value);
          });
          LSremoveItem('test');
      }
    
      var callbacks = {};
      window.addEventListener('message', function(event) {
          if (event.source === frames['myPostMessage']) {
              console.log(event)
              var data = /^#localStorage#(\d+)(null)?#([\S\s]*)/.exec(event.data);
              if (data) {
                  if (callbacks[data[1]]) {
                      callbacks[data[1]](data[2] === 'null' ? null : data[3]);
                  }
                  delete callbacks[data[1]];
              }
          }
      }, false);
    
      var domain = '*';
      // 增加
      function LSsetItem(key, value) {
          var obj = {
              setItem: key,
              value: value
          };
          frames['myPostMessage'].postMessage(JSON.stringify(obj), domain);
      }
      // 获取
      function LSgetItem(key, callback) {
          var identifier = new Date().getTime();
          var obj = {
              identifier: identifier,
              getItem: key
          };
          callbacks[identifier] = callback;
          frames['myPostMessage'].postMessage(JSON.stringify(obj), domain);
      }
      // 删除
      function LSremoveItem(key) {
          var obj = {
              removeItem: key
          };
          frames['myPostMessage'].postMessage(JSON.stringify(obj), domain);
      }
    </script>
    
    <!-- localhost:10001 -->
    <script>
      window.addEventListener('message', function(event) {
        console.log('Receiver debugging', event);
        if (event.origin == 'http://localhost:10000') {
          var data = JSON.parse(event.data);
          if ('setItem' in data) {
            localStorage.setItem(data.setItem, data.value);
          } else if ('getItem' in data) {
            var gotItem = localStorage.getItem(data.getItem);
            event.source.postMessage(
              '#localStorage#' + data.identifier +
              (gotItem === null ? 'null#' : '#' + gotItem),
              event.origin
            );
          } else if ('removeItem' in data) {
            localStorage.removeItem(data.removeItem);
          }
        }
      }, false);
    </script>

    注意Safari一下,会报错:

    Blocked a frame with origin “http://localhost:10001” from accessing a frame with origin “http://localhost:10000“. Protocols, domains, and ports must match.

    避免该错误,可以在Safari浏览器中勾选开发菜单==>停用跨域限制。或者只能使用服务器端转存的方式实现,因为Safari浏览器默认只支持CORS跨域请求。

    方式六:修改document.domain跨子域

    前提条件:这两个域名必须属于同一个基础域名!而且所用的协议,端口都要一致,否则无法利用document.domain进行跨域,所以只能跨子域

    在根域范围内,允许把domain属性的值设置为它的上一级域。例如,在”aaa.xxx.com”域内,可以把domain设置为 “xxx.com” 但不能设置为 “xxx.org” 或者”com”。

    现在存在两个域名aaa.xxx.com和bbb.xxx.com。在aaa下嵌入bbb的页面,由于其document.name不一致,无法在aaa下操作bbb的js。可以在aaa和bbb下通过js将document.name = 'xxx.com';设置一致,来达到互相访问的作用。

    方式七:WebSocket

    WebSocket protocol 是HTML5一种新的协议。它实现了浏览器与服务器全双工通信,同时允许跨域通讯,是server push技术的一种很棒的实现。相关文章,请查看:WebSocket、WebSocket-SockJS

    需要注意:WebSocket对象不支持DOM 2级事件侦听器,必须使用DOM 0级语法分别定义各个事件。

    方式八:代理

    同源策略是针对浏览器端进行的限制,可以通过服务器端来解决该问题

    DomainA客户端(浏览器) ==> DomainA服务器 ==> DomainB服务器 ==> DomainA客户端(浏览器)

    来源:blog.csdn.net/ligang2585116/article/details/73072868

    87.说一下 JSONP 实现原理?

    jsonp 即 json+padding,动态创建script标签,利用script标签的src属性可以获取任何域下的js脚本,通过这个特性(也可以说漏洞),服务器端不在返货json格式,而是返回一段调用某个函数的js代码,在src中进行了调用,这样实现了跨域。


    九、设计模式

    88. 说一下你熟悉的设计模式?

    参考:常用的设计模式汇总,超详细!

    89. 简单工厂和抽象工厂有什么区别?

    简单工厂模式

    这个模式本身很简单而且使用在业务较简单的情况下。一般用于小项目或者具体产品很少扩展的情况(这样工厂类才不用经常更改)。

    它由三种角色组成:

    • 工厂类角色:这是本模式的核心,含有一定的商业逻辑和判断逻辑,根据逻辑不同,产生具体的工厂产品。如例子中的Driver类。
    • 抽象产品角色:它一般是具体产品继承的父类或者实现的接口。由接口或者抽象类来实现。如例中的Car接口。
    • 具体产品角色:工厂类所创建的对象就是此角色的实例。在java中由一个具体类实现,如例子中的Benz、Bmw类。

    来用类图来清晰的表示下的它们之间的关系:

    抽象工厂模式:

    先来认识下什么是产品族: 位于不同产品等级结构中,功能相关联的产品组成的家族。

    图中的BmwCar和BenzCar就是两个产品树(产品层次结构);而如图所示的BenzSportsCar和BmwSportsCar就是一个产品族。他们都可以放到跑车家族中,因此功能有所关联。同理BmwBussinessCar和BenzBusinessCar也是一个产品族。

    可以这么说,它和工厂方法模式的区别就在于需要创建对象的复杂程度上。而且抽象工厂模式是三个里面最为抽象、最具一般性的。抽象工厂模式的用意为:给客户端提供一个接口,可以创建多个产品族中的产品对象。

    而且使用抽象工厂模式还要满足一下条件:

    1. 系统中有多个产品族,而系统一次只可能消费其中一族产品
    2. 同属于同一个产品族的产品以其使用。

    来看看抽象工厂模式的各个角色(和工厂方法的如出一辙):

    • 抽象工厂角色: 这是工厂方法模式的核心,它与应用程序无关。是具体工厂角色必须实现的接口或者必须继承的父类。在java中它由抽象类或者接口来实现。
    • 具体工厂角色:它含有和具体业务逻辑有关的代码。由应用程序调用以创建对应的具体产品的对象。在java中它由具体的类来实现。
    • 抽象产品角色:它是具体产品继承的父类或者是实现的接口。在java中一般有抽象类或者接口来实现。
    • 具体产品角色:具体工厂角色所创建的对象就是此角色的实例。在java中由具体的类来实现。

    十、Spring / Spring MVC

    90. 为什么要使用 spring?

    1.简介

    • 目的:解决企业应用开发的复杂性
    • 功能:使用基本的JavaBean代替EJB,并提供了更多的企业应用功能
    • 范围:任何Java应用

    简单来说,Spring是一个轻量级的控制反转(IoC)和面向切面(AOP)的容器框架。

    2.轻量 

    从大小与开销两方面而言Spring都是轻量的。完整的Spring框架可以在一个大小只有1MB多的JAR文件里发布。并且Spring所需的处理开销也是微不足道的。此外,Spring是非侵入式的:典型地,Spring应用中的对象不依赖于Spring的特定类。

    3.控制反转  

    Spring通过一种称作控制反转(IoC)的技术促进了松耦合。当应用了IoC,一个对象依赖的其它对象会通过被动的方式传递进来,而不是这个对象自己创建或者查找依赖对象。你可以认为IoC与JNDI相反——不是对象从容器中查找依赖,而是容器在对象初始化时不等对象请求就主动将依赖传递给它。

    4.面向切面  

    Spring提供了面向切面编程的丰富支持,允许通过分离应用的业务逻辑与系统级服务(例如审计(auditing)和事务(transaction)管理)进行内聚性的开发。应用对象只实现它们应该做的——完成业务逻辑——仅此而已。它们并不负责(甚至是意识)其它的系统级关注点,例如日志或事务支持。

    5.容器

    Spring包含并管理应用对象的配置和生命周期,在这个意义上它是一种容器,你可以配置你的每个bean如何被创建——基于一个可配置原型(prototype),你的bean可以创建一个单独的实例或者每次需要时都生成一个新的实例——以及它们是如何相互关联的。然而,Spring不应该被混同于传统的重量级的EJB容器,它们经常是庞大与笨重的,难以使用。

    6.框架

    Spring可以将简单的组件配置、组合成为复杂的应用。在Spring中,应用对象被声明式地组合,典型地是在一个XML文件里。Spring也提供了很多基础功能(事务管理、持久化框架集成等等),将应用逻辑的开发留给了你。

    所有Spring的这些特征使你能够编写更干净、更可管理、并且更易于测试的代码。它们也为Spring中的各种模块提供了基础支持。

    91. 解释一下什么是 aop?

    AOP(Aspect-Oriented Programming,面向方面编程),可以说是OOP(Object-Oriented Programing,面向对象编程)的补充和完善。OOP引入封装、继承和多态性等概念来建立一种对象层次结构,用以模拟公共行为的一个集合。当我们需要为分散的对象引入公共行为的时候,OOP则显得无能为力。也就是说,OOP允许你定义从上到下的关系,但并不适合定义从左到右的关系。例如日志功能。日志代码往往水平地散布在所有对象层次中,而与它所散布到的对象的核心功能毫无关系。对于其他类型的代码,如安全性、异常处理和透明的持续性也是如此。这种散布在各处的无关的代码被称为横切(cross-cutting)代码,在OOP设计中,它导致了大量代码的重复,而不利于各个模块的重用。

    而AOP技术则恰恰相反,它利用一种称为“横切”的技术,剖解开封装的对象内部,并将那些影响了多个类的公共行为封装到一个可重用模块,并将其名为“Aspect”,即方面。所谓“方面”,简单地说,就是将那些与业务无关,却为业务模块所共同调用的逻辑或责任封装起来,便于减少系统的重复代码,降低模块间的耦合度,并有利于未来的可操作性和可维护性。AOP代表的是一个横向的关系,如果说“对象”是一个空心的圆柱体,其中封装的是对象的属性和行为;那么面向方面编程的方法,就仿佛一把利刃,将这些空心圆柱体剖开,以获得其内部的消息。而剖开的切面,也就是所谓的“方面”了。然后它又以巧夺天功的妙手将这些剖开的切面复原,不留痕迹。

    使用“横切”技术,AOP把软件系统分为两个部分:核心关注点和横切关注点。业务处理的主要流程是核心关注点,与之关系不大的部分是横切关注点。横切关注点的一个特点是,他们经常发生在核心关注点的多处,而各处都基本相似。比如权限认证、日志、事务处理。Aop 的作用在于分离系统中的各种关注点,将核心关注点和横切关注点分离开来。正如Avanade公司的高级方案构架师Adam Magee所说,AOP的核心思想就是“将应用程序中的商业逻辑同对其提供支持的通用服务进行分离。”

    92. 解释一下什么是 ioc?

    IOC是Inversion of Control的缩写,多数书籍翻译成“控制反转”。

    1996年,Michael Mattson在一篇有关探讨面向对象框架的文章中,首先提出了IOC 这个概念。对于面向对象设计及编程的基本思想,前面我们已经讲了很多了,不再赘述,简单来说就是把复杂系统分解成相互合作的对象,这些对象类通过封装以后,内部实现对外部是透明的,从而降低了解决问题的复杂度,而且可以灵活地被重用和扩展。

    IOC理论提出的观点大体是这样的:借助于“第三方”实现具有依赖关系的对象之间的解耦。如下图:

    大家看到了吧,由于引进了中间位置的“第三方”,也就是IOC容器,使得A、B、C、D这4个对象没有了耦合关系,齿轮之间的传动全部依靠“第三方”了,全部对象的控制权全部上缴给“第三方”IOC容器,所以,IOC容器成了整个系统的关键核心,它起到了一种类似“粘合剂”的作用,把系统中的所有对象粘合在一起发挥作用,如果没有这个“粘合剂”,对象与对象之间会彼此失去联系,这就是有人把IOC容器比喻成“粘合剂”的由来。

    我们再来做个试验:把上图中间的IOC容器拿掉,然后再来看看这套系统:

    我们现在看到的画面,就是我们要实现整个系统所需要完成的全部内容。这时候,A、B、C、D这4个对象之间已经没有了耦合关系,彼此毫无联系,这样的话,当你在实现A的时候,根本无须再去考虑B、C和D了,对象之间的依赖关系已经降低到了最低程度。所以,如果真能实现IOC容器,对于系统开发而言,这将是一件多么美好的事情,参与开发的每一成员只要实现自己的类就可以了,跟别人没有任何关系!

    我们再来看看,控制反转(IOC)到底为什么要起这么个名字?我们来对比一下:

    软件系统在没有引入IOC容器之前,如图1所示,对象A依赖于对象B,那么对象A在初始化或者运行到某一点的时候,自己必须主动去创建对象B或者使用已经创建的对象B。无论是创建还是使用对象B,控制权都在自己手上。

    软件系统在引入IOC容器之后,这种情形就完全改变了,如图3所示,由于IOC容器的加入,对象A与对象B之间失去了直接联系,所以,当对象A运行到需要对象B的时候,IOC容器会主动创建一个对象B注入到对象A需要的地方。

    通过前后的对比,我们不难看出来:对象A获得依赖对象B的过程,由主动行为变为了被动行为,控制权颠倒过来了,这就是“控制反转”这个名称的由来。

    93. spring 有哪些主要模块?

    Spring框架至今已集成了20多个模块。这些模块主要被分如下图所示的核心容器、数据访问/集成,、Web、AOP(面向切面编程)、工具、消息和测试模块。

    更多信息:howtodoinjava.com/java-spring-framework-tutorials/

    94. spring 常用的注入方式有哪些?

    Spring通过DI(依赖注入)实现IOC(控制反转),常用的注入方式主要有三种:

    1. 构造方法注入
    2. setter注入
    3. 基于注解的注入

    95. spring 中的 bean 是线程安全的吗?

    Spring容器中的Bean是否线程安全,容器本身并没有提供Bean的线程安全策略,因此可以说spring容器中的Bean本身不具备线程安全的特性,但是具体还是要结合具体scope的Bean去研究。

    96. spring 支持几种 bean 的作用域?

    当通过spring容器创建一个Bean实例时,不仅可以完成Bean实例的实例化,还可以为Bean指定特定的作用域。Spring支持如下5种作用域:

    • singleton:单例模式,在整个Spring IoC容器中,使用singleton定义的Bean将只有一个实例
    • prototype:原型模式,每次通过容器的getBean方法获取prototype定义的Bean时,都将产生一个新的Bean实例
    • request:对于每次HTTP请求,使用request定义的Bean都将产生一个新实例,即每次HTTP请求将会产生不同的Bean实例。只有在Web应用中使用Spring时,该作用域才有效
    • session:对于每次HTTP Session,使用session定义的Bean豆浆产生一个新实例。同样只有在Web应用中使用Spring时,该作用域才有效
    • globalsession:每个全局的HTTP Session,使用session定义的Bean都将产生一个新实例。典型情况下,仅在使用portlet context的时候有效。同样只有在Web应用中使用Spring时,该作用域才有效

    其中比较常用的是singleton和prototype两种作用域。对于singleton作用域的Bean,每次请求该Bean都将获得相同的实例。容器负责跟踪Bean实例的状态,负责维护Bean实例的生命周期行为;如果一个Bean被设置成prototype作用域,程序每次请求该id的Bean,Spring都会新建一个Bean实例,然后返回给程序。在这种情况下,Spring容器仅仅使用new 关键字创建Bean实例,一旦创建成功,容器不在跟踪实例,也不会维护Bean实例的状态。

    如果不指定Bean的作用域,Spring默认使用singleton作用域。Java在创建Java实例时,需要进行内存申请;销毁实例时,需要完成垃圾回收,这些工作都会导致系统开销的增加。因此,prototype作用域Bean的创建、销毁代价比较大。而singleton作用域的Bean实例一旦创建成功,可以重复使用。因此,除非必要,否则尽量避免将Bean被设置成prototype作用域。

    97. spring 自动装配 bean 有哪些方式?

    Spring容器负责创建应用程序中的bean同时通过ID来协调这些对象之间的关系。作为开发人员,我们需要告诉Spring要创建哪些bean并且如何将其装配到一起。

    spring中bean装配有两种方式:

    • 隐式的bean发现机制和自动装配
    • 在java代码或者XML中进行显示配置

    当然这些方式也可以配合使用。

    98. spring 事务实现方式有哪些?

    1. 编程式事务管理对基于 POJO 的应用来说是唯一选择。我们需要在代码中调用beginTransaction()、commit()、rollback()等事务管理相关的方法,这就是编程式事务管理。
    2. 基于 TransactionProxyFactoryBean 的声明式事务管理
    3. 基于 @Transactional 的声明式事务管理
    4. 基于 Aspectj AOP 配置事务

    99. 说一下 spring 的事务隔离?

    事务隔离级别指的是一个事务对数据的修改与另一个并行的事务的隔离程度,当多个事务同时访问相同数据时,如果没有采取必要的隔离机制,就可能发生以下问题:

    • 脏读:一个事务读到另一个事务未提交的更新数据。
    • 幻读:例如第一个事务对一个表中的数据进行了修改,比如这种修改涉及到表中的“全部数据行”。同时,第二个事务也修改这个表中的数据,这种修改是向表中插入“一行新数据”。那么,以后就会发生操作第一个事务的用户发现表中还存在没有修改的数据行,就好象发生了幻觉一样。
    • 不可重复读:比方说在同一个事务中先后执行两条一模一样的select语句,期间在此次事务中没有执行过任何DDL语句,但先后得到的结果不一致,这就是不可重复读。

    100. 说一下 spring mvc 运行流程?

    Spring MVC运行流程图:

    Spring运行流程描述:

    1. 用户向服务器发送请求,请求被Spring 前端控制Servelt DispatcherServlet捕获;

    2. DispatcherServlet对请求URL进行解析,得到请求资源标识符(URI)。然后根据该URI,调用HandlerMapping获得该Handler配置的所有相关的对象(包括Handler对象以及Handler对象对应的拦截器),最后以HandlerExecutionChain对象的形式返回;

    3. DispatcherServlet 根据获得的Handler,选择一个合适的HandlerAdapter;(附注:如果成功获得HandlerAdapter后,此时将开始执行拦截器的preHandler(...)方法)

    4.  提取Request中的模型数据,填充Handler入参,开始执行Handler(Controller)。 在填充Handler的入参过程中,根据你的配置,Spring将帮你做一些额外的工作:

    • HttpMessageConveter: 将请求消息(如Json、xml等数据)转换成一个对象,将对象转换为指定的响应信息
    • 数据转换:对请求消息进行数据转换。如String转换成Integer、Double等
    • 数据根式化:对请求消息进行数据格式化。 如将字符串转换成格式化数字或格式化日期等
    • 数据验证: 验证数据的有效性(长度、格式等),验证结果存储到BindingResult或Error中

    5.  Handler执行完成后,向DispatcherServlet 返回一个ModelAndView对象;

    6.  根据返回的ModelAndView,选择一个适合的ViewResolver(必须是已经注册到Spring容器中的ViewResolver)返回给DispatcherServlet ;

    7. ViewResolver 结合Model和View,来渲染视图;

    8. 将渲染结果返回给客户端。

    101. spring mvc 有哪些组件?

    Spring MVC的核心组件:

    1. DispatcherServlet:中央控制器,把请求给转发到具体的控制类
    2. Controller:具体处理请求的控制器
    3. HandlerMapping:映射处理器,负责映射中央处理器转发给controller时的映射策略
    4. ModelAndView:服务层返回的数据和视图层的封装类
    5. ViewResolver:视图解析器,解析具体的视图
    6. Interceptors :拦截器,负责拦截我们定义的请求然后做处理工作

    102. @RequestMapping 的作用是什么?

    RequestMapping是一个用来处理请求地址映射的注解,可用于类或方法上。用于类上,表示类中的所有响应请求的方法都是以该地址作为父路径。

    RequestMapping注解有六个属性,下面我们把她分成三类进行说明。

    value, method:

    • value:指定请求的实际地址,指定的地址可以是URI Template 模式(后面将会说明);
    • method:指定请求的method类型, GET、POST、PUT、DELETE等;

    consumes,produces

    • consumes:指定处理请求的提交内容类型(Content-Type),例如application/json, text/html;
    • produces:指定返回的内容类型,仅当request请求头中的(Accept)类型中包含该指定类型才返回;

    params,headers

    • params: 指定request中必须包含某些参数值是,才让该方法处理。
    • headers:指定request中必须包含某些指定的header值,才能让该方法处理请求。

    103. @Autowired 的作用是什么?

    《@Autowired用法详解》


    未完待续......


    欢迎大家关注我的公众号:Java团长,后续面试题更新之后可以在第一时间获取~

    展开全文
  • ZIP压缩算法原理解析(好文推荐,看完就懂)

    万次阅读 多人点赞 2019-05-28 16:08:02
    数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据压缩,两者本质上没啥区别,在数学家看来,都是映射。一方面在进行通信的时候,有必要将...

    转自:https://www.cnblogs.com/esingchan/p/3958962.html

    感谢作者

    最近自己实现了一个ZIP压缩数据的解压程序,觉得有必要把ZIP压缩格式进行一下详细总结,数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据压缩,两者本质上没啥区别,在数学家看来,都是映射。一方面在进行通信的时候,有必要将待传输的数据进行压缩,以减少带宽需求;另一方面,计算机存储数据的时候,为了减少磁盘容量需求,也会将文件进行压缩,尽管现在的网络带宽越来越高,压缩已经不像90年代初那个时候那么迫切,但在很多场合下仍然需要,其中一个原因是压缩后的数据容量减小后,磁盘访问IO的时间也缩短,尽管压缩和解压缩过程会消耗CPU资源,但是CPU计算资源增长得很快,但是磁盘IO资源却变化得很慢,比如目前主流的SATA硬盘仍然是7200转,如果把磁盘的IO压力转化到CPU上,总体上能够提升系统运行速度。压缩作为一种非常典型的技术,会应用到很多很多场合下,比如文件系统、数据库、消息传输、网页传输等等各类场合。尽管压缩里面会涉及到很多术语和技术,但无需担心,博主尽量将其描述得通俗易懂。另外,本文涉及的压缩算法非常主流并且十分精巧,理解了ZIP的压缩过程,对理解其它相关的压缩算法应该就比较容易了。

     

    1、引子

    压缩可以分为无损压缩和有损压缩,有损,指的是压缩之后就无法完整还原原始信息,但是压缩率可以很高,主要应用于视频、话音等数据的压缩,因为损失了一点信息,人是很难察觉的,或者说,也没必要那么清晰照样可以看可以听;无损压缩则用于文件等等必须完整还原信息的场合,ZIP自然就是一种无损压缩,在通信原理中介绍数据压缩的时候,往往是从信息论的角度出发,引出香农所定义的熵的概念,这方面的介绍实在太多,这里换一种思路,从最原始的思想出发,为了达到压缩的目的,需要怎么去设计算法。而ZIP为我们提供了相当好的案例。

    尽管我们不去探讨信息论里面那些复杂的概念,不过我们首先还是要从两位信息论大牛谈起。因为是他们奠基了今天大多数无损数据压缩的核心,包括ZIP、RAR、GZIP、GIF、PNG等等大部分无损压缩格式。这两位大牛的名字分别是Jacob Ziv和Abraham Lempel,是两位以色列人,在1977年的时候发表了一篇论文《A Universal Algorithm for Sequential Data Compression》,从名字可以看出,这是一种通用压缩算法,所谓通用压缩算法,指的是这种压缩算法没有对数据的类型有什么限定。不过论文我觉得不用仔细看了,因为博主作为一名通信专业的PHD,看起来也焦头烂额,不过我们后面可以看到,它的思想还是很简单的,之所以看起来复杂,主要是因为IEEE的某些杂志就是这个特点,需要从数学上去证明,这种压缩算法到底有多优,比如针对一个各态历经的随机序列(不用追究什么叫各态历经随机序列),经过这样的压缩算法后,是否可以接近信息论里面的极限(也就是前面说的熵的概念)等等,不过在理解其思想之前,个人认为没必要深究这些东西,除非你要发论文。这两位大牛提出的这个算法称为LZ77,两位大牛过了一年又提了一个类似的算法,称为LZ78,思想类似,ZIP这个算法就是基于LZ77的思想演变过来的,但ZIP对LZ77编码之后的结果又继续进行压缩,直到难以压缩为止。除了LZ77、LZ78,还有很多变种的算法,基本都以LZ开头,如LZW、LZO、LZMA、LZSS、LZR、LZB、LZH、LZC、LZT、LZMW、LZJ、LZFG等等,非常多,LZW也比较流行,GIF那个动画格式记得用了LZW。我也写过解码程序,以后有时间可以再写一篇,但感觉跟LZ77这些类似,写的必要性不大。

    ZIP的作者是一个叫Phil Katz的人,这个人算是开源界的一个具有悲剧色彩的传奇人物。虽然二三十年前,开源这个词还没有现在这样风起云涌,但是总有一些具有黑客精神的牛人,内心里面充满了自由,无论他处于哪个时代。Phil Katz这个人是个牛逼程序员,成名于DOS时代,我个人也没有经历过那个时代,我是从Windows98开始接触电脑的,只是从书籍中得知,那个时代网速很慢,拨号使用的是只有几十Kb(比特不是字节)的猫,56Kb实际上是这种猫的最高速度,在ADSL出现之后,这种技术被迅速淘汰。当时记录文件的也是硬盘,但是在电脑之间拷贝文件的是软盘,这个东西我大一还用过,最高容量记得是1.44MB,这还是200X年的软盘,以前的软盘容量具体多大就不知道了,Phil Katz上网的时候还不到1990年,WWW实际上就没出现,浏览器当然是没有的,当时上网干嘛呢?基本就是类似于网管敲各种命令,这样实际上也可以聊天、上论坛不是吗,传个文件不压缩的话肯定死慢死慢的,所以压缩在那个时代很重要。当时有个商业公司提供了一种称为ARC的压缩软件,可以让你在那个时代聊天更快,当然是要付费的,Phil Katz就感觉到不爽,于是写了一个PKARC,免费的,看名字知道是兼容ARC的,于是网友都用PKARC了,ARC那个公司自然就不爽,把哥们告上了法庭,说牵涉了知识产权等等,结果Phil Katz坐牢了。。。牛人就是牛人, 在牢里面冥思苦想,决定整一个超越ARC的牛逼算法出来,牢里面就是适合思考,用了两周就整出来的,称为PKZIP,不仅免费,而且这次还开源了,直接公布源代码,因为算法都不一样了,也就不涉及到知识产权了,于是ZIP流行开来,不过Phil Katz这个人没有从里面赚到一分钱,还是穷困潦倒,因为喝酒过多等众多原因,2000年的时候死在一个汽车旅馆里。英雄逝去,精神永存,现在我们用UE打开ZIP文件,我们能看到开头的两个字节就是PK两个字符的ASCII码。

     

    2、一个案例的入门思考

    好了,Phil Katz在牢里面到底思考了什么?用什么样的算法来压缩数据呢?我们想一个简单的例子:

    生,容易。活,容易。生活,不容易。

    上面这句话假如不压缩,如果使用Unicode编码,每个字会用2个字节表示。为什么是两个字节呢?Unicode是一种国际标准,把常见各国的字符,比如英文字符、日文字符、韩文字符、中文字符、拉丁字符等等全部制定了一个标准,显然,用2个字节可以最多表示2^16=65536个字符,那么65536就够了吗?生僻字其实是很多的,比如光康熙字典里面收录的汉字就好几万,所以实际上是不够的,那么是不是扩到4个字节?也可以,这样空间倒是变大了,可以收录更多字符,但一方面扩到4个字节就一定保证够吗?另一方面,4个字节是不是太浪费空间了,就为了那些一般情况都不会出现的生僻字?所以,一般情况下,使用2个字节表示,当出现生僻字的时候,再使用4个字节表示。这实际上就体现了信息论中数据压缩基本思想,出现频繁的那些字符,表示得短一些;出现稀少的,可以表示得长些(反正一般情况下也不会出现),这样整体长度就会减小。除了Unicode,ASCII编码是针对英文字符的编码方案,用1个字节即可,除了这两种编码方案,还有很多地区性的编码方案,比如GB2312可以对中文简体字进行编码,Big5可以对中文繁体字进行编码。两个文件如果都使用一种编码方案,那是没有问题的,不过考虑到国际化,还是尽量使用Unicode这种国际标准吧。不过这个跟ZIP没啥关系,纯属背景介绍。

    好了,回到我们前面说的例子,一共有17个字符(包括标点符号),如果用普通Unicode表示,一共是17*2=34字节。可不可以压缩呢?所有人一眼都可以看出里面出现了很多重复的字符,比如里面出现了好多次容易(实际上是容易加句号三个字符)这个词,第一次出现的时候用普通的Unicode,第二次出现的“容易。”则可以用(距离、长度)表示,距离的意思是接下来的字符离前面重复的字符隔了几个,长度则表示有几个重复字符,上面的例子的第二个“容易。”就表示为(5,3),就是距离为5个字符,长度是3,在解压缩的时候,解到这个地方的时候,往前跳5个字符,把这个位置的连续3个字符拷贝过来就完成了解压缩,这实际上不就是指针的概念?没有错,跟指针很类似,不过在数据压缩领域,一般称为字典编码,为什么叫字典呢,当我们去查一个字的时候,我们总是先去目录查找这个字在哪一页,再翻到那一页去看,指针不也是这样,指针不就是内存的地址,要对一个内存进行操作,我们先拿到指针,然后去那块内存去操作。所谓的指针、字典、索引、目录等等术语,不同的背景可能称呼不同,但我们要理解他们的本质。如果使用(5,3)这种表示方法,原来需要用6个字节表示,现在只需要记录5和3即可。那么,5和3怎么记录呢?一种方法自然还是可以用Unicode,那么就相当于节省了2个字节,但是有两个问题,第一个问题是解压缩的时候怎么知道是正常的5和3这两个字符,还是这只是一个特殊标记呢?所以前面还得加一个标志来区分一下,到底接下来的Unicode码是指普通字符,还是指距离和长度,如果是普通Unicode,则直接查Unicode码表,如果是距离和长度,则往前面移动一段距离,拷贝即可。第二个问题,还是压缩程度不行,这么一弄,感觉压缩不了多少,如果重复字符比较长那倒是比较划算,因为反正“距离+长度”就够了,但比如这个例子,如果5和3前面加一个特殊字节,岂不是又是3个字节,那还不如不压缩。咋办呢?能不能对(5,3)这种整数进行再次压缩?这里就利用了我们前面说的一个基本原则:出现的少的整数多编一些比特,出现的多的整数少编一些比特。那么,比如3、4、5、6、7、8、9这些距离谁出现得多?谁出现的少呢?谁知道?

    压缩之前当然不知道,不过扫描一遍不就知道了?比如,后面那个重复的字符串“容易。”按照前面的规则可以表示为(7,3),即离前面重复的字符串距离为7,长度为3。(7,3)指着前面跟自己一样那个字符串。那么,为什么不指着第一个“容易。”要指着第二个“容易。”呢?如果指着第一个,那就不是(7,3)了,就是(12,3)了。当然,表示为(12,3)也可以解压缩,但是有一个问题,就是12这个值比7大,大了又怎么了?我们在生活中会发现一些普遍规律,重复现象往往具有局部性。比如,你跟一个人说话,你说了一句话以后,往往很快会重复一遍,但是你不会隔了5个小时又重复这句话,这种特点在文件里面也存在着,到处都是这种例子,比如你在编程的时候,你定义了一个变量int nCount,这个nCount一般你很快就会用到,不会离得很远。我们前面所说的距离代表了你隔了多久再说这句话,这个距离一般不大,既然如此,应该以离当前字符串距离最近的那个作为记录的依据(也就是指向离自己最近那个重复字符串),这样的话,所有的标记都是一些短距离,比如都是3、4、5、6、7而不会是3、5、78、965等等,如果大多数都是一些短距离,那么这些短距离就可以用短一些的比特表示,长一些的距离不太常见,则用一些长一些的比特表示。这样, 总体的表示长度就会减少。好了,我们前面得到了(5,3)、(7、3)这种记录重复的表示,距离有两种:5、7;长度只有1种:3。咋编码?越短越好。

    既然表示的比特越短越好,3表示为0、5表示为10、7表示为11,行不行?这样(5,3),(7,3)就只需要表示为100、110,这样岂不是很短?貌似可以,貌似很高效。

    但解压缩遇到10这两个比特的时候,怎么知道10表示5呢?这种表示方法是一个映射表,称为码表。我们设计的上面这个例子的码表如下:

    3-->0

    5-->10

    7-->11

    这个码表也得传过去或者记录在压缩文件里才行啊,否则无法解压缩,但会不会记录了码表以后整体空间又变大了,会不会起不到压缩的作用?而且一个码表怎么记录?码表记录下来也是一堆数据,是不是也需要编码?码表是否可以继续压缩?那岂不是又需要新的码表?压缩会不会是一个永无止境的过程?作为一个入门级的同学,大概想到这儿就不容易想下去了。

     

    3、ZIP中的LZ编码思想

    上面我们说的重复字符串用指针标记记录下来,这种方法就是LZ这两个人提出来的,理解起来比较简单。后面分析(5,3)这种指针标记应该怎么编码的时候,就涉及到一种非常广泛的编码方式,Huffman编码,Huffman大致和香农是一个时代的人,这种编码方式是他在MIT读书的时候提出来的。接下来,我们来看看ZIP是怎么做的。

    以上面的例子,一个很简单的示意图如下:

    可以看出,ZIP中使用的LZ77算法和前面分析的类似,当然,如果仔细对比的话,ZIP中使用的算法和LZ提出来的LZ77算法其实还是有差异的,不过我建议不用仔细去扣里面的差异,思想基本是相同的,我们后面会简要分析一下两者的差异。LZ77算法一般称为“滑动窗口压缩”,我们前面说过,该算法的核心是在前面的历史数据中寻找重复字符串,但如果要压缩的文件有100MB,是不是从文件头开始找?不是,这里就涉及前面提过的一个规律,重复现象是具有局部性的,它的基本假设是,如果一个字符串要重复,那么也是在附近重复,远的地方就不用找了,因此设置了一个滑动窗口,ZIP中设置的滑动窗口是32KB,那么就是往前面32KB的数据中去找,这个32KB随着编码不断进行而往前滑动。当然,理论上讲,把滑动窗口设置得很大,那样就有更大的概率找到重复的字符串,压缩率不就更高了?初看起来如此,找的范围越大,重复概率越大,不过仔细想想,可能会有问题,一方面,找的范围越大,计算量会增大,不顾一切地增大滑动窗口,甚至不设置滑动窗口,那样的软件可能不可用,你想想,现在这种方式,我们在压缩一个大文件的时候,速度都已经很慢了,如果增大滑动窗口,速度就更慢,从工程实现角度来说,设置滑动窗口是必须的;另一方面,找的范围越大,距离越远,出现的距离很多,也不利于对距离进行进一步压缩吧,我们前面说过,距离和长度最好出现的值越少越好,那样更好压缩,如果出现的很多,如何记录距离和长度可能也存在问题。不过,我相信滑动窗口设置得越大,最终的结果应该越好一些,不过应该不会起到特别大的作用,比如压缩率提高了5%,但计算量增加了10倍,这显然有些得不偿失。

    在第一个图中,“容易。”是一个重复字符串,距离distance=5,字符串长度length=3。当对这三个字符压缩完毕后,接下来滑动窗口向前移动3个字符,要压缩的是“我...”这个字符串,但这个串在滑动窗口内没找到,所以无法使用distance+length的方式记录。这种结果称为literal。literal的中文含义是原义的意思,表示没有使用distance+length的方式记录的那些普通字符。literal是不是就用原始的编码方式,比如Unicode方式表示?ZIP里不是这么做的,ZIP把literal认为也是一个数,尽管不能用distance+length表示,但不代表不可以继续压缩。另外,如果“我”出现在了滑动窗口内,是不是就可以用distance+length的方式表示?也不是,因为一个字出现重复,不值得用这种方式表示,两个字呢?distance+length就是两个整数,看起来也不一定值得,ZIP中确实认为2个字节如果在滑动窗口内找到重复,也不管,只有3个字节以上的重复字符串,才会用distance+length表示,重复字符串的长度越长越好,因为不管多长,都用distance+length表示就行了。

    这样的话,一段字符串最终就可以表示成literal、distance+length这两种形式了。LZ系列算法的作用到此为止,下面,Phil Katz考虑使用Huffman对上面的这些LZ压缩后的结果进行二次压缩。个人认为接下来的过程才是ZIP的核心,所以我们要熟悉一下Huffman编码。

     

    4、ZIP中的Huffman编码思想

    上面LZ压缩结果有三类(literal、distance、length),我们拿出distance一类来举例。distance代表重复字符串离前一个一模一样的字符串之间的距离,是一个大于0的整数。如何对一个整数进行编码呢?一种方法是直接用固定长度表示,比如采用计算机里面描述一个4字节整数那样去记录,这也是可以的,主要问题当然是浪费存储空间,在ZIP中,distance这个数表示的是重复字符串之间的距离,显然,一般而言,越小的距离,出现的数量可能越多,而越大的距离,出现的数量可能越少,那么,按照我们前面所说的原则,小的值就用较少比特表示,大的值就用较多比特表示,在我们这个场景里,distance当然也不会无限大,比如不会超过滑动窗口的最大长度,假如对一个文件进行LZ压缩后,得到的distance值为:

    3、6、4、3、4、3、4、3、5

    这个例子里,3出现了4次,4出现了3次,5出现了1次,6出现了1次。当然,不同的文件得到的结果不同,这里只是举一个典型的例子,因为只有4种值,所以我们没有必要对其它整数编码。只需要对这4个整数进行编码即可。

    那么,怎么设计一个算法,符合3的编码长度最短?6的编码长度最长这种直观上可行的原则(我们并没有说这是理论上最优的方式)呢?

    看起来似乎很难想出来。我们先来简化一下,用固定长度表示。这里有4个整数,只要使用2个比特表示即可。于是这样表示就很简单:

    00-->3; 01-->4; 10-->5;  11-->6。

    00、01这种编码结果称为码字,码字的平均长度是2。上面这个对应关系即为码表,在压缩时,需要将码表放在最前面,后面的数字就用码字表示,解码时,先把码表记录在内存里,比如用一个哈希表记录下来,解压缩时,遇到00,就解码为3等等。

    因为出现了9个数,所以全部码字总长度为18个比特。(我们暂时不考虑记录码表到底要占多少空间)

    想要编码结果更短,因为3出现的最多,所以考虑把3的码字缩短点,比如3是不是可以用1个比特表示,这样才算缩短吧,因为0和1只是二进制的一个标志,所以用0还是1没有本质区别,那么,我们暂定把3用比特0表示。那么,4、5、6还能用0开头的码字表示呢?

    这样会存在问题,因为4、5、6的编码结果如果以0开头,那么,在解压缩的时候,遇到比特0,就不知道是表示3还是表示4、5、6了,就无法解码,当然,似乎理论上也不是不可以,比如可以往后解解看,比如假定0表示3的条件下往后解,如果无效则说明这个假设不对,但这种方式很容易出现两个字符串的编码结果是一样的,这个谁来保证?所以,4、5、6都得以1开头才行,那么,按照这个原则,4用1个比特也不行,因为5、6要么以0开头,要么以1开头,就无法编码了,所以我们将4的码字增加至2个比特,比如10,于是我们得到了部分码表:

    0-->3;10-->4。

    按照这个道理,5、6既不能以0开头,也不能以10开头了,因为同样存在无法解码的问题,所以5应该以11开头,就定为11行不行呢?也不行,因为6就不知道怎么编码了,6也不能以0开头,也不能以10、11开头,那就无法表示了,所以,迫不得已,我们必须把5扩展一位,比如110,那么,6显然就可以用111表示了,反正也没有其他数了。于是我们得到了最终的码表:

    0-->3;10-->4;110-->5;111-->6。

    看起来,编码结果只能是这样了,我们来算一下,码字的总长度减少了没有,原来的9个数是3、6、4、3、4、3、4、3、5,分别对应的码字是:

    0、111、10、0、10、0、10、0、110

    算一下,总共16个比特,果然比前面那种方式变短了。我们在前面的设计过程中,是按照这些值出现次数由高到底的顺序去找码字的,比如先确定3,再确定4、5、6等等。按照一个码字不能是另一个码字的前缀这一规则,逐步获得所有的码字。这种编码规则有一个专用术语,称为前缀码。Huffman编码基本上就是这么做的,把出现频率排个序,然后逐个去找,这个逐个去找的过程,就引入了二叉树。不过Huffman的算法一般是从频率由低到高排序,从树的下面依次往上合并,不过本质上没区别,理解思想即可。上面的结果可以用一颗二叉树表示为下图:

    这棵树也称为码树,其实就是码表的一种形式化描述,每个节点(除了叶子节点)都会分出两个分支,左分支代表比特0,右边分支代表1,从根节点到叶子节点的一个比特序列就是码字。因为只有叶子节点可以是码字,所以这样也符合一个码字不能是另一个码字的前缀这一原则。说到这里,可以说一下另一个话题,就是一个映射表map在内存中怎么存储,没有相关经验的可以跳过,map实现的是key-->value这样的一个表,map的存储一般有哈希表和树形存储两类,树形存储就可以采用上面这棵树,树的中间节点并没有什么含义,叶子节点的值表示value,从根节点到叶子节点上分支的值就是key,这样比较适合存储那些key由多个不等长字符组成的场合,比如key如果是字符串,那么把二叉树的分支扩展很多,成为多叉树,每个分支就是a,b,c,d这种字符,这棵树也就是Trie树,是一种很好使的数据结构。利用树的遍历算法,就实现了一个有序Map。

    好了,我们理解了Huffman编码的思想,我们来看看distance的实际情况。ZIP中滑动窗口大小固定为32KB,也就是说,distance的值范围是1-32768。那么,通过上面的方式,统计频率后,就得到32768个码字,按照上面这种方式可以构建出来。于是我们会遇到一个最大的问题,那就是这棵树太大了,怎么记录呢?

    好了,个人认为到了ZIP的核心了,那就是码树应该怎么缩小,以及码树怎么记录的问题。

     

    5、ZIP中Huffman码树的记录方式

    分析上面的例子,看看这个码表:

    0-->3;10-->4;110-->5;111-->6。

    我们之前提过,0和1就是二进制的一个标志,互换一下其实根本不影响编码长度,所以,下面的码表其实是一样的:

    1-->3;00-->4;010-->5;011-->6。

    1-->3;01-->4;000-->5;001-->6。

    0-->3;11-->4;100-->5;101-->6。

    。。。。。

    这些都可以,而且编码长度完全一样,只是码字不同而已。

    对比一下第一个和第二个例子,对应的码树是这个样子:

    也就是说,我们把码树的任意节点的左右分支旋转(0、1互换),也可以称为树的左右互换,其实不影响编码长度,也就是说,这些码表其实都是一样好的,使用哪个都可以。

    这个规律暗示了什么信息呢?暗示了码表可以怎么记录呢?Phil Katz当年在牢里也深深地思考了这一问题。

    为了体会Phil Katz当时的心情,我们有必要盯着这两棵树思考几分钟:怎么把一颗树用最少的比特记录下来?

    Phil Katz当时思考的逻辑我猜是这样的,既然这些树的压缩程度都一样,那干脆使用最特殊的那棵树,反正压缩程度都一样,只要ZIP规定了这棵树的特殊性,那么我记录的信息就可以最少,这种特殊化的思想在后面还会看到。不同的树当然有不同的特点,比如数据结构里面常见的平衡树也是一类特殊的树,他选的树就是左边那棵,这棵树有一个特点,越靠左边越浅,越往右边越深,是这些树中最不平衡的树。ZIP里的压缩算法称为Deflate算法,这棵树也称为Deflate树,对应的解压缩算法称为Inflate,Deflate的大致意思是把轮胎放气了,意为压缩;Inflate是给轮胎打气的意思,意为解压。那么,Deflate树的特殊性又带来什么了?

    揭晓答案吧,Phil Katz认为换来换去只有码字长度不变,如果规定了一类特殊的树,那么就只需要记录码字长度即可。比如,一个有效的码表是0-->3;10-->4;110-->5;111-->6。但只需要记录这个对应关系即可:

    3  4  5  6

    1  2  3  3

    也就是说,把1、2、3、3记录下来,解压一边照着左边那棵树的形状构造一颗树,然后只需要1、2、3、3这个信息自然就知道是0、10、110、111。这就是Phil Katz想出来的ZIP最核心的一点:这棵码树用码字长度序列记录下来即可。

    当然,只把1、2、3、3这个序列记录下来还不行,比如不知道111对应5还是对应6?

    所以,构造出树来只是知道了有哪些码字了,但是这些码字到底对应哪些整数还是不知道。

    Phil Katz于是又出现了一个想法:记录1、2、3、3还是记录1、3、2、3,或者3、3、2、1,其实都能构造出这棵树来,那么,为什么不按照一个特殊的顺序记录呢?这个顺序就是整数的大小顺序,比如上面的3、4、5、6是整数大小顺序排列的,那么,记录的顺序就是1、2、3、3。而不是2、3、3、1。

    好了,根据1、2、3、3这个信息构造出了码字,这些码字对应的整数一个比一个大,假如我们知道编码前的整数就是3、4、5、6这四个数,那就能对应起来了,不过到底是哪四个还是不知道啊?这个整数可以表示距离啊,距离不知道怎么去解码LZ?

    Phil Katz又想了,既然distance的范围是1-32768,那么就按照这个顺序记录。上面的例子1和2没有,那就记录长度0。所以记录下来的码字长度序列为:

    0、0、1、2、3、3、0、0、0、0、0、。。。。。。。。。。。。

    这样就知道构造出来的码字对应哪个整数了吧,但因为distance可能的值很多(32768个),但实际出现的往往不多,中间会出现很多0(也就是根本就没出现这个距离),不过这个问题倒是可以对连续的0做个特殊标记,这样是不是就行了呢?还有什么问题?

    我们还是要站在时代的高度来看待这个问题。我们明白,每个distance肯定对应唯一一个码字,使用Huffman编码可以得到所有码字,但是因为distance可能非常多,虽然一般不会有32768这么多,但对一个大些的文件进行LZ编码,distance上千还是很正常的,所以这棵树很大,计算量、消耗的内存都容易超越了那个时代的硬件条件,那么怎么办呢?这里再次体现了Phil Katz对Huffman编码掌握的深度,他把distance划分成多个区间,每个区间当做一个整数来看,这个整数称为Distance Code。当一个distance落到某个区间,则相当于是出现了那个Code,多个distance对应于一个Distance Code,Distance虽然很多,但Distance Code可以划分得很少,只要我们对Code进行Huffman编码,得到Code的编码后,Distance Code再根据一定规则扩展出来。那么,划分多少个区间?怎么划分区间呢?我们分析过,越小的距离,出现的越多;越大的距离,出现的越少,所以这种区间划分不是等间隔的,而是越来越稀疏的,类似于下面的划分:

    1、2、3、4这四个特殊distance不划分,或者说1个Distance就是1个区间;5,6作为一个区间;7、8作为一个区间等等,基本上,区间的大小都是1、2、4、8、16、32这么递增的,越往后,涵盖的距离越多。为什么这么分呢?首先自然是距离越小出现频率越高,所以距离值小的时候,划分密一些,这样相当于一个放大镜,可以对小的距离进行更精细地编码,使得其编码长度与其出现次数尽量匹配;对于距离较大那些,因为出现频率低,所以可以适当放宽一些。另一个原因是,只要知道这个区间Code的码字,那么对于这个区间里面的所有distance,后面追加相应的多个比特即可,比如,17-24这个区间的Huffman码字是110,因为17-24这个区间有8个整数,于是按照下面的规则即可获得其distance对应的码字:

    17-->110 000

    18-->110 001

    19-->110 010

    20-->110 011

    21-->110 100

    22-->110 101

    23-->110 110

    24-->110 111

    这样计算复杂度和内存消耗是不是很小了,因为需要进行Huffman编码的整数一下字变少了,这棵树不会多大,计算起来时间和空间复杂度降低,扩展起来也比较简单。当然,从理论上来说,这样的编码方式实际上将编码过程分为了两级,并不是理论上最优的,把所有distance当作一个大空间去编码才可能得到最优结果,不过还是那句话,工程实现的限制,在压缩软件实现上,我们不能用压缩率作为衡量一个算法优劣的唯一指标,其实耗费的时间和空间同样是指标,所以需要看综合指标。很多其他软件也一样,扩展性、时间空间复杂度、稳定性、移植性、维护的方便性等等是工程上很重要的东西。我没有看过RAR是如何压缩的,有可能是在类似的地方进行了改进,如果如此,那也是站在巨人的肩膀上,而且硬件条件不同,进行一些改进也并不奇怪。

    具体来说,Phil Katz把distance划分为30个区间,如下图:

    这个图是我从David Salomon的《Data Compression The Complete Reference》这本书(第四版)中拷贝出来的,下面的有些图也是,如果需要对数据压缩进行全面的了解,这本书几乎是最全的了,强烈推荐。

    当然,你要问为什么是30个区间,我也没分析过,也许是复杂度和压缩率经过试验之后的一种折中吧。

    其中,左边的Code表示区间的编号,是0-29,共30个区间,这只是个编号,没有特别的含义,但Huffman就是对0-29这30个Code进行编码的,得到区间的码字;

    bits表示distance的码字需要在Code的码字基础上扩展几位,比如0就表示不扩展,最大的13表示要扩展13位,因此,最大的区间包含的distance数量为8192个。

    Distance一列则表示这个区间涵盖的distance范围。

    理解了码树如何有效记录,以及如何缩小码树的过程,我觉得就理解了ZIP的精髓。

     

    6、ZIP中literal和length的压缩方式

    说完了distance,LZ编码结果还有两类:literal和length。这两类也利用了类似于distance的方式进行压缩。

    前面分析过,literal表示未匹配的字符,我们前面之所以拿汉字来举例,完全是为了便于理解,ZIP之所以是通用压缩,它实际上是针对字节作为基本字符来编码的,所以一个literal至多有256种可能。

    length表示重复字符串长度,length=1当然不会出现,因为一个字符不值得用distance+length去记录,重复字符串当然越长越好,Phil Katz(下面还是简称PK了,拷贝太麻烦)认为,length=2也不值得用这种方式记录,还是太短了,所以PK把length最小值认为是3,必须3个以上字符的字符串出现重复才用distance+length记录。那么,最大的length是多少呢?理论上当然可以很长很长,比如一个文件就是连续的0,这个重复字符串长度其实接近于这个文件的实际长度。但是PK把length的范围做了限制,限定length的个数跟literal一样,也只有256个,因为PK认为,一个重复字符串达到了256个已经很长了,概率非常小;另外,其实哪怕超过了256,我还是认为是一段256再加上另外一段,增加一个distance+length就行了嘛,并不影响结果。而且这样做,我想同样也考虑了硬件条件吧。

    初看有点奇怪的在于,将literal和length二者合二为一,什么意思呢?就是对这两种整数(literal本质上是一个字节)共用一个Huffman码表,一会儿解释为什么。PK对Huffman的理解我觉得达到了炉火纯青的地步,前面已经看到,后面还会看到。他认为Huffman编码的输入反正说白了就是一个集合的元素就行,无论这个元素是啥,所以多个集合看做一个集合当作Huffman编码的输入没啥问题。literal用整数0-255表示,256是一个结束标志,解码以后结果是256表示解码结束;从257开始表示length,所以257这个数表示length=3,258这个数表示length=4等等,但PK也不是一直这么一一对应,和distance一样,也是把length(总共256个值)划分为29个区间,其结果如下图:

    其中的含义和distance类似,不再赘述,所以literal/length这个Huffman编码的输入元素一共285个,其中256表示解码结束标志。为什么要把二者合二为一呢?因为当解码器接收到一个比特流的时候,首先可以按照literal/length这个码表来解码,如果解出来是0-255,就表示未匹配字符,如果是256,那自然就结束,如果是257-285之间,则表示length,把后面扩展比特加上形成length后,后面的比特流肯定就表示distance,因此,实际上通过一个Huffman码表,对各类情况进行了统一,而不是通过加一个什么标志来区分到底是literal还是重复字符串。

    好了,理解了上面的过程,就理解了ZIP压缩的第二步,第一步是LZ编码,第二步是对LZ编码后结果(literal、distance、length)进行的再编码,因为literal/length是一个码表,我称其为Huffman码表1,distance那个码表称为Huffman码表2。前面我们已经分析了,Huffman码树用一个码字长度序列表示,称为CL(Code Length),记录两个码表的码字长度序列分别记为CL1、CL2。码树记录下来,对literal/length的编码比特流称为LIT比特流;对distance的编码比特流称为DIST比特流。

    按照上面的方法,LZ的编码结果就变成四块:CL1、CL2、LIT比特流、DIST比特流。CL1、CL2是码字长度的序列,这个序列说白了就是一堆正整数,因此,PK继续深挖,认为这个序列还应该继续压缩,也就是说,对码表进行压缩。

     

    7、ZIP中对CL进行再次压缩的方法

    这里仍然沿用Huffman的想法,因为CL也是一堆整数,那么当然可以再次应用Huffman编码。不过在这之前,PK对CL序列进行了一点处理。这个处理也是很精巧的。

    CL序列表示一系列整数对应的码字长度,对于literal/length来说,总共有0-285这么多符号,所以这个序列长度为286,每个符号都有一个码字长度,当然,这里面可能会出现大段连续的0,因为某些字符或长度不存在,尤其是对英文文本编码的时候,非ASCII字符就根本不会出现,length较大的值出现概率也很小,所以出现大段的0是很正常的;对于distance也类似,也可能出现大段的0。PK于是先进行了一下游程编码。在说什么是游程编码之前,我们谈谈PK对CL序列的认识。

    literal/length的编码符号总共286个(回忆:256个Literal+1个结束标志+29个length区间),distance的编码符号总共30个(回忆:30个区间),所以这颗码树不会特别深,Huffman编码后的码字长度不会特别长,PK认为最长不会超过15,也就是树的深度不会超过15,这个是否是理论证明我还没有分析,有兴趣的同学可以分析一下。因此,CL1和CL2这两个序列的任意整数值的范围是0-15。0表示某个整数没有出现(比如literal=0x12, length Code=8, distance Code=15等等)。

    什么叫游程呢?就是一段完全相同的数的序列。什么叫游程编码呢?说起来原理更简单,就是对一段连续相同的数,记录这个数一次,紧接着记录出现了多少个即可。David的书中举了这个例子,比如CL序列如下:

    4, 4, 4, 4, 4, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2
    那么,游程编码的结果为:

    4, 16, 01(二进制), 3, 3, 3, 6, 16, 11(二进制), 16, 00(二进制), 17,011(二进制), 2, 16, 00(二进制)
    这是什么意思呢?因为CL的范围是0-15,PK认为重复出现2次太短就不用游程编码了,所以游程长度从3开始。用16这个特殊的数表示重复出现3、4、5、6个这样一个游程,分别后面跟着00、01、10、11表示(实际存储的时候需要低比特优先存储,需要把比特倒序来存,博文的一些例子有时候会忽略这点,实际写程序的时候一定要注意,否则会得到错误结果)。于是4,4,4,4,4,这段游程记录为4,16,01,也就是说,4这个数,后面还会连续出现了4次。6,16,11,16,00表示6后面还连续跟着6个6,再跟着3个6;因为连续的0出现的可能很多,所以用17、18这两个特殊的数专门表示0游程,17后面跟着3个比特分别记录长度为3-10(总共8种可能)的游程;18后面跟着7个比特表示11-138(总共128种可能)的游程。17,011(二进制)表示连续出现6个0;18,0111110(二进制)表示连续出现62个0。总之记住,0-15是CL可能出现的值,16表示除了0以外的其它游程;17、18表示0游程。因为二进制实际上也是个整数,所以上面的序列用整数表示为:

    4, 16, 1, 3, 3, 3, 6, 16, 3, 16, 0, 17, 3, 2, 16, 0

    我们又看到了一串整数,这串整数的值的范围是0-18。这个序列称为SQ(Sequence的意思)。因为有两个CL1、CL2,所以对应的有两个SQ1、SQ2。

    针对SQ1、SQ2,PK用了第三个Huffman码表来对这两个序列进行编码。通过统计各个整数(0-18范围内)的出现次数,按照相同的思路,对SQ1和SQ2进行了Huffman编码,得到的码流记为SQ1 bits和SQ2 bits。同时,这里又需要记录第三个码表,称为Huffman码表3。同理,这个码表也用相同的方法记录,也等效为一个码长序列,称为CCL,因为至多有0-18个,PK认为树的深度至多为7,于是CCL的范围是0-7。

    当得到了CCL序列后,PK决定不再折腾,对这个序列用普通的3比特定长编码记录下来即可,即000代表0,111代表7。但实际上还有一点小折腾,就是最后这个序列如果全部记录,那就需要19*3=57个比特,PK认为CL序列里面CL范围为0-15,特殊的几个值是16、17、18,如果把CCL序列位置置换一下,把16、17、18这些放前面,那么这个CCL序列就很可能最后面跟着一串0(因为CL=14,15这些很可能没有),所以最后还引入了一个置换,其示意图如下,分别表示置换前的CCL序列和置换后的CCL。可以看出,16、17、18对应的CCL被放到了前面,这样如果尾部出现了一些0,就只需要记录CCL长度即可,后面的0不记录。可以继续节省一些比特,不过这个例子尾部置换后只有1个0:

    不过粗看起来,这个置换效果并不好,我一开始接触这个置换的时候,我觉得应该按照16、17、18、0、1、2、3、。。。这样的顺序来存储,如果按照我理解的,那么置换后的结果如下:

    2、4、0、4、5、5、1、5、0、6、0、0、0、0、0、0、0、0、0

    这样后面的一大串0直接截断,比PK的方法更短。但PK却按照上面的顺序。我总是认为,我觉得牛人可能出错了的时候,往往是我自己错了,所以我又仔细想了一下,上面的顺序特点比较明显,直观上看,PK认为CL为0和中间的值出现得比较多(放在了前面),但CL比较小的和比较大的出现得比较少(1、15、2、14这些放在了后面,你看,后面交叉着放),在文件比较小的时候,这种方法效果不算好,上面就是一个典型的例子,但文件比较大了以后,CL1、CL2码树比较大,码字长度普遍比较长,大部分很可能接近于中间值,那么这个时候PK的方法可能就体现出优势了。不得不说,对一个算法或者数据结构的优化程度,简直完全取决于程序员对那个东西细节的理解的深度。当我仔细研究了ZIP压缩算法的过程之后,我对PK这种深夜埋头冥思苦想的大牛佩服得五体投地。

    到此为止,ZIP压缩算法的结果已经完毕。这个算法命名为Deflate算法。总结一下其编码流程为:

     

    8、Deflate压缩数据格式

    ZIP的格式实际上就是Deflate压缩码流外面套了一层文件相关的信息,这里先介绍Deflate压缩码流格式。其格式为:

    Header:3个比特,第一个比特如果是1,表示此部分为最后一个压缩数据块;否则表示这是.ZIP文件的某个中间压缩数据块,但后面还有其他数据块。这是ZIP中使用分块压缩的标志之一;第2、3比特表示3个选择:压缩数据中没有使用Huffman、使用静态Huffman、使用动态Huffman,这是对LZ77编码后的literal/length/distance进行进一步编码的标志。我们前面分析的都是动态Huffman,其实Deflate也支持静态Huffman编码,静态Huffman编码原理更为简单,无需记录码表(因为PK自己定义了一个固定的码表),但压缩率不高,所以大多数情况下都是动态Huffman。

    HLIT:5比特,记录literal/length码树中码长序列(CL1)个数的一个变量。后面CL1个数等于HLIT+257(因为至少有0-255总共256个literal,还有一个256表示解码结束,但length的个数不定)。

    HDIST:5比特,记录distance码树中码长序列(CL2)个数的一个变量。后面CL2个数等于HDIST+1。哪怕没有1个重复字符串,distance都为0也是一个CL。

    HCLEN:4比特,记录Huffman码表3中码长序列(CCL)个数的一个变量。后面CCL个数等于HCLEN+4。PK认为CCL个数不会低于4个,即使对于整个文件只有1个字符的情况。

    接下来是3比特编码的CCL,一共HCLEN+4个,用以构造Huffman码表3;

    接下来是对CL1(码长)序列经过游程编码(SQ1:缩短的整数序列)后,并对SQ1继续用Huffman编码后的比特流。包含HLIT+257个CL1,其解码码表为Huffman码表3,用以构造Huffman码表1;

    接下来是对CL2(码长)序列经过游程编码(SQ2:缩短的整数序列)后,并对SQ2继续用Huffman编码后的比特流。包含HDIST+1个CL2,其解码码表为Huffman码表3,用于构造Huffman码表2;

    总之,上面的数据都是为了构造LZ解码需要的2个Huffman码表。

    接下来才是经过Huffman编码的压缩数据,解码码表为Huffman码表1和码表2。
    最后是数据块结束标志,即literal/length这个码表输入符号位256的编码比特。
    对倒数第1、2内容块进行解码时,首先利用Huffman码表1进行解码,如果解码所得整数位于0-255之间,表示literal未匹配字符,接下来仍然利用Huffman码表1解码;如果位于257-285之间,表示length匹配长度,之后需要利用Huffman码表2进行解码得到distance偏移距离;如果等于256,表示数据块解码结束。

     

    9、ZIP文件格式解析

     上面各节对ZIP的原理进行了分析,这一节我们来看一个实际的例子,为了更好地描述,我们尽量把这个例子举得简单一些。下面是我随便从一本书拷贝出来的一段较短的待压缩的英文文本数据:

    As mentioned above,there are many kinds of wireless systems other than cellular.

    这段英文文本长度为80字节。经过ZIP压缩后,其内容如下:

    可以看到,第1、2字节就是PK。看着怎么比原文还长,这怎么叫压缩?实际上,这里面大部分内容是ZIP的文件标记开销,真正压缩的内容(也就是我们前面提到的Deflate数据,划线部分都是ZIP文件开销)其实肯定要比原文短(否则ZIP不会启用压缩),我们这个例子是个短文本,但对于更长的文本而言,那ZIP文件总体长度肯定是要短于原始文本的。上面的这个ZIP文件,可以看到好几个以PK开头的区域,也就是不同颜色的划线区域,这些其实都是ZIP文件本身的开销。

    所以,我们首先来看一看ZIP的格式,其格式定义为:

    [local file header 1]
    [file data 1]
    [data descriptor 1]
    ..........
    [local file header n]
    [file data n]
    [data descriptor n]
    [archive decryption header] 
    [archive extra data record] 
    [central directory]
    [zip64 end of central directory record]
    [zip64 end of central directory locator] 
    [end of central directory record]
    local file header+file data+data descriptor这是一段ZIP压缩数据,在一个ZIP文件里,至少有一段,至多那就不好说了,假如你要压缩的文件一共有10个,那这个地方至少会有10段,ZIP对每个文件进行了独立压缩,RAR在此进行了改进,将多个文件联合起来进行压缩,提高了压缩率。local file header的格式如下:

    可见,起始的4个字节就是0x50(P)、0x4B(K)、0x03、0x04,因为是低字节优先,所以Signature=0x03044B50.接下来的内容按照上面的格式解析,十分简单,这个区域在上面ZIP数据的那个图里面是红色划线区域,之后则是压缩后的Deflate数据。在文件的尾部,还有ZIP尾部数据,上面这个例子包含了central directory和end of central directory record,一般这两部分也是必须的。central directory以0x50、0x4B、0x01、0x02开头;end of central directory record以0x50、0x4B、0x05、0x06开头,其含义比较简单,分别对应于上面ZIP数据那个图的蓝色和绿色部分,下面是两者的格式:

    end of central directory record格式:

    这几张图是我从网上找的,写得比较清晰。对于其中的含义,解释起来也比较简单,我分析的结果如下:注意ZIP采用的低字节优先,在一个字节里面低位优先,需要反过来看。

    Local File Header: (38B,304b)
    00001010110100101100000000100000 (signature)
    0000000000010100 (version:20)
    0000000000000000 (generalBitFlag)
    0000000000001000 (compressionMethod:8)
    0100110110001110 (lastModTime:19854)
    0100010100100101 (lastModDate:17701)
    01010100101011010100001100111100 (CRC32)
    00000000000000000000000001001000 (compressedSize:72)
    00000000000000000000000001010000 (uncompressedSize:80)
    0000000000001000 (filenameLength:8)
    0000000000000000 (extraFieldLength:0)
    0010101010100110110011100010111001110100001011100001111000101110 (fileName:Test.txt)
     (extraField)


    Central File Header: (54B,432b)
    00001010110100101000000001000000 (signature)
    0000000000010100 (versionMadeBy:20)
    0000000000010100 (versionNeeded:20)
    0000000000000000 (generalBitFlag)
    0000000000001000 (compressionMethod:8)
    0100110110001110 (lastModTime:19854)
    0100010100100101 (lastModDate:17701)
    01010100101011010100001100111100 (CRC32)
    00000000000000000000000001001000 (compressedSize:72)
    00000000000000000000000001010000 (uncompressedSize:80)
    0000000000001000 (filenameLength:8)
    0000000000000000 (extraFieldLength:0)
    0000000000000000 (fileCommenLength:0)
    0000000000000000 (diskNumberStart)
    0000000000000001 (internalFileAttr)
    10000001100000000000000000100000 (externalFileAttr)
    00000000000000000000000000000000 (relativeOffsetLocalHeader)
    0010101010100110110011100010111001110100001011100001111000101110 (fileName:Test.txt)
     (extraField)
     (fileComment)


    end of Central Directory Record: (22B,176b)
    00001010110100101010000001100000 (signature)
    0000000000000000 (numberOfThisDisk:0)
    0000000000000000 (numberDiskCentralDirectory:0)
    0000000000000001 (EntriesCentralDirectDisk:1)
    0000000000000001 (EntriesCentralDirect:1)
    00000000000000000000000000110110 (sizeCentralDirectory:54)
    00000000000000000000000001101110 (offsetStartCentralDirectory:110)
    0000000000000000 (fileCommentLength:0)
     (fileComment)

    Local File Header Length:304
    Central File Header Length:432
    End Central Directory Record Length:176

    可见,开销总的长度为38+54+22=114字节,整个文件长度为186字节,因此Deflate压缩数据长度为72字节(576比特)。尽管这里看起来只是从80字节压缩到72字节,那是因为这是一段短文本,重复字符串出现较少,但如果文本较长,那压缩率就会增加,这里只是举个例子。

    下面对其中的关键部分,也就是Deflate压缩数据进行解析。

     

    10,Deflate解码过程实例分析

    我们按照ZIP格式把Deflate压缩数据(72字节)提取出来,如下(每行8字节):

    1010100001010011100010111011000000000001000001000011000010100010
    1000101110101010011110110000000001100011101110000011100010100101
    0101001111001100000010001101001010010010000101101010101100001101
    1011110100011111100011101111111001110010011101110110011100010101
    0010110100010100101100110001100100000100110111101101111000011101
    0010001001100110111001000010011001101010101000110110000001110101
    0100011010010011100010110111001000111101101001011100101010010111
    0111000011111000011110000011010111001011011111111100100010001001
    1010001100001110000010101010111101101010100101111101011111100000

    Deflate格式除了上面的介绍,也可以参考RFC1951,解析如下:

    Header:101, 第一个比特是1,表示此部分为最后一个压缩数据块;后面的两个比特01表示采用动态哈夫曼、静态哈夫曼、或者没有编码的标志,01表示采用动态Huffman;在RFC1951里面是这么说明的:

    00 - no compression

    01 - compressed with fixed Huffman codes

    10 - compressed with dynamic Huffman codes

    11 - reserved (error)

    注意,这里需要按照低比特在先的方式去看,否则会误以为是静态Huffman。

    接下来:
    HLIT:01000,记录literal/length码树中码长序列个数的一个变量,表示HLIT=2(低位在前),说明后面存在HLIT + 257=259个CL1,CL1即0-258被编码后的长度,其中0-255表示Literal,256表示无效符号,257、258分别表示Length=3、4(length从3开始)。因此,这里实际上只出现了两种重复字符串的长度,即3和4。回顾这个图可以更清楚:

    继续:
    HDIST:01010,记录distance码树中码长序列个数的一个变量,表示HDIST=10,说明后面存在HDIST+1=11个CL2,CL2即Distance Code=0-10被编码的长度。

    继续:

    HCLEN:0111,记录Huffman码树3中码长序列个数的一个变量,表示HCLEN=14(1110二进制),即说明紧接着跟着HCLEN+4=18个CCL,前面已经分析过,CCL记录了一个Huffman码表,这个码表可以用一个码长序列表示,根据这个码长序列可以得到码表。于是接下来我们把后面的18*3=54个比特拷贝出来,上面的码流目前解析为下面的结果:

    101(Header) 01000(HLIT) 01010(HDIST) 0111(HCLEN) 
    000 101 110 110 000 000 000 010 000 010 000 110 000 101 000 101 000 101 (CCL)
    110101010011110110000000001100011101110000011100010100101
    0101001111001100000010001101001010010010000101101010101100001101
    1011110100011111100011101111111001110010011101110110011100010101
    0010110100010100101100110001100100000100110111101101111000011101
    0010001001100110111001000010011001101010101000110110000001110101
    0100011010010011100010110111001000111101101001011100101010010111
    0111000011111000011110000011010111001011011111111100100010001001
    1010001100001110000010101010111101101010100101111101011111100000

    标准的CCL长度为19(回忆一下:CCL范围为0-18,按照整数大小排序记录各自的码字长度),因此最后一个补0。得到序列:

    000 101 110 110 000 000 000 010 000 010 000 110 000 101 000 101 000 101 000

    其长度分别为(低位在前):
    0、5、3、3、0、0、0、2、0、2、0、3、0、5、0、5、0、5、0
    前面已经分析过,这个CCL序列实际上是经过一次置换操作得到的,需要进行相反的置换,置换后为:

    3、5、5、5、3、2、2、0、0、0、0、0、0、0、0、0、0、5、3
    这个就是对应于0-18的码字长度序列。
    根据Deflate树的构造方式,得到下面的码表(Huffman码表3):

    00      <-->   5
    01      <-->   6
    100     <-->  0
    101     <-->  4
    110     <-->  18
    11100   <-->1
    11101   <-->2
    11110   <-->3
    11111   <-->17

    接下来就是CL1序列,按照前面的指示,一共有259个,分别对应于literal/length:0-258对应的码字长度序列,我们队跟着CCL后面的比特按照上面获得的码表进行逐步解码,在解码之前,实际上并不知道CL1的比特流长度有多少,需要根据259这个数字来判定,解完了259个整数,表明解析CL1完毕:

    101(Header) 01000(HLIT) 01010(HDIST) 0111(HCLEN) 
    000 101 110 110 000 000 000 010 000 010 000 110 000 101 000 101 000 101 (CCL)

    110(18)1010100(7比特,记录连续的11-138个0,此处一共0010101b=21,即记录21+11=32个0)

    11110(3)110(18)0000000(7比特,记录连续的11-138个0,此处为全0,即记录0+11=11个0)

    01(6)100(0)01(6)110(18)1110000(7比特,记录连续的11-138个0,此处为111b=7,即记录7+11=18个0)

    01(6)110(18)0010100(7比特,记录连续的11-138个0,此处为10100b=20,即记录20+11=31个0)

    101(4)01(6)01(6)00(5)11110(3)01(6)100(0)00(5)00(5)100(0)01(6)101(4)

    00(5)101(4)00(5)100(0)100(0)00(5)101(4)101(4)01(6)01(6)01(6)100(0)

    00(5)110(18)1101111(7比特,记录连续的11-138个0,此处为1111011b=123,即记录123+11=134个0)

    统计一下,上面已经解了32+11+18+31+134+30=256个数了,因为总共259个,还差三个:

    01(6)00(5)01(6)

    好了,CL1比特流解析完毕了,得到的CL1码长序列为:

    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 
    0 0 0 0 6 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 6 6 5 3 6 0 5 5 0 6 4 5 4 5 0 0 5 4 4 6 6 6 
    0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 5 6

    总共259个,每行40个。根据这个序列,同样按照Deflate树构造方法,得到literal/length码表(Huffman码表1)为:

    000     --> (System.Char)(看前面的CL1序列,空格对应的ASCII为0x20=32,码字长度3,即上面序列中第一个3)
    001     -->e(System.Char)
    0100    -->a(System.Char)
    0101    -->l(System.Char)
    0110    -->n(System.Char)
    0111    -->s(System.Char)
    1000    -->t(System.Char)
    10010   -->d(System.Char)
    10011   -->h(System.Char)
    10100   -->i(System.Char)
    10101   -->m(System.Char)
    10110   -->o(System.Char)
    10111   -->r(System.Char)
    11000   -->y(System.Char)
    11001   -->3(System.Int32)(看前面的CL1序列,对应257,码字长度5)
    110100  -->,(System.Char)
    110101  -->.(System.Char)
    110110  -->A(System.Char)
    110111  -->b(System.Char)
    111000  -->c(System.Char)
    111001  -->f(System.Char)
    111010  -->k(System.Char)
    111011  -->u(System.Char)
    111100  -->v(System.Char)
    111101  -->w(System.Char)
    111110  -->-1(System.Int32)(看前面的CL1序列,对应256,码字长度6)
    111111  -->4(System.Int32)(看前面的CL1序列,对应258,码字长度6)

    可以看出,码表里存在两个重复字符串长度3和4,当解码结果为-1(上面进行了处理,即256),或者说遇到111110的时候,表示Deflate码流结束。

    按照同样的道理,对CL2序列进行解析,前面已经知道HDIST=10,即有11个CL2整数序列:

    11111(17)000(3比特,记录连续的3-10个0,此处为0,即记录3个0)

    11101(2)11111(17)100(3比特,记录连续的3-10个0,此处为001b=1,即记录4个0)

    11100(1)100(0)11101(2)

    已经结束,总共11个。

    于是CL2序列为:

    0 0 0 2 0 0 0 0 1 0 2

    分别记录的是distance码为0-10的码字长度,根据下面的对应关系,需要进行扩展:

    比如,第1个码长2记录的是Code=3的长度,即Distance=4对应的码字为:

    10      -->4(System.Int32)

    第1个码长1记录的是Code=8的长度(码字为0,扩展三位000-111),即Distance=17-24对应的码字为(注意,低比特优先):

    0 000    -->17(System.Int32)
    0 100    -->18(System.Int32)
    0 010    -->19(System.Int32)
    0 110    -->20(System.Int32)
    0 001    -->21(System.Int32)
    0 101    -->22(System.Int32)
    0 011    -->23(System.Int32)
    0 111    -->24(System.Int32)

    注意,扩展的时候还是低比特优先。

    最后1个码长2记录的是Code=10的长度(其实是码字:11,扩展四位0000-1111),即Distance=33-48对应的码字为:

    11 0000  -->33(System.Int32)
    11 1000  -->34(System.Int32)
    11 0100  -->35(System.Int32)
    11 1100  -->36(System.Int32)
    11 0010  -->37(System.Int32)
    11 1010  -->38(System.Int32)
    11 0110  -->39(System.Int32)
    11 1110  -->40(System.Int32)
    11 0001  -->41(System.Int32)
    11 1001  -->42(System.Int32)
    11 0101  -->43(System.Int32)
    11 1101  -->44(System.Int32)
    11 0011  -->45(System.Int32)
    11 1011  -->46(System.Int32)
    11 0111  -->47(System.Int32)
    11 1111  -->48(System.Int32)

    至此为止,Huffman码表1、Huffman码表2已经还原出来,接下来是对LZ压缩所得到的literal、distance、length进行解码,目前剩余的比特流如下,先按照Huffman码表1解码,如果解码结果是长度(>256),则接下来按照Huffman码表2解码,逐步解码即可:

    [As ]:110110(A)0111(s)000(空格)

    [mentioned ]:10101(m)001(e)0110(n)1000(t)10100(i)10110(o)0110(n)001(e)10010(d)000(空格)

    [above,]:0100(a)110111(b)10110(o)111100(v)001(e)110100(,)

    [there ]:1000(t)10011(h)001(e)10111(r)001(e)000(空格)

    [are ]:0100(a)11001(长度3,表示下一个需要用Huffman解码)10(Distance=4,即重复字符串为re空格)

    [many ]:10101(m)0100(a)0110(n)11000(y)000(空格)

    [kinds ]:111010(k)10100(i)0110(n)10010(d)0111(s)000(空格)

    [of ]:10110(o)111001(f)000(空格)

    [wireless ]:111101(w)10100(i)10111(r)001(e)0101(l)001(e)0111(s)0111(s)000(空格)

    [systems o]:0111(s)11000(y)0111(s)1000(t)001(e)10101(m)11001(长度指示=3,接下来根据distance解码)0110(Distance=20,即重复字符串为s o)

    [ther ]:111111(长度指示=4,接下来根据distance解码)111001(Distance=42,即重复字符串为ther)000(空格)

    [than ]:1000(t)10011(h)0100(a)0110(n)000(空格)

    [cellular.]:111000(c)001(e)0101(l)0101(l)111011(u)0101(l)0100(a)10111(r)110101(.)

    [256,结束标志]111110(结束标志)0000(字节补齐的0)

    于是解压缩结果为:

    As mentioned above,there are many kinds of wireless systems other than cellular.

    再来回顾我们的解码过程:

    译码过程:
    1、根据HCLEN得到截尾信息,并参照固定置换表,根据CCL比特流得到CCL整数序列;
    2、根据CCL整数序列构造出等价于CCL的二级Huffman码表3;
    3、根据二级Huffman码表3对CL1、CL2比特流进行解码,得到SQ1整数序列,SQ2整数序列;
    4、根据SQ1整数序列,SQ2整数序列,利用游程编码规则得到等价的CL1整数序列、CL2整数序列;
    5、根据CL1整数序列、CL2整数序列分别构造两个一级Huffman码表:literal/length码表、distance码表;
    6、根据两个一级Huffman码表对后面的LZ压缩数据进行解码得到literal/length/distance流;
    7、根据literal/length/distance流按照LZ规则进行解码。

    Deflate码流长度总共为72字节=576比特,其中:

    3比特Header;

    5比特HLIT;

    5比特HDIST;

    4比特HCLEN;

    54比特CCL序列码流;

    133比特CL1序列码流;

    34比特CL2序列码流;

    338比特LZ压缩后的literal/length/distance码流。

    11、ZIP的其它说明

    上面各个环节已经详细分析了ZIP压缩的过程以及解码流程,通过对一个实例的解压缩过程分析,可以彻底地掌握ZIP压缩和解压缩的原理和过程。还有一些情况需要说明:

    (1)上面的算法复杂度主要在于压缩一端,因为需要统计literal/length/distance,创建动态Huffman码表,相反解压只需要还原码表后,逐比特解析即可,这也是压缩软件的一个典型特点,解压速度远快于压缩速度。

    (2)上面我们分析了动态Huffman,对于LZ压缩后的literal/length/distance,也可以采用静态Huffman编码,这主要取决于ZIP在压缩中看哪种方式更节省空间,静态Huffman编码不需要记录码表,因为这个码表是固定的,在RFC1951里面也有说明。对于literal/length码表来说,需要对0-285进行编码,其码表为:

    对于Distance来说,需要对Code=0-29的数进行编码,则直接采用5比特表示。Distance和动态Huffman一样,在此基础上进行扩展。

    (3)ZIP中使用的LZ77算法是一种改进的LZ77。主要区别有两点:

    1)标准LZ77在找到重复字符串时输出三元组(length, distance, 下一个未匹配的字符)(有兴趣可以关注LZ77那篇论文);Deflate在找到重复字符串时仅输出双元组(length, distance)。
    2)标准LZ77使用”贪婪“的方式解析,寻找的都是最长匹配字符串。Deflate中不完全如此。David Salomon的书里给了一个例子:

    对于上面这个例子,标准LZ77在滑动窗口中查找最长匹配字符串,找到的是"the"与前面的there的前三个字符匹配,这种贪婪解析方式逻辑简单,但编码效率不一定最高。Deflate则不急于输出,跳过t继续往后查看,发现"th ne"这5个字符存在重复字符串,因此,Deflate算法会选择将t作为未匹配字符输出,而对后面的匹配字符串用(length, distance)编码输出。显然,这样就提高了压缩效率,因为标准的LZ77找到的重复字符串长度为3,而Deflate找到的是5。换句话说,Deflate算法并不是简单的寻找最长匹配后输出,而是会权衡几种可行的编码方式,用其中最高效的方式输出。

     

    12、总结

    本篇博文对ZIP中使用的压缩算法进行了详细分析,从一个简单地例子出发,一步步地分析了PK设计Deflate算法的思路。最后,通过一个实际例子,分析了其解压缩流程。总的来看,ZIP的核心在于如何对LZ压缩后的literal、length、distance进行Huffman编码,以及如何以最小空间记录Huffman码表。整个过程充满了对数据结构尤其是树的深入优化利用。按照上面的分析,如果要对ZIP进行进一步改进,可以考虑的地方也有不少,典型的有:

    (1)扩大LZ编码的滑动窗口的大小;

    (2)将Huffman编码改进为算术编码等压缩率更高的方法,毕竟,Huffman的码字长度必须为整数,这就从理论上限制了它的压缩率只能接近于理论极限,但难以达到。我记得在JPEG图像编码领域,以前的JPEG采用了DCT变换编码+Huffman的方式,现在JPEG2000将其改为小波变换+算数编码,所以数据压缩也可以尝试类似的思路;

    (3)将多个文件进行合并压缩,ZIP中,不同的文件压缩过程没有关系,独立进行,如果将它们合并起来一起进行压缩,压缩率可以得到进一步提高。

     

    描述分析有误的地方,敬请指正。针对数据压缩相关的话题,后续会对HBase列压缩等等进行分析,看看ZIP这种文件压缩和HBase这种数据库数据压缩的区别和联系。

    展开全文
  • 图像分割综述

    万次阅读 多人点赞 2019-07-09 22:03:48
    其基本思想是,模拟由一些基因串控制的生物群体的进化过程,把该过程的原理应用到搜索算法中,以提高寻优的速度和质量。此算法的搜索过程不直接作用在变量上,而是在参数集进行了编码的个体,这使得遗传算法可直接对...

    本文作者净浩泽,公众号:计算机视觉life,编辑成员

    图像分割是计算机视觉研究中的一个经典难题,已经成为图像理解领域关注的一个热点,图像分割是图像分析的第一步,是计算机视觉的基础,是图像理解的重要组成部分,同时也是图像处理中最困难的问题之一。所谓图像分割是指根据灰度、彩色、空间纹理、几何形状等特征把图像划分成若干个互不相交的区域,使得这些特征在同一区域内表现出一致性或相似性,而在不同区域间表现出明显的不同。简单的说就是在一副图像中,把目标从背景中分离出来。对于灰度图像来说,区域内部的像素一般具有灰度相似性,而在区域的边界上一般具有灰度不连续性。 关于图像分割技术,由于问题本身的重要性和困难性,从20世纪70年代起图像分割问题就吸引了很多研究人员为之付出了巨大的努力。虽然到目前为止,还不存在一个通用的完美的图像分割的方法,但是对于图像分割的一般性规律则基本上已经达成的共识,已经产生了相当多的研究成果和方法。

    本文对于目前正在使用的各种图像分割方法进行了一定的归纳总结,由于笔者对于图像分割的了解也是初窥门径,所以难免会有一些错误,还望各位读者多多指正,共同学习进步。

    传统分割方法

    这一大部分我们将要介绍的是深度学习大火之前人们利用数字图像处理、拓扑学、数学等方面的只是来进行图像分割的方法。当然现在随着算力的增加以及深度学习的不断发展,一些传统的分割方法在效果上已经不能与基于深度学习的分割方法相比较了,但是有些天才的思想还是非常值得我们去学习的。
    1.基于阈值的分割方法
    阈值法的基本思想是基于图像的灰度特征来计算一个或多个灰度阈值,并将图像中每个像素的灰度值与阈值作比较,最后将像素根据比较结果分到合适的类别中。因此,该方法最为关键的一步就是按照某个准则函数来求解最佳灰度阈值。
    阈值法特别适用于目标和背景占据不同灰度级范围的图。
    图像若只有目标和背景两大类,那么只需要选取一个阈值进行分割,此方法成为单阈值分割;但是如果图像中有多个目标需要提取,单一阈值的分割就会出现作物,在这种情况下就需要选取多个阈值将每个目标分隔开,这种分割方法相应的成为多阈值分割。

    如图所示即为对数字的一种阈值分割方法。
    阀值分割方法的优缺点:

    • 计算简单,效率较高;
    • 只考虑像素点灰度值本身的特征,一般不考虑空间特征,因此对噪声比较敏感,鲁棒性不高。
      从前面的介绍里我们可以看出,阈值分割方法的最关键就在于阈值的选择。若将智能遗传算法应用在阀值筛选上,选取能最优分割图像的阀值,这可能是基于阀值分割的图像分割法的发展趋势。
      2.基于区域的图像分割方法
      基于区域的分割方法是以直接寻找区域为基础的分割技术,基于区域提取方法有两种基本形式:一种是区域生长,从单个像素出发,逐步合并以形成所需要的分割区域;另一种是从全局出发,逐步切割至所需的分割区域。
      区域生长
      区域生长是从一组代表不同生长区域的种子像素开始,接下来将种子像素邻域里符合条件的像素合并到种子像素所代表的生长区域中,并将新添加的像素作为新的种子像素继续合并过程,知道找不到符合条件的新像素为止(小编研一第一学期的机器学习期末考试就是手写该算法 T.T),该方法的关键是选择合适的初始种子像素以及合理的生长准则。
      区域生长算法需要解决的三个问题:
      (1)选择或确定一组能正确代表所需区域的种子像素;
      (2)确定在生长过程中能将相邻像素包括进来的准则;
      (3)指定让生长过程停止的条件或规则。
      区域分裂合并
      区域生长是从某个或者某些像素点出发,最终得到整个区域,进而实现目标的提取。而分裂合并可以说是区域生长的逆过程,从整幅图像出发,不断的分裂得到各个子区域,然后再把前景区域合并,得到需要分割的前景目标,进而实现目标的提取。其实如果理解了上面的区域生长算法这个区域分裂合并算法就比较好理解啦。
      四叉树分解法就是一种典型的区域分裂合并法,基本算法如下:
      (1)对于任一区域,如果H(Ri)=FALSE就将其分裂成不重叠的四等分;
      (2)对相邻的两个区域Ri和Rj,它们也可以大小不同(即不在同一层),如果条件H(RiURj)=TURE满足,就将它们合并起来;
      (3)如果进一步的分裂或合并都不可能,则结束。
      其中R代表整个正方形图像区域,P代表逻辑词。
      区域分裂合并算法优缺点:
      (1)对复杂图像分割效果好;
      (2)算法复杂,计算量大;
      (3)分裂有可能破怪区域的边界。
      在实际应用当中通常将区域生长算法和区域分裂合并算法结合使用,该类算法对某些复杂物体定义的复杂场景的分割或者对某些自然景物的分割等类似先验知识不足的图像分割效果较为理想。
      分水岭算法
      分水岭算法是一个非常好理解的算法,它根据分水岭的构成来考虑图像的分割,现实中我们可以想象成有山和湖的景象,那么一定是如下图的,水绕山山围水的景象。
      分水岭分割方法,是一种基于拓扑理论的数学形态学的分割方法,其基本思想是把图像看作是测地学上的拓扑地貌,图像中每一点像素的灰度值表示该点的海拔高度,每一个局部极小值及其影响区域称为集水盆,而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面,刺穿一个小孔,然后把整个模型慢慢浸入水中,随着浸入的加深,每一个局部极小值的影响域慢慢向外扩展,在两个集水盆汇合处构筑大坝,即形成分水岭。
      分水岭对微弱边缘具有良好的响应,图像中的噪声、物体表面细微的灰度变化都有可能产生过度分割的现象,但是这也同时能够保证得到封闭连续边缘。同时,分水岭算法得到的封闭的集水盆也为分析图像的区域特征提供了可能。

    3.基于边缘检测的分割方法

    基于边缘检测的图像分割算法试图通过检测包含不同区域的边缘来解决分割问题。它可以说是人们最先想到也是研究最多的方法之一。通常不同区域的边界上像素的灰度值变化比较剧烈,如果将图片从空间域通过傅里叶变换到频率域,边缘就对应着高频部分,这是一种非常简单的边缘检测算法。
    边缘检测技术通常可以按照处理的技术分为串行边缘检测和并行边缘检测。串行边缘检测是要想确定当前像素点是否属于检测边缘上的一点,取决于先前像素的验证结果。并行边缘检测是一个像素点是否属于检测边缘高尚的一点取决于当前正在检测的像素点以及与该像素点的一些临近像素点。
    最简单的边缘检测方法是并行微分算子法,它利用相邻区域的像素值不连续的性质,采用一阶或者二阶导数来检测边缘点。近年来还提出了基于曲面拟合的方法、基于边界曲线拟合的方法、基于反应-扩散方程的方法、串行边界查找、基于变形模型的方法。

    边缘检测的优缺点:
    (1)边缘定位准确;
    (2)速度快;
    (3)不能保证边缘的连续性和封闭性;
    (4)在高细节区域存在大量的碎边缘,难以形成一个大区域,但是又不宜将高细节区域分成小碎片;
    由于上述的(3)(4)两个难点,边缘检测只能产生边缘点,而非完整意义上的图像分割过程。这也就是说,在边缘点信息获取到之后还需要后续的处理或者其他相关算法相结合才能完成分割任务。
    在以后的研究当中,用于提取初始边缘点的自适应阈值选取、用于图像的层次分割的更大区域的选取以及如何确认重要边缘以去除假边缘将变得非常重要。

    结合特定工具的图像分割算法

    基于小波分析和小波变换的图像分割方法

    小波变换是近年来得到的广泛应用的数学工具,也是现在数字图像处理必学部分,它在时间域和频率域上都有量高的局部化性质,能将时域和频域统一于一体来研究信号。而且小波变换具有多尺度特性,能够在不同尺度上对信号进行分析,因此在图像分割方面的得到了应用,
    二进小波变换具有检测二元函数的局部突变能力,因此可作为图像边缘检测工具。图像的边缘出现在图像局部灰度不连续处,对应于二进小波变换的模极大值点。通过检测小波变换模极大值点可以确定图像的边缘小波变换位于各个尺度上,而每个尺度上的小波变换都能提供一定的边缘信息,因此可进行多尺度边缘检测来得到比较理想的图像边缘。

    上图左图是传统的阈值分割方法,右边的图像就是利用小波变换的图像分割。可以看出右图分割得到的边缘更加准确和清晰
    另外,将小波和其他方法结合起来处理图像分割的问题也得到了广泛研究,比如一种局部自适应阈值法就是将Hilbert图像扫描和小波相结合,从而获得了连续光滑的阈值曲线。

    基于遗传算法的图像分割

    ​ 遗传算法(Genetic Algorithms,简称GA)是1973年由美国教授Holland提出的,是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法。是仿生学在数学领域的应用。其基本思想是,模拟由一些基因串控制的生物群体的进化过程,把该过程的原理应用到搜索算法中,以提高寻优的速度和质量。此算法的搜索过程不直接作用在变量上,而是在参数集进行了编码的个体,这使得遗传算法可直接对结构对象(图像)进行操作。整个搜索过程是从一组解迭代到另一组解,采用同时处理群体中多个个体的方法,降低了陷入局部最优解的可能性,并易于并行化。搜索过程采用概率的变迁规则来指导搜索方向,而不采用确定性搜索规则,而且对搜索空间没有任何特殊要求(如连通性、凸性等),只利用适应性信息,不需要导数等其他辅助信息,适应范围广。
    ​ 遗传算法擅长于全局搜索,但局部搜索能力不足,所以常把遗传算法和其他算法结合起来应用。将遗传算法运用到图像处理主要是考虑到遗传算法具有与问题领域无关且快速随机的搜索能力。其搜索从群体出发,具有潜在的并行性,可以进行多个个体的同时比较,能有效的加快图像处理的速度。但是遗传算法也有其缺点:搜索所使用的评价函数的设计、初始种群的选择有一定的依赖性等。要是能够结合一些启发算法进行改进且遗传算法的并行机制的潜力得到充分的利用,这是当前遗传算法在图像处理中的一个研究热点。

    基于主动轮廓模型的分割方法

    ​ 主动轮廓模型(active contours)是图像分割的一种重要方法,具有统一的开放式的描述形式,为图像分割技术的研究和创新提供了理想的框架。在实现主动轮廓模型时,可以灵活的选择约束力、初始轮廓和作用域等,以得到更佳的分割效果,所以主动轮廓模型方法受到越来越多的关注。
    ​ 该方法是在给定图像中利用曲线演化来检测目标的一类方法,基于此可以得到精确的边缘信息。其基本思想是,先定义初始曲线C,然后根据图像数据得到能量函数,通过最小化能量函数来引发曲线变化,使其向目标边缘逐渐逼近,最终找到目标边缘。这种动态逼近方法所求得的边缘曲线具有封闭、光滑等优点。

    ​ 传统的主动轮廓模型大致分为参数主动轮廓模型和几何主动轮廓模型。参数主动轮廓模型将曲线或曲面的形变以参数化形式表达,Kass等人提出了经典的参数活动轮廓模型即“Snake”模型,其中Snake定义为能量极小化的样条曲线,它在来自曲线自身的内力和来自图像数据的外力的共同作用下移动到感兴趣的边缘,内力用于约束曲线形状,而外力则引导曲线到特征此边缘。参数主动轮廓模型的特点是将初始曲线置于目标区域附近,无需人为设定曲线的的演化是收缩或膨胀,其优点是能够与模型直接进行交互,且模型表达紧凑,实现速度快;其缺点是难以处理模型拓扑结构的变化。比如曲线的合并或分裂等。而使用水平集(level set)的几何活动轮廓方法恰好解决了这一问题。

    基于深度学习的分割

    1.基于特征编码(feature encoder based)

    在特征提取领域中VGGnet和ResNet是两个非常有统治力的方法,接下来的一些篇幅会对这两个方法进行简短的介绍

    a.VGGNet

    ​ 由牛津大学计算机视觉组合和Google DeepMind公司研究员一起研发的深度卷积神经网络。它探索了卷积神经网络的深度和其性能之间的关系,通过反复的堆叠33的小型卷积核和22的最大池化层,成功的构建了16~19层深的卷积神经网络。VGGNet获得了ILSVRC 2014年比赛的亚军和定位项目的冠军,在top5上的错误率为7.5%。目前为止,VGGNet依然被用来提取图像的特征。

    ​ VGGNet的优缺点

    1. 由于参数量主要集中在最后的三个FC当中,所以网络加深并不会带来参数爆炸的问题;
    2. 多个小核卷积层的感受野等同于一个大核卷积层(三个3x3等同于一个7x7)但是参数量远少于大核卷积层而且非线性操作也多于后者,使得其学习能力较强
    3. VGG由于层数多而且最后的三个全连接层参数众多,导致其占用了更多的内存(140M)
    b.ResNet

    ​ 随着深度学习的应用,各种深度学习模型随之出现,虽然在每年都会出现性能更好的新模型,但是对于前人工作的提升却不是那么明显,其中有重要问题就是深度学习网络在堆叠到一定深度的时候会出现梯度消失的现象,导致误差升高效果变差,后向传播时无法将梯度反馈到前面的网络层,使得前方的网络层的参数难以更新,训练效果变差。这个时候ResNet恰好站出来,成为深度学习发展历程中一个重要的转折点。
    ​ ResNet是由微软研究院的Kaiming He等四名华人提出,他们通过自己提出的ResNet Unit成功训练出来152层的神经网络并在ILSVRC2015比赛中斩获冠军。ResNet语义分割领域最受欢迎且最广泛运用的神经网络.ResNet的核心思想就是在网络中引入恒等映射,允许原始输入信息直接传到后面的层中,在学习过程中可以只学习上一个网络输出的残差(F(x)),因此ResNet又叫做残差网络。、

    使用到ResNet的分割模型:

    • Efficient Neural Network(ENet):该网络类似于ResNet的bottleNeck方法;
    • ResNet-38:该网络在训练or测试阶段增加并移除了一些层,是一种浅层网络,它的结构是ResNet+FCN;
    • full-resolution residual network(FRRN):FRRN网络具有和ResNet相同优越的训练特性,它由残差流和池化流两个处理流组成;
    • AdapNey:根据ResNet-50的网络进行改进,让原本的ResNet网络能够在更短的时间内学习到更多高分辨率的特征;
      ……
      ResNet的优缺点:
      1)引入了全新的网络结构(残差学习模块),形成了新的网络结构,可以使网络尽可能地加深;
      2)使得前馈/反馈传播算法能够顺利进行,结构更加简单;
      3)恒等映射地增加基本上不会降低网络的性能;
      4)建设性地解决了网络训练的越深,误差升高,梯度消失越明显的问题;
      5)由于ResNet搭建的层数众多,所以需要的训练时间也比平常网络要长。

    2.基于区域选择(regional proposal based)

    Regional proposal 在计算机视觉领域是一个非常常用的算法,尤其是在目标检测领域。其核心思想就是检测颜色空间和相似矩阵,根据这些来检测待检测的区域。然后根据检测结果可以进行分类预测。
    在语义分割领域,基于区域选择的几个算法主要是由前人的有关于目标检测的工作渐渐延伸到语义分割的领域的,接下来小编将逐步介绍其个中关系。

    Stage Ⅰ: R-CNN

    伯克利大学的Girshick教授等人共同提出了首个在目标检测方向应用的深度学习模型:Region-based Convolutional Neural Network(R-CNN)。该网络模型如下图所示,其主要流程为:先使用selective search算法提取2000个候选框,然后通过卷积网络对候选框进行串行的特征提取,再根据提取的特征使用SVM对候选框进行分类预测,最后使用回归方法对区域框进行修正。

    R-CNN的优缺点:

    • 是首个开创性地将深度神经网络应用到目标检测的算法;
    • 使用Bounding Box Regression对目标检测的框进行调整;
    • 由于进行特征提取时是串行,处理耗时过长;
    • Selective search算法在提取每一个region时需要2s的时间,浪费大量时间
    Stage Ⅱ:Fast R-CNN

    ​ 由于R-CNN的效率太低,2015年由Ross等学者提出了它的改进版本:Fast R-CNN。其网络结构图如下图所示(从提取特征开始,略掉了region的选择)Fast R-CNN在传统的R-CNN模型上有所改进的地方是它是直接使用一个神经网络对整个图像进行特征提取,就省去了串行提取特征的时间;接着使用一个RoI Pooling Layer在全图的特征图上摘取每一个RoI对应的特征,再通过FC进行分类和包围框的修正。

    Fast R-CNN的优缺点

    • 节省了串行提取特征的时间;
    • 除了selective search以外的其它所有模块都可以合在一起训练;
    • 最耗时间的selective search算法依然存在。
    Stage Ⅲ:Faster R-CNN

    2016年提出的Faster R-CNN可以说有了突破性的进展(虽然还是目标检测哈哈哈),因为它改变了它的前辈们最耗时最致命的部位:selective search算法。它将selective search算法替换成为RPN,使用RPN网络进行region的选取,将2s的时间降低到10ms,其网络结构如下图所示:

    Faster R-CNN优缺点:

    • 使用RPN替换了耗时的selective search算法,对整个网络结构有了突破性的优化;
    • Faster R-CNN中使用的RPN和selective search比起来虽然速度更快,但是精度和selective search相比稍有不及,如果更注重速度而不是精度的话完全可以只使用RPN;
    Stage Ⅳ:Mask R-CNN

    Mask R-CNN(终于到分割了!)是何恺明大神团队提出的一个基于Faster R-CNN模型的一种新型的分割模型,此论文斩获ICCV 2017的最佳论文,在Mask R-CNN的工作中,它主要完成了三件事情:目标检测,目标分类,像素级分割。
    恺明大神是在Faster R-CNN的结构基础上加上了Mask预测分支,并且改良了ROI Pooling,提出了ROI Align。其网络结构真容就如下图所示啦:

    Mask R-CNN的优缺点:

    • 引入了预测用的Mask-Head,以像素到像素的方式来预测分割掩膜,并且效果很好;
    • 用ROI Align替代了ROI Pooling,去除了RoI Pooling的粗量化,使得提取的特征与输入良好对齐;
    • 分类框与预测掩膜共享评价函数,虽然大多数时间影响不大,但是有的时候会对分割结果有所干扰。
    Stage Ⅴ:Mask Scoring R-CNN

    最后要提出的是2019年CVPR的oral,来自华中科技大学的研究生黄钊金同学提出的
    MS R-CNN,这篇文章的提出主要是对上文所说的Mask R-CNN的一点点缺点进行了修正。他的网络结构也是在Mask R-CNN的网络基础上做了一点小小的改进,添加了Mask-IoU。
    黄同学在文章中提到:恺明大神的Mask R-CNN已经很好啦!但是有个小毛病,就是评价函数只对目标检测的候选框进行打分,而不是分割模板(就是上文提到的优缺点中最后一点),所以会出现分割模板效果很差但是打分很高的情况。所以黄同学增加了对模板进行打分的MaskIoU Head,并且最终的分割结果在COCO数据集上超越了恺明大神,下面就是MS R-CNN的网络结构啦~

    MS R-CNN的优缺点:

    • 优化了Mask R-CNN中的信息传播,提高了生成预测模板的质量;
    • 未经大批量训练的情况下,就拿下了COCO 2017挑战赛实例分割任务冠军;
    • 要说缺点的话。。应该就是整个网络有些庞大,一方面需要ResNet当作主干网络,另一方面需要其它各种Head共同承担各种任务。

    3.基于RNN的图像分割

    Recurrent neural networks(RNNs)除了在手写和语音识别上表现出色外,在解决计算机视觉的任务上也表现不俗,在本篇文章中我们就将要介绍RNN在2D图像处理上的一些应用,其中也包括介绍使用到它的结构或者思想的一些模型。
    RNN是由Long-Short-Term Memory(LSTM)块组成的网络,RNN来自序列数据的长期学习的能力以及随着序列保存记忆的能力使其在许多计算机视觉的任务中游刃有余,其中也包括语义分割以及数据标注的任务。接下来的部分我们将介绍几个使用到RNN结构的用于分割的网络结构模型:

    1.ReSeg模型

    ReSeg可能不被许多人所熟知,在百度上搜索出的相关说明与解析也不多,但是这是一个很有效的语义分割方法。众所周知,FCN可谓是图像分割领域的开山作,而RegNet的作者则在自己的文章中大胆的提出了FCN的不足:没有考虑到局部或者全局的上下文依赖关系,而在语义分割中这种依赖关系是非常有用的。所以在ReSeg中作者使用RNN去检索上下文信息,以此作为分割的一部分依据。

    该结构的核心就是Recurrent Layer,它由多个RNN组合在一起,捕获输入数据的局部和全局空间结构。
    优缺点:

    • 充分考虑了上下文信息关系;
    • 使用了中值频率平衡,它通过类的中位数(在训练集上计算)和每个类的频率之间的比值来重新加权类的预测。这就增加了低频率类的分数,这是一个更有噪声的分割掩码的代价,因为被低估的类的概率被高估了,并且可能导致在输出分割掩码中错误分类的像素增加。
    2.MDRNNs(Multi-Dimensional Recurrent Neural Networks)模型

    传统的RNN在一维序列学习问题上有着很好的表现,比如演讲(speech)和在线手写识别。但是 在多为问题中应用却并不到位。MDRNNs在一定程度上将RNN拓展到多维空间领域,使之在图像处理、视频处理等领域上也能有所表现。
    该论文的基本思想是:将单个递归连接替换为多个递归连接,相应可以在一定程度上解决时间随数据样本的增加呈指数增长的问题。以下就是该论文提出的两个前向反馈和反向反馈的算法。

    4.基于上采样/反卷积的分割方法

    卷积神经网络在进行采样的时候会丢失部分细节信息,这样的目的是得到更具特征的价值。但是这个过程是不可逆的,有的时候会导致后面进行操作的时候图像的分辨率太低,出现细节丢失等问题。因此我们通过上采样在一定程度上可以不全一些丢失的信息,从而得到更加准确的分割边界。
    接下来介绍几个非常著名的分割模型:

    a.FCN(Fully Convolutional Network)

    是的!讲来讲去终于讲到这位大佬了,FCN!在图像分割领域已然成为一个业界标杆,大多数的分割方法多多少少都会利用到FCN或者其中的一部分,比如前面我们讲过的Mask R-CNN。
    在FCN当中的反卷积-升采样结构中,图片会先进性上采样(扩大像素);再进行卷积——通过学习获得权值。FCN的网络结构如下图所示:

    当然最后我们还是需要分析一下FCN,不能无脑吹啦~
    优缺点:

    • FCN对图像进行了像素级的分类,从而解决了语义级别的图像分割问题;
    • FCN可以接受任意尺寸的输入图像,可以保留下原始输入图像中的空间信息;
    • 得到的结果由于上采样的原因比较模糊和平滑,对图像中的细节不敏感;
    • 对各个像素分别进行分类,没有充分考虑像素与像素的关系,缺乏空间一致性。
    2.SetNet

    SegNet是剑桥提出的旨在解决自动驾驶或者智能机器人的图像语义分割深度网络,SegNet基于FCN,与FCN的思路十分相似,只是其编码-解码器和FCN的稍有不同,其解码器中使用去池化对特征图进行上采样,并在分各种保持高频细节的完整性;而编码器不使用全连接层,因此是拥有较少参数的轻量级网络:

    图像分割是计算机视觉研究中的一个经典难题,已经成为图像理解领域关注的一个热点,图像分割是图像分析的第一步,是计算机视觉的基础,是图像理解的重要组成部分,同时也是图像处理中最困难的问题之一。所谓图像分割是指根据灰度、彩色、空间纹理、几何形状等特征把图像划分成若干个互不相交的区域,使得这些特征在同一区域内表现出一致性或相似性,而在不同区域间表现出明显的不同。简单的说就是在一副图像中,把目标从背景中分离出来。对于灰度图像来说,区域内部的像素一般具有灰度相似性,而在区域的边界上一般具有灰度不连续性。 关于图像分割技术,由于问题本身的重要性和困难性,从20世纪70年代起图像分割问题就吸引了很多研究人员为之付出了巨大的努力。虽然到目前为止,还不存在一个通用的完美的图像分割的方法,但是对于图像分割的一般性规律则基本上已经达成的共识,已经产生了相当多的研究成果和方法。

    本文对于目前正在使用的各种图像分割方法进行了一定的归纳总结,由于笔者对于图像分割的了解也是初窥门径,所以难免会有一些错误,还望各位读者多多指正,共同学习进步。

    SetNet的优缺点:

    • 保存了高频部分的完整性;
    • 网络不笨重,参数少,较为轻便;
    • 对于分类的边界位置置信度较低;
    • 对于难以分辨的类别,例如人与自行车,两者如果有相互重叠,不确定性会增加。
      以上两种网络结构就是基于反卷积/上采样的分割方法,当然其中最最最重要的就是FCN了,哪怕是后面大名鼎鼎的SegNet也是基于FCN架构的,而且FCN可谓是语义分割领域中开创级别的网络结构,所以虽然这个部分虽然只有两个网络结构,但是这两位可都是重量级嘉宾,希望各位能够深刻理解~

    5.基于提高特征分辨率的分割方法

    在这一个模块中我们主要给大家介绍一下基于提升特征分辨率的图像分割的方法。换一种说法其实可以说是恢复在深度卷积神经网络中下降的分辨率,从而获取更多的上下文信息。这一系列我将给大家介绍的是Google提出的DeepLab 。
    DeepLab是结合了深度卷积神经网络和概率图模型的方法,应用在语义分割的任务上,目的是做逐像素分类,其先进性体现在DenseCRFs(概率图模型)和DCNN的结合。是将每个像素视为CRF节点,利用远程依赖关系并使用CRF推理直接优化DCNN的损失函数。
    在图像分割领域,FCN的一个众所周知的操作就是平滑以后再填充,就是先进行卷积再进行pooling,这样在降低图像尺寸的同时增大感受野,但是在先减小图片尺寸(卷积)再增大尺寸(上采样)的过程中一定有一些信息损失掉了,所以这里就有可以提高的空间。
    接下来我要介绍的是DeepLab网络的一大亮点:Dilated/Atrous Convolution,它使用的采样方式是带有空洞的采样。在VGG16中使用不同采样率的空洞卷积,可以明确控制网络的感受野。

    图a对应3x3的1-dilated conv,它和普通的卷积操作是相同的;图b对应3x3的2-dilated conv,事迹卷积核的尺寸还是3x3(红点),但是空洞为1,其感受野能够达到7x7;图c对应3x3的4-dilated conv,其感受野已经达到了15x15.写到这里相信大家已经明白,在使用空洞卷积的情况下,加大了感受野,使每个卷积输出都包含了较大范围的信息。
    这样就解决了DCNN的几个关于分辨率的问题:
    1)内部数据结构丢失;空间曾计划信息丢失;
    2)小物体信息无法重建;
    当然空洞卷积也存在一定的问题,它的问题主要体现在以下两方面:
    1)网格效应
    加入我们仅仅多次叠加dilation rate 2的 3x3 的卷积核则会出现以下问题

    我们发现卷积核并不连续,也就是说并不是所有的像素都用来计算了,这样会丧失信息的连续性;
    2)小物体信息处理不当
    我们从空洞卷积的设计背景来看可以推测出它是设计来获取long-ranged information。然而空洞步频选取得大获取只有利于大物体得分割,而对于小物体的分割可能并没有好处。所以如何处理好不同大小物体之间的关系也是设计好空洞卷积网络的关键。

    6.基于特征增强的分割方法

    基于特征增强的分割方法包括:提取多尺度特征或者从一系列嵌套的区域中提取特征。在图像分割的深度网络中,CNN经常应用在图像的小方块上,通常称为以每个像素为中心的固定大小的卷积核,通过观察其周围的小区域来标记每个像素的分类。在图像分割领域,能够覆盖到更大部分的上下文信息的深度网络通常在分割的结果上更加出色,当然这也伴随着更高的计算代价。多尺度特征提取的方法就由此引进。
    在这一模块中我先给大家介绍一个叫做SLIC,全称为simple linear iterative cluster的生成超像素的算法。
    首先我们要明确一个概念:啥是超像素?其实这个比较容易理解,就像上面说的“小方块”一样,我们平常处理图像的最小单位就是像素了,这就是像素级(pixel-level);而把像素级的图像划分成为区域级(district-level)的图像,把区域当成是最基本的处理单元,这就是超像素啦。
    算法大致思想是这样的,将图像从RGB颜色空间转换到CIE-Lab颜色空间,对应每个像素的(L,a,b)颜色值和(x,y)坐标组成一个5维向量V[l, a, b, x, y],两个像素的相似性即可由它们的向量距离来度量,距离越大,相似性越小。
    算法首先生成K个种子点,然后在每个种子点的周围空间里搜索距离该种子点最近的若干像素,将他们归为与该种子点一类,直到所有像素点都归类完毕。然后计算这K个超像素里所有像素点的平均向量值,重新得到K个聚类中心,然后再以这K个中心去搜索其周围与其最为相似的若干像素,所有像素都归类完后重新得到K个超像素,更新聚类中心,再次迭代,如此反复直到收敛。
    有点像聚类的K-Means算法,最终会得到K个超像素。
    Mostahabi等人提出的一种前向传播的分类方法叫做Zoom-Out就使用了SLIC的算法,它从多个不同的级别提取特征:局部级别:超像素本身;远距离级别:能够包好整个目标的区域;全局级别:整个场景。这样综合考虑多尺度的特征对于像素或者超像素的分类以及分割来说都是很有意义的。
    接下来的部分我将给大家介绍另一种完整的分割网络:PSPNet:Pyramid Scene Parsing Network
    论文提出在场景分割是,大多数的模型会使用FCN的架构,但是FCN在场景之间的关系和全局信息的处理能力存在问题,其典型问题有:1.上下文推断能力不强;2.标签之间的关系处理不好;3.模型可能会忽略小的东西。
    本文提出了一个具有层次全局优先级,包含不同子区域时间的不同尺度的信息,称之为金字塔池化模块。
    该模块融合了4种不同金字塔尺度的特征,第一行红色是最粗糙的特征–全局池化生成单个bin输出,后面三行是不同尺度的池化特征。为了保证全局特征的权重,如果金字塔共有N个级别,则在每个级别后使用1×1 1×11×1的卷积将对于级别通道降为原本的1/N。再通过双线性插值获得未池化前的大小,最终concat到一起。其结构如下图:

    最终结果就是,在融合不同尺度的feature后,达到了语义和细节的融合,模型的性能表现提升很大,作者在很多数据集上都做过训练,最终结果是在MS-COCO数据集上预训练过的效果最好。

    为了捕捉多尺度特征,高层特征包含了更多的语义和更少的位置信息。结合多分辨率图像和多尺度特征描述符的优点,在不丢失分辨率的情况下提取图像中的全局和局部信息,这样就能在一定程度上提升网络的性能。

    7.使用CRF/MRF的方法

    首先让我们熟悉熟悉到底啥是MRF的CRF的。
    MRF全称是Marcov Random Field,马尔可夫随机场,其实说起来笔者在刚读硕士的时候有一次就有同学在汇报中提到了隐马尔可夫、马尔可夫链啥的,当时还啥都不懂,小白一枚(现在是准小白hiahia),觉得马尔可夫这个名字贼帅,后来才慢慢了解什么马尔科夫链呀,马尔可夫随机场,并且在接触到图像分割了以后就对马尔科夫随机场有了更多的了解。
    MRF其实是一种基于统计的图像分割算法,马尔可夫模型是指一组事件的集合,在这个集合中,事件逐个发生,并且下一刻事件的发生只由当前发生的事件决定,而与再之前的状态没有关系。而马尔可夫随机场,就是具有马尔可夫模型特性的随机场,就是场中任何区域都只与其临近区域相关,与其他地方的区域无关,那么这些区域里元素(图像中可以是像素)的集合就是一个马尔可夫随机场。
    CRF的全称是Conditional Random Field,条件随机场其实是一种特殊的马尔可夫随机场,只不过是它是一种给定了一组输入随机变量X的条件下另一组输出随机变量Y的马尔可夫随机场,它的特点是埃及设输出随机变量构成马尔可夫随机场,可以看作是最大熵马尔可夫模型在标注问题上的推广。
    在图像分割领域,运用CRF比较出名的一个模型就是全连接条件随机场(DenseCRF),接下来我们将花费一些篇幅来简单介绍一下。
    CRF在运行中会有一个问题就是它只对相邻节点进行操作,这样会损失一些上下文信息,而全连接条件随机场是对所有节点进行操作,这样就能获取尽可能多的临近点信息,从而获得更加精准的分割结果。
    在Fully connected CRF中,吉布斯能量可以写作:

    我们重点关注二元部分:

    其中k(m)为高斯核,写作:

    该模型的一元势能包含了图像的形状,纹理,颜色和位置,二元势能使用了对比度敏感的的双核势能,CRF的二元势函数一般是描述像素点与像素点之间的关系,鼓励相似像素分配相同的标签,而相差较大的像素分配不同标签,而这个“距离”的定义与颜色值和实际相对距离有关,这样CRF能够使图像尽量在边界处分割。全连接CRF模型的不同就在于其二元势函数描述的是每一个像素与其他所有像素的关系,使用该模型在图像中的所有像素对上建立点对势能从而实现极大地细化和分割。
    在分割结果上我们可以看看如下的结果图:

    可以看到它在精细边缘的分割比平常的分割方法要出色得多,而且文章中使用了另一种优化算法,使得本来需要及其大量运算的全连接条件随机场也能在很短的时间里给出不错的分割结果。
    至于其优缺点,我觉得可以总结为以下几方面:

    • 在精细部位的分割非常优秀;
    • 充分考虑了像素点或者图片区域之间的上下文关系;
    • 在粗略的分割中可能会消耗不必要的算力;
    • 可以用来恢复细致的局部结构,但是相应的需要较高的代价。
      OK,那么本次的推送就到这里结束啦,本文的主要内容是对图像分割的算法进行一个简单的分类和介绍。综述对于各位想要深入研究的看官是非常非常重要的资源:大佬们经常看综述一方面可以了解算法的不足并在此基础上做出改进;萌新们可以通过阅读一篇好的综述入门某一个学科,比如今天的内容就是图像分割。
      谢谢各位朋友们的观看!

    推荐阅读

    如何从零开始系统化学习视觉SLAM?
    从零开始一起学习SLAM | 为什么要学SLAM?
    从零开始一起学习SLAM | 学习SLAM到底需要学什么?
    从零开始一起学习SLAM | SLAM有什么用?
    从零开始一起学习SLAM | C++新特性要不要学?
    从零开始一起学习SLAM | 为什么要用齐次坐标?
    从零开始一起学习SLAM | 三维空间刚体的旋转
    从零开始一起学习SLAM | 为啥需要李群与李代数?
    从零开始一起学习SLAM | 相机成像模型
    从零开始一起学习SLAM | 不推公式,如何真正理解对极约束?
    从零开始一起学习SLAM | 神奇的单应矩阵
    从零开始一起学习SLAM | 你好,点云
    从零开始一起学习SLAM | 给点云加个滤网
    从零开始一起学习SLAM | 点云平滑法线估计
    从零开始一起学习SLAM | 点云到网格的进化
    从零开始一起学习SLAM | 理解图优化,一步步带你看懂g2o代码
    从零开始一起学习SLAM | 掌握g2o顶点编程套路
    从零开始一起学习SLAM | 掌握g2o边的代码套路
    零基础小白,如何入门计算机视觉?
    SLAM领域牛人、牛实验室、牛研究成果梳理
    我用MATLAB撸了一个2D LiDAR SLAM
    可视化理解四元数,愿你不再掉头发
    最近一年语义SLAM有哪些代表性工作?
    视觉SLAM技术综述
    汇总 | VIO、激光SLAM相关论文分类集锦
    研究SLAM,对编程的要求有多高?
    2018年SLAM、三维视觉方向求职经验分享
    2018年SLAM、三维视觉方向求职经验分享
    深度学习遇到SLAM | 如何评价基于深度学习的DeepVO,VINet,VidLoc?
    视觉SLAM关键方法总结
    SLAM方向公众号、知乎、博客上有哪些大V可以关注?
    SLAM实验室
    SLAM方向国内有哪些优秀公司?
    SLAM面试常见问题
    SLAM相关领域数据集调研
    从零开始一起学习SALM-ICP原理及应用
    解放双手——相机与IMU外参的在线标定
    目标检测

    展开全文
  • 如果页面浮动布局多,就要增加很多空div,让人感觉很不好 3,父级div定义 伪类:after 和 zoom 原理:IE8以上和非IE浏览器才支持:after,原理和方法2有点类似,zoom(IE转有属性)可解决ie6,ie7浮动问题 优点:浏览器...

    近期总结一一些面试题 都是企业的面试题笔记题

    感觉薪资10k下的都会出笔试题   

    特别高的薪资都是直接技术面试或者是 现场编程 

    总结很多人的面试题,后期会对于单个知识点再说笔记详细讲解。

    最新Vue面试题网址:2021年 Vue经典面试题 -- 必问知识点 --(包含答案)_xm1037782843的博客-CSDN博客_vue面试题

    敬请关注公众 :包含全套 Vue 最新面试题  js最近面试题 等大量前端知识技术。

     

    部分都是百度的答案,不是特全面的,可以自己找下

    同时分享一个自己录制的CSS3动画特效经典案例【推荐教程】--后期会更新vue框架 微信小程序等内容。

    最近录制的ajax从基础到实战的视频,包含原生ajax  jquery的ajax 以及ajax接口获取数据等

    Ajax前端开发、项目实战、从零基础到精通、接口数据调用-学习视频教程-腾讯课堂

    红色为常见面试题

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

    前端面试题: 

    1. 一个200*200的div在不同分辨率屏幕上下左右居中,用css实现

    <div style="width:500px;height:500px;border:1px solid green;display:flex;justify-content:center;align-items:center;">
      <div style="">
        上下左右居中
      </div>
    </div>

    2. 写一个左中右布局占满屏幕,其中左右两块是固定宽度200 ,中间自适应宽,要求先加载中间块,请写出结构及样式:

    <div id="left">我是左边</div>
        <div id="center">我是中间</div>
        <div id="right">我是右边</div>
    
    html,body{ margin: 0px;width: 100%; } 
    #left,#right{width: 200px;height: 200px;background-color: aqua;
        position: absolute;}
        #left{left: 0;top:0;}
        #right{right: 0;top:0;}
        #center{margin: 0 200px;background-color: blue;height: 200px;}

    或者利用弹性盒子

        <style>
            * {
                margin: 0;
                padding: 0;
            }
    
            html,
            body {
                height: 100%;
            }
    
            body {
                display: flex;
            }
    
            .left {
                width: 100px;
                background-color: rgb(199, 170, 223);
            }
    
            .center {
                background-color: rgb(151, 228, 148);
                flex: 1;
            }
    
            .right {
                width: 100px;
                background-color: rgb(199, 170, 223);
    
    
            }
        </style>
    
    <body>
        <div class="left">left</div>
        <div class="center">center</div>
        <div class="right">right</div>
    </body>
    

    3. 阐述清楚浮动的几种方式(常见问题)

    1.父级div定义 height

    原理:父级div手动定义height,就解决了父级div无法自动获取到高度的问题。
    优点:简单、代码少、容易掌握
    缺点:只适合高度固定的布局,要给出精确的高度,如果高度和父级div不一样时,会产生问题

    2.父级div定义 overflow:hidden

    原理:必须定义width或zoom:1,同时不能定义height,使用overflow:hidden时,浏览器会自动检查浮动区域的高度
    优点:简单、代码少、浏览器支持好

    4. 结尾处加空div标签 clear:both

    原理:添加一个空div,利用css提高的clear:both清除浮动,让父级div能自动获取到高度
    优点:简单、代码少、浏览器支持好、不容易出现怪问题

    缺点:不少初学者不理解原理;如果页面浮动布局多,就要增加很多空div,让人感觉很不好

    5. 解释css sprites ,如何使用?

    CSS Sprites其实就是把网页中一些背景图片整合到一张图片文件中,再利用CSS的“background-image”,“background- repeat”,“background-position”的组合进行背景定位,background-position可以用数字能精确的定位出背景图片的位置。

    CSS Sprites为一些大型的网站节约了带宽,让提高了用户的加载速度和用户体验,不需要加载更多的图片

    6. 如何用原生js给一个按钮绑定两个onclick事件?

    Var  btn=document.getElementById(‘btn’);

    //事件监听 绑定多个事件

    var btn4 = document.getElementById("btn4");

    btn4.addEventListener("click",hello1);

    btn4.addEventListener("click",hello2);

    function hello1(){

     alert("hello 1");

    }

    function hello2(){

     alert("hello 2");

    }

    7. 拖拽会用到哪些事件

    · dragstart:拖拽开始时在被拖拽元素上触发此事件,监听器需要设置拖拽所需数据,从操作系统拖拽文件到浏览器时不触发此事件.

    · dragenter:拖拽鼠标进入元素时在该元素上触发,用于给拖放元素设置视觉反馈,如高亮

    · dragover:拖拽时鼠标在目标元素上移动时触发.监听器通过阻止浏览器默认行为设置元素为可拖放元素.

    · dragleave:拖拽时鼠标移出目标元素时在目标元素上触发.此时监听器可以取消掉前面设置的视觉效果.

    · drag:拖拽期间在被拖拽元素上连续触发

    · drop:鼠标在拖放目标上释放时,在拖放目标上触发.此时监听器需要收集数据并且执行所需操作.如果是从操作系统拖放文件到浏览器,需要取消浏览器默认行为.

    · dragend:鼠标在拖放目标上释放时,在拖拽元素上触发.将元素从浏览器拖放到操作系统时不会触发此事件.

    8. 请列举jquery中的选择器:

    9. Javascript中的定时器有哪些?他们的区别及用法是什么?

    setTimeout 只执行一次
    setInterval 会一直重复执行

    9.请描述一下 cookies sessionStorage和localstorage区别

    相同点:都存储在客户端
    不同点:1.存储大小

    · cookie数据大小不能超过4k。

    · sessionStorage和localStorage 虽然也有存储大小的限制,但比cookie大得多,可以达到5M或更大。

    2.有效时间

    · localStorage    存储持久数据,浏览器关闭后数据不丢失除非主动删除数据;

    · sessionStorage  数据在当前浏览器窗口关闭后自动删除。

    · cookie          设置的cookie过期时间之前一直有效,即使窗口或浏览器关闭

    3. 数据与服务器之间的交互方式

    · cookie的数据会自动的传递到服务器,服务器端也可以写cookie到客户端

    · sessionStorage和localStorage不会自动把数据发给服务器,仅在本地保存。

    10.计算一个数组arr所有元素的和

    var arr1=[1,2,3,4,5,6,7,8,9];

    var sum1=0;

    for (var i=0;i<=arr1.length;i++) {

    if (typeof arr1[i]=="number") {

    sum1+=arr1[i];

    }

    }

    document.write(sum1);

    //====================================

    function sum2(arr){

    var all=0;

    for (var i=0;i<arr.length;i++) {

    if (typeof arr[i]=="number") {

    all+=arr[i];

    }

    }

    return all;

    }

    document.write(sum2([1,2,3,4]));

    11.编写一个方法去掉数组里面 重复的内容  var arr=[1,2,3,4,5,1,2,3]

    一个数组去重的简单实现

     

    var arr = ['abc','abcd','sss','2','d','t','2','ss','f','22','d'];

    //定义一个新的数组

    var s = [];

    //遍历数组

    for(var i = 0;i<arr.length;i++){

        if(s.indexOf(arr[i]) == -1){  //判断在s数组中是否存在,不存在则push到s数组中

            s.push(arr[i]);

        }

    }

    console.log(s);

    //输出结果:["abc", "abcd", "sss", "2", "d", "t", "ss", "f", "22"]

    方法二:用sort()  然后相邻比较也可以实现

    12.document.write和innerHTML的区别:

    document.write是直接写入到页面的内容流,如果在写之前没有调用document.open, 浏览器会自动调用open。每次写完关闭之后重新调用该函数,会导致页面被重写。

    innerHTML则是DOM页面元素的一个属性,代表该元素的html内容。你可以精确到某一个具体的元素来进行更改。如果想修改document的内容,则需要修改document.documentElement.innerElement。

    innerHTML将内容写入某个DOM节点,不会导致页面全部重绘

     

    innerHTML很多情况下都优于document.write,其原因在于其允许更精确的控制要刷新页面的那一个部分。

    13.ajax的步骤

    什么是ajax?

    ajax(异步javascript xml) 能够刷新局部网页数据而不是重新加载整个网页。

    如何使用ajax?

    第一步,创建xmlhttprequest对象,var xmlhttp =new XMLHttpRequest();XMLHttpRequest对象用来和服务器交换数据。

    var xhttp;

    if (window.XMLHttpRequest) {

    //现代主流浏览器

    xhttp = new XMLHttpRequest();

    } else {

    // 针对浏览器,比如IE5或IE6

    xhttp = new ActiveXObject("Microsoft.XMLHTTP");

    }

    第二步,使用xmlhttprequest对象的open()和send()方法发送资源请求给服务器。

    第三步,使用xmlhttprequest对象的responseText或responseXML属性获得服务器的响应。

    第四步,onreadystatechange函数,当发送请求到服务器,我们想要服务器响应执行一些功能就需要使用onreadystatechange函数,每次xmlhttprequest对象的readyState发生改变都会触发onreadystatechange函数

    14.xml和json的区别,请用四个词语来形容

    ·  JSON相对于XML来讲,数据的体积小,传递的速度更快些

    ·  JSON与JavaScript的交互更加方便,更容易解析处理,更好的数据交互

    ·  XML对数据描述性比较好;

    ·  JSON的速度要远远快于XML

     

    15.清楚浮动的方法?(多次出现在面试题)

    1.父级div定义 height
    原理:父级div手动定义height,就解决了父级div无法自动获取到高度的问题。
    优点:简单、代码少、容易掌握

    缺点:只适合高度固定的布局,要给出精确的高度,如果高度和父级div不一样时,会产生问题

    2,结尾处加空div标签 clear:both

    原理:添加一个空div,利用css提高的clear:both清除浮动,让父级div能自动获取到高度
    优点:简单、代码少、浏览器支持好、不容易出现怪问题
    缺点:不少初学者不理解原理;如果页面浮动布局多,就要增加很多空div,让人感觉很不好
    3,父级div定义 伪类:after 和 zoom

    原理:IE8以上和非IE浏览器才支持:after,原理和方法2有点类似,zoom(IE转有属性)可解决ie6,ie7浮动问题
    优点:浏览器支持好、不容易出现怪问题(目前:大型网站都有使用,如:腾迅,网易,新浪等等)
    缺点:代码多、不少初学者不理解原理,要两句代码结合使用才能让主流浏览器都支持
    4,父级div定义 overflow:hidden

    原理:必须定义width或zoom:1,同时不能定义height,使用overflow:hidden时,浏览器会自动检查浮动区域的高度
    优点:简单、代码少、浏览器支持好
    缺点:不能和position配合使用,因为超出的尺寸的会被隐藏。

     

    16.box-sizing常用的属性有哪些?分别有什么作用?

    属性值

    · box-sizing:content-box

    · box-sizing:border-box

    · box-sizing:inherit

     

    content-box

    · 这是box-sizing的默认属性值

    · 是CSS2.1中规定的宽度高度的显示行为

    · 在CSS中定义的宽度和高度就对应到元素的内容框

    · 在CSS中定义的宽度和高度之外绘制元素的内边距和边框

     

    border-box

    · 在CSS中微元素设定的宽度和高度就决定了元素的边框盒

    · 即为元素在设置内边距和边框是在已经设定好的宽度和高度之内进行绘制

    · CSS中设定的宽度和高度减去边框和内间距才能得到元素内容所占的实际宽度和高度

    (Q1)box-sizing: content-box|border-box|inherit;
    (Q2)content-box:宽度和高度分别应用到元素的内容框。在宽度和高度之外绘制元素的内边距和边框(元素默认效果)。
    border-box:元素指定的任何内边距和边框都将在已设定的宽度和高度内进行绘制。通过从已设定的宽度和高度分别减去边框和内边距才能得到内容的宽度和高度。

     

    17.css选择器有哪些,选择器的权重的优先级

    选择器类型

    1、ID  #id

    2、class  .class

    3、标签  p

    4、通用  *

    5、属性  [type="text"]

    6、伪类  :hover

    7、伪元素  ::first-line

    8、子选择器、相邻选择器

    三、权重计算规则

    1. 第一等:代表内联样式,如: style=””,权值为1000。

    2. 第二等:代表ID选择器,如:#content,权值为0100。

    3. 第三等:代表类,伪类和属性选择器,如.content,权值为0010。

    4. 第四等:代表类型选择器和伪元素选择器,如div p,权值为0001。

    5. 通配符、子选择器、相邻选择器等的。如*、>、+,权值为0000。

    6. 继承的样式没有权值。

    18. 块级元素水平垂直居中的方法有哪些(三个方法)

    让div等块级元素水平和垂直都居中,即永远处于屏幕的正中央,当我们做如登录块时非常有用!

     实现一、原理:要让div等块级元素水平和垂直居中,必需知道该div等块级元素的宽度和高度,然后设置位置为绝对位置,距离页面窗口左边框和上边框的距离设置为50%,这个50%就是指页面窗口的宽度和高度的50%,最后将该div等块级元素分别左移和上移,左移和上移的大小就是该div等块级元素宽度和高度的一半。

       CSS代码:

    .mycss{ 

       width:300px;  

       height:200px;  

       position:absolute;  

       left:50%;  

       top:50%;  

       margin:-100px 0 0 -150px }

     实现二原理:利用CSS的margin设置为auto让浏览器自己帮我们水平和垂直居中。

       CSS代码:

    .mycss{

        position: absolute;

        left: 0px;

        right: 0;

        top: 0;

        bottom: 0;

        margin: auto;

        height: 200px;

        width: 300px;

    }

    jQuery实现水平和垂直居中

     原理:jQuery实现水平和垂直居中的原理就是通过jQuery设置div等块级元素的CSS,获取div等块级元素的左、上的边距偏移量,边距偏移量的算法就是用页面窗口 的宽度减去该div等块级元素的宽度,得到的值再除以2即左偏移量,右偏移量算法相同。注意div等块级元素的CSS设置要在resize()方法中完成,就是每次改变窗口大 小时,都要执行设置div等块级元素的CSS。

    jquery代码:

    $(window).resize(function(){

        $(".myblock").css({

            position: "absolute",

            left: ($(window).width() - $(".myblock").outerWidth())/2,

            top: ($(window).height() - $(".myblock").outerHeight())/2     });        

    });

    此外在页面载入时,就需要调用resize()方法

    $(function(){

        $(window).resize();

    });

     

    19.三个盒子,左右定宽,中间自适应有几种方法

    第一种:左右侧采用浮动 中间采用margin-left 和 margin-right 方法。

    代码如下:

    <div style="width:100%; margin:0 auto;"> 

     

           <div style="width:200px; float:right; background-color:#960">这是右侧的内容 固定宽度</div>

     

           <div style="width:150px; float:left; background:#6FF">这是左侧的内容 固定宽度</div>

     

           <div style="margin-left:150px;margin-right:200px; background-color:#9F3">中间内容,自适应宽度</div>

     

        </div>

    第二种:左右两侧采用绝对定位 中间同样采用margin-left margin-right方法:

     

    第三种负的margin

    使用这种方法就稍微复杂了一些了,使用的是负的margin值,而且html标签也增加了,先来看其代码吧:

    <div id="main">

     <div id="mainContainer">main content</div></div><div id="left">

     <div id="leftContainer" class="inner">left content</div></div><div id="right">

     <div id="rightContainer" class="inner">right</div></div>

    #main {

     float: left;

     width: 100%;

    }

    #mainContainer {

     margin: 0 230px;

     height: 200px;

     background: green;

    }

    #left {

     float: left;

     margin-left: -100%;

     width: 230px} 

    #right {

     float: left;

     margin-left: -230px;

     width: 230px;

    } 

    #left .inner,

    #right .inner {

     background: orange;

     margin: 0 10px;

     height: 200px;

    }

    20.js有几种数据类型,其中基本数据类型有哪些

    五种基本类型: Undefined、Null、Boolean、Number和String。

    1中复杂的数据类型————Object,Object本质上是由一组无序的名值对组成的。

    Object、Array和Function则属于引用类型

     

    21.undefined 和 null 区别

     

    null: Null类型,代表“空值”,代表一个空对象指针,使用typeof运算得到 “object”,所以你可以认为它是一个特殊的对象值。

    undefined: Undefined类型,当一个声明了一个变量未初始化时,得到的就是undefined。

    null是javascript的关键字,可以认为是对象类型,它是一个空对象指针,和其它语言一样都是代表“空值”,不过 undefined 却是javascript才有的。undefined是在ECMAScript第三版引入的,为了区分空指针对象和未初始化的变量,它是一个预定义的全局变量。没有返回值的函数返回为undefined,没有实参的形参也是undefined。

     

    javaScript权威指南: null 和 undefined 都表示“值的空缺”,你可以认为undefined是表示系统级的、出乎意料的或类似错误的值的空缺,而null是表示程序级的、正常的或在意料之中的值的空缺。

    22.http 和 https 有何区别?如何灵活使用?

     

    http是HTTP协议运行在TCP之上。所有传输的内容都是明文,客户端和服务器端都无法验证对方的身份。

    https是HTTP运行在SSL/TLS之上,SSL/TLS运行在TCP之上。所有传输的内容都经过加密,加密采用对称加密,但对称加密的密钥用服务器方的证书进行了非对称加密。此外客户端可以验证服务器端的身份,如果配置了客户端验证,服务器方也可以验证客户端的身份


    23.常见的HTTP状态码

    2开头 (请求成功)表示成功处理了请求的状态代码。

    200   (成功)  服务器已成功处理了请求。 通常,这表示服务器提供了请求的网页。 
    201   (已创建)  请求成功并且服务器创建了新的资源。 
    202   (已接受)  服务器已接受请求,但尚未处理。 
    203   (非授权信息)  服务器已成功处理了请求,但返回的信息可能来自另一来源。 
    204   (无内容)  服务器成功处理了请求,但没有返回任何内容。 
    205   (重置内容) 服务器成功处理了请求,但没有返回任何内容。
    206   (部分内容)  服务器成功处理了部分 GET 请求。

    3开头 (请求被重定向)表示要完成请求,需要进一步操作。 通常,这些状态代码用来重定向。

    300   (多种选择)  针对请求,服务器可执行多种操作。 服务器可根据请求者 (user agent) 选择一项操作,或提供操作列表供请求者选择。 
    301   (永久移动)  请求的网页已永久移动到新位置。 服务器返回此响应(对 GET 或 HEAD 请求的响应)时,会自动将请求者转到新位置。
    302   (临时移动)  服务器目前从不同位置的网页响应请求,但请求者应继续使用原有位置来进行以后的请求。
    303   (查看其他位置) 请求者应当对不同的位置使用单独的 GET 请求来检索响应时,服务器返回此代码。
    304   (未修改) 自从上次请求后,请求的网页未修改过。 服务器返回此响应时,不会返回网页内容。 
    305   (使用代理) 请求者只能使用代理访问请求的网页。 如果服务器返回此响应,还表示请求者应使用代理。 
    307   (临时重定向)  服务器目前从不同位置的网页响应请求,但请求者应继续使用原有位置来进行以后的请求。

    4开头 (请求错误)这些状态代码表示请求可能出错,妨碍了服务器的处理。

    400   (错误请求) 服务器不理解请求的语法。 
    401   (未授权) 请求要求身份验证。 对于需要登录的网页,服务器可能返回此响应。 
    403   (禁止) 服务器拒绝请求。
    404   (未找到) 服务器找不到请求的网页。
    405   (方法禁用) 禁用请求中指定的方法。 
    406   (不接受) 无法使用请求的内容特性响应请求的网页。 
    407   (需要代理授权) 此状态代码与 401(未授权)类似,但指定请求者应当授权使用代理。
    408   (请求超时)  服务器等候请求时发生超时。 
    409   (冲突)  服务器在完成请求时发生冲突。 服务器必须在响应中包含有关冲突的信息。 
    410   (已删除)  如果请求的资源已永久删除,服务器就会返回此响应。 
    411   (需要有效长度) 服务器不接受不含有效内容长度标头字段的请求。 
    412   (未满足前提条件) 服务器未满足请求者在请求中设置的其中一个前提条件。 
    413   (请求实体过大) 服务器无法处理请求,因为请求实体过大,超出服务器的处理能力。 
    414   (请求的 URI 过长) 请求的 URI(通常为网址)过长,服务器无法处理。 
    415   (不支持的媒体类型) 请求的格式不受请求页面的支持。 
    416   (请求范围不符合要求) 如果页面无法提供请求的范围,则服务器会返回此状态代码。 
    417   (未满足期望值) 服务器未满足"期望"请求标头字段的要求。

    5开头(服务器错误)这些状态代码表示服务器在尝试处理请求时发生内部错误。 这些错误可能是服务器本身的错误,而不是请求出错。

    500   (服务器内部错误)  服务器遇到错误,无法完成请求。 
    501   (尚未实施) 服务器不具备完成请求的功能。 例如,服务器无法识别请求方法时可能会返回此代码。 
    502   (错误网关) 服务器作为网关或代理,从上游服务器收到无效响应。 
    503   (服务不可用) 服务器目前无法使用(由于超载或停机维护)。 通常,这只是暂时状态。 
    504   (网关超时)  服务器作为网关或代理,但是没有及时从上游服务器收到请求。 
    505   (HTTP 版本不受支持) 服务器不支持请求中所用的 HTTP 协议版本。

     

     

    24. 如何进行网站性能优化

    1. 从用户角度而言,优化能够让页面加载得更快、对用户的操作响应得更及时,能够给用户提供更为友好的体验。
    2. 从服务商角度而言,优化能够减少页面请求数、或者减小请求所占带宽,能够节省可观的资源。
      总之,恰当的优化不仅能够改善站点的用户体验并且能够节省相当的资源利用。
      前端优化的途径有很多,按粒度大致可以分为两类,第一类是页面级别的优化,例如 HTTP请求数、脚本的无阻塞加载、内联脚本的位置优化等 ;第二类则是代码级别的优化,例如 Javascript中的DOM 操作优化、CSS选择符优化、图片优化以及 HTML结构优化等等。另外,本着提高投入产出比的目的,后文提到的各种优化策略大致按照投入产出比从大到小的顺序排列。
      一、页面级优化
    1. JavaScript 压缩和模块打包
    2. 按需加载资源
    3. 在使用 DOM 操作库时用上 array-ids
    4. 缓存
    5. 启用 HTTP/2
    6. 应用性能分析
    7. 使用负载均衡方案
    8. 为了更快的启动时间考虑一下同构
    9. 使用索引加速数据库查询
    10. 使用更快的转译方案
    11. 避免或最小化 JavaScript 和 CSS 的使用而阻塞渲染
    12. 用于未来的一个建议:使用 service workers + 流
    13. 图片编码优化

    25. react和vue有哪些不同,说说你对这两个框架的看法

    相同点

    · 都支持服务器端渲染

    · 都有Virtual DOM,组件化开发,通过props参数进行父子组件数据的传递,都实现webComponent规范

    · 数据驱动视图

    · 都有支持native的方案,React的React native,Vue的weex

    不同点

    · React严格上只针对MVC的view层,Vue则是MVVM模式

    · virtual DOM不一样,vue会跟踪每一个组件的依赖关系,不需要重新渲染整个组件树.而对于React而言,每当应用的状态被改变时,全部组件都会重新渲染,所以react中会需要shouldComponentUpdate这个生命周期函数方法来进行控制

    · 组件写法不一样, React推荐的做法是 JSX + inline style, 也就是把HTML和CSS全都写进JavaScript了,即'all in js'; Vue推荐的做法是webpack+vue-loader的单文件组件格式,即html,css,jd写在同一个文件;

    · 数据绑定: vue实现了数据的双向绑定,react数据流动是单向的

    · state对象在react应用中不可变的,需要使用setState方法更新状态;在vue中,state对象不是必须的,数据由data属性在vue对象中管理

    26.什么是mvvm mvc是什么区别 原理

    一、MVC(Model-View-Controller)

    MVC是比较直观的架构模式,用户操作->View(负责接收用户的输入操作)->Controller(业务逻辑处理)->Model(数据持久化)->View(将结果反馈给View)。

    MVC使用非常广泛,比如JavaEE中的SSH框架

     

    三、MVVM(Model-View-ViewModel)

    如果说MVP是对MVC的进一步改进,那么MVVM则是思想的完全变革。它是将“数据模型数据双向绑定”的思想作为核心,因此在View和Model之间没有联系,通过ViewModel进行交互,而且Model和ViewModel之间的交互是双向的,因此视图的数据的变化会同时修改数据源,而数据源数据的变化也会立即反应view

    27.px和em的区别

    px表示像素 (计算机屏幕上的一个点:1px = 1/96in),是绝对单位,不会因为其他元素的尺寸变化而变化;

    · 

    · 

    em表示相对于父元素的字体大小。em是相对单位 ,没有一个固定的度量值,而是由其他元素尺寸来决定的相对值。

    28.优雅降级和渐进增强

    渐进增强(Progressive Enhancement):一开始就针对低版本浏览器进行构建页面,完成基本的功能,然后再针对高级浏览器进行效果、交互、追加功能达到更好的体验。

    优雅降级(Graceful Degradation):一开始就构建站点的完整功能,然后针对浏览器测试和修复。比如一开始使用 CSS3 的特性构建了一个应用,然后逐步针对各大浏览器进行 hack 使其可以在低版本浏览器上正常浏览。

    其实渐进增强和优雅降级并非什么新概念,只是旧的概念换了一个新的说法。在传统软件开发中,经常会提到向上兼容向下兼容的概念。渐进增强相当于向上兼容,而优雅降级相当于向下兼容

    29.eval()的作用

    把字符串参数解析成JS代码并运行,并返回执行的结果;

    eval("2+3");//执行加运算,并返回运算值。  

    eval("varage=10");//声明一个age变量  

    eval的作用域

    functiona(){  

    1.  eval("var x=1"); //等效于 var x=1;  

    2.  console.log(x); //输出1  

    3. }  

    4. a();  

    5. console.log(x);//错误 x没有定

    30. JS哪些操作会造成内存泄露

    1)意外的全局变量引起的内存泄露

    function leak(){  

      leak="xxx";//leak成为一个全局变量,不会被回收  

    }

    2)闭包引起的内存泄露

    3)3)没有清理的DOM元素引用

    4)被遗忘的定时器或者回调 5)子元素存在引起的内存泄露

    31. 浏览器缓存有哪些,通常缓存有哪几种

    一、http缓存

    二、websql

    cookie

    localstorage

    sessionstorage

    flash缓存

    32:bootstrap响应式实现的原理

    百分比布局+媒体查询

    33.关于JS事件冒泡与JS事件代理(事件委托)

     事件作为DOM操作重要的一环,需要大家好好理解和运用,今天特意看了一下事件冒泡和事件代理的相关资料,感触颇深,也深感自己的无知不知道多浪费了多少内存,废话不多说进入正题:

    1.事件冒泡:

          通俗易懂的来讲,就是当一个子元素的事件被触发的时候(如onclick事件),该事件会从事件源(被点击的子元素)开始逐级向上传播,触发父级元素的点击事件。

    2.事件委托

        事件委托,首先按字面的意思就能看你出来,是将事件交由别人来执行,再联想到上面讲的事件冒泡,是不是想到了?对,就是将子元素的事件通过冒泡的形式交由父元素来执行。下面经过详细的例子来说明事件委托:

    有可能在开发的时候会遇到这种情况:如导航每一个栏目都要加一个事件,你可能会通过遍历来给每个栏目添加事件:

    事件委托是怎

    1. var ul = document.getElementById('parentUl');  

    2.     ul.οnclick=function (event) {  

    3.       var e = event||window.event,  

    4.               source = e.target || e.srcElement;//target表示在事件冒泡中触发事件的源元素,在IE中是srcElement  

    5.         if(source.nodeName.toLowerCase() == "li"){   //判断只有li触发的才会输出内容  

    6.             alert(source.innerHTML);  

    7.         }  

    8.         stopPropagation(e);                           //阻止继续冒泡  

    9.     };  

    10.     function addElement() {  

    11.         var li = document.createElement('li');  

    12.         li.innerHTML="我是新孩子";  

    13.         ul.appendChild(li);  

    14.     }  

    34. CSS样式覆盖规则

    规则一:由于继承而发生样式冲突时,最近祖先获胜。

    规则二:继承的样式和直接指定的样式冲突时,直接指定的样式获胜

    规则三:直接指定的样式发生冲突时,样式权值高者获胜。

    样式的权值取决于样式的选择器,权值定义如下表。

    CSS选择器

    权值

    标签选择器

    1

    类选择器

    10

    ID选择器

    100

    内联样式

    1000

    伪元素(:first-child等)

    1

    伪类(:link等)

    10

    可以看到,内联样式的权值>>ID选择器>>类选择器>>标签选择器,除此以外,后代选择器的权值为每项权值之和,比如”#nav .current a”的权值为100 + 10 + 1 = 111。

    规则四:样式权值相同时,后者获胜。

    规则五:!important的样式属性不被覆盖。

    !important可以看做是万不得已的时候,打破上述四个规则的”金手指”。如果你一定要采用某个样式属性,而不让它被覆盖的,可以在属性值后加上!important,以规则四的例子为例,”.byline a {color:red !important;}”可以强行使链接显示红色。大多数情况下都可以通过其他方式来控制样式的覆盖,不能滥用!important。

    35. 介绍一下box-sizing属性

    兼容问题 
    首先,box-sizing属性在FireFox中存在兼容问题,所以需要使用-moz-box-sizing做一下兼容。

     

    属性值

    · box-sizing:content-box

    · box-sizing:border-box

    · box-sizing:inherit

     

    content-box

    · 这是box-sizing的默认属性值

    · 是CSS2.1中规定的宽度高度的显示行为

    · 在CSS中定义的宽度和高度就对应到元素的内容框

    · 在CSS中定义的宽度和高度之外绘制元素的内边距和边框

     

    border-box

    · 在CSS中微元素设定的宽度和高度就决定了元素的边框盒

    · 即为元素在设置内边距和边框是在已经设定好的宽度和高度之内进行绘制

    · CSS中设定的宽度和高度减去边框和内间距才能得到元素内容所占的实际宽度和高度

    36. css选择符有哪些?优先级算法如何计算?(常见)

    37. 请简要描述margin重合问题,及解决方式

    1.同向margin的重叠:
    1图片的margin-top与3图片的margin-top发生重叠,2图片的margin-bottom与3图片的margin-bottom发生重叠。这时候重叠之后的margin值由发生重叠两片的最大值决定;如果其中一个出现负值,则由最大的正边距减去绝对值最大的负边距,如果没有最大正边距,则由0减去绝对值最大的负边距。
    解决同向重叠的方法:
    (1)在最外层的div中加入overflow:hidden;zoom:1
    (2)在最外层加入padding:1px;属性
    (3)在最外层加入:border:1px solid #cacbcc;
    2.异向重叠问题:
    1图片的margin-bottom与2图片的margin-top发生重叠,这时候重叠之后的margin值由发生重叠两图片的最大值的决定的。
    解决异向重叠问题:
    float:left(只能解决IE6浏览器中的异向重叠问题,可以解决IE8以上、chorme、firefox、opera下的同向重叠问题)

     

    38:position的值,relative\absolute\fixed分别相对于进行谁定位,有什么区别,什么时候用?

    39.解释下CSS sprites,以及你要如何在页面或网站中使用它。

    CSS Sprites其实就是把网页中一些背景图片整合到一张图片文件中,再利用CSS的“background-image”,“background-repeat”,“background-position”的组合进行背景定位,background-position可以用数字能精确的定位出背景图片的位置

     

    40.什么是闭包,如何使用它,为什么要使用它?

    包就是能够读取其他函数内部变量的函数。由于在Javascript语言中,只有函数内部的子函数才能读取局部变量,因此可以把闭包简单理解成“定义在一个函数内部的函数”。

    所以,在本质上,闭包就是将函数内部和函数外部连接起来的一座桥梁。闭包可以用在许多地方。它的最大用处有两个,一个是前面提到的可以读取函数内部的变量,另一个就是让这些变量的值始终保持在内存中。

    使用闭包的注意点:

    · 由于闭包会使得函数中的变量都被保存在内存中,内存消耗很大,所以不能滥用闭包,否则会造成网页的性能问题,在IE中可能导致内存泄露。解决方法是,在退出函数之前,将不使用的局部变量全部删除。

    · 闭包会在父函数外部,改变父函数内部变量的值。所以,如果你把父函数当作对象(object)使用,把闭包当作它的公用方法(Public Method),把内部变量当作它的私有属性(private value),这时一定要小心,不要随便改变父函数内部变量的值。

     

    41.请解释JSONP的工作原理,以及它为什么不是真正的AJAX。

    JSONP (JSON with Padding)是一个简单高效的跨域方式,HTML中的script标签可以加载并执行其他域的javascript,于是我们可以通过script标记来动态加载其他域的资源。例如我要从域A的页面pageA加载域B的数据,那么在域B的页面pageB中我以JavaScript的形式声明pageA需要的数据,然后在 pageA中用script标签把pageB加载进来,那么pageB中的脚本就会得以执行。JSONP在此基础上加入了回调函数,pageB加载完之后会执行pageA中定义的函数,所需要的数据会以参数的形式传递给该函数。JSONP易于实现,但是也会存在一些安全隐患,如果第三方的脚本随意地执行,那么它就可以篡改页面内容,截获敏感数据。但是在受信任的双方传递数据,JSONP是非常合适的选择。

    AJAX是不跨域的,而JSONP是一个是跨域的,还有就是二者接收参数形式不一样!

    42.请解释一下JavaScript的同源策略。

    在客户端编程语言中,如javascript和 ActionScript,同源策略是一个很重要的安全理念,它在保证数据的安全性方面有着重要的意义。同源策略规定跨域之间的脚本是隔离的,一个域的脚本不能访问和操作另外一个域的绝大部分属性和方法。那么什么叫相同域,什么叫不同的域呢?当两个域具有相同的协议, 相同的端口,相同的host,那么我们就可以认为它们是相同的域。同源策略还应该对一些特殊情况做处理,比如限制file协议下脚本的访问权限。本地的HTML文件在浏览器中是通过file协议打开的,如果脚本能通过file协议访问到硬盘上其它任意文件,就会出现安全隐患,目前IE8还有这样的隐患。

    43.怎样添加、移除、移动、复制、创建和查找节点?

     1)创建新节点

    createDocumentFragment() //创建一个DOM片段
    createElement() //创建一个具体的元素
    createTextNode() //创建一个文本节点

    2)添加、移除、替换、插入
    appendChild() //添加
    removeChild() //移除
    replaceChild() //替换
    insertBefore() //插入

    3)查找
    getElementsByTagName() //通过标签名称
    getElementsByName() //通过元素的Name属性的值
    getElementById() //通过元素Id,唯一性

    44.谈谈垃圾回收机制方式及内存管理

    回收机制方式

    1、定义和用法:垃圾回收机制(GC:Garbage Collection),执行环境负责管理代码执行过程中使用的内存。

    2、原理:垃圾收集器会定期(周期性)找出那些不在继续使用的变量,然后释放其内存。但是这个过程不是实时的,因为其开销比较大,所以垃圾回收器会按照固定的时间间隔周期性的执行。

    3、实例如下:

    function fn1() {

        var obj = {name: 'hanzichi', age: 10};

    }

    function fn2() {

        var obj = {name:'hanzichi', age: 10};

       return obj;

    }var a = fn1();var b = fn2();

    fn1中定义的obj为局部变量,而当调用结束后,出了fn1的环境,那么该块内存会被js引擎中的垃圾回收器自动释放;在fn2被调用的过程中,返回的对象被全局变量b所指向,所以该块内存并不会被释放。

     4、垃圾回收策略:标记清除(较为常用)和引用计数。

    标记清除:

      定义和用法:当变量进入环境时,将变量标记"进入环境",当变量离开环境时,标记为:"离开环境"。某一个时刻,垃圾回收器会过滤掉环境中的变量,以及被环境变量引用的变量,剩下的就是被视为准备回收的变量。

      到目前为止,IE、Firefox、Opera、Chrome、Safari的js实现使用的都是标记清除的垃圾回收策略或类似的策略,只不过垃圾收集的时间间隔互不相同。

    引用计数:

      定义和用法:引用计数是跟踪记录每个值被引用的次数。

      基本原理:就是变量的引用次数,被引用一次则加1,当这个引用计数为0时,被视为准备回收的对象。

    45、jQuery的事件委托方法bind 、live、delegate、on之间有什么区别?

    (1)、bind 【jQuery 1.3之前】

    定义和用法:主要用于给选择到的元素上绑定特定事件类型的监听函数;

    语法:bind(type,[data],function(eventObject));

    特点:

    (1)、适用于页面元素静态绑定。只能给调用它的时候已经存在的元素绑定事件,不能给未来新增的元素绑定事件。

    (2)、当页面加载完的时候,你才可以进行bind(),所以可能产生效率问题。

    实例如下:$( "#members li a" ).bind( "click", function( e ) {} );

    (2)、live 【jQuery 1.3之后】

    定义和用法:主要用于给选择到的元素上绑定特定事件类型的监听函数;

    语法:live(type, [data], fn);

    特点:

    (1)、live方法并没有将监听器绑定到自己(this)身上,而是绑定到了this.context上了。

    (2)、live正是利用了事件委托机制来完成事件的监听处理,把节点的处理委托给了document,新添加的元素不必再绑定一次监听器。

    (3)、使用live()方法但却只能放在直接选择的元素后面,不能在层级比较深,连缀的DOM遍历方法后面使用,即$(“ul”").live...可以,但$("body").find("ul").live...不行; 

    实例如下:$( document ).on( "click", "#members li a", function( e ) {} );

    (3)、delegate 【jQuery 1.4.2中引入】

    定义和用法:将监听事件绑定在就近的父级元素上

    语法:delegate(selector,type,[data],fn)

    特点:

    (1)、选择就近的父级元素,因为事件可以更快的冒泡上去,能够在第一时间进行处理。

    (2)、更精确的小范围使用事件代理,性能优于.live()。可以用在动态添加的元素上。

    实例如下:

    $("#info_table").delegate("td","click",function(){/*显示更多信息*/});

    $("table").find("#info").delegate("td","click",function(){/*显示更多信息*/});

    (4)、on 【1.7版本整合了之前的三种方式的新事件绑定机制】

    定义和用法:将监听事件绑定到指定元素上。

    语法:on(type,[selector],[data],fn)

    实例如下:$("#info_table").on("click","td",function(){/*显示更多信息*/});参数的位置写法与delegate不一样。

    说明:on方法是当前JQuery推荐使用的事件绑定方法,附加只运行一次就删除函数的方法是one()。

     总结:.bind(), .live(), .delegate(),.on()分别对应的相反事件为:.unbind(),.die(), .undelegate(),.off()

    46、px和em的区别

    相同点:px和em都是长度单位;

    异同点:px的值是固定的,指定是多少就是多少,计算比较容易。em得值不是固定的,并且em会继承父级元素的字体大小。
    浏览器的默认字体高都是16px。所以未经调整的浏览器都符合: 1em=16px。那么12px=0.75em, 10px=0.625em。

    47、浏览器的内核分别是什么?

    IE: trident内核

    Firefox:gecko内核

    Safari:webkit内核

    Opera:以前是presto内核,Opera现已改用Google Chrome的Blink内核

    Chrome:Blink(基于webkit,Google与Opera Software共同开发)

    48、什么叫优雅降级和渐进增强?

    渐进增强 progressive enhancement:
    针对低版本浏览器进行构建页面,保证最基本的功能,然后再针对高级浏览器进行效果、交互等改进和追加功能达到更好的用户体验。

    优雅降级 graceful degradation:
    一开始就构建完整的功能,然后再针对低版本浏览器进行兼容。

    区别:

    a. 优雅降级是从复杂的现状开始,并试图减少用户体验的供给

    b. 渐进增强则是从一个非常基础的,能够起作用的版本开始,并不断扩充,以适应未来环境的需要

    c. 降级(功能衰减)意味着往回看;而渐进增强则意味着朝前看,同时保证其根基处于安全地带

    49、sessionStorage 、localStorage 和 cookie 之间的区别

     共同点:用于浏览器端存储的缓存数据

    不同点:

    (1)、存储内容是否发送到服务器端:当设置了Cookie后,数据会发送到服务器端,造成一定的宽带浪费;

            web storage,会将数据保存到本地,不会造成宽带浪费;

    (2)、数据存储大小不同:Cookie数据不能超过4K,适用于会话标识;web storage数据存储可以达到5M;

    (3)、数据存储的有效期限不同:cookie只在设置了Cookid过期时间之前一直有效,即使关闭窗口或者浏览器;

            sessionStorage,仅在关闭浏览器之前有效;localStorage,数据存储永久有效;

    (4)、作用域不同:cookie和localStorage是在同源同窗口中都是共享的;sessionStorage不在不同的浏览器窗口中共享,即使是同一个页面;

    50、浏览器是如何渲染页面的?

    渲染的流程如下:

    1.解析HTML文件,创建DOM树。

       自上而下,遇到任何样式(link、style)与脚本(script)都会阻塞(外部样式不阻塞后续外部脚本的加载)。

    2.解析CSS。优先级:浏览器默认设置<用户设置<外部样式<内联样式<HTML中的style样式;

    3.将CSS与DOM合并,构建渲染树(Render Tree)

    4.布局和绘制,重绘(repaint)和重排(reflow)

    51:js的基本数据类型

    JavaScript中有五种基本数据类型,它们分别是:undefined,null,boolean,number,string。

    还有一种复杂数据类型-object。 

    52:事件委托

    事件委托就是利用的DOM事件的事件捕获阶段。把具体dom上发生的事件,委托给更大范围的dom去处理。好比送信员,如果每次都把信件送给每一户,非常繁琐。但是如果交给一个大范围的管理者,比如小区的传达室,那么事情会变得非常简单。事件委托就类似这种原理,我页面中有很多按钮,如果不使用事件委托,我只能在每个按钮上注册事件。非常麻烦。但如果我把事件注册在一个大范围的div(假设所有的按钮都在这个div中),那么我只要注册一次事件,就可以处理所有按钮(只要按钮包含在上述div中)事件的响应了

    53:CSS3新增了很多的属性,下面一起来分析一下新增的一些属性:

    1.CSS3边框:

    · border-radius:CSS3圆角边框。在 CSS2 中添加圆角矩形需要技巧,我们必须为每个圆角使用不同的图片,在 CSS3 中,创建圆角是非常容易的,在 CSS3 中,border-radius 属性用于创建圆角。border:2px solid;

    · box-shadow:CSS3边框阴影。在 CSS3 中,box-shadow 用于向方框添加阴影。box-shadow:10px 10px 5px #888888;

    · border-image:CSS3边框图片。通过 CSS3 的 border-image 属性,您可以使用图片来创建边框。border-image:url(border.png) 30 30 round;

    2.CSS3背景:

    · background-size: 属性规定背景图片的尺寸。在 CSS3 之前,背景图片的尺寸是由图片的实际尺寸决定的。在 CSS3 中,可以规定背景图片的尺寸,这就允许我们在不同的环境中重复使用背景图片。您能够以像素或百分比规定尺寸。如果以百分比规定尺寸,那么尺寸相对于父元素的宽度和高度。

    · background-origin :属性规定背景图片的定位区域。背景图片可以放置于 content-box、padding-box 或 border-box 区域。

    3.CSS3文字效果:

    · text-shadow:在 CSS3 中,text-shadow 可向文本应用阴影。text-shadow:5px 5px 5px #FFFFFF;

    · word-wrap :单词太长的话就可能无法超出某个区域,允许对长单词进行拆分,并换行到下一行:p{word-wrap:break-word;}

    4.CSS3 2D转换:

    transform:通过 CSS3 转换,我们能够对元素进行移动、缩放、转动、拉长或拉伸。

    · translate():元素从其当前位置移动,根据给定的 left(x 坐标) 和 top(y 坐标) 位置参数:transform:translate(50px,100px);值 translate(50px,100px) 把元素从左侧移动 50 像素,从顶端移动 100 像素。

    · rotate():元素顺时针旋转给定的角度。允许负值,元素将逆时针旋转。transform:rotate(30deg);值 rotate(30deg) 把元素顺时针旋转 30 度。

    · scale():元素的尺寸会增加或减少,根据给定的宽度(X 轴)和高度(Y 轴)参数:transform:scale(2,4);值 scale(2,4) 把宽度转换为原始尺寸的 2 倍,把高度转换为原始高x() 5.CSS3 3D转换:

    · rotateX():元素围绕其 X 轴以给定的度数进行旋转。transform:rotateX(120deg);

    · rotateY():元素围绕其 Y 轴以给定的度数进行旋转。transform:rotateY(120deg);

    6.CSS3 过渡:当元素从一种样式变换为另一种样式时为元素添加效果。

    7.CSS3动画:通过 CSS3,我们能够创建动画,这可以在许多网页中取代动画图片、Flash 动画以及 JavaScript。

    8.CSS3多列:

    · column-count:属性规定元素应该被分隔的列数。

    · column-gap:属性规定列之间的间隔。

    · column-rule :属性设置列之间的宽度、样式和颜色规则。

    9.CSS3用户界面:

    · resize:属性规定是否可由用户调整元素尺寸。

    · box-sizing:属性允许您以确切的方式定义适应某个区域的具体内容。

    · outline-offset :属性对轮廓进行偏移,并在超出边框边缘的位置绘制轮廓。

    54:从输入url到显示页面,都经历了什么

    第一步:客户机提出域名解析请求,并将该请求发送给本地的域名服务器。

    第二步:当本地的域名服务器收到请求后,就先查询本地的缓存,如果有该纪录项,则本地的域名服务器就直接把查询的结果返回。

    第三步:如果本地的缓存中没有该纪录,则本地域名服务器就直接把请求发给根域名服务器,然后根域名服务器再返回给本地域名服务器一个所查询域(根的子域)的主域名服务器的地址。
    第四步:本地服务器再向上一步返回的域名服务器发送请求,然后接受请求的服务器查询自己的缓存,如果没有该纪录,则返回相关的下级的域名服务器的地址。
    第五步:重复第四步,直到找到正确的纪录

    2种解释:

    一般会经历以下几个过程:

    1、首先,在浏览器地址栏中输入url

    2、浏览器先查看浏览器缓存-系统缓存-路由器缓存,如果缓存中有,会直接在屏幕中显示页面内容。若没有,则跳到第三步操作。

    3、在发送http请求前,需要域名解析(DNS解析)(DNS(域名系统,Domain Name System)是互联网的一项核心服务,它作为可以将域名和IP地址相互映射的一个分布式数据库,能够使人更方便的访问互联网,而不用去记住IP地址。),解析获取相应的IP地址。

    4、浏览器向服务器发起tcp连接,与浏览器建立tcp三次握手(TCP即传输控制协议。TCP连接是互联网连接协议集的一种。)

    5、握手成功后,浏览器向服务器发送http请求,请求数据包

    6、服务器处理收到的请求,将数据返回至浏览器

    7、浏览器收到HTTP响应

    8、读取页面内容,浏览器渲染,解析html源码

    9、生成Dom树、解析css样式、js交互

    10、客户端和服务器交互

    11、ajax查询

    55:对<meta></meta>标签有什么理解

    什么是meta标签?

    引自下W3school的定义说明一下。

    元数据(metadata)是关于数据的信息。

    标签提供关于 HTML 文档的元数据。元数据不会显示在页面上,但是对于机器是可读的。

    典型的情况是,meta 元素被用于规定页面的描述、关键词、文档的作者、最后修改时间以及其他元数据。

    标签始终位于 head 元素中。

    元数据可用于浏览器(如何显示内容或重新加载页面),搜索引擎(关键词),或其他 web 服务。

    其实对上面的概念简单总结下就是:<meta> 标签提供关于 HTML 文档的元数据。它不会显示在页面上,但是对于机器是可读的。可用于浏览器(如何显示内容或重新加载页面),搜索引擎(关键词),或其他 web 服务。

    meta的作用

    meta里的数据是供机器解读的,告诉机器该如何解析这个页面,还有一个用途是可以添加服务器发送到浏览器的http头部内容

    56:new操作符到底到了什么

    先看代码

    [javascript] view plain copy

    1. var Func=function(){  

    2. };  

    3. var func=new Func ();  

    new共经过了4几个阶段

    1、创建一个空对象

    [javascript] view plain copy

    1. varobj=new Object();  

    2、设置原型链

    [javascript] view plain copy

    1. obj.__proto__= Func.prototype;  

    3、让Func中的this指向obj,并执行Func的函数体。

    [javascript] view plain copy

    1. var result =Func.call(obj);  

    4、判断Func的返回值类型:

    如果是值类型,返回obj。如果是引用类型,就返回这个引用类型的对象。

    [javascript] view plain copy

    1. if (typeof(result) == "object"){  

    2.   func=result;  

    3. }  

    4. else{  

    5.     func=obj;;  

    6. }  

    57:h5新特性

    HTML5新特性 —— 新特性
    (1)新的语义标签和属性
    (2)表单新特性
    (3)视频和音频
    (4)Canvas绘图
    (5)SVG绘图
    (6)地理定位
    (7)拖放API
    58:vue的生命周期

     

     

    58:请写出你对闭包的理解,并列出简单的理解

    使用闭包主要是为了设计私有的方法和变量。闭包的优点是可以避免全局变量的污染,缺点是闭包会常驻内存,会增大内存使用量,使用不当很容易造成内存泄露。

    闭包有三个特性:

    1.函数嵌套函数 

    2.函数内部可以引用外部的参数和变量 

    3.参数和变量不会被垃圾回收机制回收

     

    59:display none visibility hidden区别?

    1.display:none是彻底消失,不在文档流中占位,浏览器也不会解析该元素;visibility:hidden是视觉上消失了,可以理解为透明度为0的效果,在文档流中占位,浏览器会解析该元素;

    2.使用visibility:hidden比display:none性能上要好,display:none切换显示时visibility,页面产生回流(当页面中的一部分元素需要改变规模尺寸、布局、显示隐藏等,页面重新构建,此时就是回流。所有页面第一次加载时需要产生一次回流),而visibility切换是否显示时则不会引起回流。

    60:JavaScript中如何检测一个变量是一个String类型?请写出函数实现

    typeof(obj) === "string"

    typeof obj === "string"

    obj.constructor === String

    61:如何理解闭包?

    1、定义和用法:当一个函数的返回值是另外一个函数,而返回的那个函数如果调用了其父函数内部的其它变量,如果返回的这个函数在外部被执行,就产生了闭包。

    2、表现形式:使函数外部能够调用函数内部定义的变量。

    3、实例如下:

    (1)、根据作用域链的规则,底层作用域没有声明的变量,会向上一级找,找到就返回,没找到就一直找,直到window的变量,没有就返回undefined。这里明显count 是函数内部的flag2 的那个count 。

    var count=10;   //全局作用域 标记为flag1function add(){

        var count=0;    //函数全局作用域 标记为flag2

        return function(){

            count+=1;   //函数的内部作用域        alert(count);

        }

    }var s = add()

    s();//输出1

    s();//输出2

    4、变量的作用域

    要理解闭包,首先必须理解Javascript特殊的变量作用域。

    变量的作用域分类:全局变量和局部变量。

    特点:

    1、函数内部可以读取函数外部的全局变量;在函数外部无法读取函数内的局部变量。

    2、函数内部声明变量的时候,一定要使用var命令。如果不用的话,你实际上声明了一个全局变量!

     5、使用闭包的注意点

    1)滥用闭包,会造成内存泄漏:由于闭包会使得函数中的变量都被保存在内存中,内存消耗很大,所以不能滥用闭包,否则会造成网页的性能问题,在IE中可能导致内存泄露。解决方法是,在退出函数之前,将不使用的局部变量全部删除。

    2)会改变父函数内部变量的值。所以,如果你把父函数当作对象(object)使用,把闭包当作它的公用方法(Public Method),把内部变量当作它的私有属性(private value),这时一定要小心,不要随便改变父函数内部变量的值。

    62:谈谈垃圾回收机制方式及内存管理

    回收机制方式

    1、定义和用法:垃圾回收机制(GC:Garbage Collection),执行环境负责管理代码执行过程中使用的内存。

    2、原理:垃圾收集器会定期(周期性)找出那些不在继续使用的变量,然后释放其内存。但是这个过程不是实时的,因为其开销比较大,所以垃圾回收器会按照固定的时间间隔周期性的执行。

    3、实例如下:

    function fn1() {

        var obj = {name: 'hanzichi', age: 10};

    }

    function fn2() {

        var obj = {name:'hanzichi', age: 10};

       return obj;

    }var a = fn1();var b = fn2();

    fn1中定义的obj为局部变量,而当调用结束后,出了fn1的环境,那么该块内存会被js引擎中的垃圾回收器自动释放;在fn2被调用的过程中,返回的对象被全局变量b所指向,所以该块内存并不会被释放。

     4、垃圾回收策略:标记清除(较为常用)和引用计数。

    标记清除:

      定义和用法:当变量进入环境时,将变量标记"进入环境",当变量离开环境时,标记为:"离开环境"。某一个时刻,垃圾回收器会过滤掉环境中的变量,以及被环境变量引用的变量,剩下的就是被视为准备回收的变量。

      到目前为止,IE、Firefox、Opera、Chrome、Safari的js实现使用的都是标记清除的垃圾回收策略或类似的策略,只不过垃圾收集的时间间隔互不相同。

    引用计数:

      定义和用法:引用计数是跟踪记录每个值被引用的次数。

      基本原理:就是变量的引用次数,被引用一次则加1,当这个引用计数为0时,被视为准备回收的对象。

    63:判断一个字符串中出现次数最多的字符,统计这个次数

    var str = 'asdfssaaasasasasaa';

    var json = {};

    for (var i = 0; i < str.length; i++) {

        if(!json[str.charAt(i)]){

           json[str.charAt(i)] = 1;

        }else{

           json[str.charAt(i)]++;

        }

    };var iMax = 0;var iIndex = '';for(var i in json){

        if(json[i]>iMax){

             iMax = json[i];

             iIndex = i;

        }

    }        console.log('出现次数最多的是:'+iIndex+'出现'+iMax+'次');

    64、$(document).ready()方法和window.onload有什么区别?

     (1)、window.onload方法是在网页中所有的元素(包括元素的所有关联文件)完全加载到浏览器后才执行的。

     (2)、$(document).ready() 方法可以在DOM载入就绪时就对其进行操纵,并调用执行绑定的函数。

    65、 jquery中$.get()提交和$.post()提交有区别吗?

    相同点:都是异步请求的方式来获取服务端的数据;

    异同点:

    1、请求方式不同:$.get() 方法使用GET方法来进行异步请求的。$.post() 方法使用POST方法来进行异步请求的。

    2、参数传递方式不同:get请求会将参数跟在URL后进行传递,而POST请求则是作为HTTP消息的实体内容发送给Web服务器的,这种传递是对用户不可见的。

    3、数据传输大小不同:get方式传输的数据大小不能超过2KB 而POST要大的多

    4、安全问题: GET 方式请求的数据会被浏览器缓存起来,因此有安全问题。

    66、jQuery的事件委托方法bind 、live、delegate、on之间有什么区别?(常见)

    (1)、bind 【jQuery 1.3之前】

    定义和用法:主要用于给选择到的元素上绑定特定事件类型的监听函数;

    语法:bind(type,[data],function(eventObject));

    特点:

    (1)、适用于页面元素静态绑定。只能给调用它的时候已经存在的元素绑定事件,不能给未来新增的元素绑定事件。

    (2)、当页面加载完的时候,你才可以进行bind(),所以可能产生效率问题。

    实例如下:$( "#members li a" ).bind( "click", function( e ) {} );

    (2)、live 【jQuery 1.3之后】

    定义和用法:主要用于给选择到的元素上绑定特定事件类型的监听函数;

    语法:live(type, [data], fn);

    特点:

    (1)、live方法并没有将监听器绑定到自己(this)身上,而是绑定到了this.context上了。

    (2)、live正是利用了事件委托机制来完成事件的监听处理,把节点的处理委托给了document,新添加的元素不必再绑定一次监听器。

    (3)、使用live()方法但却只能放在直接选择的元素后面,不能在层级比较深,连缀的DOM遍历方法后面使用,即$(“ul”").live...可以,但$("body").find("ul").live...不行; 

    实例如下:$( document ).on( "click", "#members li a", function( e ) {} );

    (3)、delegate 【jQuery 1.4.2中引入】

    定义和用法:将监听事件绑定在就近的父级元素上

    语法:delegate(selector,type,[data],fn)

    特点:

    (1)、选择就近的父级元素,因为事件可以更快的冒泡上去,能够在第一时间进行处理。

    (2)、更精确的小范围使用事件代理,性能优于.live()。可以用在动态添加的元素上。

    实例如下:

    $("#info_table").delegate("td","click",function(){/*显示更多信息*/});

    $("table").find("#info").delegate("td","click",function(){/*显示更多信息*/});

    (4)、on 【1.7版本整合了之前的三种方式的新事件绑定机制】

    定义和用法:将监听事件绑定到指定元素上。

    语法:on(type,[selector],[data],fn)

    实例如下:$("#info_table").on("click","td",function(){/*显示更多信息*/});参数的位置写法与delegate不一样。

    说明:on方法是当前JQuery推荐使用的事件绑定方法,附加只运行一次就删除函数的方法是one()。

     总结:.bind(), .live(), .delegate(),.on()分别对应的相反事件为:.unbind(),.die(), .undelegate(),.off()

    67、px和em的区别(常见)

     

    相同点:px和em都是长度单位;

    异同点:px的值是固定的,指定是多少就是多少,计算比较容易。em得值不是固定的,并且em会继承父级元素的字体大小。
    浏览器的默认字体高都是16px。所以未经调整的浏览器都符合: 1em=16px。那么12px=0.75em, 10px=0.625em。

    68、浏览器的内核分别是什么?

    IE: trident内核

    Firefox:gecko内核

    Safari:webkit内核

    Opera:以前是presto内核,Opera现已改用Google Chrome的Blink内核

    Chrome:Blink(基于webkit,Google与Opera Software共同开发)

    69、什么叫优雅降级和渐进增强?(常见)

    渐进增强 progressive enhancement:
    针对低版本浏览器进行构建页面,保证最基本的功能,然后再针对高级浏览器进行效果、交互等改进和追加功能达到更好的用户体验。

    优雅降级 graceful degradation:
    一开始就构建完整的功能,然后再针对低版本浏览器进行兼容。

    区别:

    a. 优雅降级是从复杂的现状开始,并试图减少用户体验的供给

    b. 渐进增强则是从一个非常基础的,能够起作用的版本开始,并不断扩充,以适应未来环境的需要

    c. 降级(功能衰减)意味着往回看;而渐进增强则意味着朝前看,同时保证其根基处于安全地带

    70、sessionStorage 、localStorage 和 cookie 之间的区别(常见)

     共同点:用于浏览器端存储的缓存数据

    不同点:

    (1)、存储内容是否发送到服务器端:当设置了Cookie后,数据会发送到服务器端,造成一定的宽带浪费;

            web storage,会将数据保存到本地,不会造成宽带浪费;

    (2)、数据存储大小不同:Cookie数据不能超过4K,适用于会话标识;web storage数据存储可以达到5M;

    (3)、数据存储的有效期限不同:cookie只在设置了Cookid过期时间之前一直有效,即使关闭窗口或者浏览器;

            sessionStorage,仅在关闭浏览器之前有效;localStorage,数据存储永久有效;

    (4)、作用域不同:cookie和localStorage是在同源同窗口中都是共享的;sessionStorage不在不同的浏览器窗口中共享,即使是同一个页面;

     

    展开全文
  • JAVA面试笔记

    千次阅读 多人点赞 2019-03-07 17:52:40
    循环注入的原理, aop 的实现原理,说说 aop 中的几个术语,它们是怎么相互工作的? 17、BeanFactory和ApplicationContext有什么区别? 18、你对Spring核心组件的理解? 19、简述Bean的生命周期? 20、@AspectJ 的...
  • C#基础教程-c#实例教程,适合初学者

    万次阅读 多人点赞 2016-08-22 11:13:24
    面向对象程序设计方法提出了一个全新的概念:类,它的主要思想是将数据(数据成员)及处理这些数据的相应方法(函数成员)封装到类中,类的实例则称为对象。这就是我们常说的封装性。 类的基本概念 类可以认为是对...
  • 手势识别 技术

    万次阅读 多人点赞 2019-04-19 16:02:27
    核心思想是对输入的手势轨迹进行重新采样,将采样轨迹中心点与x轴的连线旋转到0度,将旋转后的手势缩放到标准的正方形大小并进行手势平移。然后,对处理过的手势和搜索匹配模板使用“黄金选择搜索”(GSS),得到每个...
  • XGBoost

    千次阅读 多人点赞 2019-06-25 00:53:07
    xgboost 还考虑了当数据量比较大,内存不够时怎么有效的使用磁盘,主要是结合多线程、数据压缩、分片的方法,尽可能的提高算法的效率。   XGBoost原理 目标函数:损失与正则 在监督学习中,我们通常会...
  • Hash表 Hash算法 的介绍与思考

    千次阅读 2017-06-08 14:41:05
    这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的...
  • LZW压缩算法——简明原理与实现

    万次阅读 热门讨论 2012-09-19 13:12:14
    LZW和哈夫曼编码一样,是无损压缩中的一种。该算法通过建立字典,实现字符重用与编码,适用于source中重复率很高的文本压缩。本文首先讲下LZW的编解码原理,然后给出LZW的实现code。 *********************原理...
  • 计算机组成原理复习笔记-2

    千次阅读 多人点赞 2018-05-27 10:37:04
    Abstract: 计算机组成原理期末复习知识点总结 ~ 1.基础概念硬件和软件等效原理:任何可以利用软件实现的工作可以利用硬件来实现,反之,任何可以通过硬件来实现的事件也同样可以利用软件来实现。此原理说明,可以用...
  • 凹凸映射(Bump Map)实现原理

    千次阅读 2013-06-18 22:06:34
    James EBlinn在1978年提出了凹凸纹理映射技术的思想基础。这种方法并不是真正改变了物体表面的几何外观,而是在通过扰动物体表面的法向量来实现具有凹凸感的假象。 我翻译这篇教程的目的是为了帮助那些对图形渲染...
  • 第四讲. 经典算法之哈希映射

    千次阅读 多人点赞 2018-12-05 15:10:05
    经典算法之哈希映射1. 简介2. 从一个简单例题开始3. 哈希中的碰撞冲突3.1 线性探测法3.2 链地址法3.3 再哈希法3.4 ...4. 哈希函数的设计4.1 更大的哈希表4.2 更好的哈希运算5. 最后说几句 1. 简介 哈希即Hash,一般...
  • Container原理 ArrayContainer BitmapContainer RunContainer 时空分析 Container的创建与转换 RBM的应用 Lucene Spark Greenplum Redis The End 位图法简述 对于我们大数据工作者来说,海量数据的判重和...
  • LZW压缩算法原理解析

    千次阅读 2017-09-30 13:07:19
    里面我实现了哈夫曼树,LZW字典和算数编码三种压缩算法,时隔几年几乎没什么印象了,尤其是后两种连原理都基本忘了,所以把它们拎出来整理一下,也算是逼自己做个回忆。 本篇先讲LZW算法,Wiki里给出的介绍和样例...
  • 【JAVA面试】java面试题整理(3)

    千次阅读 2018-10-28 12:50:13
    思想:给对象设置引用计数器,没引用该对象一次,计数器就+1,引用失效时,计数器就-1,当任意时候引用计数器的值都为0时,则该对象可被回收 Java不适用原因:无法解决对象互相循环引用的问题   可达性...
  • Redis哈希对象之hashtable和ziplist实现原理分析前言哈希对象hashtable字典rehash操作rehash步骤渐进式rehashziplistziplist和hashtable的编码转换总结 前言 上一篇我们分析了列表对象的底层存储结构linkedlist,...
  • 压缩感知理论

    万次阅读 多人点赞 2018-09-18 20:07:17
     简单地说,压缩感知理论指出:只要信号是可压缩的或在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中...
  • Linux实用教程(第三版)

    万次阅读 多人点赞 2019-08-27 22:55:59
    优秀的安装界面 独特的RPM升级方式 丰富的软件包 安全性能好 方便的系统管理界面 详细而完整的在线文档 1.4.2 RHEL 7新特点(1) 包含Kernel 3.10版本,支持swap内存压缩可保证显著减少I/O并提高性能,采用 NUMA...
  • 常见的文本压缩算法

    万次阅读 2017-08-15 14:32:18
    1.目前主要的文本压缩算法 文本压缩是根据一定的方法对大量数据...原理简介 huffman压缩是数据结构课程中的常见内容, 是典型的贪心算法与二叉树的应用. 压缩前, 以ascii文本为例, 每个字符如a,b…都采用等长的8位ac
  • 主成分分析(PCA)原理详解

    万次阅读 多人点赞 2018-06-09 15:08:25
    “微信公众号”本文同步更新在我的微信公众号里,地址:https://mp.weixin.qq.com/s/Xt1vLQfB20rTmtLjiLsmww本文同步更新在我的知乎专栏里面:主成分分析(PCA)原理详解 - Microstrong的文章 - 知乎...
  • DES算法基本原理

    千次阅读 2019-02-22 00:42:57
    DES算法基本原理 DES算法为密码体制中的对称密码体制,又被称为美国数据加密标准。 DES是一个分组加密算法,典型的DES以64位为分组对数据加密,加密和解密用的是同一个算法。 密钥长64位,密钥事实上是56位参与...
  • 还有,这里我们所要说的变换(transform)虽然是数学意义上的变换,但跟函数变换是不同的,函数变换是符合一一映射准则的,对于离散数字信号处理(DSP),有许多的变换:傅立叶变换、拉普拉斯变换、Z变换、希尔伯特...
  • CS压缩感知

    千次阅读 2019-08-04 16:36:30
    忽然想不起 压缩感知的原理 采样定理的原理上的差别。 奈奎斯特采样定理:https://www.cnblogs.com/AndyJee/p/5050321.html 定理:为了不失真地恢复模拟信号,离散信号系统的采样频率不小于模拟信号...
  • 计算机组成原理-白中英版

    万次阅读 多人点赞 2018-12-24 13:31:29
    因此,发展出来了多总线结构,其基本思想均是将速度相近的设备挂接在同一组总线上,总线之间通过总线控制器相连。 例如CPU和Cache之间、I/O设备之间等。 6、集中式总线判优控制有哪三种方式,哪种方式的优先级不能...
  • 闲话模型压缩之量化(Quantization)篇

    万次阅读 多人点赞 2020-06-25 15:21:52
    之前在浅谈端上智能之计算优化中有过一些简单的论述,同时在闲话模型压缩之网络剪枝(Network Pruning)篇中更加具体地整理了些关于网络剪枝(network pruning)的东西,今天就再将目光放到另一类方法上
  • Qt实现哈夫曼编码解压缩软件详解

    千次阅读 多人点赞 2020-06-02 22:52:37
    诸位既然点开了本帖,相信对此问题已有初步了解,哈夫曼树的原理不再赘述,我们开门见山,直入主题。 一、概要设计 问题拆解:设计一个基于哈夫曼编码的解压缩软件,这个问题我认为可以分解为以下几个子问题: 读取...
  • 几种压缩算法

    千次阅读 2018-01-24 16:37:37
    一、 行程长度压缩  原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。... 1.PCX行程压缩方法: 该算法实际上是位映射格式到压缩格式的转换算法,该算法对于连续 出现1次的字节

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,207
精华内容 8,882
关键字:

压缩映射原理的思想