常见面试题备忘

设计模式

• 观察者（Observer），LiveData
• 单例（Singleton），double check
• 适配器（Adapter），RecyclerView.Adapter
• 装饰器（Decorator），ContextWrapper
• 代理模式（Proxy），例如 VPN、Retrofit
• 责任链（Chain of Responsibility），OkHttp 大体上就是个责任链模式
• 建造者（Builder）
• 工厂（Factory）

代理模式强调不能直接访问一个对象，只能通过代理间接访问，不能直接访问的原因比如：权限校验、操作日志、RPC，比如 AIDL 生成的 IAidlInterface.Stub.Proxy 类就是代理了 remote IBinder

装饰器模式强调增强对象的功能：把一个对象的功能拆分为几部分，在运行时按需组装，比如：BufferedOutputStream、JarOutputStream、ZipOutputStream

实现 LRU

map + 双端链表，链尾是最近使用过的，链头是最久未使用的

• get(key)，通过 map 可以在 O(1) 时间内找到 value，然后把 value 从双端链表中断开并移到链尾，双端链表的特性使得「断开」操作很容易实现
• put(key, value)，把 value 添加到链尾，当超过容量限制时，从链头逐个移除 value 直到满足容量限制

几个重要的排序算法

• 归并排序 O(nlogn)
  step 从 1 逐步递增，合并两个长度为 step 的已排序区间，当 step > length/2 时，已排序区间就等于整个数组
  合并两个有序区间很简单，用「双指针法」即可

• 快速排序 O(nlogn)
  双指针，一个在头一个在尾，取第一个元素为「基准」（挖出一个坑），从尾部找一个比「基准」小的填入坑，然后又从头部找一个比「基准」大的填入尾部的坑，循环往复直到双指针碰头，那么这个位置就是「基准」的位置
  每一轮都可以找出一个元素的排序后的位置，从整体看，这个元素和它左右两块是已排序的
  然后递归操作左右两块区间直到区间长度为 1

• 堆排序 O(nlogn)
  利用「堆」这个特殊的数据结构来排序（大顶堆、小顶堆）
  恰好堆也是用数组实现的，初始已排序区间的长度为 1，逐步扩大长度相当于逐个添加一个新元素到堆
  添加一个新元素到堆，相当于添加到数组尾部，逻辑上看就是添加到二叉树叶子那层最左边，为了让堆继续满足性质，需要把新元素逐层地跟它的父节点比较：新节点大于父节点则交换（大顶堆，小顶堆则相反）
  当已排序区间 == 数组时，整个数组就排好序了

五层网络

应用层	HTTP
传输层	TCP、UDP
网络层	IP 地址（替代 MAC 地址，形成网络），ARP（通过 IP 地址查询得到 MAC 地址）
链接层	以太网协议（Ethernet），帧（Frame），MAC 地址，广播（同一网络的所有计算机都会受到消息，它们比较帧的 MAC 地址和自己的 MAC 地址是否相同来决定是否接收）
物理层（实体层）

抽象类和接口的区别

抽象类是对实体的抽象，而接口是对特征的抽象；所以 Java 类最多只能继承自一个抽象类，但却可是实现多个特征

多线程同步的方法

• synchronized
• volatile
• Lock & Condition & Atoimc

HashMap 和 HashTable 的区别

• 都是数组 + 链表的实现（链表是为了解决 hash 冲突）
• HashTable 是线程安全的（大多数方法都加了 synchronized），而 HashMap 不是
• HashMap 允许为 null 的 key 和 value，而 HashTable 则不允许
• HashMap 重算了 hash code：(h = key.hashCode()) ^ (h >>> 16)，而 HashTable 直接使用 hashCode()

怎么解决 ANR 问题

先把 /data/anr/trace.txt 拉下来，搜索包名定位到 app 进程那一段，找到 main 线程，看看主线程是不是出于异常状态（比如 Blocked、Sleeping）
如果主线程状态异常，那么查看主线程的调用堆栈，看看是哪段代码导致主线程进入异常状态
像 Blocked 有可能是锁导致的，能看到主线程被哪个锁阻塞，那个锁被哪个线程持有
有时候主线程没发现异常，看调用堆栈发现主线程正在执行 binder 相关操作，此时有可能是阻塞在这里（等待 binder 对面那端的响应）

还找不到问题，就在 logcat 里搜索 anr 找到 anr 相关日志，它会有一个 CPU 负载统计，如果 io 占比很大说明卡在 io 上了，继续往上找找看当时正在做什么文件操作，或者在 trace 文件里找找

Double Check 会有什么问题？

mSingleton = new Object(); 这行语句实际上会分解为多条 CPU 指令：

1. 为 Object 分配一块内存
2. 初始化 Object 实例
3. 把 mSingleton 指向这块内存

但是「指令重排」可能导致第三部与第二部交换位置，也就是说把 mSingleton 指向了一块尚未初始化的内存区域；此时线程 B 在执行 if (mSingleton == null) 时就会发现 mSingleton 的确不为 null 并返回 mSingleton，从而导致程序异常（因为 mSingleton 指向的内存还没有初始化）

使用 volatile 修饰 mSingleton 即可，volatile 可以防止相关指令的重排

IdleHandler 是怎么实现的？

在 MessageQueue.next 里，当队列为空，或者还不到第一个消息的执行时间时（Message 是按照执行时间排序的），在 MessageQueue.mIdleHandlers 里的 IdleHandler 会被执行

Retrofit 是怎么接口的？

使用动态代理 Proxy.newProxyInstance，其核心是方法拦截

在运行时创建一个实现了所选接口的类，这个类的构造函数需要一个 InvocationHandler，接口所有的方法调用都会代理至 InvocationHandler

public <T> T Retrofit.create(final Class<T> service) {
  Utils.validateServiceInterface(service);
  if (validateEagerly) {
    eagerlyValidateMethods(service);
  }
  return (T) Proxy.newProxyInstance(service.getClassLoader(), new Class<?>[] { service },
      new InvocationHandler() {
        private final Platform platform = Platform.get();
        private final Object[] emptyArgs = new Object[0];
        @Override public Object invoke(Object proxy, Method method, @Nullable Object[] args)
            throws Throwable {
          // If the method is a method from Object then defer to normal invocation.
          if (method.getDeclaringClass() == Object.class) {
            return method.invoke(this, args);
          }
          if (platform.isDefaultMethod(method)) {
            return platform.invokeDefaultMethod(method, service, proxy, args);
          }
          return loadServiceMethod(method).invoke(args != null ? args : emptyArgs);
        }
      });
}

Activity 重建的过程

旧的 Activity 走向死亡（onPause -> onStop -> onDestroy），新的 Activity 进入（onCreate -> onStart -> onResume）

ActivityThread.handleRelaunchActivity(...)

private void handleRelaunchActivityInner(ActivityClientRecord r, int configChanges,
        List<ResultInfo> pendingResults, List<ReferrerIntent> pendingIntents,
        PendingTransactionActions pendingActions, boolean startsNotResumed,
        Configuration overrideConfig, String reason) {
    // Preserve last used intent, it may be set from Activity#setIntent().
    final Intent customIntent = r.activity.mIntent;

    // 旧的 Activity 走向死亡（销毁）
    // Need to ensure state is saved.
    if (!r.paused) {
        performPauseActivity(r, false, reason, null /* pendingActions */);
    }
    if (!r.stopped) {
        callActivityOnStop(r, true /* saveState */, reason);
    
    handleDestroyActivity(r.token, false, configChanges, true, reason)
    r.activity = null;
    r.window = null;
    r.hideForNow = false;
    r.nextIdle = null;
    // Merge any pending results and pending intents; don't just replace them
    if (pendingResults != null) {
        if (r.pendingResults == null) {
            r.pendingResults = pendingResults;
        } else {
            r.pendingResults.addAll(pendingResults);
        }
    }
    if (pendingIntents != null) {
        if (r.pendingIntents == null) {
            r.pendingIntents = pendingIntents;
        } else {
            r.pendingIntents.addAll(pendingIntents);
        }
    }
    r.startsNotResumed = startsNotResumed;
    r.overrideConfig = overrideConfig
    // 走创建新 Activity 的流程
    handleLaunchActivity(r, pendingActions, customIntent);
}

ViewModel 和 Fragment 会随之重建吗?

不会，在 Activity.onStop 之后 Activity.onDestory 之前，FragmentActivity 将 Fragment 和 ViewModelStore 借由方法 onRetainNonConfigurationInstance 传递给 ActivityClientRecord 保存
并在 Activity.attach 被重新赋值给新的 Activity

public final Object FragmentActivity.onRetainNonConfigurationInstance() {
    Object custom = onRetainCustomNonConfigurationInstance()
    FragmentManagerNonConfig fragments = mFragments.retainNestedNonConfig()
    if (fragments == null && mViewModelStore == null && custom == null) {
        return null;
    
    // 在旧的 Activity 销毁前，保存 ViewModel 和 Fragment
    NonConfigurationInstances nci = new NonConfigurationInstances();
    nci.custom = custom;
    nci.viewModelStore = mViewModelStore;
    nci.fragments = fragments;
    return nci;
}

protected void onCreate(@Nullable Bundle savedInstanceState) {
    mFragments.attachHost(null /*parent*/);
    super.onCreate(savedInstanceState);
    NonConfigurationInstances nc =
            (NonConfigurationInstances) getLastNonConfigurationInstance();
    // 恢复 ViewModel
    if (nc != null && nc.viewModelStore != null && mViewModelStore == null) {
        mViewModelStore = nc.viewModelStore;
    }
    if (savedInstanceState != null) {
        Parcelable p = savedInstanceState.getParcelable(FRAGMENTS_TAG);
        // 恢复 Fragment
        mFragments.restoreAllState(p, nc != null ? nc.fragments : null);
    // ...
}

// 旧的 Activity 实例会被销毁，但其对应的 ActivityClientRecord 不会被销毁
// 那么 NonConfigurationInstances 就由 ActivityClientRecord 暂时保管
ActivityClientRecord performDestroyActivity(IBinder token, boolean finishing,
        int configChanges, boolean getNonConfigInstance, String reason) {
    ActivityClientRecord r = mActivities.get(token);
    Class<? extends Activity> activityClass = null;
    if (localLOGV) Slog.v(TAG, "Performing finish of " + r);
    if (r != null) {
        activityClass = r.activity.getClass();
        r.activity.mConfigChangeFlags |= configChanges;
        if (finishing) {
            r.activity.mFinished = true;
        }
        performPauseActivityIfNeeded(r, "destroy");
        if (!r.stopped) {
            callActivityOnStop(r, false /* saveState */, "destroy");
        }
        if (getNonConfigInstance) {
            try {
                r.lastNonConfigurationInstances
                        = r.activity.retainNonConfigurationInstances();
            } catch (Exception e) {
                if (!mInstrumentation.onException(r.activity, e)) {
                    throw new RuntimeException(
                            "Unable to retain activity "
                            + r.intent.getComponent().toShortString()
                            + ": " + e.toString(), e);
                }
            }
        }
        // call destory
    }
    // ...
}

// 然后在 launch activity 时重新把 NonConfigurationInstances 赋给新建的 Activity 实例
private Activity performLaunchActivity(ActivityClientRecord r, Intent customIntent) {
    // ...
    activity.attach(appContext, this, getInstrumentation(), r.token,
            r.ident, app, r.intent, r.activityInfo, title, r.parent,
            r.embeddedID, r.lastNonConfigurationInstances, config,
            r.referrer, r.voiceInteractor, window, r.configCallback,
            r.assistToken);
    // ...
}
final void attach(...) {
    // ...
    mLastNonConfigurationInstances = lastNonConfigurationInstances;
    // ...
}

CountDownLatch 和 CyclicBarrier 的区别

开始多个线程通过 CountDownLatch.await() 被它阻塞，然后其他线程执行完一个任务就通过 countDown() 把里面的计算器 count 减一，直到计数器归零阻塞的线程才被唤醒；它是 oneshot 不能重复使用，内部通过 AQS 实现

N 个并行线程执行任务，执行完就阻塞在 CyclicBarrier.await() 上面，直到 N 个线程都执行完任务，最后一个调用 await() 的线程执行完 barrierCommand 后，其他线程被唤醒，而 CyclicBarrier 被重置为初始状态；不同于 CountDownLatch 的一次性，CyclicBarrier 可以重复使用

如何让 N 个线程串行执行？

public class JoinThread extends Thread {
    private Runnable task;
    private Thread prev;

    public JoinThread(Runnable task, Thread prev) {
        this.task = task;
        this.prev = prev;
    }

    /**
     * 使用 Thread.join()，调用后当前线程被阻塞直到 prev 执行完毕才恢复
     * join 可以使并行的线程串行执行
     */
    public void run() {
        prev.join();
        task.run();
    }
}

5 个线程，前 4 个执行完后才执行第 5 个

用 CountDownLatch，计算器设为 4，第 5 个线程通过 await() 阻塞在计数器上面，前 4 个执行到最后一步时使计数器减一，当计数器为零时第 5 个线程被唤醒

两个线程交替输出 1 - 100

自旋 + volatile

既然是交替输出，那必然一个输出奇数一个输出偶数，输出日志这一操作是很快的，所以可以考虑乐观锁：自旋

public class App {

    public static volatile int count;

    public static void main(String[] args) {
        new OddThread().start();
        new EvenThread().start();
    }

    public static void print(int i) {
        System.out.printf("%s - %d%n", Thread.currentThread().getName(), i);
    }

    public static class OddThread extends Thread {
        public OddThread() { super("Odd"); }

        @Override
        public void run() {
            for (;;) {
                int c = count;
                if (c >= 100) break;

                if (++c % 2 == 1) {
                    print(c);
                    count = c;
                }
            }
        }
    }

    public static class EvenThread extends Thread {
        public EvenThread() { super("Even"); }

        @Override
        public void run() {
            for (;;) {
                int c = count;
                if (c >= 100) break;

                if (++c % 2 == 0) {
                    print(c);
                    count = c;
                }
            }
        }
    }
}

基于条件变量 Condition

public class App {

    public static volatile int count;
    public static final ReentrantLock lock = new ReentrantLock();
    public static final Condition cond = lock.newCondition();

    public static void main(String[] args) {
        Runnable run = new Runnable() {
            @Override
            public void run() {
                for (;;) {
                    lock.lock();
                    cond.signalAll();
                    try {
                        if (count >= 100) break;
                        count++;
                        print(count);
                        cond.await();
                    } catch (InterruptedException ignored) {
                    } finally {
                        lock.unlock();
                    }
                }
            }
        };

        new Thread(run, "A").start();
        new Thread(run, "B").start();
    }

    public static void print(int i) {
        System.out.printf("%s - %d%n", Thread.currentThread().getName(), i);
    }
}

思考：N 个线程按顺序输出 1 - 100 ？

不使用锁的情况下，把判断奇偶的逻辑改一下，通过 (count % N) == i 判断该数字是否应该由当前线程打印

用条件变量的情况下，每个线程都在自己的条件变量上阻塞，前面的线程持有下一个线程的条件变量（形成一个环），打印完后唤醒下一个线程；开始时主线程主动唤醒第一个线程

LinkedHashMap

在 HashMap 的基础上给 Entry 添加了先后次序，也就说它里面的 Entry 是有序的：LinkedHashMap = HashMap + LinkedList，是 LRU 算法的典型实现

Least Recently Used，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰

• Entry 的实现为 LinkedHashMapEntry，它增加了 before 和 after 两个成员变量分别指向上一节点和下一节点，这样所有的 Entry 都可以通过这两个指针串联成一个 LinkedList
• LinkedHashMapEntry 增加了 head 和 tail 成员变量分别指向 LinkedList 的头节点和尾结点，这样 entry list 就变成了双向链表
• head 是最旧的节点，而 tail 是最新的节点
• 还增加了标识 accessOrder，true：entry list 按访问时间排序（最近访问的是尾结点），false：entry list 按插入次序排序（最近插入的是尾结点）
• 迭代器（Iterator）从 head 开始遍历

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

class LinkedHashMap {
    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMapEntry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMapEntry<K,V> tail;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
    final boolean accessOrder;    
}

• 新插入的节点作为新的尾结点 tail，相当于 append 到 LinkedList 上，新插入的节点也可以认为是最近访问的节点
• 当按访问时间排序时（accessOrder == true），get(key) 会导致 Entry 成为新的 tail

class LinkedHashMap {
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMapEntry<K,V> p =
            new LinkedHashMapEntry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    // link at the end of list
    private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }                    
}