1.ArrayMap 综述

特点：

1).实现了Map接口，并使用int[]数来存储key的hash值，数组的索引用作index，而使用Object[]数组来存储key<->value ，这还是比较新颖的。

2).使用二分查找查找hash值在key数组中的位置，然后根据这个位置得到value数组中对应位置的元素。

3).和SparseArray类似，当数据有几百条时，性能会比HashMap低50%，因此ArrayMap适用于数据量很小的场景。

2.ArrayMap和HashMap的区别？

1).ArrayMap的存在是为了解决HashMap占用内存大的问题，它内部使用了一个int数组用来存储元素的hashcode，使用了一个Object数组用来存储元素，两者根据索引对应形成key-value结构，这样就不用像HashMap那样需要额外的创建Entry对象来存储，减少了内存占用。但是在数据量比较大时，ArrayMap的性能就会远低于HashMap，因为 ArrayMap基于二分查找算法来查找元素的，并且数组的插入操作如果不是末尾的话需要挪动数组元素，效率较低。

2).而HashMap内部基于数组+单向链表+红黑树实现，也是key-value结构， 正如刚才提到的，HashMap每put一个元素都需要创建一个Entry来存放元素，导致它的内存占用会比较大，但是在大数据量的时候，因为HashMap中当出现冲突时，冲突的数据量大于8，就会从单向链表转换成红黑树，而红黑树的插入、删除、查找的时间复杂度为O(logn),相对于ArrayMap的数组而言在插入和删除操作上要快不少，所以数据量上百的情况下，使用HashMap会有更高的效率。

3.如何解决冲突问题？

在ArrayMap中，假设存在冲突的话，并不会像HashMap那样使用单向链表或红黑树来保留这些冲突的元素，而是全部key、value都存储到一个数组当中，然后查找的话通过二分查找进行，这也就是当数据量大时不宜用ArrayMap的原因了。

4.HashMap的内部数据结构
数组+链表/红黑树

5.HashMap允许空键空值么？
HashMap最多只允许一个键为Null(多条会覆盖)，但允许多个值为Null。

6.影响HashMap性能的重要参数
初始容量：创建哈希表(数组)时的数量，默认为16。在不指定capacity情况下，初始化容量是16，但不是初始化的时候就创建了一个16大小的数组，而是在第一次put的时候去判断是否需要初始化。太小了就有可能频繁发生扩容，影响效率。太大了又浪费空间，不划算。所以，16就作为一个经验值被采用了。

负载因子(扩容因子,加载因子)：哈希表在其容量自动增加之前可以达到多满的一种尺度，默认为 0.75。扩容因子是用来判断当前数组(“哈希桶”)什么时候需要进行扩容，假设因子为0.5，那么HashMap的初始化容量是16，则16*0.5 = 8个元素的时候，HashMap就会进行扩容。

7.为什么扩容因子是0.75？

扩容因子设置比较大的时候，相当于扩容的门槛就变高了，发生扩容的频率变低了，但此时发生Hash冲突的几率就会提升，当冲突的元素过多的时候，变成链表或者红黑树都会增加了查找成本（hash 冲突增加，链表长度变长）。而扩容因子过小的时候，会频繁触发扩容，占用的空间变大，比如重新计算Hash等，使得操作性能会比较高。

8.HashMap的工作原理

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。

9.new HashMap()

在JDK 8中，在调用new HashMap()的时候并没有分配数组堆内存，只是做了一些参数校验，初始化了一些常量。

10.HashMap什么时候开辟bucket数组占用内存？

在HashMap第一次put的时候调用resize方法，无论Java 8还是Java 7都是这样实现的。

11.HashMap是线程不安全的

在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失，在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

12.HashMap在1.8中做了如下优化：

①数组+链表改成了数组+链表或红黑树；

②链表的插入方式从头插法改成了尾插法；

③扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；

④在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容。

13.Java8中为什么要引进红黑树，是为了解决什么场景的问题？

引入红黑树是为了避免hash性能急剧下降，引起HashMap的读写性能急剧下降的场景，正常情况下，一般是不会用到红黑树的，在一些极端场景下，假如客户端实现了一个性能拙劣的hashCode方法，可以保证HashMap的读写复杂度不会低于O(lgN)。

14.HashMap如何处理key为null的键值对

放置在桶数组中下标为0的桶中。

15.桶中的元素链表何时转换为红黑树，什么时候转回链表，为什么要这么设计？

当同一个桶中的元素数量大于等于8的时候元素中的链表转换为红黑树，反之，当桶中的元素数量小于等于6的时候又会转为链表，这样做的原因是避免红黑树和链表之间频繁转换，引起性能损耗。

16.ArrayList介绍

ArrayList是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List，RandomAccess，Cloneable，java.io.Serializable这些接口。

17.ArrayList的线程安全性

对ArrayList进行添加元素的操作的时候是分两个步骤进行的:

1).即第一步先在object[size]的位置上存放需要添加的元素；

2).第二步将size的值增加1。

由于这个过程在多线程的环境下是不能保证具有原子性的，因此ArrayList在多线程的环境下是线程不安全的。

18.ArrayList的数据结构

ArrayList的底层数据结构就是一个数组，数组元素的类型为Object类型，对ArrayList的所有操作底层都是基于数组的。

19.ArrayList常用优化方案

1).如果事先能够估算ArrayList需要的长度，可在构造时指定初始数组长度，节省扩容开销。

2).频繁调用void add(int index, E element)函数且指定下标位置靠前时，考虑转换为LinkedList。

3).调用boolean contains(Object o) 函数比较频繁时，可以考虑把元素放入HashSet里进行查询。

20.ArrayList优缺点

优点：

1).ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快。

2).ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已。

3).根据下标遍历元素，效率高。

4).根据下标访问元素，效率高。

5).可以自动扩容，默认为每次扩容为原来的1.5倍。

6).修改元素和通过下标查询元素效率高。

7).集合是有顺序的。

缺点：

1).插入和删除元素的效率不高。

2).根据元素下标查找元素需要遍历整个元素数组，效率不高。

3).线程不安全。

4).删除元素效率低，因为要通过拷贝数组来实现。

5).大量新增效率低，因为大量新增的时候要不断进行扩容和数组的拷贝。

6)清除集合效率低，因为清除功能是通过循环数组进行清除的。

7).移除元素后，容量有大量剩余，需要手动调用trimToSize进行清理。

21.LinkedList()和ArrayList()

ArrayList() : 代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。

LinkedList()：在实现中采用链表数据结构。插入和删除速度快，访问速度慢。

22.ArrayMap和HashMap的对比

1).存储方式不同。

HashMap内部有一个HashMapEntry<K, V>[]对象，每一个键值对都存储在这个对象里，当使用put方法添加键值对时，就会new一个HashMapEntry对象。

2).添加数据时扩容时的处理不一样，进行了new操作，重新创建对象，开销很大。ArrayMap用的是copy数据，所以效率相对要高。

3).ArrayMap提供了数组收缩的功能，在clear或remove后，会重新收缩数组，是否空间。

4).ArrayMap采用二分法查找。

23.HashMap和HashTable的区别？

1).HashMap不是线程安全的，效率高一点、方法不是Synchronize的要提供外同步，有containsvalue和containsKey方法。

2).hashtable是线程安全，不允许有null的键和值，效率稍低，方法是是Synchronize的。有contains方法方法。Hashtable 继承于Dictionary 类。

24.ArrayList和LinkedList的区别，以及应用场景。

ArrayList是基于数组实现的，ArrayList线程不安全。

LinkedList是基于双链表实现的。

使用场景：

1).如果应用程序对各个索引位置的元素进行大量的存取或删除操作，ArrayList对象要远优于LinkedList对象；

2).如果应用程序主要是对列表进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象。

25.HashMap与HashSet的区别？

hashMap:HashMap实现了Map接口,HashMap储存键值对,使用put()方法将元素放入map中,HashMap中使用键对象来计算hashcode值,HashMap比较快，因为是使用唯一的键来获取对象。

HashSet实现了Set接口，HashSet仅仅存储对象，使用add()方法将元素放入set中，HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false。HashSet较HashMap来说比较慢。

26.数组和链表的区别？

数组：是将元素在内存中连续存储的；它的优点：因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高；它的缺点：在存储之前，我们需要申请一块连续的内存空间，并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，当数据两比较大的时候，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间。在改变数据个数时，增加、插入、删除数据效率比较低。

链表：是动态申请内存空间，不需要像数组需要提前申请好内存的大小，链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置，通过应用来关联数据（就是通过存在元素的指针来联系）。

27.LinkedList

LinkedList本质上是一个双向链表的存储结构。

对于元素查询来说，ArrayList优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作，LinedList比较占优势，因为ArrayList要移动数据。

28.HashMap默认的bucket数组是多大？

默认是16，即时指定的大小不是2的整数次幂，HashMap也会找到一个最近的2的整数次幂来初始化桶数组。

小伙伴如果有兴趣的话，欢迎来阅读更多文章，搜索并关注公众号“Android技术迷”关注后即可阅读更多文章，感谢关注。