1. Date API
Java 8
在包
java.time
下包含了一组全新的时间日期
API
。新的日期
API
和开源的
Joda-Time
库差不多，但 又不完全一样，下面的例子展示了这组新API
里最重要的一些部分：
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);
System.out.println(millis);
System.out.println(legacyDate);
LocalTime
本地时间
LocalTime now1 = LocalTime.of(23, 59, 59);
LocalTime now2 = LocalTime.of(10,10, 59);
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);
System.out.println(minutesBetween);
System.out.println(now1); // 23:59:59
System.out.println(now3);
LocalDate
本地日期
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(today);
System.out.println(tomorrow);
System.out.println(yesterday);
System.out.println(independenceDay);
System.out.println(dayOfWeek);
从字符串解析一个
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
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
格式化
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:132. Annotation 注解
在
Java 8
中支持多重注解了，先看个例子来理解一下是什么意思。
首先定义一个包装类
Hints
注解用来放置一组具体的
Hint
注解：
代码如下:
@interface Hints {
Hint[] value();
}@Repeatable(Hints.class)
@interface Hint {
String value();
}
Java 8
允许我们把同一个类型的注解使用多次，只需要给该注解标注一下
@Repeatable
即可。
例
1:
使用包装类当容器来存多个注解（老方法）
代码如下
:
@Hints({@Hint("hint1"), @Hint("hint2")})class Person {}
例
2
：使用多重注解（新方法）
代码如下
:
@Hint("hint1")@Hint("hint2")class Person {}
第二个例子里
java
编译器会隐性的帮你定义好
@Hints
注解，了解这一点有助于你用反射来获取这些信 息：
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); // 23. ConcurrentHashMap的红黑树实现分析
红黑树
红黑树是一种特殊的二叉树，主要用它存储有序的数据，提供高效的数据检索，时间复杂度为
O(lgn)
，
每个节点都有一个标识位表示颜色，红色或黑色，有如下
5
种特性：
1
、每个节点要么红色，要么是黑色；
2
、根节点一定是黑色的；
3
、每个空叶子节点必须是黑色的；
4
、如果一个节点是红色的，那么它的子节点必须是黑色的；
5
、从一个节点到该节点的子孙节点的所有路径包含相同个数的黑色节点；
结构示意图
只要满足以上
5
个特性的二叉树都是红黑树，当有新的节点加入时，有可能会破坏其中一些特性，需要通
过左旋或右旋操作调整树结构，重新着色，使之重新满足所有特性。
ConcurrentHashMap
红黑树实现
谈谈
ConcurrentHashMap1.7
和
1.8
的不同实现中已经提到，在
1.8
的实现中，当一个链表中的元素达到
8
个时，会调用
treeifyBin()
方法把链表结构转化成红黑树结构，实现如下：
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
从上述实现可以看出：并非一开始就创建红黑树结构，如果当前
Node
数组长度小于阈值
MIN_TREEIFY_CAPACITY
，默认为
64
，先通过扩大数组容量为原来的两倍以缓解单个链表元素过大的性
能问题。
红黑树构造过程
下面对红黑树的构造过程进行分析：
1
、通过遍历
Node
链表，生成对应的
TreeNode
链表，其中
TreeNode
在实现上继承了
Node
类；
class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
// needed to unlink next upon deletion
boolean red;
}
假设
TreeNode
链表如下，其中节点中的数值代表
hash
值：
2
、根据
TreeNode
链表初始化
TreeBin
类对象，
TreeBin
在实现上同样继承了
Node
类，所以初始化完
成的
TreeBin
类对象可以保持在
Node
数组中；
class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
volatile Thread waiter;
volatile int lockState;
// values for lockState
// set while holding write lock
static final int WRITER = 1;
// set when waiting for write lock
static final int WAITER = 2;
// increment value for setting read lock
static final int READER = 4;
}
3
、遍历
TreeNode
链表生成红黑树，一开始二叉树的根节点
root
为空，则设置链表中的第一个节点
80
为
root
，并设置其
red
属性为
false
，因为在红黑树的特性
1
中，明确规定根节点必须是黑色的；
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (r == null) {
x.parent = null;
x.red = false;
r = x;
}
4
、加入节点
60
，如果
root
不为空，则通过比较节点
hash
值的大小将新节点插入到指定位置，实现如
下：
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = r;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
r = balanceInsertion(r, x);
break;
}
}
其中
x
代表即将插入到红黑树的节点，
p
指向红黑树中当前遍历到的节点，从根节点开始递归遍历，
x
的插入过程如下：
1)
、如果
x
的
hash
值小于
p
的
hash
值，则判断
p
的左节点是否为空，如果不为空，则把
p
指向其左节
点，并继续和
p
进行比较，如果
p
的左节点为空，则把
x
指向的节点插入到该位置；
2)
、如果
x
的
hash
值大于
p
的
hash
值，则判断
p
的右节点是否为空，如果不为空，则把
p
指向其右节
点，并继续和
p
进行比较，如果
p
的右节点为空，则把
x
指向的节点插入到该位置；
3)
、如果
x
的
hash
值和
p
的
hash
值相等，怎么办？
解决：首先判断节点中的
key
对象的类是否实现了
Comparable
接口，如果实现
Comparable
接口，则
调用
compareTo
方法比较两者
key
的大小，但是如果
key
对象没有实现
Comparable
接口，或则
compareTo
方法返回了
0
，则继续调用
tieBreakOrder
方法计算
dir
值，
tieBreakOrder
方法实现如
下：
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
最终比较
key
对象的默认
hashCode()
方法的返回值，因为
System.identityHashCode(a)
调用的是对
象
a
默认的
hashCode()
；
插入节点
60
之后的二叉树：
5
、当有新节点加入时，可能会破坏红黑树的特性，需要执行
balanceInsertion()
方法调整二叉树，
使之重新满足特性，方法中的变量
xp
指向
x
的父节点，
xpp
指向
xp
父节点，
xppl
和
xppr
分别指向
xpp
的左右子节点，
balanceInsertion()
方法首先会把新加入的节点设置成红色。
①、加入节点
60
之后，此时
xp
指向节点
80
，其父节点为空，直接返回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
调整之后的二叉树：
②、加入节点50，二叉树如下：
继续执行 balanceInsertion() 方法调整二叉树，此时节点50的父节点60是左儿子，走如下逻辑：
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
根据上述逻辑，把节点
60
设置成黑色，把节点
80
设置成红色，并对节点
80
执行右旋操作，右旋实现如
下：
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
右旋之后的红黑树如下：
③、加入节点70，二叉树如下：
继续执行
balanceInsertion()
方法调整二叉树，此时父节点
80
是个右儿子，节点
70
是左儿子，且叔节
点
50
不为空，且是红色的，则执行如下逻辑：
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
此时二叉树如下：
此时 x 指向 xpp ，即节点60，继续循环处理 x ，设置其颜色为黑色，最终二叉树如下：
④、加入节点20，二叉树变化如下：
因为节点
20
的父节点
50
是一个黑色的节点，不需要进行调整；
⑤、加入节点
65
，二叉树变化如下：
1
、对节点
20
执行左旋操作；
2
、对节点
50
执行右旋操作；
最后加入节点
10
，二叉树变化如下：
