Ramdon

伪随机数

在大部分的程序语言中，随机数的生成都是伪随机的。什么是伪随机呢？伪随机性（Pseudorandomness）是指一个过程看起来是随机的，但实际上不是。它通常是使用一个确定性的算法计算出来的似乎是随机的数字，我们只要确定算法计算过程中的初始值，那么计算得到的随机数将会是固定的。

如果要获得真正的随机数，那么仅仅依靠软件去生成随机数是不够的，还需要一些随机的事件得到对应的参数指标，例如在 Linux 中获取随机数的方式就是依靠 intel CPU 电路中的热噪声信号产生的随机数，或者是用户的键盘输入的位置速度，大气中的噪声等方式获取真正的随机数，但都是依赖于专业的设备硬件。

伪随机算法

• 线性同余方法（Linear Congruential Generator）LCG
• 梅森旋转算法（Mersenne twister） MT
• M-sequence（Maximum length sequence） MLS
  
  

LCG

随机数的生成采用了递归公式，这里的 $ X_n $ 表示第 n 个数，$ X_n+1 $ 表示由上一个随机数得到的当前数值，变量 a, c, m 都是常数，LCG 的周期最大为 m，但大部分情况下都会小于 m，要令 LCG 达到最大周期，需要满足以下条件：

1. c，m 互为质数
2. m 的所有质因数都能被整除 a - 1
3. 如果 m 是4的倍数，那么 a - 1 也是
4. a, c, n都比 m 小

优点：生成随机数的速度快，消耗内存小，但得知 seed 的情况下，容易根据随机的区间推断出来

MT

梅森旋转算法是基于二进制字段上的矩阵线性递归 $F_2$，对于一个 k 位的长度，MT 会在[0, $2^k$ - 1] 的区间之间生成离散型均匀分布的随机数，由于周期很长（$2^10037$ - 1）,使得随机数得区间更大，通过对 seed 生成得梅森旋转链进行旋转，处理得到旋转结果，使随机数在区间内均等分布。

因为其优秀得生成随机数速度及内存消耗空间得优化，在多个程序语言中已经使用，如 Python，PHP，Puby等。

概念

协变与逆变 (Covariance and contravariance ) 用来描述具有父/子关系的类型通过类型转换之后的继承关系。

即：如果A、B表示类型，f()表示类型转换， 表示子类与父类之间的继承关系，那么有以下定义：
协变(Covariance)：当 A $\subseteq$ B时，f(A) $\subseteq$ f(B)成立；
逆变(contravariance)：当A $\subseteq$ B时，f(B) $\subseteq$ f(A)成立；
不变(invariance)：当A $\subseteq$ B时，以上均不成立，那么f(A)与f(B)之间不存在继承关系；

先定义几个类之间的继承关系

1
2
3
4
5
6

class Fruit{}       // base

class Apple extends Fruit{}

class Lemon extends Fruit{}
class Eureka extends Lemon{}

数据结构

LinkedHashMap 继承了HashMap,对HashMap进行了增强，通过内部维护了双向链表，使LinkedHashMap拥有了顺序访问的功能，提供了有序性。

1
2
3

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

内部构造

Entry内部维护了 before 和 after 两个entry，用于构建双向链表entry之间的指向关系，同时accessOrder 用于设置LinkedHashMap的读取是按照访问顺序还是插入顺序，通过这个accessOrder属性可以很容易实现 LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

// 头节点（最旧未使用）
transient LinkedHashMap.Entry<K,V> head;

// 尾节点 （最近使用）
transient LinkedHashMap.Entry<K,V> tail;

// 设置LinkedHashMap的读取顺序
//      false(default)：插入顺序
//      true：访问顺序
final boolean accessOrder;

产生原因

• 在多线程环境下，HashMap在扩容时会产生死循环，而线程安全的HashTable，在涉及多线程的操作都采用Synchronized锁住整个数组表，即所有线程在争夺一个资源，效率很低。

1.7 vs 1.8

• 1.7的 ConcurrentHashMap 采用的是分段锁的设计，底层数据结构是Segment + HashEntry，Segment实现了ReentrantLock，自带锁的功能，每次只锁定对应的Segment，多个线程争夺同个segment时，通过tryLock争夺，锁定的粒度下降了，性能也就提高了不少。

• 1.8的ConcurrentHashMap 摒弃了分段锁的概念（Segment），沿用了HashMap的思想，基于数组 + 链表 + 红黑树，底层采用的Node + CAS + Synchronized，保证并发的安全性，锁住的是粒度更小的Node。

分析

内部类Node, 实现了Map.Entry，用于存储键值对，节点用 volatile修饰，保证了多线程间的可见性，同时注意 value也用volatile修饰，无法通过setValue设置value变量。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey()       { return key; }
    public final V getValue()     { return val; }
    public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
    public final String toString(){ return key + "=" + val; }
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry<?,?> e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = val) || v.equals(u)));
    }

    /**
     * Virtualized support for map.get(); overridden in subclasses.
     */
    Node<K,V> find(int h, Object k) {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

特征

• 根据键的 hascode 值存储数据，可直接定位值，具有很快的数据访问数组
• 遍历的顺序不确定
• 最多允许一条 null 键，允许多条记录的键为 null
• 非线程安全
  可使用 Collections.synchronizedMap 使 HashMap 具有线程安全的能力 或 ConcurrentHashMap

底层结构

底层结构采用了数组，而数组的每一个元素都是多个 Node 构成的链表，当数组超过 threshold 时，数组将会扩容。

数组中的每一个都相当于一个单向链表，key 通过 hash() 后，相同的键值对会加入到链表中，当桶中的数过多时（链表长度 > 8），将会转化为 红黑树，相比与Jdk 1.7， Jdk 1.8 中当链表过长时，链表转化为红黑树，在维护红黑树时，最坏情况下查找的时间复杂度为 O(log n)，比起单链表的 O(1) ~ O(n), 时间复杂度降低了，但所需要维护的空间占用却更多。

ArrayList 是平时常用的数据存储结构，它基于动态数组，支持随机访问，值得一提的是：它是不安全的。造成这种不安全的原因主要是：在在多线程环境下，向 ArrayList 添加或移除时，会产生数组越界等问题。推荐使用 Vector、CopyOnWriteArrayList 代替。

ArrayList 与 Array 区别：

• Array 包含的是基本类型和对象类型，而ArrayList 只能包含对象类型
• Array 的大小的是固定的，所以在定义数组的时候尽量确定需要的数组大小，而ArrayList 的大小是动态变化的，当容量不足时能自动扩容
• ArrayList 可以看作Array的增强版，提供了更多的方法和特性，在查找等操作上更方便

定义

1
2

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable