Linux服务器安装

安装Shadowsocks:
1.下载 pip3 install shadowsocks
2.运行ssserver -c config.json -d start
config.json
{
“server”:”45.76.160.201″,
“server_port”:8388,
“local_address”: “127.0.0.1”,
“local_port”:1080,
“password”:”*******”,
“timeout”:300,
“method”:”aes-256-cfb”,
“fast_open”: false,
“workers”: 1
}

关于Java Lambda的教程,简单明了

许多热门的编程语言如今都有一个叫做lambda或者闭包的语言特性,包括比较经典的函数式编程语言Lisp,Scheme,也有稍微年轻的语言比如JavaScript,Python,Ruby,Groovy,Scale,C#,甚至C++也有Lambda表达式。一些语言是运行在java虚拟机上,作为虚拟机最具代表的语言java当然也不想落后。

究竟什么是Lambda表达式?

Lambda表达式的概念来自于Lambda演算,下面是一个java lambda的简单例子,

(int x)->{ return x+1;}

简单来看lambda像一个没有名字的方法,它具有一个方法应该有的部分:参数列表int x,方法body return x+1,和方法相比lambda好像缺少了一个返回值类型、异常抛出和名字。返回值类型和异常是通过编译器在方法体中推导出来,在上面这个例子中返回值类型是int,没有抛出异常。真正缺少的就是一个名字,从这个角度来看,lambda表达式是一种匿名方法。

Lambda表达式和匿名内部类

从上面的分析可以看出lambda和java内部类的特性有点相似,匿名内部类不只是一个方法,而是一个包含一个或多个方法的类,他们的作用都是一样的,都是作为方法的参数传递,我从JDK源码中提取出来listFiles(FileFilter) 方法:

关于Java Lambda的教程,简单明了

public interface FileFilter { boolean accept(File pathname); }

fileFilter接收一个File对象返回一个boolean值,listFiles方法把Filter应用到所有的File对象接收 那些accept返回true的文件。对于listFiles方法来讲我们必须传递一个函数式接口给他,这是FileFileter的一个实现,一般我们通过匿名类来完成:

关于Java Lambda的教程,简单明了

我们现在可以用lambda来实现:

关于Java Lambda的教程,简单明了

这两种情况我们都是传递了一个函数式接口给方法就像传递对象一样,我们使用代码就像使用数据一样,使用匿名类我们实际上传递了一个对象给方法,使用lambda不再需要创建对象,我们只需要把lambda代码传递给方法。

除了传递lambda之外我们还可以传递一个方法引用,比如:

File[] files = myDir.listFiles( File::isFile );

Lambda表达式的表示

在之前的例子,我们使用lambda表达式定义了一个函数,我们可以把它作为参数传递给一个方法,方法把它当成一个对象来使用,lambda表达式有函数和对象的一些属性,看你从什么角度来看:

  • 从概念来讲,lambda表达式是一个匿名函数,它有签名和方法体但是没有名字
  • 当lambda表达式作为参数传递给方法时,接收方法把它当对象使用,在listFiles方法内部,lambda表达式是一个对象的引用,在这里lambda表达式是一种常规的对象,比如有地址和类型。

从实际的角度来分析,lambda对象是由编译期和运行时系统来创建的,这就允许编译期进行优化而使用者不需要关心具体细节,编译器从lambda表达式的上下文环境来获取lambda对象的语义类型,但是编译期并不创建那个对象而是直到运行时由虚拟机动态创建,这里说的动态创建是指调用

invokedynamic字节码指令来创建。使用动态创建可以推迟对象的创建到对象第一次被使用时,如果你只是定义了lambda表达式而从未使用,它的类型和对象都不会创建。

函数式接口

整个魔幻之处就在于类型的推导,这个类型称为目标类型,运行时系统动态创建的类型是目标类型的子类型。之前的那个例子我们看到目标类型是FileFilter,在例子中我们定义了一个lambda表达式把它传递给listFiles方法,然后listFiles方法把它作为FileFilter子类的一个对象来使用。这里看起来好像有点神奇,我们并没有声明lambda表达式实现了FileFilter接口,listFiles方法也没有表明它很愉快的接收了lambda表达式,它只是需要一个FileFilter的子类的对象,这是如何工作的?

这里面的魔术在于编译期执行了类型推导,编译器根据lambda表达式的上下文来决定需要什么类型的对象,然后编译器观察lambda表达式是否兼容需要的类型。如果Java是一种函数式编程语言的话lambda表达式最自然的类型就是某种函数式类型,用来描述函数的一种特殊类型。函数式类型仅仅描述了函数的签名比如(int,int)->boolean.但是Java不是函数式编程语言因此没有函数式类型,语言的设计者可以选择添加一种新的类型,由于他们不想给Java的类型系统引入太多的改变,因此他们尝试寻找一种办法来集成lambda表达式到语言中而不需要添加函数式类型。

结果他们使用函数式接口来代替,函数式接口是只有一个方法的接口,这样的接口在JDK里有很多,比如经典的Runnable接口,它只有一个方法void run(),还有很多其他的,比如Readable,Callable,Iterable,closeable,Flushnable,Formattable,Comparable,Comparator,或者我们前面提到的FileFilter接口。函数是接口和lambda表达式奕扬都只有一个方法,语言的设计者决定让编译器把lambda表达式转换成匹配的函数式接口。这种转换通常是自动的。比如我们前面提到的(File f) -> { return f.isFile(); },编译器知道listFiles方法的签名,因此我们需要的类型就是FileFilter,FileFilter是这样的:
public interface FileFilter { boolean accept(File pathname); }
FileFilter仅仅需要一个方法因此它是函数式接口类型,我们定义的lambda表达式有一个相匹配的签名,接收一个File对象,返回一个boolean值,不抛出检查的异常,因此编译器把lambda表达式转换成函数式接口FileFilter类型。

假如我们有下面两个函数式接口:
关于Java Lambda的教程,简单明了

我们的lambda表达式兼容两种函数式接口类型:
关于Java Lambda的教程,简单明了

当我们试图给两个变量相互赋值时编译器会报错,虽然两个变量都是同一个lambda表达式,原因很简单两个变量是不同的类型。也有可能出现编译器无法判断匹配的函数式接口类型,比如这个例子:
Object ref = (File f) -> { return f.isFile(); };
这个赋值语句的上下文没有提供足够的信息来转换,因此编译器会报错,解决这个问题最简单的方法就是添加一个类型转换:
Object ref = (FileFilter) (File f) -> { return f.isFile(); };

Lambda表达式和匿名内部类的区别

Lambda表达式出现在我们通常需要匿名内部类的地方,在很多场合他们是可以互换的。但是他们还是有几个区别:

1.语法

匿名类一般这样编写:
关于Java Lambda的教程,简单明了

而Lambda表达式有多种形式:
关于Java Lambda的教程,简单明了

2.运行时成本

匿名类相对Lambda表达式来讲多了一些成本,使用匿名类或造成新类型的创建、新类型对象的创建。运行时匿名内需要:类加载 > 内存分配、对象初始化 > 调用非静态方法。

Lambda表达式需要函数式接口的转换和最终的调用,类型推导发生在编译期,不需要运行时消耗,之前提到过,lambda对象的创建是通过字节码指令invokedynamic来完成的,减少了类型和实例的创建消耗。

3.变量绑定

匿名类可以访问外部域的final变量,如下所示关于Java Lambda的教程,简单明了

对于lambda表达式,cnt变量不需要显式声明为final的,一旦变量在lambda中使用编译期会自动把它当成是final的变量,换句话说在lambda中使用的外部域变量是隐式final的,

关于Java Lambda的教程,简单明了

从java8开始匿名内部类也不需要再显式声明final类,编译器会自动把它当成是final。

4.作用域

匿名内部类是一个类,也就是说它自己引入了一个作用域,你可以在里面定义变量,而lambda表达式没有自己的作用域。
关于Java Lambda的教程,简单明了

lambda表达式:
关于Java Lambda的教程,简单明了

不同的作用域规则对于this和super关键字有不同的效果,在匿名类中this表示匿名类对象本身的引用,super表示匿名类的父类。在lambda表达式this和super关键字意思和外部域中this和super的意思一样,this一般是包含它的那个对象,super表示包含它的类的父类。

java8的新特性以及用法简介,再不学习,代码都看不懂了

1. 介绍

本文简单介绍下java8里面有哪些新的特性,以及相关的用法。

JAVA8是意义深远的一个新版本。随着大数据的兴起,函数式编程在处理大数据上的优势开始体现。JAVA8也紧跟时代,引入了函数式语言的特性,值得关注。下面看看其有哪些新的内容。

2 接口的默认方法

Java 8允许我们给接口添加一个非抽象的方法实现,只需要使用 default关键字即可,这个特征又叫做扩展方法。JAVA可以实现多个接口,从而来对原本的类进行方法扩展。JAVA只能继承1个类,所以以前的接口没法提供这种灵活的扩展方法。现在要简单的扩展方法,也不需要使用Spring的代码织入了,直接用扩展方法即可。不过横切逻辑织入还是用Spring好。

下面看个例子:

interface Formula {  
    double calculate(int a);  
    
    //default修饰的扩展方法 
    default double sqrt(int a) {  
        return Math.sqrt(a);  
    } 
}

Formula接口在拥有calculate方法之外同时还定义了sqrt方法,实现了Formula接口的子类只需要实现一个calculate方法,默认方法sqrt将在子类上可以直接使用。

Formula formula = new Formula() {  
    @Override  
    public double calculate(int a) { 
        return sqrt(a * 100);  
    } 
}; 
formula.calculate(100); // 100.0 
formula.sqrt(16); // 4.0

新的Java 8 的这个特新在编译器实现的角度上来说更加接近Scala的trait。 在C#中也有名为扩展方法的概念,允许给已存在的类型扩展方法,和Java 8的这个在语义上有差别。

2 lambda表达式

首先看看在老版本的Java中是如何排列字符串的:

List<String> names = Arrays.asList("peter", "anna", "mike", "xenia"); 
Collections.sort(names, new Comparator<String>() {  
    @Override  
    public int compare(String a, String b) {  
         return b.compareTo(a);  
    } 
});

只需要给静态方法 Collections.sort 传入一个List对象以及一个比较器来按指定顺序排列。通常做法都是创建一个匿名的比较器对象然后将其传递给sort方法。在Java 8 中你就没必要使用这种传统的匿名对象的方式了,Java 8提供了更简洁的语法,lambda表达式:

Collections.sort(names, 
     (String a, String b) -> {  return b.compareTo(a); });

看到了吧,代码变得更段且更具有可读性,但是实际上还可以写得更短:

Collections.sort(names, (String a, String b) -> b.compareTo(a));

对于函数体只有一行代码的,你可以去掉大括号{}以及return关键字,但是你还可以写得更短点,Java编译器可以自动推导出参数类型,所以你可以不用再写一次类型。

Collections.sort(names, (a, b) -> b.compareTo(a));

2.1 函数式接口

每个lambda表达式对应一个函数式接口。函数式接口”是指仅仅只包含一个抽象方法的接口,每一个该类型的lambda表达式都会被匹配到这个抽象方法。因为 默认方法 不算抽象方法,所以你也可以给你的函数式接口添加默认方法。

我们可以将lambda表达式当作任意只包含一个抽象方法的接口类型,确保你的接口一定达到这个要求,你只需要给你的接口添加 @FunctionalInterface 注解,编译器如果发现你标注了这个注解的接口有多于一个抽象方法的时候会报错的。

//需要注解修饰表明是函数式接口
@FunctionalInterface
interface Converter<F, T> {  
    //必须仅包含一个抽象方法,用于lambda表达式给出具体实现。这里可以包    含扩展方法 
    T convert(F from); 
} 
// Integer.valueOf(from)是函数式接口里面抽象方法的实现。Converter<String, Integer> converter = 
      (from) -> Integer.valueOf(from); 
Integer converted = converter.convert("123"); System.out.println(converted); // 123

需要注意如果@FunctionalInterface如果没有指定,上面的代码也是对的。

译者注 将lambda表达式映射到一个单方法的接口上,这种做法在Java 8之前就有别的语言实现,比如Rhino JavaScript解释器,如果一个函数参数接收一个单方法的接口而你传递的是一个function,Rhino 解释器会自动做一个单接口的实例到function的适配器

2.2 方法与构造函数引用

Java 8 允许你使用 :: 关键字来传递方法或者构造函数引用

Converter<String, Integer> converter = Integer::valueOf; 
Integer converted = converter.convert("123"); System.out.println(converted); // 123

获取构造函数的引用的话使用 ::new,后面接new关键字即可。

2.3 访问局部变量

在lambda表达式中访问外层作用域和老版本的匿名对象中的方式很相似。你可以直接访问标记了final的外层局部变量,或者实例的字段以及静态变量。

//不用final修饰也可以访问,但是要确保其不备修改,所以还是建议用final修饰final
int num = 1; 
Converter<Integer, String> stringConverter = 
     (from) -> String.valueOf(from + num); 
stringConverter.convert(2); // 3

2.4 访问对象字段与静态变量

和本地变量不同的是,lambda内部对于实例的字段以及静态变量是即可读又可写。该行为和匿名对象是一致的:

class Lambda4 {  
    static int outerStaticNum;  
    int outerNum;  
    void testScopes() {  
        Converter<Integer, String> stringConverter1 = 
           (from) -> { outerNum = 23;  
                return String.valueOf(from);  
           };  
        Converter<Integer, String> stringConverter2 = 
           (from) -> {  
                outerStaticNum = 72; 
                return String.valueOf(from); 
           };  
     } 
}

3. 内建函数式接口

JDK 1.8 API包含了很多内建的函数式接口,在老Java中常用到的比如Comparator或者Runnable接口,这些接口都增加了@FunctionalInterface注解以便能用在lambda上。

Java 8 API同样还提供了很多全新的函数式接口来让工作更加方便,有一些接口是来自Google Guava库里的,即便你对这些很熟悉了,还是有必要看看这些是如何扩展到lambda上使用的。

这些已经默认提供的内建函数式接口主要是:

  • Predicate — 传入一个参数,返回一个bool结果, 方法为boolean test(T t)
  • Consumer — 传入一个参数,无返回值,纯消费。 方法为void accept(T t)
  • Function<t,r> — 传入一个参数,返回一个结果,方法为R apply(T t)</t,r>
  • Supplier — 无参数传入,返回一个结果,方法为T get()

3.1 Predicate接口

Predicate 接口只有一个参数,返回boolean类型。该接口包含多种默认方法来将Predicate组合成其他复杂的逻辑(比如:与,或,非):

//用于做一些判断Predicate<String>

predicate = (s) -> s.length() > 0; 
predicate.test("foo"); // true
predicate.negate().test("foo"); // false 
Predicate<Boolean> nonNull = Objects::nonNull; 
Predicate<Boolean> isNull = Objects::isNull; 
Predicate<String> isEmpty = String::isEmpty; 
Predicate<String> isNotEmpty = isEmpty.negate();

3.2 Function 接口

Function 接口有一个参数并且返回一个结果,并附带了一些可以和其他函数组合的默认方法(compose, andThen):

Function<String, Integer> toInteger = Integer::valueOf; Function<String, String> backToString = toInteger.andThen(String::valueOf); 
backToString.apply("123"); // "123"

3.3 Supplier 接口

Supplier 接口返回一个任意范型的值,和Function接口不同的是该接口没有任何参数

Supplier<Person> personSupplier = Person::new; 
personSupplier.get(); // new Person

3.4 Consumer 接口

Consumer 接口表示执行在单个参数上的操作。

Consumer<Person> greeter = (p) -> System.out.println("Hello, " + p.firstName); 
greeter.accept(new Person("Luke", "Skywalker"));

3.5 Comparator 接口

Comparator 是老Java中的经典接口, Java 8在此之上添加了多种默认方法:

Comparator<Person> comparator = (p1, p2) -> p1.firstName.compareTo(p2.firstName); 
Person p1 = new Person("John", "Doe"); 
Person p2 = new Person("Alice", "Wonderland"); 
comparator.compare(p1, p2); // > 0 
comparator.reversed().compare(p1, p2); // < 0

3.6 Optional 接口

Optional 不是函数是接口,这是个用来防止NullPointerException异常的辅助类型,这是下一届中将要用到的重要概念,现在先简单的看看这个接口能干什么:

Optional 被定义为一个简单的容器,其值可能是null或者不是null。在Java 8之前一般某个函数应该返回非空对象但是偶尔却可能返回了null,而在Java 8中,不推荐你返回null而是返回Optional。

Optional<String> optional = Optional.of("bam"); 
optional.isPresent(); // true 
optional.get(); // "bam" optional.orElse("fallback"); // "bam" 
optional.ifPresent((s) -> System.out.println(s.charAt(0))); // "b"

3.7 Stream 接口

java.util.Stream 表示能应用在一组元素上一次执行的操作序列。Stream 操作分为中间操作或者最终操作两种,最终操作返回一特定类型的计算结果,而中间操作返回Stream本身,这样你就可以将多个操作依次串起来。Stream 的创建需要指定一个数据源,比如 java.util.Collection的子类,List或者Set, Map不支持。Stream的操作可以串行执行或者并行执行。

首先看看Stream是怎么用,首先创建实例代码的用到的数据List:

List<String> stringCollection = new ArrayList<>(); 
stringCollection.add("ddd2"); 
stringCollection.add("aaa2"); 
stringCollection.add("bbb1"); 
stringCollection.add("aaa1"); 
stringCollection.add("bbb3"); 
stringCollection.add("ccc"); 
stringCollection.add("bbb2"); 
stringCollection.add("ddd1");

Java 8扩展了集合类,可以通过 Collection.stream() 或者 Collection.parallelStream() 来创建一个Stream。下面几节将详细解释常用的Stream操作:

3.7.1 Filter过滤

过滤通过一个predicate接口来过滤并只保留符合条件的元素,该操作属于中间操作,所以我们可以在过滤后的结果来应用其他Stream操作(比如forEach)。forEach需要一个函数来对过滤后的元素依次执行。forEach是一个最终操作,所以我们不能在forEach之后来执行其他Stream操作。

stringCollection
   .stream()  
   .filter((s) -> s.startsWith("a"))
   .forEach(System.out::println); // "aaa2", "aaa1"

3.7.2 Sort 排序

排序是一个中间操作,返回的是排序好后的Stream。如果你不指定一个自定义的Comparator则会使用默认排序。

stringCollection
   .stream()
   .sorted()
   .filter((s) -> s.startsWith("a"))  
   .forEach(System.out::println); // "aaa1", "aaa2"

需要注意的是,排序只创建了一个排列好后的Stream,而不会影响原有的数据源,排序之后原数据stringCollection是不会被修改的:

System.out.println(stringCollection); // ddd2, aaa2, bbb1, aaa1, bbb3, ccc, bbb2, ddd1

3.7.3 Map 映射

中间操作map会将元素根据指定的Function接口来依次将元素转成另外的对象,下面的示例展示了将字符串转换为大写字符串。你也可以通过map来讲对象转换成其他类型,map返回的Stream类型是根据你map传递进去的函数的返回值决定的。

stringCollection
   .stream()  
   .map(String::toUpperCase)  
   .sorted((a, b) -> b.compareTo(a))  
   .forEach(System.out::println); // "DDD2", "DDD1", "CCC", "BBB3", "BBB2", "AAA2", "AAA1"

3.7.4 Match 匹配

Stream提供了多种匹配操作,允许检测指定的Predicate是否匹配整个Stream。所有的匹配操作都是最终操作,并返回一个boolean类型的值。

boolean anyStartsWithA = stringCollection  
    .stream() 
    .anyMatch((s) -> s.startsWith("a"));             System.out.println(anyStartsWithA); // true boolean 
allStartsWithA = stringCollection  
    .stream()  
    .allMatch((s) -> s.startsWith("a")); System.out.println(allStartsWithA); // false boolean
noneStartsWithZ =  stringCollection  
    .stream()  
    .noneMatch((s) -> s.startsWith("z")); System.out.println(noneStartsWithZ); // true

3.7.5 Count 计数

计数是一个最终操作,返回Stream中元素的个数,返回值类型是long。

long startsWithB = stringCollection  
    .stream()  
    .filter((s) -> s.startsWith("b"))  
    .count(); 
System.out.println(startsWithB); // 3

3.7.6 Reduce 规约

这是一个最终操作,允许通过指定的函数来讲stream中的多个元素规约为一个元素,规越后的结果是通过Optional接口表示的:

Optional<String> reduced = stringCollection
    .stream()  
    .sorted()  
    .reduce((s1, s2) -> s1 + "#" + s2); reduced.ifPresent(System.out::println); //"aaa1#aaa2#bbb1#bbb2#bbb3#ccc#ddd1#ddd2"

3.7.7 并行Streams

前面提到过Stream有串行和并行两种,串行Stream上的操作是在一个线程中依次完成,而并行Stream则是在多个线程上同时执行。

下面的例子展示了是如何通过并行Stream来提升性能:

首先我们创建一个没有重复元素的大表:

int max = 1000000; 
List<String> values = new ArrayList<>(max); 
for (int i = 0; i < max; i++) {  
   UUID uuid = UUID.randomUUID();  
   values.add(uuid.toString()); 
}

然后我们计算一下排序这个Stream要耗时多久,

串行排序:

long t0 = System.nanoTime(); 
long count = values.stream().sorted().count(); 
System.out.println(count); 
long t1 = System.nanoTime(); 
long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0); 
System.out.println(String.format("sequential sort took: %d ms",  millis));

// 串行耗时: 899 ms

并行排序:

long t0 = System.nanoTime(); 
long count = values.parallelStream().sorted().count(); System.out.println(count); 
long t1 = System.nanoTime(); 
long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0); 
System.out.println(String.format("parallel sort took: %d ms", millis));

// 并行排序耗时: 472 ms

上面两个代码几乎是一样的,但是并行版的快了50%之多,唯一需要做的改动就是将stream()改为parallelStream()。

4. Map

前面提到过,Map类型不支持stream,不过Map提供了一些新的有用的方法来处理一些日常任务。

Map<Integer, String> map = new HashMap<>(); 
for (int i = 0; i < 10; i++) {  
   map.putIfAbsent(i, "val" + i); 
}
map.forEach((id, val) -> System.out.println(val));

以上代码很容易理解, putIfAbsent 不需要我们做额外的存在性检查,而forEach则接收一个Consumer接口来对map里的每一个键值对进行操作。

下面的例子展示了map上的其他有用的函数:

map.computeIfPresent(3,(num, val) -> val + num); 
map.get(3); // val33 
map.computeIfPresent(9, (num, val) -> null); 
map.containsKey(9); // false 
map.computeIfAbsent(23, num -> "val" + num); 
map.containsKey(23); // true 
map.computeIfAbsent(3, num -> "bam"); 
map.get(3); // val33

接下来展示如何在Map里删除一个键值全都匹配的项:

map.remove(3, "val3"); 
map.get(3); // val33 
map.remove(3, "val33"); 
map.get(3); // null

另外一个有用的方法:

map.getOrDefault(42, "not found"); // not found

对Map的元素做合并也变得很容易了:

map.merge(9,"val9", (value, newValue) -> value.concat(newValue)); map.get(9); // val9 
map.merge(9, "concat", (value, newValue) -> value.concat(newValue)); 
map.get(9); // val9concat

Merge做的事情是如果键名不存在则插入,否则则对原键对应的值做合并操作并重新插入到map中。

5. Date API

Java 8 在包java.time下包含了一组全新的时间日期API。新的日期API和开源的Joda-Time库差不多,但又不完全一样,下面的例子展示了这组新API里最重要的一些部分:

5.1 Clock 时钟

Clock类提供了访问当前日期和时间的方法,Clock是时区敏感的,可以用来取代 System.currentTimeMillis() 来获取当前的微秒数。某一个特定的时间点也可以使用Instant类来表示,Instant类也可以用来创建老的java.util.Date对象。

Clock clock = Clock.systemDefaultZone(); 
long millis = clock.millis(); 
Instant instant = clock.instant(); 
Date legacyDate = Date.from(instant); // legacy java.util.Date

5.2 Timezones 时区

在新API中时区使用ZoneId来表示。时区可以很方便的使用静态方法of来获取到。 时区定义了到UTS时间的时间差,在Instant时间点对象到本地日期对象之间转换的时候是极其重要的。

System.out.println(ZoneId.getAvailableZoneIds());
 // prints all available timezone ids ZoneId zone1 = 
ZoneId.of("Europe/Berlin"); 
ZoneId zone2 = ZoneId.of("Brazil/East"); 
System.out.println(zone1.getRules()); 
System.out.println(zone2.getRules()); // 
ZoneRules[currentStandardOffset=+01:00] // 
ZoneRules[currentStandardOffset=-03:00]

5.3 LocalTime 本地时间

LocalTime 定义了一个没有时区信息的时间,例如 晚上10点,或者 17:30:15。下面的例子使用前面代码创建的时区创建了两个本地时间。之后比较时间并以小时和分钟为单位计算两个时间的时间差:

LocalTime now1 = LocalTime.now(zone1); 
LocalTime now2 = LocalTime.now(zone2); 
System.out.println(now1.isBefore(now2)); // false 
long hoursBetween = ChronoUnit.HOURS.between(now1, now2); 
long minutesBetween = ChronoUnit.MINUTES.between(now1, now2); 
System.out.println(hoursBetween); // -3 
System.out.println(minutesBetween); // -239

LocalTime 提供了多种工厂方法来简化对象的创建,包括解析时间字符串。

LocalTime late = LocalTime.of(23, 59, 59); 
System.out.println(late); // 23:59:59 
DateTimeFormatter germanFormatter =  
    DateTimeFormatter
    .ofLocalizedTime(FormatStyle.SHORT)  
    .withLocale(Locale.GERMAN); 
LocalTime leetTime = LocalTime.parse("13:37", germanFormatter); 
System.out.println(leetTime); // 13:37

5.4 LocalDate 本地日期

LocalDate 表示了一个确切的日期,比如 2014-03-11。该对象值是不可变的,用起来和LocalTime基本一致。下面的例子展示了如何给Date对象加减天/月/年。另外要注意的是这些对象是不可变的,操作返回的总是一个新实例。

LocalDate today = LocalDate.now(); 
LocalDate tomorrow = today.plus(1, ChronoUnit.DAYS); 
LocalDate yesterday = tomorrow.minusDays(2); 
LocalDate independenceDay = LocalDate.of(2014, Month.JULY, 4); DayOfWeek dayOfWeek = independenceDay.getDayOfWeek();

System.out.println(dayOfWeek); // FRIDAY

从字符串解析一个LocalDate类型和解析LocalTime一样简单:

DateTimeFormatter germanFormatter = DateTimeFormatter  
   .ofLocalizedDate(FormatStyle.MEDIUM)  
   .withLocale(Locale.GERMAN); 
LocalDate xmas = LocalDate.parse("24.12.2014", germanFormatter); 
System.out.println(xmas); // 2014-12-24

5.5 LocalDateTime 本地日期时间

LocalDateTime 同时表示了时间和日期,相当于前两节内容合并到一个对象上了。LocalDateTime和LocalTime还有LocalDate一样,都是不可变的。LocalDateTime提供了一些能访问具体字段的方法。

LocalDateTime sylvester = LocalDateTime.of(2014, Month.DECEMBER, 31, 23, 59, 59); 
DayOfWeek dayOfWeek = sylvester.getDayOfWeek(); 
System.out.println(dayOfWeek); // WEDNESDAY Month month = 
sylvester.getMonth(); 
System.out.println(month); // DECEMBER long 
minuteOfDay = sylvester.getLong(ChronoField.MINUTE_OF_DAY); 
System.out.println(minuteOfDay); // 1439

只要附加上时区信息,就可以将其转换为一个时间点Instant对象,Instant时间点对象可以很容易的转换为老式的java.util.Date。

Instant instant = sylvester  
   .atZone(ZoneId.systemDefault())  
   .toInstant(); 
Date legacyDate = Date.from(instant); 
System.out.println(legacyDate); // Wed Dec 31 23:59:59 CET 2014

格式化LocalDateTime和格式化时间和日期一样的,除了使用预定义好的格式外,我们也可以自己定义格式:

DateTimeFormatter formatter = DateTimeFormatter  
   .ofPattern("MMM dd, yyyy - HH:mm"); 
LocalDateTime parsed = LocalDateTime.parse("Nov 03, 2014 - 07:13", 
formatter); 
String string = formatter.format(parsed); 
System.out.println(string); // Nov 03, 2014 - 07:13

和java.text.NumberFormat不一样的是新版的DateTimeFormatter是不可变的,所以它是线程安全的。

6. Annotation 注解

6.1 多重注解

在Java 8中支持多重注解了,先看个例子来理解一下是什么意思。

首先定义一个包装类Hints注解用来放置一组具体的Hint注解:

@interface Hints {  Hint[] value(); } 
@Repeatable(Hints.class) 
@interface Hint {  String value(); }

Java 8允许我们把同一个类型的注解使用多次,只需要给该注解标注一下@Repeatable即可。

例子:

  1. 使用包装类当容器来存多个注解(老方法) java @Hints({@Hint("hint1"), @Hint("hint2")}) class Person {}
  1. 使用多重注解(新方法) java @Hint("hint1") @Hint("hint2") class Person {} 第二个例子里java编译器会隐性的帮你定义好@Hints注解,了解这一点有助于你用反射来获取这些信息:
    java
    Hint hint = Person.class.getAnnotation(Hint.class);
    System.out.println(hint); // null
    Hints hints1 =
    Person.class.getAnnotation(Hints.class);
    System.out.println(hints1.value().length); // 2
    Hint[] hints2 =
    Person.class.getAnnotationsByType(Hint.class);
    System.out.println(hints2.length); // 2即便我们没有在Person类上定义@Hints注解,我们还是可以通过 getAnnotation(Hints.class) 来获取 @Hints注解,更加方便的方法是使用 getAnnotationsByType 可以直接获取到所有的@Hint注解。

6.2 新的target

另外Java 8的注解还增加到两种新的target上了:

@Target({ElementType.TYPE_PARAMETER, ElementType.TYPE_USE}) @interface MyAnnotation {}

7. more

JDK 1.8里还有很多很有用的东西,比如Arrays.parallelSort, StampedLock和CompletableFuture等等。

https://www.kancloud.cn/wizardforcel/modern-java-zh/141721

 

常见数据结构与算法整理总结(下)

这篇文章是常见数据结构与算法整理总结的下篇,上一篇主要是对常见的数据结构进行集中总结,这篇主要是总结一些常见的算法相关内容,文章中如有错误,欢迎指出。

一、概述
二、查找算法
三、排序算法
四、其它算法
五、常见算法题
六、总结

一、概述

以前看到这样一句话,语言只是工具,算法才是程序设计的灵魂。的确,算法在计算机科学中的地位真的很重要,在很多大公司的笔试面试中,算法掌握程度的考察都占据了很大一部分。不管是为了面试还是自身编程能力的提升,花时间去研究常见的算法还是很有必要的。下面是自己对于算法这部分的学习总结。

算法简介

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。对于同一个问题的解决,可能会存在着不同的算法,为了衡量一个算法的优劣,提出了空间复杂度与时间复杂度这两个概念。

时间复杂度

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记为 ** T(n) = O(f(n)) **,它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。这里需要重点理解这个增长率。

举个例子,看下面3个代码:

1、{++x;}

2、for(i = 1; i <= n; i++) { ++x; }

3、for(j = 1; j <= n; j++) 
        for(j = 1; j <= n; j++) 
             { ++x; }

上述含有 ++x 操作的语句的频度分别为1 、n 、n^2,

假设问题的规模扩大了n倍,3个代码的增长率分别是1 、n 、n^2

它们的时间复杂度分别为O(1)、O(n )、O(n^2)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

二、查找算法

查找和排序是最基础也是最重要的两类算法,熟练地掌握这两类算法,并能对这些算法的性能进行分析很重要,这两类算法中主要包括二分查找、快速排序、归并排序等等。

顺序查找

顺序查找又称线性查找。它的过程为:从查找表的最后一个元素开始逐个与给定关键字比较,若某个记录的关键字和给定值比较相等,则查找成功,否则,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录查找不成功,它的缺点是效率低下。

二分查找

  • 简介

二分查找又称折半查找,对于有序表来说,它的优点是比较次数少,查找速度快,平均性能好。

二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。

二分查找的时间复杂度为O(logn)

  • 实现
//给定有序查找表array 二分查找给定的值data
//查找成功返回下标 查找失败返回-1

static int funBinSearch(int[] array, int data) {

    int low = 0;
    int high = array.length - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        if (data == array[mid]) {
            return mid;
        } else if (data < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

三、排序算法

排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。下面主要对一些常见的排序算法做介绍,并分析它们的时空复杂度。

常见排序算法

常见排序算法性能比较:

图片来自网络

上面这张表中有稳定性这一项,排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前和排序后他们的相对位置不发生变化。

下面从冒泡排序开始逐一介绍。

冒泡排序

  • 简介

冒泡排序的基本思想是:设排序序列的记录个数为n,进行n-1次遍历,每次遍历从开始位置依次往后比较前后相邻元素,这样较大的元素往后移,n-1次遍历结束后,序列有序。

例如,对序列(3,2,1,5)进行排序的过程是:共进行3次遍历,第1次遍历时先比较3和2,交换,继续比较3和1,交换,再比较3和5,不交换,这样第1次遍历结束,最大值5在最后的位置,得到序列(2,1,3,5)。第2次遍历时先比较2和1,交换,继续比较2和3,不交换,第2次遍历结束时次大值3在倒数第2的位置,得到序列(1,2,3,5),第3次遍历时,先比较1和2,不交换,得到最终有序序列(1,2,3,5)。

需要注意的是,如果在某次遍历中没有发生交换,那么就不必进行下次遍历,因为序列已经有序。

  • 实现
// 冒泡排序 注意 flag 的作用
static void funBubbleSort(int[] array) {

    boolean flag = true;

    for (int i = 0; i < array.length - 1 && flag; i++) {

        flag = false;

        for (int j = 0; j < array.length - 1 - i; j++) {

            if (array[j] > array[j + 1]) {

                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                flag = true;
            }
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}
  • 分析

最佳情况下冒泡排序只需一次遍历就能确定数组已经排好序,不需要进行下一次遍历,所以最佳情况下,时间复杂度为** O(n) **。

最坏情况下冒泡排序需要n-1次遍历,第一次遍历需要比较n-1次,第二次遍历需要n-2次,…,最后一次需要比较1次,最差情况下时间复杂度为** O(n^2) **。

简单选择排序

  • 简介

简单选择排序的思想是:设排序序列的记录个数为n,进行n-1次选择,每次在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有效序列中的第i个记录。

例如,排序序列(3,2,1,5)的过程是,进行3次选择,第1次选择在4个记录中选择最小的值为1,放在第1个位置,得到序列(1,3,2,5),第2次选择从位置1开始的3个元素中选择最小的值2放在第2个位置,得到有序序列(1,2,3,5),第3次选择因为最小的值3已经在第3个位置不需要操作,最后得到有序序列(1,2,3,5)。

  • 实现
static void funSelectionSort(int[] array) {

    for (int i = 0; i < array.length - 1; i++) {

        int mink = i;

            // 每次从未排序数组中找到最小值的坐标
        for (int j = i + 1; j < array.length; j++) {

            if (array[j] < array[mink]) {
                mink = j;
            }
        }

        // 将最小值放在最前面
        if (mink != i) {
            int temp = array[mink];
            array[mink] = array[i];
            array[i] = temp;
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}
  • 分析

简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况** 无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为 O(n^2) ,进行移动操作的时间复杂度为 O(n) 。总的时间复杂度为 O(n^2) **。

最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。

简单选择排序是不稳定排序。

直接插入排序

  • 简介

直接插入的思想是:是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。

例如,排序序列(3,2,1,5)的过程是,初始时有序序列为(3),然后从位置1开始,先访问到2,将2插入到3前面,得到有序序列(2,3),之后访问1,找到合适的插入位置后得到有序序列(1,2,3),最后访问5,得到最终有序序列(1,2,3,5).

  • 实现
static void funDInsertSort(int[] array) {

    int j;

    for (int i = 1; i < array.length; i++) {

        int temp = array[i];

        j = i - 1;

        while (j > -1 && temp < array[j]) {

            array[j + 1] = array[j];

            j--;
        }

        array[j + 1] = temp;

    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}
  • 分析

最好情况下,当待排序序列中记录已经有序时,则需要n-1次比较,不需要移动,时间复杂度为** O(n) 。最差情况下,当待排序序列中所有记录正好逆序时,则比较次数和移动次数都达到最大值,时间复杂度为 O(n^2) 。平均情况下,时间复杂度为 O(n^2) **。

希尔排序

希尔排序又称“缩小增量排序”,它是基于直接插入排序的以下两点性质而提出的一种改进:(1) 直接插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。(2) 直接插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。点击查看更多关于希尔排序的内容

归并排序

  • 简介

归并排序是分治法的一个典型应用,它的主要思想是:将待排序序列分为两部分,对每部分递归地应用归并排序,在两部分都排好序后进行合并。

例如,排序序列(3,2,8,6,7,9,1,5)的过程是,先将序列分为两部分,(3,2,8,6)和(7,9,1,5),然后对两部分分别应用归并排序,第1部分(3,2,8,6),第2部分(7,9,1,5),对两个部分分别进行归并排序,第1部分继续分为(3,2)和(8,6),(3,2)继续分为(3)和(2),(8,6)继续分为(8)和(6),之后进行合并得到(2,3),(6,8),再合并得到(2,3,6,8),第2部分进行归并排序得到(1,5,7,9),最后合并两部分得到(1,2,3,5,6,7,8,9)。

  • 实现
    //归并排序
    static void funMergeSort(int[] array) {

        if (array.length > 1) {

            int length1 = array.length / 2;
            int[] array1 = new int[length1];
            System.arraycopy(array, 0, array1, 0, length1);
            funMergeSort(array1);

            int length2 = array.length - length1;
            int[] array2 = new int[length2];
            System.arraycopy(array, length1, array2, 0, length2);
            funMergeSort(array2);

            int[] datas = merge(array1, array2);
            System.arraycopy(datas, 0, array, 0, array.length);
        }

    }

    //合并两个数组
    static int[] merge(int[] list1, int[] list2) {

        int[] list3 = new int[list1.length + list2.length];

        int count1 = 0;
        int count2 = 0;
        int count3 = 0;

        while (count1 < list1.length && count2 < list2.length) {

            if (list1[count1] < list2[count2]) {
                list3[count3++] = list1[count1++];
            } else {
                list3[count3++] = list2[count2++];
            }
        }

        while (count1 < list1.length) {
            list3[count3++] = list1[count1++];
        }

        while (count2 < list2.length) {
            list3[count3++] = list2[count2++];
        }

        return list3;
    }
  • 分析

归并排序的时间复杂度为O(nlogn),它是一种稳定的排序,java.util.Arrays类中的sort方法就是使用归并排序的变体来实现的。

快速排序

  • 简介

快速排序的主要思想是:在待排序的序列中选择一个称为主元的元素,将数组分为两部分,使得第一部分中的所有元素都小于或等于主元,而第二部分中的所有元素都大于主元,然后对两部分递归地应用快速排序算法。

  • 实现
// 快速排序
static void funQuickSort(int[] mdata, int start, int end) {
    if (end > start) {
        int pivotIndex = quickSortPartition(mdata, start, end);
        funQuickSort(mdata, start, pivotIndex - 1);
        funQuickSort(mdata, pivotIndex + 1, end);
    }
}

// 快速排序前的划分
static int quickSortPartition(int[] list, int first, int last) {

    int pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {

        while (low <= high && list[low] <= pivot) {
            low++;
        }

        while (low <= high && list[high] > pivot) {
            high--;
        }

        if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }

    while (high > first && list[high] >= pivot) {
        high--;
    }

    if (pivot > list[high]) {
        list[first] = list[high];
        list[high] = pivot;
        return high;
    } else {
        return first;
    }
}
  • 分析

在快速排序算法中,比较关键的一个部分是主元的选择。在最差情况下,划分由n个元素构成的数组需要进行n次比较和n次移动,因此划分需要的时间是O(n)。在最差情况下,每次主元会将数组划分为一个大的子数组和一个空数组,这个大的子数组的规模是在上次划分的子数组的规模上减1,这样在最差情况下算法需要(n-1)+(n-2)+…+1= ** O(n^2) **时间。

最佳情况下,每次主元将数组划分为规模大致相等的两部分,时间复杂度为** O(nlogn) **。

堆排序

  • 简介

在介绍堆排序之前首先需要了解堆的定义,n个关键字序列K1,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):(1) ki <= k(2i)且 ki <= k(2i+1) (1 ≤ i≤ n/2),当然,这是小根堆,大根堆则换成>=号。

如果将上面满足堆性质的序列看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有的非终端节点的值均不大于(或不小于)其左右孩子节点的值。

堆排序的主要思想是:给定一个待排序序列,首先经过一次调整,将序列构建成一个大顶堆,此时第一个元素是最大的元素,将其和序列的最后一个元素交换,然后对前n-1个元素调整为大顶堆,再将其第一个元素和末尾元素交换,这样最后即可得到有序序列。

  • 实现
//堆排序
public class TestHeapSort {

    public static void main(String[] args) {
        int arr[] = { 5, 6, 1, 0, 2, 9 };
        heapsort(arr, 6);
        System.out.println(Arrays.toString(arr));
    }

    static void heapsort(int arr[], int n) {

        // 先建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, n);
        }

        for (int i = 0; i < n - 1; i++) {
            swap(arr, 0, n - i - 1);
            heapAdjust(arr, 0, n - i - 1);
        }
    }

    // 交换两个数
    static void swap(int arr[], int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    // 调整堆
    static void heapAdjust(int arr[], int index, int n) {

        int temp = arr[index];

        int child = 0;

        while (index * 2 + 1 < n) {
                        
            child = index * 2 + 1;
                        
            // child为左右孩子中较大的那个
            if (child != n - 1 && arr[child] < arr[child + 1]) {
                child++;
            }
            // 如果指定节点大于较大的孩子 不需要调整
            if (temp > arr[child]) {
                break;
            } else {
                // 否则继续往下判断孩子的孩子 直到找到合适的位置
                arr[index] = arr[child];
                index = child;
            }
        }

        arr[index] = temp;
    }
}

  • 分析

由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序时间复杂度也为O(nlogn),空间复杂度为O(1)。它是不稳定的排序方法。与快排和归并排序相比,堆排序在最差情况下的时间复杂度优于快排,空间效率高于归并排序。

四、其它算法

在上面的篇幅中,主要是对查找和常见的几种排序算法作了介绍,这些内容都是基础的但是必须掌握的内容,尤其是二分查找、快排、堆排、归并排序这几个更是面试高频考察点。(这里不禁想起百度一面的时候让我写二分查找和堆排序,二分查找还行,然而堆排序当时一脸懵逼…)下面主要是介绍一些常见的其它算法。

递归

  • 简介

在平常解决一些编程或者做一些算法题的时候,经常会用到递归。程序调用自身的编程技巧称为递归。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。上面介绍的快速排序和归并排序都用到了递归的思想。

  • 经典例子

斐波那契数列,又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)。

//斐波那契数列 递归实现
static long funFib(long index) {

    if (index == 0) {
        return 0;
    } else if (index == 1) {
        return 1;
    } else {
        return funFib(index - 1) + funFib(index - 2);
    }
}

上面代码是斐波那契数列的递归实现,然而我们不难得到它的时间复杂度是O(2^n),递归有时候可以很方便地解决一些问题,但是它也会带来一些效率上的问题。下面的代码是求斐波那契数列的另一种方式,效率比递归方法的效率高。

static long funFib2(long index) {

    long f0 = 0;
    long f1 = 1;
    long f2 = 1;

    if (index == 0) {
        return f0;
    } else if (index == 1) {
        return f1;
    } else if (index == 2) {
        return f2;
    }

    for (int i = 3; i <= index; i++) {
        f0 = f1;
        f1 = f2;
        f2 = f0 + f1;
    }

    return f2;
}

分治算法

分治算法的思想是将待解决的问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立最终的解。分治算法中关键地一步其实就是递归地求解子问题。关于分治算法的一个典型例子就是上面介绍的归并排序。查看更多关于分治算法的内容

动态规划

动态规划与分治方法相似,都是通过组合子问题的解来求解待解决的问题。但是,分治算法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,而动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题。动态规划方法通常用来求解最优化问题。查看更多关于动态规划的内容

动态规划典型的一个例子是最长公共子序列问题。

常见的算法还有很多,比如贪心算法,回溯算法等等,这里都不再详细介绍,想要熟练掌握,还是要靠刷题,刷题,刷题,然后总结。

五、常见算法题

下面是一些常见的算法题汇总。

不使用临时变量交换两个数

static void funSwapTwo(int a, int b) {

    a = a ^ b;
    b = b ^ a;
    a = a ^ b;

    System.out.println(a + " " + b);
}

判断一个数是否为素数

static boolean funIsPrime(int m) {

    boolean flag = true;

    if (m == 1) {
        flag = false;
    } else {

        for (int i = 2; i <= Math.sqrt(m); i++) {
            if (m % i == 0) {
                flag = false;
                break;
            }
        }
    }

    return flag;
}

其它算法题

1、15道使用频率极高的基础算法题
2、二叉树相关算法题
3、链表相关算法题
4、字符串相关算法问题

六、总结

以上就是自己对常见的算法相关内容的总结,算法虐我千百遍,我待算法如初恋,革命尚未成功,同志仍需刷题,加油。

常见数据结构与算法整理总结(上)

数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。

为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架,有需要的可以阅读这篇文章。Java – 集合框架完全解析

一、线性表
  1.数组实现
  2.链表
二、栈与队列
三、树与二叉树
  1.树
  2.二叉树基本概念
  3.二叉查找树
  4.平衡二叉树
  5.红黑树
四、图
五、总结

一、线性表

线性表是最常用且最简单的一种数据结构,它是n个数据元素的有限序列。

实现线性表的方式一般有两种,一种是使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)。

数组实现

数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后,它的大小就无法改变了,但是当数组不能再存储线性表中的新元素时,我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

  • 代码1 创建一个更大的数组来替换当前数组
int[] oldArray = new int[10];
        
int[] newArray = new int[20];
        
for (int i = 0; i < oldArray.length; i++) {
    newArray[i] = oldArray[i];
}

// 也可以使用System.arraycopy方法来实现数组间的复制     
// System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
        
oldArray = newArray;
  • 代码2 在数组位置index上添加元素e
//oldArray 表示当前存储元素的数组
//size 表示当前元素个数
public void add(int index, int e) {

    if (index > size || index < 0) {
        System.out.println("位置不合法...");
    }

    //如果数组已经满了 就扩容
    if (size >= oldArray.length) {
        // 扩容函数可参考代码1
    }

    for (int i = size - 1; i >= index; i--) {
        oldArray[i + 1] = oldArray[i];
    }

    //将数组elementData从位置index的所有元素往后移一位
    // System.arraycopy(oldArray, index, oldArray, index + 1,size - index);

    oldArray[index] = e;

    size++;
}

上面简单写出了数组实现线性表的两个典型函数,具体我们可以参考Java里面的ArrayList集合类的源码。数组实现的线性表优点在于可以通过下标来访问或者修改元素,比较高效,主要缺点在于插入和删除的花费开销较大,比如当在第一个位置前插入一个元素,那么首先要把所有的元素往后移动一个位置。为了提高在任意位置添加或者删除元素的效率,可以采用链式结构来实现线性表。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next,Next指向下一个节点,这样当添加或者删除时,只需要改变相关节点的Next的指向,效率很高。

单链表的结构

下面主要用代码来展示链表的一些基本操作,需要注意的是,这里主要是以单链表为例,暂时不考虑双链表和循环链表。

  • 代码3 链表的节点
class Node<E> {

    E item;
    Node<E> next;
    
    //构造函数
    Node(E element) {
       this.item = element;
       this.next = null;
   }
}
  • 代码4 定义好节点后,使用前一般是对头节点和尾节点进行初始化
//头节点和尾节点都为空 链表为空
Node<E> head = null;
Node<E> tail = null;
  • 代码5 空链表创建一个新节点
//创建一个新的节点 并让head指向此节点
head = new Node("nodedata1");

//让尾节点也指向此节点
tail = head;
  • 代码6 链表追加一个节点
//创建新节点 同时和最后一个节点连接起来
tail.next = new Node("node1data2");

//尾节点指向新的节点
tail = tail.next;
  • 代码7 顺序遍历链表
Node<String> current = head;
while (current != null) {
    System.out.println(current.item);
    current = current.next;
}
  • 代码8 倒序遍历链表
static void printListRev(Node<String> head) {
//倒序遍历链表主要用了递归的思想
    if (head != null) {
        printListRev(head.next);
        System.out.println(head.item);
    }
}
  • 代码 单链表反转
//单链表反转 主要是逐一改变两个节点间的链接关系来完成
static Node<String> revList(Node<String> head) {

    if (head == null) {
        return null;
    }

    Node<String> nodeResult = null;

    Node<String> nodePre = null;
    Node<String> current = head;

    while (current != null) {

        Node<String> nodeNext = current.next;

        if (nodeNext == null) {
            nodeResult = current;
        }

        current.next = nodePre;
        nodePre = current;
        current = nodeNext;
    }

    return nodeResult;
}

上面的几段代码主要展示了链表的几个基本操作,还有很多像获取指定元素,移除元素等操作大家可以自己完成,写这些代码的时候一定要理清节点之间关系,这样才不容易出错。

链表的实现还有其它的方式,常见的有循环单链表,双向链表,循环双向链表。 循环单链表 主要是链表的最后一个节点指向第一个节点,整体构成一个链环。 双向链表 主要是节点中包含两个指针部分,一个指向前驱元,一个指向后继元,JDK中LinkedList集合类的实现就是双向链表。** 循环双向链表** 是最后一个节点指向第一个节点。

二、栈与队列

栈和队列也是比较常见的数据结构,它们是比较特殊的线性表,因为对于栈来说,访问、插入和删除元素只能在栈顶进行,对于队列来说,元素只能从队列尾插入,从队列头访问和删除。

栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫作栈顶,对栈的基本操作有push(进栈)和pop(出栈),前者相当于插入,后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表,即后进先出。

栈的模型

下面我们看一道经典题目,加深对栈的理解。

关于栈的一道经典题目

上图中的答案是C,其中的原理可以好好想一想。

因为栈也是一个表,所以任何实现表的方法都能实现栈。我们打开JDK中的类Stack的源码,可以看到它就是继承类Vector的。当然,Stack是Java2前的容器类,现在我们可以使用LinkedList来进行栈的所有操作。

队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列示意图

我们可以使用链表来实现队列,下面代码简单展示了利用LinkedList来实现队列类。

  • 代码9 简单实现队列类
public class MyQueue<E> {

    private LinkedList<E> list = new LinkedList<>();

    // 入队
    public void enqueue(E e) {
        list.addLast(e);
    }

    // 出队
    public E dequeue() {
        return list.removeFirst();
    }
}

普通的队列是一种先进先出的数据结构,而优先队列中,元素都被赋予优先级。当访问元素的时候,具有最高优先级的元素最先被删除。优先队列在生活中的应用还是比较多的,比如医院的急症室为病人赋予优先级,具有最高优先级的病人最先得到治疗。在Java集合框架中,类PriorityQueue就是优先队列的实现类,具体大家可以去阅读源码。

三、树与二叉树

树型结构是一类非常重要的非线性数据结构,其中以树和二叉树最为常用。在介绍二叉树之前,我们先简单了解一下树的相关内容。

** 树 是由n(n>=1)个有限节点组成一个具有层次关系的集合。它具有以下特点:每个节点有零个或多个子节点;没有父节点的节点称为节点;每一个非根节点有且只有一个 父节点 **;除了根节点外,每个子节点可以分为多个不相交的子树。

树的结构

二叉树基本概念

  • 定义

二叉树是每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

  • 相关性质

二叉树的每个结点至多只有2棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

二叉树的第i层至多有2(i-1)个结点;深度为k的二叉树至多有2k-1个结点。

一棵深度为k,且有2^k-1个节点的二叉树称之为** 满二叉树 **;

深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为** 完全二叉树 **。

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

  • 三种遍历方法

在二叉树的一些应用中,常常要求在树中查找具有某种特征的节点,或者对树中全部节点进行某种处理,这就涉及到二叉树的遍历。二叉树主要是由3个基本单元组成,根节点、左子树和右子树。如果限定先左后右,那么根据这三个部分遍历的顺序不同,可以分为先序遍历、中序遍历和后续遍历三种。

(1) 先序遍历 若二叉树为空,则空操作,否则先访问根节点,再先序遍历左子树,最后先序遍历右子树。
(2) 中序遍历 若二叉树为空,则空操作,否则先中序遍历左子树,再访问根节点,最后中序遍历右子树。
(3) 后序遍历 若二叉树为空,则空操作,否则先后序遍历左子树访问根节点,再后序遍历右子树,最后访问根节点。

给定二叉树写出三种遍历结果
  • 树和二叉树的区别

(1) 二叉树每个节点最多有2个子节点,树则无限制。
(2) 二叉树中节点的子树分为左子树和右子树,即使某节点只有一棵子树,也要指明该子树是左子树还是右子树,即二叉树是有序的。
(3) 树决不能为空,它至少有一个节点,而一棵二叉树可以是空的。

上面我们主要对二叉树的相关概念进行了介绍,下面我们将从二叉查找树开始,介绍二叉树的几种常见类型,同时将之前的理论部分用代码实现出来。

二叉查找树

  • 定义

二叉查找树就是二叉排序树,也叫二叉搜索树。二叉查找树或者是一棵空树,或者是具有下列性质的二叉树:

(1) 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2) 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3) 左、右子树也分别为二叉排序树;
(4) 没有键值相等的结点。

典型的二叉查找树的构建过程
  • 性能分析

对于二叉查找树来说,当给定值相同但顺序不同时,所构建的二叉查找树形态是不同的,下面看一个例子。

不同形态平衡二叉树的ASL不同

可以看到,含有n个节点的二叉查找树的平均查找长度和树的形态有关。最坏情况下,当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度为n,其平均查找长度(n+1)/2(和顺序查找相同),最好的情况是二叉查找树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比。平均情况下,二叉查找树的平均查找长度和logn是等数量级的,所以为了获得更好的性能,通常在二叉查找树的构建过程需要进行“平衡化处理”,之后我们将介绍平衡二叉树和红黑树,这些均可以使查找树的高度为O(log(n))。

  • 代码10 二叉树的节点

class TreeNode<E> {

    E element;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E e) {
        element = e;
    }
}

二叉查找树的三种遍历都可以直接用递归的方法来实现:

  • 代码12 先序遍历
protected void preorder(TreeNode<E> root) {

    if (root == null)
        return;

    System.out.println(root.element + " ");

    preorder(root.left);

    preorder(root.right);
}
  • 代码13 中序遍历
protected void inorder(TreeNode<E> root) {

    if (root == null)
        return;

    inorder(root.left);

    System.out.println(root.element + " ");

    inorder(root.right);
}
  • 代码14 后序遍历
protected void postorder(TreeNode<E> root) {

    if (root == null)
        return;

    postorder(root.left);

    postorder(root.right);

    System.out.println(root.element + " ");
}
  • 代码15 二叉查找树的简单实现
/**
 * @author JackalTsc
 */
public class MyBinSearchTree<E extends Comparable<E>> {

    // 根
    private TreeNode<E> root;

    // 默认构造函数
    public MyBinSearchTree() {
    }

    // 二叉查找树的搜索
    public boolean search(E e) {

        TreeNode<E> current = root;

        while (current != null) {

            if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else {
                return true;
            }
        }

        return false;
    }

    // 二叉查找树的插入
    public boolean insert(E e) {

        // 如果之前是空二叉树 插入的元素就作为根节点
        if (root == null) {
            root = createNewNode(e);
        } else {
            // 否则就从根节点开始遍历 直到找到合适的父节点
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
            while (current != null) {
                if (e.compareTo(current.element) < 0) {
                    parent = current;
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    parent = current;
                    current = current.right;
                } else {
                    return false;
                }
            }
            // 插入
            if (e.compareTo(parent.element) < 0) {
                parent.left = createNewNode(e);
            } else {
                parent.right = createNewNode(e);
            }
        }
        return true;
    }

    // 创建新的节点
    protected TreeNode<E> createNewNode(E e) {
        return new TreeNode(e);
    }

}

// 二叉树的节点
class TreeNode<E extends Comparable<E>> {

    E element;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E e) {
        element = e;
    }
}

上面的代码15主要展示了一个自己实现的简单的二叉查找树,其中包括了几个常见的操作,当然更多的操作还是需要大家自己去完成。因为在二叉查找树中删除节点的操作比较复杂,所以下面我详细介绍一下这里。

  • 二叉查找树中删除节点分析

要在二叉查找树中删除一个元素,首先需要定位包含该元素的节点,以及它的父节点。假设current指向二叉查找树中包含该元素的节点,而parent指向current节点的父节点,current节点可能是parent节点的左孩子,也可能是右孩子。这里需要考虑两种情况:

  1. current节点没有左孩子,那么只需要将parent节点和current节点的右孩子相连。
  2. current节点有一个左孩子,假设rightMost指向包含current节点的左子树中最大元素的节点,而parentOfRightMost指向rightMost节点的父节点。那么先使用rightMost节点中的元素值替换current节点中的元素值,将parentOfRightMost节点和rightMost节点的左孩子相连,然后删除rightMost节点。
    // 二叉搜索树删除节点
    public boolean delete(E e) {

        TreeNode<E> parent = null;
        TreeNode<E> current = root;

        // 找到要删除的节点的位置
        while (current != null) {
            if (e.compareTo(current.element) < 0) {
                parent = current;
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                parent = current;
                current = current.right;
            } else {
                break;
            }
        }

        // 没找到要删除的节点
        if (current == null) {
            return false;
        }

        // 考虑第一种情况
        if (current.left == null) {
            if (parent == null) {
                root = current.right;
            } else {
                if (e.compareTo(parent.element) < 0) {
                    parent.left = current.right;
                } else {
                    parent.right = current.right;
                }
            }
        } else { // 考虑第二种情况
            TreeNode<E> parentOfRightMost = current;
            TreeNode<E> rightMost = current.left;
            // 找到左子树中最大的元素节点
            while (rightMost.right != null) {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;
            }

            // 替换
            current.element = rightMost.element;

            // parentOfRightMost和rightMost左孩子相连
            if (parentOfRightMost.right == rightMost) {
                parentOfRightMost.right = rightMost.left;
            } else {
                parentOfRightMost.left = rightMost.left;
            }
        }

        return true;
    }

平衡二叉树

平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

平衡二叉树

AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

红黑树

红黑树是平衡二叉树的一种,它保证在最坏情况下基本动态集合操作的事件复杂度为O(log n)。红黑树和平衡二叉树区别如下:

(1) 红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。
(2) 平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。点击查看更多

四、图

  • 简介

图是一种较线性表和树更为复杂的数据结构,在线性表中,数据元素之间仅有线性关系,在树形结构中,数据元素之间有着明显的层次关系,而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。图的应用相当广泛,特别是近年来的迅速发展,已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。

  • 相关阅读

因为图这部分的内容还是比较多的,这里就不详细介绍了,有需要的可以自己搜索相关资料。

(1) 《百度百科对图的介绍》
(2) 《数据结构之图(存储结构、遍历)》

五、总结

到这里,关于常见的数据结构的整理就结束了,断断续续大概花了两天时间写完,在总结的过程中,通过查阅相关资料,结合书本内容,收获还是很大的,在下一篇博客中将会介绍常用数据结构与算法整理总结(下)之算法篇,欢迎大家关注。

POSIX I/O模型之阻塞、非阻塞、同步、异步浅析

服务端编程常需要接触I/O。最近对I/O模型有了进一步的认识,这里就总结一下POSIX I/O模型,并简略总结一下Java中的Network I/O模型。常见的POSIX I/O模型有四种:

  • 同步阻塞I/O(Synchrohous, blocking I/O)
  • 同步非阻塞I/O(Synchrohous, non-blocking I/O)
  • I/O多路复用(I/O Multiplexing),较为典型的有selectepoll模型
  • 异步I/O(Asynchronous I/O)

通俗解释

在详细解释各个I/O模型之前,我们先来通俗地解释一下各个I/O模型,便于理解。

  • 同步阻塞I/O:去餐厅吃饭,等餐的时候需要在取餐处一直等着,不能干其他事情。
  • 同步非阻塞I/O:去餐厅吃饭,等餐的时候可以干别的事,但需要不断去窗口询问饭是否准备好了(轮询)。
  • 异步I/O:去餐厅吃饭,等餐的时候只需要坐着等人送来即可。

下面我们来详细解释一下各个I/O模型,为了简单起见这里采用UDP协议作为示例。

Blocking I/O

首先对于一个从socket读取数据的操作,通常将其分为两个阶段:

  1. 等待远程数据就绪。网卡会将数据报文传给协议栈,封装处理之后拷贝到内核缓冲区中
  2. 将数据从内核缓冲区拷贝到进程中

最简单的模型就是blocking I/O模型了。进行recvfrom系统调用(读取数据)以后,调用者进程会被阻塞,直到内核接收到数据并拷贝到进程中才返回。进行recvfrom系统调用后,内核首先会等待数据就绪,这通常需要一段时间。当数据就绪并到达内核缓冲区后,内核就会将数据拷贝至用户内存空间,并且返回结果,此时调用者进程才会解除阻塞状态,恢复执行。Blocking I/O不会浪费CPU时间片,但是只能处理一个连接,对于多个连接的情况就需要用到下面要提到的的I/O多路复用了。

可以看出,blocking I/O会阻塞上面两个阶段:

Synchrohous, blocking IO

Non-blocking I/O

与blocking I/O不同,non-blocking I/O的意思是在读取数据(recvfrom)时,如果数据没有就绪则立刻返回一个错误,而不会被阻塞住,这样我们还可以继续进行其它的操作。为了读取到数据,我们需要不断调用recvfrom进行轮询操作,一旦数据准备好了,内核就会将数据拷贝至用户内存空间,并且返回读取成功的结果。这种模型的弊端就是轮询操作会占用时间片,浪费CPU资源。可以看出,non-blocking I/O会阻塞上面的阶段(2):

Non-blocking IO

I/O multiplexing

I/O多路复用(multiplexing)是网络编程中最常用的模型,像我们最常用的selectepoll都属于这种模型。以select为例:

IO Multiplexing

看起来它与blocking I/O很相似,两个阶段都阻塞。但它与blocking I/O的一个重要区别就是它可以等待多个文件描述符就绪,即可以处理多个连接。这里的select相当于一个“代理”,调用select以后进程会被select阻塞,这时候在内核空间内select会监听指定的的多个文件描述符(如socket连接),如果其中任意一个数据就绪了就返回。此时程序再进行数据读取操作,将数据拷贝至当前进程内。由于select可以监听多个socket,我们可以用它来处理多个连接。

select模型中每个socket一般都设置成non-blocking,虽然阶段(1)仍然是阻塞状态,但是它是被select调用阻塞的,而不是直接被I/O阻塞的。select底层通过轮询机制来判断每个socket读写是否就绪。

当然select也有一些缺点,比如底层轮询机制会增加开销、支持的文件描述符数量过少等。为此,Linux引入了epoll作为select的改进版本,具体的区别和改进后面会另开一篇总结。

Asynchronous I/O

Asynchronous I/O的过程:

Asynchronous IO

这里面的读取操作的语义与上面的几种模型都不同。这里的读取操作(aio_read)会通知内核进行读取操作并将数据拷贝至进程中,完事后通知进程整个操作全部完成(绑定一个回调函数处理数据)。读取操作会立刻返回,程序可以进行其它的操作,所有的读取、拷贝工作都由内核去做,做完以后通知进程,进程调用绑定的回调函数来处理数据。

异步I/O在网络编程中几乎用不到,在File I/O中可能会用到。

Java中的Network I/O模型

Java原生的Network I/O模型分为以下几种:

  • BIO(如ServerSocket)
  • NIO(JDK 1.4引入,如ServerSocketChannel)
  • NIO.2(AIO, JDK 1.7引入,如AsynchronousServerSocketChannel)

其中BIO对应传统的同步阻塞I/O,而NIO对应I/O多路复用(select模型,Reactor模式),NIO.2则对应异步IO模型(依然是基于I/O多路复用,和POSIX的asynchronous I/O模型不同)。在Linux下,NIO和NIO.2底层都是通过epoll实现的。

Netty的I/O模型也类似,分为OIO和NIO两种。

总结

我们来总结一下阻塞、非阻塞,同步和异步这两组概念。

先来说阻塞和非阻塞。阻塞调用会一直等待远程数据就绪再返回,即上面的阶段(1)会阻塞调用者,直到读取结束。而非阻塞无论在什么情况下都会立即返回。

接下来是同步和异步。POSIX标准里是这样定义同步和异步的:

  • A synchronous I/O operation causes the requesting process to be blocked until that I/O operation completes.
  • An asynchronous I/O operation does not cause the requesting process to be blocked.

同步方法会一直阻塞进程,直到I/O操作结束,注意这里相当于上面的(1)(2)两个阶段都会阻塞调用者。而异步方法不会阻塞调用者进程,即使是从内核空间的缓冲区将数据拷贝到进程中这一操作也不会阻塞进程,拷贝完毕后内核会通知进程数据拷贝结束。

下面的这张图很好地总结了之前讲的这几种POSIX I/O模型(来自Unix Network Programming):

IO模型比较


References