Android⾯试之设计模式与算法
⾯试专题我放在git上了，地址Github 欢迎fork然后⼀起更新
设计模式
0，什么是设计模式，设计模式的六⼤原则，你是否在代码中使⽤过设计模式？
设计模式是世界上各种各样程序员⽤来解决特定设计问题的尝试和测试的⽅法。设计模式是代码可⽤性的延伸。
设计模式分三类：
创建型，与对象创建有关包括单例模式，⼯⼚⽅法模式，抽象⼯⼚模式，建造者模式，原型模式
结构性，结构性设计模式是从程序的结构上解决模块之间的耦合问题，包括适配器模式，代理模式，装饰模式，外观模式，桥接模式，组合模式和享元模式
⾏为型，主要处理类或对象如何交互及如何分配职责，包括策略模式，模板⽅法模式，观察者模式，迭代器模式，责任链模式，命令模式，备忘录模式，状态模式，访问者模式，中介模式，解析器模式
a.单⼀职责原则：就⼀个类来说，应该只有⼀个引起它变化的原因
⼀个类做⼀件事情，避免职责过多。⽐如这种情况是不太好的，在⼀个Activity中既有bean⽂件，⼜有http请求，还有adapter等等，这就导致我们需要修改任何⼀个东西的时候都会导致Activity的改变，这样⼀来就有多个引起它变化的原因，不符合单⼀职责原则
b.开放封闭原则：类，模块，函数应该是可以扩展的，但是不可以修改
对于扩展是开放的，对于修改是封闭的。尽量做到⾯对需求的改变时，我们的代码能保持相对稳定，通过扩展的⽅式应对变化，⽽不是修改原有代码实现
c.⾥⽒替换原则：所有引⽤基类的地⽅，必须可以透明的时候其⼦类的对象
⾥⽒替换原则是实现开放封闭原则的重要⽅式之⼀，我们知道，使⽤基类的地⽅都可以使⽤⼦类去实现，因为⼦类拥有基类的所有⽅法，所以在程序设计中尽量使⽤基类类型对对象进⾏定义，在运⾏时确定⼦类类型。
d.依赖倒置原则：⾼层模块不应该依赖于底层模块，两者都应该依赖于抽象，抽象不应该依赖于细节，细节应该依赖于抽象
依赖倒置原则针对的是模块之间的依赖关系，⾼层模块指调⽤端，底层模块指具体的实现类，抽象指接⼝或抽象类，细节就是实现类。该原则的具体表现就是模块间的依赖通过抽象发⽣，直线类之间不发⽣直接依赖关系，依赖通过接⼝或抽象类产⽣，降低耦合，⽐如MVP模式下，View层和P层通过接⼝产⽣依赖关系
e.迪⽶特原则（最少知识原则）：⼀个软件实体应该尽可能少的与其他实体发⽣相互作⽤
迪⽶特原则要求我们在设计系统时，尽量减少对象之间的交互
f.接⼝隔离原则：⼀个类对另⼀个类的依赖应该建⽴在最⼩的接⼝上
接⼝隔离原则的关键是接⼝以及这个接⼝要⼩，如何⼩呢，也就是我们要为专门的类创建专门的接⼝，这个接⼝只对它有效，不要试图让⼀个接⼝包罗万象，要建⽴最⼩的依赖关系
1，单例模式
单例模式是⼀种确保系统中的⼀个类只产⽣⼀个实例的对象创建模式；Java.lang.Runtime就是单例的经典例⼦
好处：
对于频繁使⽤的对象，可以省略创建对象所花费的时间，这对于那些重量级对象⽽⾔，是⾮常可观的⼀笔系统开销
由于new操作的次数减少，因⽽对系统内存的使⽤频率也会减低，这将减轻GC压⼒，缩短GC停顿时间。
单例的多种写法
2，JDK中⼏个常⽤是设计模式？
单例（Singleton），⽤于Runtime，Calender和其他类中
⼯⼚模式（Factory），⽤于各种不可变的类如Boolean，像Boolean.valueOf
观察者模式（Observer），⽤于Swing和很多事件监听中
装饰器模式（Decorator design），⽤于多个JavaIO类中
3，Java中，什么叫观察者模式？
观察者模式是基于对象的状态变化和观察者的通讯，以便他们作出相应的操作。简单的例⼦就是⼀个
天⽓系统，当天⽓变化时必须在展⽰给公众的视图中进⾏反映。这个视图对象是⼀个主体，⽽不同的视图是观察者。
5.使⽤⼯⼚模式最主要的好处是什么？在哪⾥使⽤？
⼯⼚模式的最⼤好处是增加了创建对象时的封装层次。如果你使⽤⼯⼚来创建对象，之后你可以使⽤更⾼级和更⾼性能的实现来替换原始的产品实现或类，这不需要在调⽤层做任何修改。
6.举⼀个⽤ Java 实现的装饰模式(decorator design pattern)？它是作⽤于对象层次还是类层次？
装饰模式增加强了单个对象的能⼒。Java IO 到处都使⽤了装饰模式，典型例⼦就是Buffered 系列类如 BufferedReader 和
BufferedWriter，它们增强了 Reader 和 Writer 对象，以实现提升性能的 Buffer 层次的读取和写⼊。
7.在 Java 中，为什么不允许从静态⽅法中访问⾮静态变量？
Java 中不能从静态上下⽂访问⾮静态数据只是因为⾮静态变量是跟具体的对象实例关联的，⽽静态的却没有和任何实例关联。
8.设计⼀个 ATM 机，请说出你的设计思路？
⽐如设计⾦融系统来说，必须知道它们应该在任何情况下都能够正常⼯作。不管是断电还是其他情况，ATM 应该保持正确的状态（事务） , 想想加锁（locking）、事务（transaction）、错误条件（error condition）、边界条件（boundary condition） 等等。尽管你不能想到具体的设计，但如果你可以指出⾮功能性需求，提出⼀些问题，想到关于边界条件，这些都会是很好的。
9.在 Java 中，什么时候⽤重载，什么时候⽤重写？
如果你看到⼀个类的不同实现有着不同的⽅式来做同⼀件事，那么就应该⽤重写（overriding），⽽重载（overloading）是⽤不同的输⼊做同⼀件事。在 Java 中，重载的⽅法签名不同，⽽重写并不是。
10.举例说明什么情况下会更倾向于使⽤抽象类⽽不是接⼝？
接⼝和抽象类都遵循”⾯向接⼝⽽不是实现编码”设计原则，它可以增加代码的灵活性，可以适应不断变化的需求。
下⾯有⼏个点可以帮助你回答这个问题：
在 Java 中，你只能继承⼀个类，但可以实现多个接⼝。所以⼀旦你继承了⼀个类，你就失去了继承其他类的机会了。
接⼝通常被⽤来表⽰附属描述或⾏为如：Runnable、Clonable、Serializable 等等，因此当你使⽤抽象类来表⽰⾏为时，你的类就不能同时是Runnable 和 Clonable(注：这⾥的意思是指如果把 Runnable 等实现为抽象类的情况)，因为在 Java 中你不能继承两个类，但当你使⽤接⼝时，你的类就可以同时拥有多个不同的⾏为。在⼀些对时间要求⽐较⾼的应⽤中，倾向于使⽤抽象类，它会⽐接⼝稍快⼀点。如果希望把⼀系列⾏为都规范在类继承层次内，并且可以更好地在同⼀个地⽅进⾏编码，那么抽象类是⼀个更好的选择。有时，接⼝和抽象类可以⼀起使⽤，接⼝中定义函数，⽽在抽象类中定义默认的实现
alertdialog使用方法
11，android中举例说说⽤到了什么设计模式？
o AlertDialog、Notification 源码中使⽤了 Builder（建造者）模式完成参数的初始化
o Okhttp 内部使⽤了责任链模式来完成每个 Interceptor 的调⽤
o RxJava 的观察者模式；单例模式；GridView 的适配器模式；Intent 的原型模式
o ⽇常开发的 BaseActivity 抽象⼯⼚模式
数据结构
1、常⽤数据结构简介
数据结构是指相互之间存在着⼀种或多种关系的数据元素的集合和该集合中数据元素间的关系组成。常⽤的数据有：数组、栈、队列、链表、树、
图、堆、散列表。
1）数组：在内存中连续存储多个元素的结构。数组元素通过下标访问，下标从0开始。优点：访问速度快；缺点：数组⼤⼩固定后⽆法扩容，只能存储⼀种类型的数据，添加删除操作慢。适⽤场景：适⽤于需频繁查，对存储空间要求不⾼，很少添加删除。
2）栈：⼀种特殊的线性表，只可以在栈顶操作，先进后出，从栈顶放⼊元素叫⼊栈，从栈顶取出元素叫出栈。应⽤场景：⽤于实现递归功能，如斐波那契数列。
3）队列：⼀种线性表，在列表⼀端添加元素，另⼀端取出，先进先出。使⽤场景：多线程阻塞队列管理中。
4）链表：物理存储单元上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，⼀个是存储元素的数据域，⼀个是指向下⼀个结点地址的指针域。有单链表、双向链表、循环链表。优点：可以任意加减元素，不需要初始化容量，添加删除元素只需改变前后两个元素结点的指针域即可。缺点：因为含有⼤量指针域，固占⽤空间⼤，查耗时。适⽤场景：数据量⼩，需频繁增加删除操作。
5）树：由n个有限节点组成⼀种具有层次关系的集合。⼆叉树（每个结点最多有两个⼦树，结点的度最⼤为2，左⼦树和右⼦树有顺序）、红⿊树（HashMap底层源码）、B+树（mysql的数据库索引结构）
6）散列表（哈希表）：根据键值对来存储访问。
7）堆：堆中某个节点的值总是不⼤于或不⼩于其⽗节点的值，堆总是⼀棵完全⼆叉树。
8）图：由结点的有穷集合V和边的集合E组成。
2、并发集合了解哪些？
1）并发List，包括Vector和CopyOnWriteArrayList是两个线程安全的List，Vector读写操作都⽤了同步，CopyOnWriteArrayList在写的时候会复制⼀个副本，对副本写，写完⽤副本替换原值，读时不需要同步。
2）并发Set，CopyOnWriteArraySet基于CopyOnWriteArrayList来实现的，不允许存在重复的对象。
3）并发Map，ConcurrentHashMap，内部实现了锁分离，get操作是⽆锁的。
4）并发Queue，ConcurrentLinkedQueue适⽤于⾼并发场景下的队列，通过⽆锁⽅式实现。 BlockingQueue阻塞队列，应⽤场景，⽣产者-消费者模式，若⽣产快于消费，⽣产队列装满时会阻塞，等待消费。
5）并发Deque, LinkedBlockingDueue没有进⾏读写锁分离，同⼀时间只能有⼀个线程对其操作。
6）并发锁重⼊锁ReentrantLock，互斥锁，⼀次最多只能⼀个线程拿到锁。
7）读写锁ReadWriteLock，有读取和写⼊锁两种，读取允许多个读取线程同时持有，⽽写⼊只能有⼀个线程持有。
3、列举java的集合以及集合之间的继承关系
5、容器类介绍以及之间的区别
1）Collection接⼝：集合框架的根接⼝，它是集合类框架中最具⼀般性的顶层接⼝。
2）Map接⼝：提供了键值对的映射关系的集合，关键字不能有重复值，每个关键字⾄多可映射⼀个值。HashMap(通过散列机制，⽤于快速访问)，TreeMap（保持key处于排序状态，访问速度不如hashmap）, LinkedHashMap(保持元素的插⼊顺序)
3）Set接⼝：可包含重复的元素，LinkedHashSet TreeSet(⽤红⿊树来存储元素) HashSet
4）List接⼝：可通过索引对元素进⾏精准的插⼊和查，实现类有ArrayList LinkedList
5）Queue接⼝：继承⾃Collection接⼝，LinkedList实现了Queue接⼝，提供了⽀持队列的⾏为。
6）Iterator接⼝：为了迭代集合
7）Comparable接⼝：⽤于⽐较
6、List,Set,Map的区别
Set是⼀个⽆序的集合，不能包含重复的元素；
list是⼀个有序的集合可以包含重复的元素，提供了按索引访问的⽅式；
map包含了key-value对，map中key必须唯⼀，value可以重复。
7、HashMap的实现原理
1）数据结构
jdk1.7及以前，HashMap由数组+链表组成，数组Entry是HashMap的主体，Entry是HashMap中的⼀个静态内部类，每⼀个Entry包含⼀个key-value键值对，链表是为解决哈希冲突⽽存在。
从jdk1.8起，HashMap是由数组+链表/红⿊树组成，当某个bucket位置的链表长度达到阀值8时，这个链表就转变成红⿊树。
2）HashMap是线程不安全的，存储⽐较快，能接受null值，HashMap通过put(key, value)来储存元素，通过get(key)来得到value值，通过hash算法来计算hashcode值，⽤hashcode标识Entry在bucket中存储的位置。
3）HashMap中为什么要使⽤加载因⼦，为什么要进⾏扩容
加载因⼦是指当HashMap中存储的元素/最⼤空间值的阀值，如果超过这个值，就会进⾏扩容。加载因⼦是为了让空间得到充分利⽤，如果加载因⼦太⼤，虽对空间利⽤更充分，但查效率会降低；如果加载因⼦太⼩，表中的数据过于稀疏，很多空间还没⽤就开始扩容，就会对空间造成浪费。
⾄于为什么要扩容，如果不扩容，HashMap中数组处的链表会越来越长，这样查效率就会⼤⼤降低。
7.1 HashMap如何put数据（从HashMap源码⾓度讲解）？
当我们使⽤put(key, value)存储对象到HashMap中时，具体实现步骤如下：
1）先判断table数组是否为空，为空以默认⼤⼩构建table，table默认空间⼤⼩为16
2）计算key的hash值，并计算hash&(n-1)值得到在数组中的位置index，如果该位置没值即table[index]为空，则直接将该键值对存放在
table[index]处。
3）如果table[index]处不为空，说明发⽣了hash冲突，判断table[index]处结点是否是TreeNode(红⿊树结点)类型数据，如果是则执⾏putTreeVal⽅法，按红⿊树规则将键值对存⼊；
4）如果table[index]是链表形式，遍历该链表上的数据，将该键值对放在table[index]处，并将其指向原index处的链表。判断链表上的结点数是否⼤于链表最⼤结点限制（默认为8），如果超过了需执⾏treeifyBin()操作，则要将该链表转换成红⿊树结构。
5）判断HashMap中数据个数是否超过了（最⼤容量*装载因⼦），如果超过了，还需要对其进⾏扩容操作。
7.2 HashMap如何get数据？
get(key)⽅法获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=table[hash&(n-1)]，先判断first（即数组中的那个）的key是否与参数key相等，不等的话，判断结点是否是TreeNode类型，是则调⽤getTreeNode(hash, key)从⼆叉树中查结点，不是TreeNode类型说明还是链表型，就遍历链表到相同的key值返回对应的value值即可。
7.3 当两个对象的hashcode相同，即发⽣碰撞时，HashMap如何处理
当两个对象的hashcode相同，它们的bucket位置相同，hashMap会⽤链表或是红⿊树来存储对象。Entry类⾥有⼀个next属性，作⽤是指向下⼀个Entry。第⼀个键值对A进来，通过计算其key的hash得到index，记做Entry[index]=A。⼀会⼜进来⼀个键值对B，通过计算其key的hash 也是index，HashMap会将B.next=A, Entry[index]=B.如果⼜进来C，其key的hash也是index，会将C.next=B, Entry[index]=C.这样bucket 为index的地⽅存放了A\B\C三个键值对，它们能过next属性链在⼀起。数组中存储的是最后插⼊的元素，其他元素都在后⾯的链表⾥。
7.4 如果两个键的hashcode相同，如何获取值对象？
当调⽤get⽅法时，hashmap会使⽤键对象的hashcode到bucket位置，到bucket位置后，会调⽤key.equals()⽅法去到链表中正确的节点，最终到值对象。
7.5 hashMap如何扩容
HashMap默认负载因为是0.75，当⼀个map填满了75%的bucket时，和其他集合类⼀样，将会创建原来HashMap⼤⼩两倍的bucket数组，来重新调整HashMap的⼤⼩，并将原来的对象放⼊新的bucket数组中。
在jdk1.7及以前，多线程扩容可能出现死循环。因为在调整⼤⼩过程中，存储在某个bucket位置中的链表元素次序会反过来，⽽多线程情况下可能某个线程翻转完链表，另外⼀个线程⼜开始翻转，条件竞争发⽣了，那么就死循环了。
⽽在jdk1.8中，会将原来链表结构保存⾄节点e中，将原来数组中的位置设为null，然后依次遍历e，根据hash&n是否为0分成两条⽀链，保存在新数组中。如果多线程情况可能会取到null值造成数据丢失。
8、ConcurrentHashMap的实现原理
1）jdk1.7及以前：⼀个ConcurrentHashMap由⼀个segment数组和多个HashEntry组成，每⼀个segment都包含⼀个HashEntry数组, Segment继承ReentrantLock⽤来充当锁⾓⾊，每⼀个segment包含了对⾃⼰的HashEntry的操作，如get\put\replace操作，这些操作发⽣时，对⾃⼰的HashEntry进⾏锁定。由于每⼀个segment写操作只锁定⾃⼰的HashEntry，可以存在多个线程同时写的情况。
jdk1.8以后：ConcurrentHashMap取消了segments字段，采⽤transient volatile HashEntry<K, V> tabl
e保存数据，采⽤table数组元素作为锁，实现对每⼀个数组数据进⾏加锁，进⼀⼩减少并发冲突概率。ConcurrentHashMap是⽤Node数组+链表+红⿊树数据结构来实现的，并发制定⽤synchronized和CAS操作。
2）Segment实现了ReentrantLock重⼊锁，当执⾏put操作，会进⾏第⼀次key的hash来定位Segment的位置，若该Segment还没有初始化，会通过CAS操作进⾏赋值，再进⾏第⼆次hash操作，到相应的HashEntry位置。
9、ArrayMap和HashMap的对⽐
1)存储⽅式不⼀样，HashMap内部有⼀个Node<K,V>[]对象，每个键值对都会存储到这个对象⾥，当⽤put⽅法添加键值对时，会new⼀个Node对象，tab[i] = newNode(hash, key, value, next);
ArrayMap存储则是由两个数组来维护，int[] mHashes; Object[] mArray; mHashes数组中保存的是每⼀项的HashCode值，mArray存的是键值对，每两个元素代表⼀个键值对，前⾯保存key，后⾯保存value。mHashes[index]=hash; mArray[index<<1]=key;
mArray[(index<<1)+1]=value;
ArrayMap相对于HashMap，⽆需为每个键值对创建Node对象，且在数组中连续存放，更省空间。
2）添加数据时扩容处理不⼀样，进⾏了new操作，重新创建对象，开销很⼤；⽽ArrayMap⽤的是copy数据，所有效率相对⾼些；
3）ArrayMap提供了数组收缩功能，在clear或remove后，会重新收缩数组，释放空间；
4）ArrayMap采⽤⼆分法查，mHashes中的hash值是按照从⼩到⼤的顺序连续存放的，通过⼆分查来获取对应hash下标index，去mArray中查键值对。mHashes中的index2是mArray中的key下标，index2+1为value的下标，由于存在hash碰撞情况，⼆分查到的下标可能是多个连续相同的hash值中的任意⼀个，此时需要⽤equals⽐对命中的key对象是否相等，不相等，应当从当前index先向后再向前遍历所有相同hash值。
5）sparseArray⽐ArrayMap进⼀步优化空间，SparseArray专门对基本类型做了优化，Key只能是可排序的基本类型，如int\long，对value，除了泛型Value，还对每种基本类型有单独实现，如SparseBooleanArray\SparseLongArray等。⽆需包装，直接使⽤基本类型值，⽆需hash，直接使⽤基本类型值索引和判断相等，⽆碰撞，⽆需调⽤hashCode⽅法，⽆需equals⽐较。SparseArray延迟删除。
10、HashTable实现原理
Hashtable中的⽆参构造⽅法Hashtable()中调⽤了this(11, 0.75f)，说明它默认容量是11，加载因⼦是0.75，在构造⽅法上会new HashtableEntry<?, ?>[initialCapacity]; 会新建⼀个容量是初始容量的HashtableEntry数组。HashtableEntry数组中包含

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。