Java中常用Map数据结构介绍

REFERENCES

http://ifeve.com/selectors/

前言

A Red-Black tree based {@link NavigableMap} implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the {@code containsKey}, {@code get}, {@code put} and {@code remove} operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.

上面是一段关于TreeMap的官方Javadoc描述，简单来说就是，TreeMap底层是基于红黑树，保持了key的大小有序性，因此查找等操作的时间复杂度为O(logn)；

在这篇文章中我主要分析Java中是如何利用红黑树实现TreeMap的，关于红黑树的详细原理介绍可以参考这篇文章《教你透彻了解红黑树》。

首先我们来看一个Java的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * @author Shuai Junlan[shuaijunlan@gmail.com].
 * @since Created in 1:43 PM 1/17/19.
 */
public class ArrayTraverse {
    private static long[][] arrs = new long[1024*1024][8];
    public static void main(String[] args) {
        long temp = 0;
        long start = System.currentTimeMillis();

        // Vertical traverse
        for (int i = 0; i < 8; i ++){
            for (int j = 0; j < 1024 * 1024; j++){
                temp = arrs[j][i];
            }
        }
        System.out.println("Vertical traverse spending time: " + (System.currentTimeMillis() - start) + "ms");

        start = System.currentTimeMillis();
        // Horizontal traverse
        for (int i = 0; i < 1024 * 1024; i++){
            for (int j = 0; j < 8; j++){
                temp = arrs[i][j];
            }
        }
        System.out.println("Horizontal traverse spending time: " + (System.currentTimeMillis() - start) + "ms");
    }
}

上述代码中定义了一个二维数组，分别从横向遍历和纵向遍历了；两个方面来计算耗时，相信通过上面的代码大家也都能知道两种遍历方式耗时差距很大，结果确实是这样的：

1
2

Vertical traverse spending time: 75ms
Horizontal traverse spending time: 13ms

看上面的输出结果，耗时差距确实很大，但是为什么会有这个大的差距呢？显然跟我们这篇文章的题目有关，那就是横向遍历充分利用了CPU高速缓存机制，使得遍历速度要快于纵向遍历，那么……

在Java中的原子类中频繁的使用CAS策略来保证数据更新的安全性，它是一种Lock-Free机制，这篇文章将会讲解CAS原理，以及它在Java中的应用。