【推荐算法工程师技术栈系列】程序语言--Java

时间:2020-12-09 20:04:25

JDK 初步

ArrayList

底层就是一个Object数组,初始容量为10,每当元素要超过容量时,重新创建一个更大的数组,并把原数据拷到新数组中来。

ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。

size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性(roughly speaking)。

每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

LinkedList

LinkedList采用双向链表。集合中的每一个元素都会有两个成员变量prev和next,分别指向它的前一元素和后一元素。

LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。注意LinkedList没有同步方法。

Vector

Vector底层实现和ArrayList类似,区别在于在许多方法上加了synchronized关键字,来实现了多线程安全。但代价是性能的降低。由于加锁的是整个集合,所以并发情况下进行迭代会锁住很长时间。

Stack

Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

HashMap

HashMap采用的是哈希表结构,用链表法来解决hash冲突。

【推荐算法工程师技术栈系列】程序语言--Java

HashMap是非同步的,并且允许null,即null value和null key。Map不保证顺序;get,put方法运行时间为常数。

但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低

HashMap有两个重要参数影响性能:初始容量(initial capacity)和负载因子(load factor)。capacity是哈希表创建时候的桶数;load factor是衡量HashMap多满的时候增加capacity的大小(也就是增加bucket的比例,默认0.75),也就是说当size >(capacity * loadFactor)的时候会出现HashMap重新初始化一个新的数组,然后把原来的所有的元素重新hash到新的数组中,所以如果你使用的场景是在短时间内需要往HashMap中添加较多的元素,那么建议不要使用HashMap的默认capacity,因为这样会引起多次的rehash(也就是ArrayList中的arrayCopy操作差不多),从而引起性能的下降。

Hashtable

Hashtable实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。Hashtable是同步的。

添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。

Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。

LinkedHashMap

在HashMap的基础上加了双链表,非同步的,并且允许null,即null value和null key。保证迭代顺序

该集合中的每个元素也都保留了前一个元素和后一个元素的“指针”。这样便可以按照插入顺序来迭代

LinkedHashMap(int,float,boolean)构造函数被用来构建LRU缓存:其迭代顺序包含了是最近最频繁的几个元素。调用put,putIfAbsent,get,getOrDefault,compute,computeIfAbsent,computeIfPresent或merge方法会导致访问相应的条目(假设key存在)。如果替换了值,replace方法只会导致访问该替换条目。putAll方法为指定映射中的每个映射生成一个条目访问,按照指定映射的条目集迭代器提供键 - 值映射的顺序。removeEldestEntry(Map.Entry)强制在将新KV添加到map时自动删除过时KV的策略。

由于要维护额外的双链表,LinkedHashMap增删操作会比HashMap慢,但迭代时会比HashMap快

TreeMap

TreeMap是红黑树基于NavigableMap的实现,非同步的

根据使用的构造器决定该map是根据key值进行自然排序(Comparable)还是按照map创建时指定的规则(Comparator)进行排序。

该实现保证了containsKey,get,put,remove操作均具有log(n)的时间复杂度

注意TreeMap维持的排序和任何排序的map一样,无论是否提供明确的比较器,要正确地实现map接口,必须有一致的equals方法。这是因为Map接口是根据equals方法定义,但是一个排序map使用compare或者compareTo进行键值的比较,所以从这个角度看,两个键值相等的元素是相等的。

HashSet

HashSet底层实现其实就是一个固定value(PRESENT属性)的HashMap,允许null,不保证迭代顺序;非同步的;

LinkedHashSet

LinkedHashSet就是一个value(PRESENT属性)固定的LinkedHashMap,允许null,保证迭代顺序;非同步的;

TreeSet

TreeSet就是一个value(PRESENT属性)固定的TreeMap,允许null,不保证迭代顺序;非同步的;

PriorityQueue

PriorityQueue是基于优先级堆(小顶堆)实现的*优先级队列。优先级队列中的元素根据其可比较的(Comparable)自然顺序来排序,或者由构造队列时提供的比较器(Comparator)来排序,这取决于使用的是哪个构造函数。优先级队列不允许插入空元素。一个依赖自然排序的优先级队列同样不允许插入不可比较的对象。

队列的头部是与指定顺序相关的最小元素。如果有多个相同优先级的最小元素,则从中任意选取一个作为队列的头。队列的检索操作如poll()、remove()、peek()、element()都是从队列的头部元素开始。

优先级队列是*的,但队列具有可以控制存储元素数组大小的内部容量。它总是至少和队列大小一样大。当元素被添加到优先级队列时,其容量会自动增长。队列容量的增长策略细节并没有指定。

需要注意的是,优先级队列并不是同步的。当一个线程正在修改队列时,其他多个线程不应该同时访问队列。可以使用线程安全的PriorityBlockingQueue。

实现大顶堆代码

// 大顶堆实现
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(size, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return -o1.compareTo(o2);
}
});

ConcurrentLinkedQueue

ConcurrentLinkedQueue一个基于链接节点线程安全的*队列。队列的元素顺序为FIFO。队列的头部,是在队列上时间最久的元素。队列的尾元素是在队列中时间最短的元素

新元素添加到队列的尾部,队列获取元素,从队列头部获取。ConcurrentLinkedQueue适用于多个线程需要同时访问一个相同集合的场景。与大多数并发集合一样,不允许插入null元素。队列的实现是基于一个有效的wait-free算法,具体参见链接:简单快速实用的并发

不像大多数的集合,size操作时间复杂度不是一个常量,因为队列异步操作的天性,决定了遍历队列元素时,有可能其他线程修改队列,导致最终size的数量可能不准确。另外addAll,removeAll,retainAll,containsAll,equals,toArray都不能保证原子性。比如遍历操作和addAll操作同时发生,可能会看到一些相同的新增元素。ConcurrentLinkedQueue实现了所有Queue和Iterator接口的所有方法。内存一致性影响:与其他并发线程集合一样,线程添加一个元素到队列发生在其他线程访问或移除队列元素之前。

第三方类库

Apache HttpComponents Client

HttpComponents项目就是专门设计来简化HTTP客户端与服务器进行各种通讯编程。以下列出的是 HttpClient 提供的主要的功能。

实现了所有 HTTP 的方法(GET,POST,PUT,HEAD 等)

支持自动转向

支持 HTTPS 协议

支持代理服务器等

支持Cookie

HttpClient Quick Start

HttpClient Tutorial

spring-core

spring是一个开源的,轻量级控制反转和面向切面的容器框架,解决企业应用开发的复杂性,降低耦合,更易于测试。

spring核心的功能就是一个工厂模式,spring相当于为你的项目专门成立一个工厂,这个工厂负责创建对象,维护对象之间的关系,以前是直接new,现在从spring的工厂里面获取。

docs/4.3.10.RELEASE/spring-framework-reference

Spring Resource框架体系介绍

jetty

Jetty是一个用 Java 实现、开源、基于标准的,并且具有丰富功能的 Http 服务器和 Web 容器。 Jetty 可以用来作为一个传统的 Web 服务器,也可以作为一个动态的内容服务器,并且 Jetty 可以非常容易的嵌入到 Java 应用程序当中。

jetty是轻量级的web服务器和servlet引擎。它的最大特点是:可以很方便的作为嵌入式服务器。 就是只要引入jetty的jar包,可以通过直接调用其API的方式来启动web服务。

https://www.eclipse.org/jetty/

Jetty使用教程(一)——开始使用Jetty

Jetty使用教程(四:21-22)—Jetty开发指南

Jetty使用教程(四:23)—Jetty开发指南

Jetty使用教程(四:24-27)—Jetty开发指南

Jetty使用教程(四:28-30)—Jetty开发指南

thoughtworks xstream

XStream是一个Java对象与XML互相转换的工具类库。

使用XStream实现Java对象与XML互相转换

thoughtworks xstream 官网

fastjson

FastJSOn是阿里巴巴开源的JSON处理工具。

Fastjson是一个json处理工具包,包括“序列化”和“反序列化”两部分,它具备如下特征:

速度最快,测试表明,fastjson具有极快的性能,超越任其他的java json parser。包括自称最快的jackson。

功能强大,完全支持java bean、集合、Map、日期、Enum,支持范型,支持自省。

无依赖,能够直接运行在Java SE 5.0以上版本

支持Android。

官网地址:http://code.alibabatech.com/wiki/display/FastJSON/Overview

Fastjson介绍

commons 组件

  • commons-lang3/commons-lang

    包结构

    org.apache.commons.lang3

    org.apache.commons.lang3.builder

    org.apache.commons.lang3.concurrent

    org.apache.commons.lang3.event

    org.apache.commons.lang3.exception

    org.apache.commons.lang3.math

    org.apache.commons.lang3.mutable

    org.apache.commons.lang3.reflect

    org.apache.commons.lang3.text

    org.apache.commons.lang3.text.translate

    org.apache.commons.lang3.time

    org.apache.commons.lang3.tuple

    【小家Java】Java第二API之apache的commons-lang3工具包史上最完整的讲解(书写优雅代码必备工具)

    【小家Java】common-lang3中StringUtils的使用详解

    日期格式化类DateFormatUtils【org.apache.commons.lang3.time.DateFormatUtils】

  • apache commons-math3/apache commons-math

    apache-commons-math3是java的一种科学计算类库。

    官方文档

  • commons-net

    Apache commons net 项目中封装了各种网络协议的客户端。

    编写更少量的代码:使用apache commons工具类库

    api doc

  • fastutil

    fastutil扩展了Java集合框架,通过提供特定类型的map、set、list和queue,以及小内存占用、快速访问和插入;也提供大(64位)array、set 和 list,以及快速、实用的 二进制文件和文本文件的I/O类。

    官方文档

  • commons-dbpc

  • commons-pool

  • mysql-connector-java

  • guava

    Guava是一种基于开源的Java库,其中包含谷歌正在由他们很多项目使用的很多核心库。这个库是为了方便编码,并减少编码错误。这个库提供用于集合,缓存,支持原语,并发性,常见注解,字符串处理,I/O和验证的实用方法。Guava 的好处:

    标准化 - Guava库是由谷歌托管。

    高效 - 可靠,快速和有效的扩展JAVA标准库

    优化 -Guava库经过高度的优化。

    函数式编程 -增加JAVA功能和处理能力。

    实用程序 - 提供了经常需要在应用程序开发的许多实用程序类。

    验证 -提供标准的故障安全验证机制。

    最佳实践 - 强调最佳的做法。

    Google的Java常用类库 Guava

logback日志组件

cache组件

附录