接下来讲确定哈希桶索引位置的做法。
简单的做法就是通过 hash 对数组长度取模运算得到索引，这样元素分布相对来说也是比较均匀的，但是取模运算不及位运算，HashMap 采用的是 (n-1)&hash，当 n 为 2 的次方时，(n-1)&hash 等价于取模运算，但是位运算执行效率显然是高于取模运算的。
同时，取 hash 的时候是通过 hashCode 的高十六位和低十六位异或得到，这样做在数组长度比较小的时候也能保证高位 bit 都能参与到 hash 计算中，同时不会有太大开销。
然后再讲一下扩容机制，扩容的时候是容量翻倍，也就是 x2，这也同时保证了长度依旧是 2 的次方，所以前面基于位运算取索引的优化得以保留。既然数组长度改变了，那么肯定需要重新计算索引位置呀？这里又有一个优化点，当 n 为 2 次方时，x2 不过是在高位补 1，然后在进行与运算，与 1 进行与运算就是它本身嘛。所以这时只需要看 hash 的高位是 1 还是 0，如果是 0，索引不变，如果是 1，新索引就是原索引加旧桶值。这也就避免了重新计算索引，只需要看 hash 的高位是 1 还是 0 即可。但是你可能会说，这必须得保证数组长度为 n 次方呀，我们可以在初始化 HashMap 时传一个非 2 的 n 次方的数，这就炸了。其实呢，HashMap 会根据你数组容量，自动调节到 2 的 n 次方上，比如传 15 就是 16，传 17 呢就是 32，向上转一个最接近的 2 次幂数。
最后，在这里面我并没有将 HashMap 的具体 put/remove/get 的实现，这些其实就是数组或链表或红黑树的操作，数组和链表大家都很熟悉了，红黑树我也不是很懂，只需要记得每次 put/remove 时，都会进行着色和旋转，使得红黑树更加平衡。再不济就把红黑树看成一颗二叉搜索树也行趴。
Hashtable
首先这个 Hashtable 的命名就有点离谱，没有遵循驼峰命名法。它的实现是通过一个 Entry 数组来做的，put/remove/get 都加了 synchronized，是线程安全的，它的取 index 是 (hash & 0x7FFFFFFF) % tab.length，前面和 0x7FFFFFF 是为了让 hash 值变为正数，那你可能会问，为啥不用 Math.abs 呢，其实在数值溢出时，abs 也是可能会得到负值的；HashMap 的可以只有一个 key 为 null，多个 value 为 null 的，而 Hashtable 是不允许 key/value 为 null 的，不然直接抛空指针。
Hashtable 在扩容时，是 x2 + 1 的。Hashtable 在处理 hash冲突时，是插入到链表的头部，即头插法。
TreeMap
TreeMap 底层的数据结构就是红黑树，和 HashMap 的红黑树结构一样。不同的是，TreeMap 通过 compare 来比较 key 的大小，然后利用红黑树左小右大的特性，为每个 key 找到自己的位置，维护了 key 的大小关系，适用于 key 需要排序的场景。
因为底层使用的是红黑树的结构，所以它的 put/remove/get 等方法时间复杂度都是 log(n) 的。
LinkedHashMap
HashMap 是无序的，TreeMap 可以按照 key 进行排序，那有没有 Map 是可以维护插入顺序的呢？这就是 LinkedHashMap。
LinkedHashMap 本身是继承 HashMap 的，所以它拥有 HashMap 的所有特性，在此基础上还提供了两大特性，第一个是按照插入顺序访问，第二个呢是实现了最近最少使用策略，这个需要在构造方法中传一个 accessOrder = true，默认是 false 也就是按照插入顺序访问。
在我们调用 put/remove 方法时，其实是调用的 HashMap 的 put/remove 方法，而重写了 get 方法实现了以上特性。那么它是如何基于 HashMap 实现了以上特性的呢？其实是通过重写 HashMap 里面的三个方法，这个三个方法是每当 HashMap 调用 put/get/remove 时都会调用的，只不过在 HashMap 中是一个空实现，而在 LinkedHashMap 中它被用来记录插入顺序，其实也就是扩展 HashMap 的 Node 使其具备链表结构，也就是每个数组元素增加 befor 和 after 属性。
但是呢，LinkedHashMap 只提供了单向访问，即按照插入的顺序从头到尾进行访问，不能像 LinkedList 那样可以双向访问。
在使用 LRU 策略时，可以覆写删除策略的方法 removeEldestEntry 方法，比如可以指定当节点数大于 10 就开始删除头结点（size() > 10）等等。
HashSet
HashSet 的源码还是很少的，它保证了每个元素是不会重复的。在它的构造方法中，其实是 new HashMap 来做的，一般我们只使用它的 add 和 contains 方法，其实都是调用 HashMap 来实现的。
这个类也没说可说的了，代码就那几十行。
TreeSet
TreeSet 大致的结构和 HashSet 相似，底层组合的是 TreeMap，所以继承了 TreeMap key 能够排序的功能，同时也具有 Set 不可重复的属性。
TreeSet 的 add 方法是调用 NavigableMap 的 put 方法的，它是一个接口，它的实现是在 TreeMap 中，也就是说，TreeSet 定义了接口的规范，TreeMap 负责去实现。
TreeSet 基本上不常用，一般需要不重复元素且能根据元素进行排序的时候，才会用到 TreeSet，使用时需要我们注意最好实现 Comparable 接口，这样方便底层的 TreeMap 根据 key 进行排序。
CopyOnWriteArrayList
CopyOnWriteArrayList 是一个线程安全的 ArrayList，使用了写时复制策略，它是通过 synchronized + 数组拷贝 + volatile 关键字保证了线程安全。在它 add value 时，是先 synchronized 加锁保证同一时刻只有一个线程执行 add 方法，再拷贝一份长度加一的新数组，把 value 加到新数组的末尾，最后再把新数组赋值给原数组。你可能会问了，这都加锁了，为啥不在原数组上面直接操作呢？原因主要有两个：
-
在新的数组上进行拷贝，对老数组没有任何影响，只有新数组完全拷贝完成之后，外部才能访问到，降低了在赋值过程中，老数组数据变动的影响
-
volatile 关键字修饰的是数组，如果只是简单的在原数组上修改其中某几个元素的值，是无法触发可见性的，我们必须通过修改数组的内存地址才行，也就说要对数组进行重新赋值才行
数组拷贝也有一点好处，那就是没有空间损耗，元素是占满数组的。
remove 时和 add 相似，就不多说了。
CopyOnWriteArrayList 读的时候不需要加锁，适合读多写少的场景，这同时也会带来一个弱一致性的问题，即获取迭代器后迭代元素，其他线程对该 list 进行的增删改不可见，因为它们操作的是两个不同的数组，这就是弱一致性。简单来说，就是 CopyOnWriteArrayList 提供了弱一致性的迭代器，从而保证获取迭代器后，其他线程对 list 的修改是不可见的，迭代器遍历的数组是一个快照。
CopyOnWriteArraySet 的内部实现就是在其构造方法中 new CopyOnWriteArrayList 来实现的。
ConcurrentHashMap
ConcurrentHashMap 和 HashMap 相比，它的底层也是使用数组 + 链表 + 红黑树来实现的，不过新增了转移节点（ForwardingNode），是为了保证扩容时的线程安全的节点。而且红黑树结构略有不同，HashMap 的红黑树节点叫做 TreeNode，TreeNode 不仅仅有属性，还维护着红黑树的结构，比如说查找、新增等；ConcurrentHashMap 中红黑树被拆分成两块，TreeNode 仅仅维护属性和查找功能，新增了 TreeBin，来维护红黑树结构，并负责根节点的加锁和解锁。
和 HashTable 相比，它也是线程安全的，但是 ConcurrentHashMap 多个线程同时进行 put、remove 等操作时并不会阻塞，可以同时进行；HashTable 在操作时，会锁住整个 Map。
ConcurrentHashMap 在 put 时，在一个 for 死循环里面，也就是一定能保证 put 成功。第一次 put 时，会先通过 CAS 保证只有一个线程扩容，如果有其他线程在执行扩容操作，就会调用 Thread.yield 释放当前 CPU 调度权，重新发起锁的竞争，这一步是在一个 while 循环里面去做的只要容量为空，就一直循环。再求出 table 索引之后，如果该槽点为空并不是直接新增，而是通过 CAS 新增。如果判断当前是转移节点（转移节点的 hash 值固定为 MOVED 为 -1），表示该槽点正在扩容，就会一直等待扩容完成；如果当前槽点有值，就是 key 的 hash 冲突的情况，此时槽点上可能是链表或红黑树，这时候就会通过 synchronized 锁住槽点，来保证同一时刻只会有一个线程能对槽点进行修改。也就是说，put 是通过自旋 + CAS + 锁来实现线程安全的。
在进行扩容时，首先需要把老数组的值全部拷贝到新数组上，先从数组的队尾开始拷贝，拷贝数组的槽点时，会先把原数组的槽点锁住，保证原数组槽点不能操作，成功拷贝到新数组时，把原数组槽点赋值为转移节点。如果此时有数据要 put 到此槽点就会一直等待。拷贝时也是扩容原数组两倍大小。
ConcurrentHashMap 的 get 和 HashMap 基本无差。
LinkedBlockingQueue
LinkedBlockingQueue 即链表阻塞队列，它实现了 BlockingQueue 接口，BlockingQueue 在 Queue 的基础上加上了阻塞的概念；链表维护了先入先出的队列，新元素被放在队尾，获取元素从队头拿；当我们调用 put 时，队列满了就一直阻塞，在阻塞时被其他线程设置了中断标志，则被阻塞的线程会抛出 InterruptedException 异常而返回，也可以调用非阻塞的 offer 方法，如果队列满了就放弃当前元素返回 false；调用 take 时，如果队列为空也是一直阻塞，也可以调用非阻塞的 poll 方法，如果队列为空就直接返回 null。
LinkedBlockingQueue 内部构成简单来说，可以分为三个部分：链表存储 + 锁 + 迭代器。它内部有两把 ReentrantLock 锁，分别是 put 锁和 take 锁，保证了队列操作的线程安全，设计两把锁，是为了 put 和 take 两种操作可以同时进行，互不影响。
在 put 时，先调用 ReentrantLock 的 lockInterruptibly 设置可中断锁，然后判断队列是否满了，如果满了就调用 Condition 的 await 函数无限等待，否则就添加到队列尾部；如果这时队列不为空，就唤醒一个 take 的等待线程，最后在解锁。
在 take 时，也是先加 take 锁，然后判断队列是否为空，为空就无限等待，否则就删除链表头节点返回，如果这时队列没有满，就唤醒一个 put 的等待线程，最后在解锁。
在 remove 时会获取双重锁，获取后，其他线程进行入队或出队操作都会被阻塞挂起，然后遍历队列找到要删除的元素删除，找到了就删除并唤醒一个阻塞的 put 线程，否则返回 false。
LinkedBlockingQueue 主要用在线程池中，当我们使用 Executors 的 newFixedThreadPool 或 newSingleThreadPool 创建线程池时，阻塞队列用的就是 LinkedBlockingQueue，但是通常我们不建议这样直接使用 Executors 创建线程池，因为 LinkedBlockingQueue 的默认队列大小是 Integer.MAX_VALUE，可能会爆内存。
在 Android 中，AsyncTask 在核心线程池不够用的情况下触发任务拒绝策略时，会用到 LinkedBlockingQueue。
SynchronousQueue
SynchronousQueue 是一个不存储元素的阻塞队列，每一个 put 操作必须等待 take 操作，否则不能添加元素。在使用 Executors 的 newCachedThreadPool 创建线程池用的就是它，在 AsyncTask 创建的一个单线程池用的也是它，核心线程数为 1，最大线程数为 20，非核心线程空闲存活时间为三秒，适合任务多但是执行比较快的场景中。
源码水太深了，还没看明白，待定。
SparseArray
SparseArray 是 Android 中一种特有的数据结构，用来替代 HashMap 的。初始化时容量为 10，它里面有两个数组，一个是 int[] 数组存放 key，一个是 Object[] value 数组。也就是它的 key 只能为 int；在 put 时，会根据传入的 key 进行二分查找找到合适的插入位置，如果当前位置有值或者是 DELETED 节点，就直接覆盖，否则就需要拷贝数组后移一位，空出一个位置让其插入。如果数组满了但是还有 DELETED 节点，就需要调用 gc 方法，gc 方法所做的就是把 DELETED 节点后面的数前移，也就是真正的把 DELETED 节点删掉然后在插入，否则就只能扩容了。
调用 remove 时，并不会直接把 key 从 int[] 数组里面删掉，而是把当前 key 指向的 value 设置成 DELETED 节点，这样做是为了减少 int[] 数组的结构调整，结构调整就意味着数据拷贝。但是当我们调用 keyAt/valueAt 获取索引时，如果有 DELETED 节点就必须得调用 gc，不然获得的 index 肯定不对。延迟回收的好处适合频繁删除和插入来回执行的场景，性能很好。
get 方法就比较简单了，二分查找获取 key 对应的索引 index，返回 values[index] 即可。
可以看到，SparseArray 比 HashMap 少了基本数据的自动装箱操作，而且不需要额外的结构体，单个元素存储成本低，在数据量小的情况下，随机访问的效率很高。但是缺点也是显而易见的，就是增删的效率比较低，在数据量比较大的时候，调用 gc 拷贝数组成本巨大。
除了 SparseArray，Android 还提供了 SparseIntArray（int:int）、SparseBooleanArray（int:boolean）、SparseLongArray（int:long） 等，其实就是把对应的 value 换成基本数据类型。
ArrayMap
SparseArray 只能存 key 为 int 的键值对，如果需要存其他类型的 key，就可以使用 ArrayMap 了。ArrayMap 的底层和 SparseArray 类似，都是有两个数组，不过 ArrayMap 的一个数组存 hashCode 值，一个数组存 key-value 键值对，键值对数组的大小显然要是 hashCode 数组大小的两倍。为了减少频繁的创建和回收 Map 对象，ArrayMap 还采用了两个大小为 10 的缓存队列来分别保存大小为 4 和 8 的 ArrayMap 对象。为了节省内存，还有内存扩张和内存收缩策略。
ArrayMap 在 put/remove 时，和 SparseArray 基本一致，也是通过二分查找求数组索引，然后在执行相应的操作。不同的是 ArrayMap 的扩容机制和缩容机制。
在 put 需要扩容时，如果容量小于 4 就给 4，小于 8 就给 8，其次就是扩容 1.5 倍。之所以给 4 或 8 是因为可以利用缓存的 ArrayMap 对象；在 remove 时，如果数组长度大于 8 但是存储的数据不足数据大小的 1/3 时，就会缩容，mSize 小于等于 8，则设置新大小为 8，否则就设置为 mSize 的 1.5 倍，也就是说在内存使用量不足 1/3 时，内存数据收紧 50%。
这个缓存还是很有必要的，毕竟 ArrayMap 的使用量还是蛮大的，Bundle 的底层就是用 ArrayMap 来存数据的，可想而知了。但是可以思考一下 Bundle 为啥用 ArrayMap 而不用 SparseArray 呢？
除了 put 方法，ArrayMap 和 SparseArray 都有一个 append 方法，它和 put 很相似，append 的差异在于该方法不会去做扩容操作，是一个轻量级的插入方法。在明确知道肯定会插入队尾的情况下使用 append 性更好，因为 put 一上来就做二分查找，时间复杂度 O(logn)，而 append 时间复杂度为 O(1)。
ArraySet 也是 Android 特有的数据结构，用来替代 HashSet 的，和 ArrayMap 几乎一致，包含了缓存机制、扩容机制等。
Android及相关开发源码学习资源
其实客户端开发的知识点就那么多，面试问来问去还是那么点东西。所以面试没有其他的诀窍，只看你对这些知识点准备的充分程度。so，出去面试时先看看自己复习到了哪个阶段就好。
这里再分享一下我面试期间的复习路线：（以下体系的复习资料是我从各路大佬收集整理好的）
《Android开发七大模块核心知识笔记》
文末
架构师不是天生的，是在项目中磨练起来的，所以，我们学了技术就需要结合项目进行实战训练，那么在Android里面最常用的架构无外乎 MVC，MVP，MVVM，但是这些思想如果和模块化，层次化，组件化混和在一起，那就不是一件那么简单的事了，我们需要一个真正身经百战的架构师才能讲解透彻其中蕴含的深理。
一线互联网Android面试题总结含详解（初级到高级专题）
，那么在Android里面最常用的架构无外乎 MVC，MVP，MVVM，但是这些思想如果和模块化，层次化，组件化混和在一起，那就不是一件那么简单的事了，我们需要一个真正身经百战的架构师才能讲解透彻其中蕴含的深理。
[外链图片转存中…(img-6uMGmKwg-1631011352147)]
[外链图片转存中…(img-6xr2Eenv-1631011352148)]
一线互联网Android面试题总结含详解（初级到高级专题）
[外链图片转存中…(img-20UdHDQF-1631011352149)]