列表和队列（三）：剖析 ArrayDeque

发表于 2019-01-16 | 分类于面试篇

ArrayDeque 的实现原理是？
答：
- ArrayDeque 内部是一个动态扩展的逻辑上的循环数组，通过 head 和 tail 变量维护数组的开始和结尾。数组长度为 2 的幂次方，使用高效的位操作进行各种判断，以及对 head 和 tail 进行维护。
- ArrayDeque 的高效来源于 head 和 tail 这两个变量，它们使得物理上简单的从头到尾的数组变成了一个逻辑上循环的数组，避免了在头尾操作时的移动。
- 所谓循环是指元素到数组尾之后可以接着从数组头开始，数组的长度、第一个和最后一个元素都与 head 和 tail 这两个变量有关。
- ArrayDeque 内部主要有如下实例变量：
  1
  2
  3
  private transient E[] elements;
  private transient int head;
  private transient int tail;
ArrayDeque 有什么特点？
答：ArrayDeque 实现了双端队列 Deque，内部使用循环数组实现，这决定了它有如下特点：
- 在两端添加、删除元素的效率很高，动态扩展需要的内存分配以及数组复制开销可以被平摊。具体来说，添加 N 个元素的效率为 O(N)。
- 根据元素内容查找和删除的效率比较低，为 O(N)。
- 与 ArrayList 和 LinkedList 不同，没有索引位置的概念，不能根据索引位置进行操作。
- 无论 ArrayList、LinkedList 还是 ArrayDeque ，按内容查找元素的效率都很低，都需要逐个进行比较。
ArrayDeque 和 LinkedList 都实现了 Deque 接口，应该用哪一个？
答：
- 如果只需要 Deque 接口，从两端进行操作，一般而言，ArrayDeque 效率更高一些，应该被优先使用。
- 如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除操作，则应该选 LinkedList。

列表和队列（二）：剖析 LinkedList

发表于 2019-01-16 | 分类于面试篇

LinkedList 实现的接口有？
答：
- LinkedList 除了实现了 List 列表接口外，还实现了 Deque 双端队列接口和 Queue 队列接口，可以按照队列、栈、双端队列的方式进行操作。
- 栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，不过，使用不同的名称和方法在概念上更为清晰。

怎样理解队列接口 Queue？
答：

队列的特点就是先进先出，即：在尾部添加元素、从头部删除元素。

接口定义：

public interface Queue<E> extends Collection<E> {
	boolean add(E e); // 在尾部添加元素
	boolean offer(E  e); // 在尾部添加元素
	E remove(); // 返回头部元素，并且从队列中删除
	E poll(); // 返回头部元素，并且从队列中删除
	E element(); // 返回头部元素，但不改变队列
	E peek(); // 返回头部元素，但不改变队列
}

Queue 接口的添加、删除和查看操作都有两种形式，区别是什么？
答：区别在于，对于特殊情况的处理不同。
- 特殊情况是指队列为空或者队列为满。
- LinkedList 的实现中，队列长度没有限制，但别的 Queue 的实现可能有。
- 队列为空时，element() 和 remove() 会抛出 NoSuchElementException 异常，而 peek 和 poll 返回特殊值 null。
- 队列为满时，add() 会抛出 IllegalStateException 异常，而 offer() 只是返回 false。
Java 中是怎样实现栈这种数据结构的？
答：
- 栈的特点是先进后出、后进先出。
- Java 中没有单独的栈接口，栈相关方法包括在了表示双端队列的接口 Deque 中，主要有 push()、pop()、peek()三个方法。
- 需要注意的是，Java 中有一个类 Stack，单词意思是栈，它也实现了栈的一些方法，如 push()、pop()、peek() 等，但它没有实现 Deque 接口。Stack 是 Vector 的子类，它增加的这些方法也通过 synchronized 实现了线程安全。不需要线程安全的情况下，推荐使用 LinkedList 或 ArrayDeque。

【笔试题】使用 LinkedList 表示栈和队列 Queue 的实例代码写一下？
答：

// 把 LinkedList 当做 Queue 使用
Queue<String> queue = new LinkedList<> ();
queue.offer("a");
queue.offer("b");
queue.offer("c");
while(queue.peek() != null) {
	System.out.println(queue.poll()); // 输出有三行，依次是 a、b、c
}

// 把 LinkedList 当做栈使用
Deque<String> stack = new LinkedList<> ();
stack.push("a");
stack.push("b");
stack.push("c");
while(stack.peek() != null) {
	System.out.println(stack.pop()); // 输出有三行，依次是 c、b、a
}

LinkedList 的实现原理？
答：
- LinkedList 直译就是链表，内部实现是双向链表。
- 在内存中，每个元素是单独存放的，元素之间通过链接连在一起，内存按需分配。
- 在 add() 方法中，modCount++ 的目的与 ArrayList 是一样的，纪录修改次数，便于迭代中间检测结构性变化。
LinkedList 的特点是什么？
答：用法上，LinkedList 是一个 List，但也实现了 Deque 接口，可以作为队列、栈和双端队列使用。实现原理上，LinkedList 内部是一个双向链表，并维护了长度、头节点和尾节点。这决定了它有如下特点：
- 按需分配空间，不需要预先分配很多空间。
- 不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率是 O(N/2)。
- 不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率是 O(N)。
- 在两端添加、删除元素的效率很高，为 O(1)。
- 在中间插入、删除元素，要先定位，效率比较低，为 O(N)，但修改本身的效率很高，效率为 O(1)。

列表和队列（一）：剖析 ArrayList

发表于 2019-01-15 | 分类于面试篇

ArrayList 的基本用法？
答：
- ArrayList 是 Java 中真正的动态数组容器类。
- ArrayList 是一个泛型容器，新建 ArrayList 需要实例化类型参数。比如：
  1
  2
  ArrayList<Integer> intList = new ArrayList<Integer> ();
  ArrayList<String> strList = new ArrayList<String> ();

ArrayList 的基本原理？
答：代码基于 Java 7：

1 2	private transient Object[] elementData; private int size;

* 内部有一个有一个数组 **`elementData`**，一般会有一些预留的空间。
* 有一个整数 **`size`** 纪录实际的元素个数。
* **各种 `public` 方法内部操作的基本都是这个数**组和这个整数，`elementData` 会随着实际元素个数的增多而重新分配，而 `size` 则始终纪录实际的元素个数。

ArrayList 的 add() 方法的实现原理？
答：

add() 方法的主要代码：

public boolean add(E e) {
	ensureCapacityInternal(size + 1);
	elementData[size++] = e;
	return true;
}

    首先调用 **`ensureCapacityInternal()`** 方法确保数组容量是够的。

* `ensureCapacityInternal()` 方法代码：

    1
2
3
4
5
6
private void ensureCapacityInternal(int minCapacity) {
	if(elementData == EMPTY_ELEMENTDATA) {
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}



    **它首先判断数组是不是空的，如果是空的，则首次至少要分配的大小为 `DEFAULT_CAPACITY`，`DEFAULT_CAPACITY` 的值为 10**。接下来调用 `ensureExplicitCapacity()` 方法。

* `ensureExplicitCapacity()` 方法代码：

    1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	if(minCapacity - elementData.length > 0) {
		grow(minCapacity);
	}
}



    **`modCount` 表示内部的修改次数**，`modCount++` 就是增加修改次数。如果需要的长度大于当前数组的长度，则调用 `grow()` 方法。

* `grow()` 方法主要代码：

    1
2
3
4
5
6
7
8
9
10
private void grow(int minCapacity) {
	int oldCapacity = elementData.length;
	// 右移一位相当于除 2，所以，newCapacity 相当于 oldCapacity 的1.5 倍。
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	// 如果扩展 1.5 倍还是小于 minCapacity，就扩展为 minCapacity。
	if(newCapacity - minCapacity < 0) {
		newCapacity = minCapacity;
	}
	elementData = Arrays.copyOf(elementData, newCapacity);
}

怎样理解 foreach 语法？
答：foreach 语法更简洁，适用于各种容器、更为通用。

foreach 语法背后是怎样实现的？
答：

ArrayList<Integer> intList = new ArrayList<Integer> ();
intList.add(123);
intList.add(456);
intList.add(789);

// ArrayList 实现了 Iterable 接口
for(Integer a : intList) {
	System.out.println(a);
}

// Java 编译器会将 foreach 语法转换为类似如下代码：
Iterator<Integer> it = intList.iterator();
while(it.hasNext()) {
	System.out.println(it.next());
}

Iterable 和 Iterator 的定义分别是？
答：源码基于 Java 7。

// Iterable 表示可迭代
public interface Iterable<T> {
	Iterator<T> iterator();
}

// Iterator 表示迭代器
public interface Iterator<E> {
	boolean hasNext(); // 判断是否还有元素未访问
	E next(); // 返回下一个元素
	void remove(); // 删除最后返回的元素
}

Iterable 和 Iterator 的联系是？
答：
- Iterable 表示对象可以被迭代，它有一个方法 iterator()，返回 Iterator 迭代器对象，实际通过 Iterator 接口的方法进行遍历。
- 如果对象实现了 Iterable 接口，就可以使用 foreach 语法。
- 类可以不实现 Iterable 接口，也可以创建 Iterator 对象。
- Java 8 对 Iterable 添加了默认方法 forEach() 和 spliterator()，对 Iterator 增加了默认方法 forEachRemaining() 和 remove()。

ArrayList 对 Iterator 接口的增强有？
答：

除了 iterator()，ArrayList 还提供了两个返回 Iterator 接口的方法：

1 2	public ListIterator<E> listIterator(); // 返回的迭代器从 0 开始遍历 public ListIterator<E> listIterator(int index); // 返回的迭代器从指定位置 index 开始遍历

ListIterator 扩展了 Iterator 接口，增加了一些方法：向前遍历、添加元素、修改元素、返回索引位置等，添加的方法有：

public interface ListIterator<E> extends Iterator<E> {
	boolean hasPrevious();
	E previous();
	int nextIndex();
	int previousIndex();
	void set(E e);
	void add(E e);	
}

对于一个 ArrayList，从末尾往前遍历，代码怎样实现？
答：

public void reverseTraverse(List<Integer> list) {
	ListIterator<Integer> it = list.listIterator(list.size());
	while(it.hasPrevious) {
		System.out.println(int.previous);
	}
}

关于迭代器，有一种常见的误用是？
答：在迭代的过程中调用容器的删除方法（不是迭代器的删除方法），这是一种常见的误用。

接上题，下面代码是否合法？为什么？

// 删除一个整数 ArrayList 中【所有小于 100】 的整数
public void remove(ArrayList<Integer> list) {
	for(Integer a : list) {
		if(a <= 100) {
			list.remove(a);
		}
	}
}

答：

* 结论：运行时抛出 `ConcurrentModificationException` 并发修改异常。
* 原因：**因为迭代器内部会维护一些索引位置相关的数据（`cursor、lastR**et、expectedModCount`），要求在迭代过程中，容器不能发生结构性变化，否则这些索引位置就失效了。
* 概念：所谓**结构性变化就是添加、插入和删除元素，只是修改元素内容不算结构性变化**。
* 解决方法：**使用迭代器的 `remove()` 方法**。代码如下：

    1
2
3
4
5
6
public static void remove(ArrayList<Integer> list) {
	Iterator<Integer> it = list.iterator();
	while(it.next <= 100) {
		it.remove();
	}
}

迭代器如何知道发生了结构性变化或者迭代器的实现原理是？
答：

ArrayList 中 iterator() 方法的实现，代码为：

public Iterator<E> iterator() {
	return new Itr();
}

``` 

新建了一个 `Itr` 对象，`Itr` 是一个**成员内部类**（可以直接访问外部类的实例变量），实现了 `Iterator` 接口，声明为：`private class Itr implements Iterator<E>`。它有三个成员变量：

int cursor; // 表示下一个要返回的元素位置
int lastRet; // 表示最后一个返回的索引位置
int expectedModCount = modCount; // 表示期望的修改次数，初始化为外部类当前的修改次数

1 2	* `Itr` 的 `hasNext()` 方法代码实现：

public boolean hasNext() {

return cursor != size;

}

1 2	* `Itr` 的 `next()` 方法代码实现：

public E next() {

checkForComodification();
int i = cursor;
if(i >= size) {
    throw new NoSuchElementException();
}
Object[] elementData = ArrayList.this.elementData;
if(i >= elementData.length) {
    throw new ConcurrentModificationException();
}
cursor = i + 1;
return (E) elementData[lastRet = i];

}

1 2	首先调用了 `checkForComodification()` 方法，它的代码为：

final void checkForComodification() {

if(modCount != expectedModCount) {
    throw new ConcurrentModificationException();
}

}

	
	所以，`next()` 方法前面部分主要就是在检查是否发生了结构性变化，如果没有变化，就更新 `cursor` 和 `lastRet` 的值，以保持其语义，然后返回对应的元素。
	
* `Itr` 的 `remove()` 方法代码实现：

public void remove() {

if(lastRet < 0) {
    throw new IllegalStateException();
}
checkForComodification();
try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
    expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificaitonException();
}

}

		
		它调用了 `ArrayList` 的 `remove()` 方法，但同时更新了 `cursor、lastRet、expectedModCount` 的值，所以它可以正确删除。
		
	* **`listIterator()` 的实现使用了另一个内部类 `ListItr`，它继承自 `Itr`，基本思路类似**。
		
13. 下面代码是否合法？为什么？怎样解决？

// 通过迭代器【删除所有】元素
public static void removeAll(ArrayList list) {

Iterator<Integer> it = list.iterator();
while(it.hasNext()) {
    it.remove();
}

}

	
	答：
	
	* 结论：运行时抛出 `IllegalStateException` 异常。
	* 原因：**调用 `remove()` 方法前必须先调用 `next()` 方法**。
	* 解决方法：在 `it.remove();` 之前先调用 `it.next();`。 当然，如果只是要删除所有元素，`ArrayList` 有现成的方法 `clear()`。

14. 为什么要通过迭代器这种方式访问元素呢？直接使用 `size()/get(index)` 语法不也可以吗？或者说，迭代器的好处是什么？
答：
	* 在一些场景下，确实没有什么差别，两者都可以。
	* 不过，`foreach` 的语法更**简洁**一些。更重要的是，迭代器语法更为**通用**，它适用于各种容器类。
	* **迭代器设计模式：是一种关注点分离的思想**，将数据的实际组织方式与数据的迭代遍历相分离，是一种常见的设计模式。
	* 从**性能**的角度考虑，`ArrayList` 的 `size()/get(index)` 语法与迭代器性能是差不多的；但在 `LinkedList`中，迭代器性能就要高很多。
	* 从**封装**的思路上讲，迭代器封装了各种数据组织方法迭代操作，提供了简单和一致的接口。

15. `ArrayList` 实现的主要接口有哪几个？
答：
	* **`Collection`: 表示一个数据集合，数据间没有位置或顺序的概念**。**`Java 8`** 新增了几个默认方法，包括：`removeIf()、stream()、spliterator()` 等。
	* **`List`: 表示有顺序或位置概念的数据集合，它扩展了 `Collection`**。**`Java 8`** 新增了几个默认方法，包括：`sort()、replaceAll()、spliterator()`；**`Java 9`** 新增了多个重载的 `of` 方法，可以根据一个或多个元素生成一个不变的 `List`。
	* **`RandomAccess`: 空接口，没有定义任何代码**。又称为**标记接口，用于声明实现类的一种属性**。这里，**实现了 `RandomAccess` 接口的类表示可以随机访问（类似数组）**。

16. 有没有声明 `RandomAccess` 有什么关系呢？
答：**主要用于一些通用的算法代码中，它可以根据这个声明而选择效率更高的实现**。比如，`Collection` 类中有一个方法 `binarySearch()`，在 `List` 中进行二分查找，它的实现代码就根据 `list` 是否实现了 `RandomAccess` 而采用不同的实现机制，代码如下：

public static int binarySearch(List<? extends Comparable<? super T>> list, T key) {

if(list instanceof RandomAccess || list.size < BINARYSEARCH_THRESHOLD) {
    return Collection.indexedBinarySearch(list, key);
} else {
    return Collection.iteratorBinarySearch(list, key);
}

}

```

ArrayList 中还有哪些常用的方法？
答：构造方法（ArrayList()）、与数组的互相转换（toArray()、Arrays.asList()）、容量大小控制（ensureCapacity()、trimTosize()）等。
ArrayList 的特点是什么？
答：它的特点就是内部采用动态数组实现，这决定了下面几点：
- 可以随机访问，按照索引位置进行访问效率很高，效率是 O(1)，即一步到位。
- 除非数组已排序，否则按照内容查找元素效率比较低，具体是 O(N)，N 为数组长度，即性能与数组长度成正比（如果已经排序，猜测效率应该和二分查找的效率一样高）。
- 添加元素的效率还可以，重新分配和复制数组的开销被平摊了，具体来说，添加 N 个元素的效率为 O(N)。
- 插入和删除元素的效率比较低，因为需要移动元素，具体为 O(N)。
- ArrayList 是线程不安全的，实现线程安全的一种方式是使用 Collection 提供的方法装饰 ArrayList；另外，类 Vector 作为Java 最早实现的容器类之一，也实现了 List 接口，基本原理与 ArrayList 类似，内部使用了 synchronized 实现了线程安全。不需要线程安全的情况下，推荐使用 ArrayList。

泛型（三）：细节和局限性

发表于 2019-01-15 | 分类于面试篇

怎样理解泛型的局限性？
答：
- 泛型的局限性主要与 Java 的实现机制有关。
- Java 中泛型是通过类型擦除来实现的，类型参数在编译时会被替换为 Object 或限定的上界，运行时 Java 虚拟机不知道泛型这回事，这就带来了很多局限性。
下面写法是否合法？为什么？解决方法是？

Pair<int> minmax = new Pair<int> (1, 100);

答：
- 结论：不合法。
- 原因：类型参数在编译时会被替换为 Object，所以 Java 泛型中不能使用基本数据类型。
- 解决方法：使用基本数据类型对应的包装类。
下面写法是否合法？为什么？

Pair<Integer>.class;

答：
- 结论：不合法。
- 原因：这个泛型对象（反射）只有一份，与泛型无关。

下面代码的输出是什么？为什么？

Pair<Integer> p1 = new Pair<Integer> (1, 100);
Pair<String> p2 = new Pair<String> ("hello", "world");
System.out.println(Pair.class == p1.getClass()); // true
System.out.println(Pair.class == p2.getClass()); // true

答：

* 结果：都是 `true`。
* 原因：**一个泛型对象的 `getClass()` 方法的返回值与原始类型对象是相同的**。

下面代码是否合法？为什么？

// 代码1
if(p1 instanceof Pair<Integer>) // 不合法

// 代码2
if(p1 instanceof Pair<?>) // 合法

答：

* 结果：代码 1 不合法；代码 2 合法。
* 原因：**`instanceof` 关键字后面是接口或类名，`instanceof` 是运行时判断，也与泛型无关，但支持通配符**。

下面代码是否合法？为什么？解决方法是？

1
2
3

class Child extends Base Implements Comparable<Child> {
	// 主体代码
}

答：

* 结论：`Java` 编译报错。
* `Comparable` 接口不能被实现两次，且两次实现的类型参数还不同，一次是 `Comparable<Base>`，一次是 `Comparable<Child>`。因为**类型擦除后，实际上只能有一个**。
* 解决方法：只能重写 `Base` 类的实现。

    1
2
3
4
5
6
7
8
9
10
11
12
class Child extends Base {
	@Override
	public int compareTo(Base o) {
		if(!(o instanceof Child)) {
			throw new IllegalArgumentException();
		}
		Child c = (Child) o;
		// 比较代码
		return 0;
	}
	//其他代码
}

下面定义重载方法是否正确？为什么？

1 2	public static void test(DynamicArray<Integer> intArr) public static void test(DynamicArray<String> strArr)

答：

* 结论：错误。
* 原因：**重载方法后，因为类型擦除，它们的声明是一样的**。

下面代码是否合法？为什么？

1
2
3

// T 是类型 参数
T elm = new T();
T[] arr = new T[10];

答：

* 结论：非法。
* 原因：因为如果允许，那么用户会以为创建的就是对应类型的对象，但**由于类型擦除，`Java` 只能创建 `Object` 类型的对象，`Java` 运行时根本不知道 T 是什么，也就无法创建 T 类型的对象**。容易引起误解，所以 `Java` 干脆禁止这么做。即：**`Java` 不支持通过类型参数创建对象**。

接上题，如果确实希望根据类型创建对象呢？举个栗子？
答：

需要设计 API 接受类型对象，即 Class 对象，并使用 Java 中的反射机制。

如果类型有默认构造方法，可以调用 Class 的 newInstance() 方法构建对象。

public static <T> T create(Class<T> type) {
	try {
		return type.newInstance();
	} catch (Exception e) {
		return null;
	}
}

Date date = create(Date.class);
StringBuilder sb = create(StringBuilder.class);

下面代码是否合法？为什么？

public class Singleton<T> {
	private static T instance;
	public synchronized static T getInstance() {
		if(instance == null) {
			// 创建实例
		}
		return instance;
	}
}

答：

* 结论：非法。
* 原因：如果合法，那么对于每种实例化类型，都需要有一个对应的静态变量和方法。但由于类型擦除，`Singleton` 类型只有一份，静态变量和方法都是类型的属性，且与类型参数无关。所以，**对于泛型类声明的类型参数，可以在实例变量和方法中使用，但在静态变量和静态方法中是不能使用的**。
* 注意：**对于静态方法，它可以是泛型的，可以声明自己的类型参数，这个参数与泛型类的类型参数是没有关系的**。

Java 泛型支持多个上界吗？举个栗子？
答：
- 支持，多个上界之间以 & 分隔。
- 举例：T extends Base & Comparable & Serializable;
- Base 为上界类，Comparable 和 Serializable 为上界接口。
- 如果有上界类，类应该放在第一个，类型擦除时，会用第一个上界替换。

下面代码是否合法？为什么？

1
2
3

Pair<Object, Integer> [] options = new Pair<Object, Integer> [] {
	new Pair("1 元", 7), new Pair("2 元", 2), new Pair("10 元", 1)
}

答：

* 结论：`Java` 编译报错。
* 原因：**`Java` 不支持创建泛型数组**。

下面代码是否合法？为什么？

1
2
3

Integer[] ints = new Integer[10];
Number[] numbers = ints;
Object[] objs = ints;

答：

* 结论：合法。
* 原因：**数组是 `Java` 直接支持的概念，它知道数组元素的实际类型**，知道 `Object` 和 `Number` 都是 `Integer` 的父类型，所以后面两种赋值都是允许的。

下面代码是否正确？为什么？

1
2
3

Integer[] ints = new Integer[10];
Object[] objs = ints;
objs[0] = "hello";

答：

* 结论：编译没有问题，运行时抛出 `ArrayStoreException` 异常。
* 原因：因为 `Java` 知道实际的类型是 `Integer`，所以写入 `String` 时会抛出异常。

Java 为什么不支持创建泛型数组？
答：因为如果 Java 支持创建泛型数组，那么可能会出现类型不匹配的数组赋值的错误操作，它既不会引起编译错误，也不会立即出发运行异常，却相当于埋下一颗定时炸弹💣，不定什么时候爆发。为避免这种情况，Java 干脆就禁止创建泛型数组。

现实中需要能够存放泛型对象的容器，怎么办？
答：

使用原始数组。比如：

1
2
3

Pair[] options = new Pair[] {
	new Pair<String, Integer> ("1 元", 7), new Pair<String, Integer> ("2 元", 2), new Pair<String, Integer> ("10 元", 1)
};

* **更好的选择是，使用泛型容器**。比如：

    1
2
3
4
DynamicArray<Pair<String, Integer>> options = new DynamicArray<> ();
options.add(new Pair<String, Integer> ("1 元", 7));
options.add(new Pair<String, Integer> ("2 元", 2));
options.add(new Pair<String, Integer> ("10 元", 1));

有时，我们希望转换泛型容器为一个数组。比如，对于 DynamicArray，我们可能希望它有这么一个方法：public E[] toArray()，而希望可以这么用：
1
2
3
4
DynamicArray<Integer> ints = new DynamicArray<Integer> ();
ints.add(100);
ints.add(34);
Integer[] arr = ints.toArray();

即，**先使用动态容器收集一些数据，然后转换为一个固定数组，对于这个常见的合理的需求，该怎样实现这个 `toArray()` 方法**？

答：**可以利用 `Java` 中的运行时类型信息和反射机制。`Java` 必须在运行时知道要转换成的数组类型**，类型可以作为参数传递给 `toArray()` 方法，比如：

1
2
3
4
5
6
7
public E[] toArray(Class<E> type) {
	Object copy = Array.newInstance(type, size);
	System.arraycopy(elemendData, 0, copy, size);
	return (E[]) copy;
}

Integer[] arr = ints.toArray(Integer.class);

泛型和数组的关系？
答：一般并不需要特别记忆，根据提示进行正确处理即可。
- Java 不支持创建泛型数组。
- 如果要存放泛型对象，可以使用原始类型的数组，或者使用泛型容器。
- 泛型容器内部使用 Object 数组，如果要转换泛型容器为对应类型的数组，需要使用反射。

泛型（二）：解析通配符

发表于 2019-01-14 | 分类于面试篇

通配符有哪几类？
答：? 表示通配符，Java 中通配符分三类：
- <?>: 无限定通配符。
- <? extends T>: 有限定通配符，匹配 T 或 T 的某个子类型。
- <? super T>: 超类型通配符，匹配 T 的某个父类型。
<T extends E> 和 <? extends E> 到底有什么关系？
答：
- <T extends E> 用于定义类型参数，它声明了一个类型参数 T，可放在泛型类定义中类名后面、泛型方法返回值前面。
- <? extends E> 用于实例化类型参数，它用于实例化泛型变量中的类型参数，只是这个具体类型是未知的，只知道它是 E 或 E 的某个子类型。

请用通配符形式重写下面方法声明代码？

public <T extends E> void addAll(DynamicArray<T> c) {
	for(int i = 0; i < c.size; i++) {
		add(c.get(i));
	}
}

答：

1
2
3
4
5
public void addAll(DynamicArray<? extends E> c) {
	for(int i = 0; i < c.size; i++) {
		add(c.get(i));
	}
}

请用通配符形式重写下面方法声明代码？

public static <T> int indexOf(DynamicArray<T> arr, Object obj) {
	for(int i = 0; i < arr.size(); i++) {
		if(arr.get(i).equals(obj)) {
			return i;
		}
	}
	return -1;
}

答：

1
2
3
4
5
6
7
8
public static int indexOf(DynamicArray<?> arr, Object obj) {
	for(int i = 0; i < arr.size(); i++) {
		if(arr.get(i).equals(obj)) {
			return i;
		}
	}
	return -1;
}

下面代码是否正确？

DynamicArray<Integer> ints = new DynamicArray<> ();
DynamicArray<? extends Number> numbers = ints;
Integer a = 200;
numbers.add(a); // Java 编译报错
numbers.add((Number) a); // Java 编译报错
numbers.add((Object) a); // Java 编译报错

答：

* 三个 `add()` 方法都是非法的，Java 编译器会报错。
* 上面通配符有一个重要的限制：只能读，不能写。**如果允许写入， `Java` 就无法确保类型安全性，这显然违背了 `Java` 关于类型安全的承诺，所以 `Java` 干脆禁止**。

下面代码是否正确？怎样解决？

public static void swap(DynamicArray<?> arr, int i, int j) {
	Object tmp = arr.get(i);
	arr.set(i, arr.get(j));
	arr.set(j, tmp);
}

答：

* `Java` 编译报错。
* 解决方法：借助带类型参数的泛型方法（**`Java` 容器类中就有类似这样的用法，公共的 `API` 是通配符形式，形式更简单，但内部调用带类型参数的方法**）。

    1
2
3
4
5
6
7
8
9
private static <T> void swapInternal(DynamicArray<T> arr, int i, int j) {
	T tmp = arr.get(i);
	arr.set(i, arr.get(j));
	arr.set(j, tmp);
}

public static void swap(DynamicArray<?> arr, int i, int j) {
	swapInternal(arr, i, j);
}

使用通配符形式简化下面方法声明的代码？

public static <D, S extends D> void copy(DynamicArray<D> dest, DynamicArray<S> src) {
	for(int i = 0; i < src.size(); i++) {
		dest.add(src.get(i));
	}
}

答：

1
2
3
4
5
public static <D> void copy(DynamicArray<D> dest, DynamicArray<? extends D> src) {
	for(int i = 0; i < src.size(); i++) {
		dest.add(src.get(i));
	}
}

下面代码能使用通配符优化吗？为什么？

public static <T extends Comparable<T>> T max(DynamicArray<T> arr) {
	T max = arr.get(0);
	for(int i = 1; i < arr.size(); i++) {
		if(arr.get(i).compareTo(max) > 0) {
			max = arr.get(i);
		}
	}
	return max;
}

答：不能。如果**返回值依赖于类型参数，则不能用通配符**。

泛型方法到底应该用通配符的形式还是加类型参数？两者到底有什么关系？
答：
- 通配符形式都可以用类型参数的形式来替代，通配符能做的，类型参数都能做。
- 通配符形式可以减少类型参数，形式上往往更为简单，可读性也更好。所以，能用通配符的就用通配符。
- 如果类型参数之间有依赖关系，或者返回值依赖类型参数，或者需要写操作，则只能用类型参数。
- 通配符形式和类型参数往往配合使用，比如，上面的 copy 方法，定义必要的类型参数，使用通配符表达依赖，并接受更广泛的数据类型。

下面代码是否正确？怎样解决？

// 在 DynamicArray 中添加一个方法
pubilc void copyTo(DynamicArray<E> dest) {
	for(int i = 0; i < size; i++) {
		dest.add(get(i));
	}
}

DynamicArray<Integer> ints = new DynamicArray<Integer> ();
ints.add(100);
ints.add(34);
DynamicArray<Number> numbers = new DynamicArray(Number);
ints.copyTo(numbers);

答：

* `Java` 编译报错。因为期望的类型是 `DynamicArray<Integer>`，不是 `DynamicArray<Number>`。
* 解决方法：使用超类型通配符。

    1
2
3
4
5
public void copyTo(DynamicArray<? super E> dest) {
	for(int i = 0; i < size; i++) {
		dest.add(get(i));
	}
}

下面代码是否正确？怎样解决？

class Base implements Comparable<Base> {

	private int sortOrder;
	
	public Base(int sortOrder) {
		this.sortOrder = sortOrder;
	}
	
	@Override
	public int compareTo(Base o) {
		if(sortOder < o.sortOrder) {
			return -1;
		} else if(sortOrder > o.sortOrder) {
			return 1;
		} else {
			return 0;
		}
	}
}

class Child extends Base {
	public Child(int sortOrder) {
		super(sortOrder);
	}
}

DynamicArray<Child> childs = new DynamicArray<Child> ();
childs.add(new Child(20));
childs.add(new Child(80));
Child maxChild = max(childs);

答：

* `Java` 编译报错，类型不匹配。
* 原因是，我们可能会以为 `Java` 会将 `max 方法` 的类型参数 T 推断为 `Child` 类型，但类型 T 的要求是 `extends Comparable<T>`，而 `Child` 并没有实现 `Comparable<Child>`，它实现的是 `Comparable<Base>`。
* 解决方法：使用超类型通配符，修改 `max 方法` 声明，即：`public static <T extends Comparable<? super T>> T max(DynamicArray<T> arr)`。
* 这么修改一下就可以了，这种写法比较抽象，将 `T` 替换为 `Child`，即：`Child extends Comparable<? super Child>`，因为 `<? super Child>` 可以匹配 `Base`，所以整体就是匹配的。

下面这种写法是否正确？

1	public <T super E> void copyTo(DynamicArray<T> dest) {} // 非法

答：

* `Java` 不支持这种语法。
* **类型参数限定只有 `extends` 形式，没有 `super` 形式**。
* 对于有限定的通配符形式 `<? extends E>`，可以用类型参数替代。
* 对于**超类型通配符，不能用参数类型替代**。

三种通配符的比较？
答：
- 它们的目的都是为了使方法接口更为灵活，可以接受更为广泛的类型。
- <? super E> 用于灵活写入或比较，使得对象可以写入父类型的容器，使得父类型的比较方法可以应用于子类对象，它不能被类型参数形式替代。
- <?> 和 <? extends E> 用于灵活读取，使得方法可以读取 E 或 E 的任意子类型的容器对象，它们可以用类型参数的形式替代，但通配符形式更为简洁。

泛型（一）：基本概念和原理

发表于 2019-01-13 | 分类于面试篇

怎样理解泛型？
答：
- 字面意思就是广泛的类型。
- 类、接口和方法的代码可以应用于非常广泛的类型，代码与它们能够操作的数据类型不再绑定在一起，同一套代码可以用于多种数据类型。
- 好处是不仅可以复用代码，降低耦合，而且可以提高代码的可读性和安全性。
怎样理解泛型类？
答：
- 类名后面多了一个 < T >。
- T 表示类型参数，泛型就是类型参数化，处理的数据类型不是固定的，而是可以作为参数传入。
- 类型参数可以有多个，多个类型之间以逗号分隔。比如，Pair<String, Integer> pair = new Pair<String, Integer>("老马", 100);
- <String, Integer> 既出现在了声明变量时，也出现在了 new 后面，比较繁琐，从 Java 7 开始，支持省略后面的类型参数。比如，Pair<String, Integer> pair = new Pair<>("老马", 100);。
泛型的基本原理？
答：
- Java 有 Java 编译器 和 Java 虚拟机，编译器将 Java 源代码转换为 .class 文件，虚拟机加载并运行 .class 文件。
- 对于泛型类，Java 编译器会将泛型代码转换为普通的非泛型代码，将类型 T 擦除，替换为 Object，插入必要的强制类型转换。Java 虚拟机在实际运行的时候，它是不知道泛型这回事的，只知道普通的类及代码。
Java 为什么要用类型擦除的方式设计泛型呢？
答：泛型是 Java 5 以后才支持的，这么设计是为了兼容性而不得已的一个选择。
泛型的好处是什么？
答：
- 更好的安全性。语言和程序设计的一个重要目标是将 bug 尽量消灭在摇篮里，能消灭在写代码的时候，就不必等到代码写完程序运行的时候。只使用 Object，代码写错的时候，开发环境和编译器不能帮我们发现问题、不会有错误提示。使用泛型，开发环境和编译器就是提示可能的类型错误，这称之为类型安全，为程序多设置一道安全防护网。
- 更好的可读性。使用泛型，还可以省去繁琐的重复的强制类型转换代码，再加上明确的类型信息，代码可读性也更好。
怎样理解容器类？
答：
- 泛型类最常见的用途是作为容器类。
- 容器类：容纳并管理多项数据的类。
- Java 泛型的引入主要也是为了更好地支持 Java 容器。

【笔试题】实现一个类似 ArrayList 的动态数组？
答：

public class DynamicArray<E> {

	private static final int DEFAULT_CAPACITY = 10;
	private int size;
	private Object[] elementData;
	
	public DynamicArray() {
		this.elementData = new Object[DEFAULT_CAPACITY];
	}
	
	private void ensureCapacity(int minCapacity) {
		int oldCapacity = elementData.length;
		if(oldCapacity >= minCapacity) {
			return;
		}
		int newCapacity = oldCapacity * 2;
		if(newCapacity < minCapacity) {
			newCapacity = minCapacity;
		}
		elementData = Arrays.copyOf(elementData, newCapacity);
	}
	
	public void add(E e) {
		ensureCapacity(size + 1);
		elementData[size++] = e;
	}
	
	public E get(int index) {
		return (E) elementData[index];
	}
	
	pubilc int size() {
		return size;
	}
	
	public E set(int index, E element) {
		E oldValue = get(index);
		elementData[index] = element;
		return oldValue;
	}

}

DynamicArray<Double> arr = new DynamicArray<Double>();
Random rnd = new Random();
int size = 1 + rnd.nextInt(100);
for(int i = 0; i < size; i++) {
	arr.add(Math.random());
}
Double d = arr.get(rnd.nextInt(size));

* 具体的类型还可以是一个泛型类，比如：`DynamicArray<Pair<Integer, String>> arr = new DynamicArray<>();`

怎样理解泛型方法？
答：
- 类型参数为 T，放在返回值前面。
- 类型参数可以有多个，以逗号分隔。比如：
  1
  2
  3
  4
  public static <U, V> Pair<U, V> makePair(U first, V second) {
  Pair<U, V> pair = new Pair<> (first, second);
  return pair;
  }

* **一个方法是不是泛型的，与它所在的类是不是泛型没有关系**。

怎样理解泛型接口？
答：
- 接口也可以是泛型的，实现接口时，应该指定具体的类型。
- Comparable 接口 和 Comparator 接口 都是泛型的。代码如下：
  1
  2
  3
  4
  5
  6
  7
  8
  public interface Comparable<T> {
  public int compareTo(T o);
  }
  
  public interface Comparator<T> {
  int compare(T o1, T o2);
  boolean equals(Object obj);
  }

怎样理解类型参数的限定？
答：
- 类型参数的上届限定通过 extends 关键字表示。
- Java 支持限定这个参数的一个上界，这个上界可以是某个具体的类或者某个具体的接口，也可以是其他的类型参数。
- 上界为某个具体的类：指定边界后，类型擦除时就不会转换为 Object 了，而是会转换为它的边界类型。
- 上界为某个接口：public static <T extends Comparable<T>> T max(T[] arr) {}。
- 上界为其他类型参数：
  1
  2
  3
  4
  5
  public <T extends E> void addAll(DynamicArray<T> c) {
  for(int i = 0; i < c.size; i++) {
  add(c.get(i));
  }
  }

需要注意的是，**虽然 `Integer` 是 `Number` 的子类，但 `DynamicArray<Integer>` 并不是 `DynamicArray<Number>` 的子类**，所以 `DynamicArray<Integer>` 的对象也就不能赋值给 `DynamicArray<Number>`。

常用基础类（六）：随机

发表于 2019-01-12 | 分类于面试篇

Java 对随机的支持？
答：
- Java 对随机的最基本的支持是 Math 类中的静态方法 random()。
- random() 方法生成一个 0 ~ 1 的随机数，类型为 double，包括 0 但不包括 1。
- 还有一些基础类，比如 UUID、Math、Objects。UUID 用于随机生成需要确保唯一性的标识符；Math 用于进行数学运算；Objects 包含一些操作对象、检查条件的方法。

Math.random() 方法是怎样实现的？
答：

源码基于 Java 7：

private static Random randomNumberGenerator;

private static synchronized Random initRNG() {
	Random rnd = randomNumberGenerator;
	return (rnd == null) ? (randomNumberGenerator = new Random()) : rnd;
}

public static double random() {
	Random rnd = randomNumberGenerator;
	if (rnd == null) rnd = initRNG();
	return rnd.nextDouble();
}

* `random()` 方法内部使用了一个 `Random` 类型的静态变量 `randomNumberGenerator`，**调用 `random()` 就是调用该变量的 `nextDouble()` 方法**，这个 `Random` 变量只有在第一次使用的时候才创建。

怎样理解 Random 类？
答：
- Random 类提供了更为丰富的随机方法，它的方法不是静态方法。
- nextInt() 方法产生一个随机的 int，可能为正数，也可能为负数；nextInt(100) 产生一个随机 int，范围是 0 ~ 100，包括 0 不包括 100。
- 除了默认构造方法，Random 类还有一个构造方法，可以接受一个 long 类型的种子参数：public Random(long seed)。
- Random 类是线程安全的，即多个线程可以同时使用一个 Random 实例对象。如果并发性很高，会产生竞争，这时可以考虑使用类 ThreadLocalRandom。
- Java 类库中还有一个随机类 SecureRandom，可以产生安全性更高、随机性更强的随机数，用于安全加密等领域。
为什么要指定种子呢？指定种子还是真正的随机吗？
答：
- 指定种子是为了实现可重复的随机。
- 比如用于模拟测试程序中，模拟要求随机，但测试要求可重复。
- 在北京购车摇号程序中，种子也是指定的。
随机的基本原理是怎样的？
答：
- Random 产生的随机数并不是真正的随机数，相反，它产生的随机数一般称为伪随机数。
- 真正的随机数比较难以产生，计算机程序中的随机数一般都是伪随机数。
- 伪随机数都是基于一个种子数的，然后每需要一个随机数，都是对当前种子进行一些数学运算得到一个数，基于这个数得到需要的随机数和新的种子。
伪随机数是什么意思？
答：
- 数学运算是固定的，所以种子确定后，产生的随机数序列就是确定的，确定的数字序列当然不是真正的随机数。但种子不同，序列就不同，每个序列中数字的分布也都是比较随机和均匀的，所以称之为伪随机数。
- 说白了，伪随机数并不是真正意义上的完全的随机数，但具有一定的随机特征，所以叫伪随机数。类似于日军和日伪军的概念。
Java 中有真正的随机数吗？
答：
- 有。Random 的默认构造方法中没有传递种子，它会自动生成一个种子，这个自动生成的种子数就是一个真正的随机数。
- Java 7，看 Random 类默认构造方法源码可知，这个真正的种子数是 seedUniquifier() 与 System.nanoTime() 按位异或的结果。具体可查看源码。
有了种子数之后，其他数是怎么生成的呢？
答：
- nextInt() 方法、nextLong() 方法、nextFloat() 方法、nextBoolean() 方法都调用了 next(int bits) 方法，生成指定位数的随机数。
- 查看源码，简单说，就是使用了如下公式：nextseed = (oldseed * mulitplier + addend) & mask;
- 算法就是：旧的种子（oldseed）乘以一个数（multiplier），加上一个数 addend，然后取低 48 位作为结果（mask）相与。
- 这个算法的名称叫线性同余随机数生成器（linear congruential pseudorandom number generator），描述在高德纳老爷子的《计算机程序设计艺术》一书中。随机的理论是一个比较复杂的话题。
- 随机的基本原理：随机数基于一个种子数，种子数固定，随机数序列就固定，Random 的默认构造方法中，种子是一个真正的随机数。

【笔试题】生成一个 6 位数字的随机密码？
答：

public static String randomPassword() {
	char[] chars = new char[6];
	Random rnd = new Random();
	for(int i = 0; i < 6; i++) {
		chars[i] = (char) ('0' + rnd.nextInt(10));
	}
	return new String(chars);
}

【笔试题】生成一个简单 8 位的随机密码？（要求：密码由大写字母、小写字母、数字和特殊符号组成）
答：

private static final String SPECIAL_CHARS = "!@#$%^&*_+=-/"; // 约定的特殊符号

private static char nextChar(Random rnd) {
	switch(rnd.nextInt(4)) {
		case 0:
			return (char) ('a' + rnd.nextInt(26)); // 小写字母
		case 1:
			return (char) ('A' + rnd.nextInt(26)); // 大写字母
		case 2:
			return (char) ('0' + rnd.nextInt(10)); // 数字
		default:
			return SPECIAL_CHARS.charAt(rnd.nextInt(SPECIAL_CHARS.length())); // 特殊符号
	}
}

public static String randomPassword() {
	char[] chars = new char[8];
	Random rnd = new Random();
	for(int i = 0; i < 8; i++) {
		chars[i] = nextChar(rnd);
	}
	return new String(chars);
}

【笔试题】生成一个复杂 8 位的随机密码？（要求：至少包含一个大写字母、一个小写字母、一个特殊符号、一个数字）
答：// 感觉有 bug

private static int nextIndex(char[] chars, Random rnd) {
	int index = rnd.nextInt(chars.length);
	while(chars[index] != 0) {
		index = rnd.nextInt(chars.length);
	}
	return index;
}

private static char nextSpecialChar(Random rnd) {
	return SPECIAL_CHARS.charAt(rnd.nextInt(SPECIAL_CHARS.length()));
}

private static char nextUpperLetter(Random rnd) {
	return (char) ('A' + rnd.nextInt(26));
}

private static char nextLowerLetter(Random rnd) {
	return (char) ('a' + rnd.nextInt(26));
}

private static char nextNumLetter(Random rnd) {
	return (char) ('0' + rnd.nextInt(10));
}

public static String randomPassword() {
	char[] chars = new char[8];
	Random rnd = new Random();
	chars[nextIndex(chars, rnd)] = nextSpecialChar(rnd);
	chars[nextIndex(chars, rnd)] = nextUpperLetter(rnd);
	chars[nextIndex(chars, rnd)] = nextLowerLetter(rnd);
	chars[nextIndex(chars, rnd)] = nextNumLetter(rnd);
	for(int i = 0; i < 8; i++) {
		if(chars[i] == 0) {
			chars[i] = nextChar(rnd);
		}
	}
	return new String(chars);
}

【笔试题】随机重排（洗牌）？
答：

private static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

public static void shuffle(int[] arr) {
	Random rnd = new Random();
	for(int i = arr.length; i > 1; i--) {
		swap(arr, i - 1, rnd.nextInt(i));
	}
}

int [] arr = new int[13]; // 前天晚上看的《狗十三》电影很好看
for(int i = 0; i < arr.length; i++) {
	arr[i] = i;
}
shuffle(arr);
System.out.println(Arrays.toString(arr));

【笔试题】带权重的随机选择（累计概率分布、nextDouble()、二分查找）？
答：

// 表示选项和权重的类 Pair
class Pair {
	Object item;
	int weight;
	public Pair(Object item, int weight) {
		this.item = item;
		this.weight = weight;
	}
	public Object getItem() {
		return item;
	}
	public int getWeight() {
		return weight;
	}
}

// 带权重的选择 WeightRandom
public class WeightRandom {
	private Pair[] options;
	private double[] cumulativeProbabilities; // double 类型的累计概率数组
	private Random rnd;
	public WeightRandom(Pair[] options) {
		this.options = options;
		this.rnd = new Random();
		prepare();
	}
	private void  prepare() {
		int weight = 0;
		for(Pair pair : options) {
			weights += pair.getWeight();
		}
		cumulativeProbabilities = new double[options.length];
		int sum = 0;
		for(int i = 0; i < options.length; i++) {
			sum += options[i].getWeight();
			cumulativeProbabhilities[i] = sum / (double) weights;
		}
	}
	public Object nextItem() {
		double randomValue = rnd.nextDouble(); // nextDouble()
		int index = Arrays.binarySearch(cumulativeProbabilities, randomValue); // 二分查找
		if(index < 0) {
			index = -index - 1;
		}
		return options[index].getItem();
	}
}

Pair[] options = new Pair[] {new Pair("1 元", 7), new Pair("2 元", 2), new Pair("10 元", 1);};
WeightRandom rnd = new WeightRandom(options);
for(int i = 0; i < 10; i++) {
	System.out.print(rnd.nextItem() + " ");
}

【笔试题】抢红包算法？
答：

public class RandomRedPacket {
	private int leftMoney;
	private int leftNum;
	private Random rnd;
	public RandomRedPacket(int total, int num) {
		this. leftMoney = total;
		this.leftNum = num;
		this.rnd = new Random();
	}
	public synchronized int nextMoney() {
		if(this.leftNum <= 0) {
			throw new IllegalStateException("红包抢光了");
		}
		if(this.leftNum == 1) {
			return this.leftMoney;
		}
		double max  = this.leftMoney / this.leftNum * 2d; // 设定随机最大值为平均值的两倍
		int money = (int) (rnd.nextDouble() * max);
		money = Math.max(1, money);
		this.leftMoney -= money;
		this.leftNum --;
		return money;
	}
}

RandomRedPackey redPackey = new RandomRedPacket(1000, 10);
for(int i = 0; i < 10; i++) {
	System.out.println(redPacket.nextMoney() + "   ");
}

* 大概思路：维护一个剩余总金额和总数量，分配时，如果数量等于 1，直接返回总金额；如果大于 1，则计算平均值，并设定随机最大值为平均值的两倍，然后取一个随机值，如果随机值小于 0.01，则为 0.01，这个随机值就是下一个的红包金额。

北京购车摇号算法的大概思路是？
答：
1）每期摇号前，将每个符合摇号资格的人，分配一个从 0 到总数的编号，这个编号是公开的。
2）摇号第一步是生成一个随机种子数，这个随机种子数在摇号当天通过一定流程生成，整个过程由公证员公证，就是生成一个真正的随机数。
3）种子数生成后，然后就是循环调用类似 Random.nextInt(int n) 方法，生成中签的编号。
- 编号是事先确定的，种子数是当场公证随机生成的，是公开的，随机算法是公开透明的，任何人都可以根据公开的种子数和编号验证中签的编号。

常用基础类（五）：剖析日期和时间

发表于 2019-01-11 | 分类于面试篇

怎样理解时区？
答：
- 全球一共有 24 个时区，英国格林尼治是 0 时区，北京是东八区。
- 0 时区的时间也称为 GMT + 0 时间，GMT 是格林尼治标准时间，北京的时间就是 GMT + 8:00。
怎样理解时刻和纪元时？
答：
- 所有计算机系统内部都用一个整数表示时刻，这个整数是距离格林尼治标准时间 1970 年 1 月 1 日 0 时 0 分 0 秒的毫秒数。
- 之所以用这个时间，更多的是历史原因。
- 格林尼治标准时间 1970 年 1 月 1 日 0 时 0 分 0 秒也被称为Epoch Time（纪元时）。
- 对于 1970 年以前的时间，使用负数表示。
怎样理解年历？
答：
- 中国有公历和农历之分。
- 公历和农历都是年历，不同的年历，一年有多少月，每月有多少天，甚至一天有多少小时，这些可能都是不一样的。
- 公历有闰年，闰年 2 月是 29 天，而其他年份则是 28 天。其他月份，有的是 30 天，有的是 31 天。
- 农历有闰月，比如闰 7 月，一年就会有两个 7 月，一共 13 个月。
- Java API 的设计思想是支持国际化的，支持多种年历，但没有直接支持中国的农历。
- 时刻是一个绝对时间，对时刻的解读则是相对的，与年历和时区相关。
Java API 中关于日期和时间的主要的类有哪些？
答：日期和时间是一个比较复杂的概念，Java 8 之前的设计有一些不足，业界有一个广泛使用的第三方类库 Joda-Time，Java 8 受 Joda-Time 影响，重新设计了日期和时间 API，新增了一个包 java.time。虽然 Java 8 之前的 API 有一些不足，但依然是被大量使用的。关于 Java 8 的 API，它使用了 Lambda 表达式。
- Date: 表示时刻，即绝对时间，与年月日无关。
- Calendar: 表示年历，是一个抽象类，其中表示公历的子类是 GregorianCalendar。
- DateFormat: 表示格式化，作用是将日期和时间与字符串进行互相转换，也是一个抽象类，其中最常用的子类是 SimpleDateFormat。
- TimeZone: 表示时区，也是一个抽象类。
- Locale: 表示国家（或地区）和语言。
怎样理解 Date？
答：
- System.currentTimeMillis() 返回当前时刻距离纪元时的毫秒数。
- Date 中的大部分方法都已经过时了。

怎样获取当前的默认时区？
答：

1 2	TimeZone tz = TimeZone.getDefault(); System.out.println(tz.getID());

怎样获取任意给定时区的实例？
答：

1 2	TimeZone tz = TimeZone.getTimeZone("US/Eastern"); // 获取美国东部时区 TimeZone tz = TimeZone.getTimeZone("GMT+08:00"); // 获取 GMT 形式的北京时区

怎样理解 Locale？
答：
- Locale 主要有国家（或地区）和语言两个参数，每个参数都有一个代码。
- CN: 中国内地；TW: 中国台湾地区；US: 美国；zh: 中文语言；en: 英文语言。

怎样获取计算机默认语言？
答：

1 2	Locale locale = Locale.getDefault(); System.out.println(locale.toString());

怎样理解 Calendar?
答：
- getInstance() 方法会根据 TimeZone 和 Locale 创建对应的 Calendar 子类对象，在中文系统中，子类一般是表示公历的 GregorianCalendar。
- 这种隐藏对象创建细节的方式，是计算机程序中一种常见的设计模式，叫工厂方法。
- Calendar 做了一项非常繁琐的工作，根据 TimeZone 和 Locale，在绝对时间毫秒数和日历字段之间自动进行转换，且对不同日历字段的修改进行自动同步更新。

怎样理解 SimpleDateFormat?
答：

SimpleDateFormat 是 DateFormat 的子类。相比 DateFormat 它的一个主要不同是，它可以接受一个自定义的模式（pattern）作为参数，这个模式规定了 Date 的字符串形式。

例子：

Calendar calendar = Calendar.getInstance();
calendar.set(2016, 07, 15, 14, 15, 20); // 2016-08-15 14:15:20
SimpleDateFormat sdf = new SimpleDateFormat("yyyy年MM月dd日 E HH时mm分ss秒"); 
// E 表示星期几；HH 表示 24 小时制的小时数，用两位数表示；hh 表示 12 小时制的小时数；a 表示是上午还是下午；SSS 表示三位的毫秒数
System.out.println(sdf.format(calendar.getTime());

输出：
2016年08月15日，星期一，14时15分20秒

怎样理解 Java 8 之前的日期与时间相关 API 的局限性？
答：
- Date 中的过时方法。Date 中的方法参数与常识不符合，过时方法标记容易被忽略，产生误用。比如，Date 构造方法中的 year 表示的是与 1900 年的差，month 是从 0 开始的。
- Calendar 操作比较繁琐。一方面，一些简单的操作都需要多次方法调用，很臃肿；另一方面，Calendar 难以进行比较复杂的日期操作，比如，计算两个日期之间有多少个月；根据生日计算年龄；计算下个月的第一个周一等。
- DateFormat 的线程安全性。DateFormat/SimpleDateFormat 是线程不安全的，即多个线程同时使用一个 DateFormat 实例的时候会有问题，因为 DateFormat 内部使用了一个 Calendar 实例对象，多线程同时调用的时候，这个 Calendar 实例的状态可能就会紊乱。
怎样解决 DateFormat/SimpleDateFormat 的线程安全问题？
答：
- 每次使用 DateFormat/SimpleDateFormat 都新建一个对象（简单粗暴）。
- 使用线程同步（技术）。
- 使用 ThreadLocal（技术）。
- 使用 Joda-Time 或 Java 8 的 API，它们是线程安全的（第三方）。

常用基础类（四）：剖析 Arrays

发表于 2019-01-11 | 分类于面试篇

Arrays 类是干嘛的？
答：
- Arrays 类包含一些对数组操作的静态方法。
- Java 8 和 Java 9 对 Arrays 类又增加了一些方法，比如将数组转换为流，并行排序、数组比较等。
怎样理解 Arrays 的 toString() 方法？
答：Arrays 的 toString() 方法可以方便地输出一个数组的字符串形式，以便查看。
怎样理解 Arrays 的 sort() 方法？
答：
- 对每种基本类型的数组，Arrays 都有 sort() 方法（boolean 除外），默认升序排列。
- 除了基本类型，sort() 方法还可以直接接受对象类型，但对象需要实现 Comparable 接口。
- 大写字母的 ASCII 码比小写字母都小。
Comparator 是干嘛的？
答：
- Comparator 的名字叫比较器，实际上就是一个接口。
- Java 7 中 Comparator 的定义是：
  1
  2
  3
  4
  public interface Comparator<T> {
  int compare(T o1, T o2);
  boolean equals(Object obj);
  }
- 最主要的是 compare() 这个方法，它比较两个对象，返回一个表示比较结果的值。-1 表示 o1 小于 o2；0 表示 o1 等于 o2；1 表示 o1 大于 o2。
- Java 8 中 Comparator 增加了多个静态方法和默认方法。
怎样理解策略模式这种设计模式？
答：
- 传递比较器 Comparator 给 sort() 方法，体现了程序设计中一种很重要的思维方式：将不变和变化相分离。
- 排序的基本步骤和算法是不变的，但按什么排序是变化的，sort() 方法将不变的算法设计为主体逻辑，而将变化的排序方式设计为参数，允许调用者动态指定，这种设计模式就是策略模式。不同的排序方式就是不同的策略。
怎样理解 Arrays 的 binarySearch() 方法？
答：
- 二分查找效率很高。
- 二分查找既可以针对基本类型数组，也可以针对对象数组。
- 如果能找到，那么 binarySearch() 返回找到的元素索引；如果没有找到，返回一个负数，这个负数等于 -（插入点 + 1）。插入点表示，如果在这个位置插入没找到的元素，则可以保持原数组有序。
- binarySearch() 针对的必须是已排序数组，如果指定了 Comparator，需要和排序时指定的 Comparator 保持一致。
- 如果数组中有多个匹配的元素，则返回哪一个是不确定的。
怎样理解多维数组？
答：
- 二维数组类似于一个矩阵或者一个表格。arr[i][j] 表示第 i 行中的第 j 个元素。
- 数组还可以是三维、四维等，一般很少用到，有几维就有几个[]。
- 在创建多维数组时，除了第一维的长度需要指定外，其他维的长度不需要指定，甚至第一维中每个元素的第二维的长度可以不一样。
多维数组到底是什么呢？
答：
- 可以认为，多维数组只是一个假象，只有一维数组，只是数组中的每个元素还可以是一个数组。
- 类似于高中时学过的立体几何。

【笔试题】请写出 Arrays 的二分查找 binarySearch() 代码实现？
答：

private static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c) {

	int low = fromIndex;
	int high = toIndex - 1;
	
	while(low <= high) {
		int mid = (low + high) >>> 1;
		T midVal = a[mid];
		int cmp = c.compare(midVal, key);
		if(com < 0) {
			low = mid + 1;
		} else if(cmp > 0) {
			high = mid - 1;
		} else {
			return mid; // key found
		}
		
	}
	return -(low + 1); // key not found
}

怎样理解 Arrays 的 sort() 排序方法？
答：
- 与 Arrays 中的其他方法相比，sort() 方法具体实现非常复杂。
- 一般而言，没有一个最好的算法，不同算法往往有不同的使用场合。
- 对于基本类型的数组，Java 采用的算法是双枢轴快速排序（Dual-Pivot Quicksort）。这个算法是 Java 7 引入的，在此之前，Java 采用的算法是普通的快速排序。双枢轴快速排序是对快速排序的优化，新算法的实现代码位于类 java.util.DualPivotQuicksort 中。
- 对于对象类型，Java 采用的算法是 TimSort。TimSort 也是在 Java 7 引入的，在此之前，Java 采用的是归并排序。TimSort 实际上是对归并排序的一系列优化，TimSort 的实现代码位于类 java.util.TimSort 中。
- 在这些排序算法中，如果数组长度比较小，它们还会采用效率更高的插入排序。
为什么基本类型和对象类型的算法不一样？怎样理解排序算法里的稳定性概念？
答：
- 排序算法有一个稳定性概念。
- 稳定性：对值相同的元素，如果排序前和排序后，算法可以保证它们的相对顺序不变，那算法就是稳定的，否则就是不稳定的。
- 快速排序更快，但不稳定；归并排序是稳定的。
- 对于基本类型，值相同就是完全相同，所以稳定不稳定没有关系；但对于对象类型，相同只是比较结果一样，它们还是不同的对象，其他实例变量也不见得一样，这时候稳定不稳定就很有关系了，所以采用归并排序。
Arrays 的 binarySearch() 只能针对已排序数组进行查找，那没有排序的数组怎么方便查找呢？
答：Apache 有一个开源包（http://commons.apache.org/proper/commons-lang/），里面有一个类 ArrayUtils（位于包 org.apache.commons.lang3），包含了更多的常用数组操作。

常用基础类（三）：剖析 StringBuilder

发表于 2019-01-11 | 分类于面试篇

怎么理解 StringBuilder 和 StringBuffer？
答：
- 如果字符串修改操作比较频繁，应该采用 StringBuilder 和 StringBuffer。
- 这两个类的方法基本是完全一样的，它们的实现代码也几乎一样。唯一的不同就在于 StringBuffer 类是线程安全的，而 StringBuilder 类不是。
- 线程安全是有成本的，影响性能，而字符串对象及操作大部分情况下不存在线程安全问题。
StringBuilder 的基本用法？
答：
- 通过 new 新建 StringBuilder 对象。
- 通过 append() 方法添加字符串。
- 通过 toString() 方法获取构建完成的字符串。
StringBuilder 的实现原理？
答：源码基于 Java 7：
- 与 String 类似，StringBuilder 类内部也封装了一个字符数组 char[] value，与 String 不同的是，它不是 final 的，可以修改。
- 另外，与 String 不同，字符数组中不一定所有位置都已经被使用，它有一个实例变量 int count 表示数组中已经使用的字符个数。
- StringBuilder 继承自 AbstractStringBuilder，它的默认构造方法是：public StringBuilder() {super(16);}。
StringBuilder 类的 append() 方法的实现原理？
答：
- 如果字符数组的长度小于需要的长度，则调用 void expandCapacity(int minimumCapacity) 方法进行扩展容量。
- 扩展的逻辑是：分配一个足够长度的新数组，然后将原内容复制到这个新数组中，最后让内部的字符数组指向这个新数组。其中，newCapacity 的计算方法是：int newCapacity = value.length * 2 + 2;。
为什么不能需要多少就分配多少？
答：不能，因为那就跟 String 一样了，每 append 一次，都会进行一次内存分配，效率低下。
这种扩展策略最后为什么要加 2？
答：这是一种指数扩展策略，加 2 的原因是在原长度为 0 时也可以一样工作。
为什么要这样扩展？
答：
- 这是一种折中策略，一方面要减少内存分配的次数，另一方面要避免空间浪费。
- 在不知道最终需要多长的情况下，指数扩展是一种常见的策略，广泛应用于各种内存分配相关的计算机程序中。
怎样理解 native 关键字？
答：
- native 关键字是一个修饰符，表示它修饰的方法的实现是通过 Java 本地接口实现的。
- Java 本地接口是 Java 提供的一种技术，用于在 Java 中调用非 Java 实现的代码。
- 实际上，insert() 方法中的用 native 修饰的 System.arraycopy() 方法使用 C++语言实现的。之所以用 C++ 语言实现是因为这个功能非常常用，而 C++ 的实现效率要远高于 Java。
String 可以直接使用 + / += 运算符的背后原理是什么？
答：
- 这是 Java 编译器提供的支持。
- 背后，Java 编译器一般会生成 StringBuilder，+ 和 += 操作会转换为调用 append() 方法。
既然直接使用 + 和 += 就相当于使用 StringBuilder 和 append()，那还有什么必要直接使用 StringBuilder 呢？
答：
- 在简单的情况下，确定没必要。
- 在稍微复杂的情况下，Java 编译器可能没有那么智能，它可能会生成过多的 StringBuilder，尤其是在有循环的情况下。
- 所以，对于简单的情况，可以直接使用 String 的 + 和 +=；对于复杂的情况，尤其是有循环的时候，应该直接使用 StringBuilder。
- 一切都是为了效率。

24隋心所欲

code for die