Java常用类库与技巧

1、Java的异常体系

                                                      

• RuntimeException：不可预知的异常，程序应当自行避免，是程序应该承担的责任
• 非RuntimeException：可预知的异常，从编译器可以校验的异常，是Java编译器应该承担的责任

2、Java的异常处理机制

• Error：程序无法处理的错误，Java编译器不做检查，属于JVM需要负担的责任
• Exception：程序可以处理的异常，捕获后程序可以恢复运行
• 总结：前者是程序无法处理的错误，后者是可以处理的异常

3、常见Error以及Exception

RuntimeException

1. NullPointerException-空指针引用异常
2. ClassCastException -类型强制转换异常
3. IllegalArgumentException-传递非法参数异常
4. IndexOutOfBoundsException-下标越界异常
5. NumberFormatException-数字格式异常

非RuntimeException

1. ClassNoFoundException-找不到指定class异常
2. IOException-IO操作异常

Error

1. NoClassDefFoundError-找不到class定义的异常
2. *Error-深递归导致栈被耗尽而抛出的异常
3. OutOfMemoryError-内存溢出异常

4、数据结构考点

• 数组和链表的区别
• 链表的操作，如反转、链表环路检测、双向链表、循环链表相关操作
• 队列、栈的应用
• 二叉树的遍历方式及其递归和非递归的实现
• 红黑树的旋转

5、算法考点

• 内部排序：如递归排序、交换排序（冒泡、快排）、选择排序、插入排序
• 外部排序：应掌握如何利用有限的内存配合海量的外部存储来处理超大的数据集，写不出来也要写出相关思路
• 那些排序是不稳定的，稳定意味着什么
• 不同数据集，各种排序的最好最差情况
• 如何优化算法

6、集合总体结构图

                                            

集合的两个*接口分别为:Collection和Map

存入元素：

Collection接口下的实现类通过add方法来完成，而Map下是通过put方法来完成。

取出元素：

Collection接口下：List接口有两种方式：1、get(脚标)；2、通过Iterator迭代方式获取元素；而Vactor多了一种枚举（Enumeration）的方式。Set接口通过迭代的方式获取元素。

Map接口下：先通地keySet获取键的系列，然后通过该系列使用Iterator迭代方式获取元素值。

7、集合之List和Set

         

8、HashMap、HashTable、ConcurrentHashMap

1)、HashMap（Java1.8以前）：数组加链表

                                  

HashMap（Java1.8及以后）：数组加链表加红黑树

            

HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量（默认值为16）只是哈希表在创建时的容量。加载因子（默认0.75）是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将扩大到具有大约两倍的桶数。

HashMap在Java1.8以前，key在产生碰撞后会自动将键值对连接在碰撞键值对的后面组成链表结构，但是在链表长度太长之后，会影响HashMap的查询性能，时间复杂度可能会从原来的O(1)变为O(n)。在Java1.8及以后，HashMap使用数组加链表加红黑树的结构，HashMap中提供一个为TREEIFY_THRESHOLD的变量，当链表长度达到8的时候，自动将链表转化为红黑树进行存储，当键值对个数少于6的时候，自动将红黑树转化为链表存储。

HashMap的put方法的逻辑：

• 如果HashMap未被初始化，则初始化
• 对Key求Hash值，然后再计算下标
• 如果没有碰撞，直接放入桶中；如果碰撞则以链表的形式存放在后面
• 如果链表长度超过阈值8，就把链表转化为红黑树；如果链表长度低于6，则把链表转化为红黑树
• 如果节点已经存在，则替换旧值
• 如果桶满（容量16*加载因子0.75），就需要resize（扩容两倍后重排）

HashMap如何减少碰撞：

• 扰动函数：让元素位置分布均匀，减少碰撞
• 使用final对象，并采用合适的equals和hashcode方法，例如用String和Integer这样类型的变量作为key

HashMap扩容可能产生的问题：

• 多线程环境下，多个线程同时调整同一个HashMap会存在条件竞争，容易造成死锁
• rehashing是一个比较耗费时间的过程

如何实现HashMap的线程安全

使用Collections.synchronizedMap（HashMap）方法，例：

package com.javabasic.bytecode;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class SafeHashMapDemo {
    public static void main(String[] args) {
        Map hashMap = new HashMap();
        Map safeHashMap = Collections.synchronizedMap(hashMap);
        safeHashMap.put("aaa","1");
        safeHashMap.put("bbb","2");
        System.out.println(safeHashMap.get("bbb"));
    }
}

2)、Hashtable

• 线程安全：涉及到修改Hashtable的方法，都使用了synchronized去修饰
• 串行化的方式运行，性能较差

3）、ConcurrentHashMap

早期ConcurrentHashMap：通过分段锁Segment来实现

                   

当前ConcurrentHashMap：CAS+synchronized使锁更细化

                

ConcurrentHashMap：put方法逻辑

1. 判断Node[]数组是否初始化，没有则进行初始化操作
2. 通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头节点），添加失败则进入下一次循环
3. 检查到内部正在扩容，就帮助他一起扩容
4. 如果头节点!=null，则使用synchronized锁住头节点，再对链表或者红黑树进行添加元素操作
5. 判断链表长度是否达到临界值8，如果节点数超过临界值，则将链表转化为红黑树，小于6则将红黑树转化为链表

ConcurrentHashMap总结：比起Segment，锁拆的更细

• 首先使用无锁操作CAS插入头节点，失败则循环重试
• 若头结点已存在，则尝试获取头结点的同步锁，在进行操作

HashMap、Hashtable、ConcurrenHashMap三者区别

• HashMap线程不安全，数组加链表加红黑树
• Hashtable线程安全，锁住整个对象，运行效率低，数组加链表
• ConcurrentHashMap线程安全，CAS+同步锁，数组加链表加红黑树
• HashMap的key、value均可以为null，其他两个不支持

9、BIO、NIO、AIO

Block-IO：基于字节流的InputStream和OutputStream，基于字符流的Read和Writer

      

NonBolck-IO（非阻塞IO）：构造多路复用、同步非阻塞的IO操作

10、Comparable和Comparator的区别

Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。

　　Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

　　两种方法各有优劣， 用Comparable 简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。