Android面试笔记三：文石信息

1. LruCache清除缓存的策略
2. 如何缓存数据到内存
3. 安全结束线程的方法
4. 为什么需要双检查锁，第一个判断和第二个判断的作用
5. 快速排序的时间复杂度
6. 说一说对内存堆栈的理解，OOM发生在哪个位置

问题一

LruCache 近期使用最少（Least Recently Use）策略，将数据写入LinkedHashMap结构中，检查当前容量大小和最大容量大小的关系，将链表中使用最少的对象清除，直到当前LruCache缓存大小(size)小于最大缓存大小（maxSize），实现控制内存缓存大小的目的

new LinkedHashMap(0,0.75f,true)为true，按访问顺序对元素进行排序

LruCache的put()方法是线程安全的，检查链表是否存在key关联的value，存在则更新value值，trimToSize()检查当前容量大小和最大缓存大小的关系

public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }

        V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);//计算当前容量大小
            previous = map.put(key, value);//检查是否存在key关联的value值，存在则更新，否则新增
            if (previous != null) {
            //为什么前面增加，这里减少？因为LinkedHashMap元素按访问顺序排序，说明没有新增元素
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        //检查当前容量大小和缓存最大容量大小的关系，size>maxSize，移除最新加入的元素，直到size<maxSize
        trimToSize(maxSize);
        return previous;
    }

LruCache的trimToSize定义了移除元素的策略

 public void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }

                if (size <= maxSize) {
                    break;//当前容量大小小于最大缓存，跳出循环
                }
                //返回最先加入链表的元素
                Map.Entry<K, V> toEvict = map.eldest();
                if (toEvict == null) {
                    break;//链表为null，跳出循环
                }

                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

            entryRemoved(true, key, value, null);
        }
    }

LruCache初始化操作，new LinkedHashMap<K, V>(0, 0.75f, true)这句代码表示，初始容量为零，0.75是加载因子，表示容量达到最大容量的75%的时候会把内存增加一半。

最后这个参数至关重要。表示访问元素的排序方式，true表示按照访问顺序排序，false表示按照插入的顺序排序。

    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

问题二

使用LruCache将数据缓存到内存，清除近期使用最少的对象，直到当前缓存大小小于最大缓存值

LruCache原理分析
https://www.jianshu.com/p/e07fca15271a
LruCache 实现原理分析
https://blog.csdn.net/u012943767/article/details/51897259

问题三

1. 设置标志位flag，通过改变flag状态，取消正在执行的工作任务
2. 使用interrupt()方法，标记线程为中断状态，等待合适的时机，线程主动结束

方法一，在遇到阻塞情况下，一直等待没法改变flag的状态，取消工作任务失败；

中断，是实现取消最合理的方式

每个线程都有一个boolean类型的中断状态。当中断线程时，这个中断状态被设置为true。

• interrupt()，中断目标线程
• interrupted()，清除当前线程的中断状态
• isInterrupted()，返回目标线程的中断状态

阻塞库方法，例如：Thread.sleep、Thread.join和Object.wait，会检查线程何时中断，并且在发现中断时提前返回。响应中断执行的操作包括：清除中断状态、抛出InterruptedException

调用interrupt并不意味中立即停止目标线程正在进行的工作，而只是传递了请求中断的消息，由线程在下一个合适的时刻中断自己

问题四

第一个判断是为了避免不必要的同步，第二个判断是为了在null的情况下创建实例

问题五

快速排序算法的时间复杂度

平均时间复杂度：O(${nlog_2n}$)

最坏时间复杂度：O(${n^2}$)

问题六

堆给创建的对象分配内存空间

栈分为Java栈和本地方法栈，Java栈存储方法中的局部变量、操作数，由每个线程独享，线程调用一个方法会往Java栈中压入栈帧，方法返回后栈帧出栈；本地方法栈存储native相关的信息

• OOM可能发生在方法区，加载的jar包很大很多情况下，class文件相关的类信息、常量、static变量等需要分配很多的内存，然而方法区的内存是有限的，内存不足请求的大小时，抛出OutOfMemeryError:GermGen Space
• OOM可能发生在堆，频繁地创建对象，同时创建的对象被一直持有，造成内存泄露，过多的内存泄露会造成OOM，抛出OutOfMemoryError:Java Heap Space
• OOM可能发生在栈，程序要求的栈深度过大导致，可以写一个死递归程序触发，抛出StackOverflowError
• OOM可能发生在创建本地线程中，线程必须有线程池提供，避免显示创建线程浪费过多的内存，抛出：OutOfMemoryError:unable to create new native thread