摘要:
最近在整理Android岗位面试题的答案,虽然工作已有两年,独立开发了好几个APP,但在不查资料的情况下,回答这些试题非常的困难,瞬间感觉一万点伤害。即使不为了找工作,整理这样一份Android面试题答案,也可以加深对各个知识点的理解,这一整套面试题基于《最全的BAT大厂面试题整理》,然后将每一个分类拆分成附带参考答案的独立的文章,在此非常感谢整理试题的原作者。
Android学习笔记九:Java线程、多线程和线程池(27号更新)
Note that:文章中给出的答案尽管参考了网上的很多资料,但肯定回答得还不够到位,更需要在实际的环境中运用、验证(有木有推荐岗位哈)
- 常用数据结构简介
常用的数据结构有:数组、链表、栈、队列、散列、树
- 并发集合了解哪些?
常用并发集合 | 举例 |
---|---|
并发List | Vector、CopyOnWriteArrayList |
并发Set | CopyOnWriteArraySet、ConcurrentSkipListSet |
并发Queue | ArrayBlockingQueue、ConcurrentLinkedQueue、LinkedBlockingQueue、LinkedTransferQueue、PriorityBlockingQueue、SynchronousQueue |
并发Deque | ConcurrentLinkedDeque、LinkedBlockingDeque |
详情:
Vector和CopyOnWriteArrayList是线程安全的。
区别:
Vector给每个方法添加了synchronized同步锁,保证多个线程同时访问add()
、get()
、remove()
等方法的安全,但不保证遍历的线程安全(即一个线程遍历,另外一个线程执行添加、删除或其他),为了保证遍历的安全,需要给遍历的Vector对象添加同步锁
CopyOnWriteArrayList的实现原理,每个线程访问的是CopyOnWriteArrayList的一个副本,最后将原对象引用指向最后的CopyOnWriteArrayList的地址,保证线程安全
如何线程安全地遍历List:Vector、CopyOnWriteArrayList
https://www.cnblogs.com/wucao/p/5350461.html
CopyOnWriteSet的实现原理和CopyOnWriteArrayList一样,通过对副本进行访问,最后将引用指向该地址
Queue和Deque,前者是普通的队列,后者是双端的队列,双端队列是指队列的头部(或尾部)可以进行入队操作和出队操作
Java中的queue和deque
http://blog.csdn.net/shf4715/article/details/47052385
- 列举java的集合以及集合之间的继承关系
List集合
ArrayList集合:
LinkedList集合:
Vector集合
Map集合
HashMap集合:
LinkedHashMap集合:
TreeMap集合
HashTable集合
Properties集合
备注:Properties
和HashTable
是Map接口的历史属性
Set集合
HashSet集合
LinkedHashSet集合
TreeSet集合
Queue集合
PriorityQueue集合
- 集合类以及集合框架
Deque集合
ArrayDeque集合
Collection体系
Map体系
Java集合类详解
http://blog.csdn.net/u014136713/article/details/52089156
- 容器类介绍以及之间的区别
Java容器类
http://alexyyek.github.io/2015/04/06/Collection/
- List,Set,Map的区别
Set集合
不允许存储a.equlas(b)
两个相同的对象,否则,后存储的对象会代替已存在的对象
List集合
允许存储a.equals(b)
两个相同的对象,同时允许存储多个null值,可以根据元素的整型索引快速访问元素
除了具备Set集合提供的方法外(Set、List都继承自Collection接口),还添加了多个根据索引访问、修改元素的方法
Map集合
不允许存储重复的键,同时不允许将自身对象作为键存储,但允许将自身对象作为值存储
- List和Map的实现方式以及存储方式
ArrayList,以数组表的方式存储数据,允许存储相同的对象,方便快速地通过索引查询
LinkedList,以链表的方式存储数据,允许存储相同的对象,适合频繁地插入、删除操作
Vector,除了支持同步操作外,和ArrayList基本一样
HashMap,以分散数组表的方式存储数据,不允许存储键相同的对象,同时也不允许将自身对象作为键存储,但可以将自身对象作为值存储,也可以存储值相同的对象
LinkedHashMap,以分散链表的方式存储数据,继承自HashMap,优化了数据的插入、删除操作
TreeMap,以二叉查找树的方式存储数据,除了具备Map集合的特点外,TreeMap还对存储的数据进行排序
List、Map、Set按存储方式说说都是怎么存储的?
http://blog.csdn.net/Mr_linjw/article/details/51335490几种 Map 内部存储方式的介绍( 以 Java 为例讲解 )
http://blog.csdn.net/weixinzhang/article/details/50614438
- HashMap的实现原理
为了提高查询的效率和减少空间的浪费,初始化HashMap的容量大小必须是2的n次方
尽量避免扩充容量,防止扩容对性能造成影响。扩容后的HashMap,需要重新计算已存在数据的在新数组中的位置,扩容后的大小是原来的两倍
默认负载因子0.75,是对时间和空间的平衡选择
快速失败策略,HashMap不是线程安全的,在进行迭代的时候有其他线程修改了map,会抛出ConcurrentModificationException
HashMap,是一种数组+链表的存储方式,对数据进行迭代需要遍历两次
第一种
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
效率高,以后一定要使用此种方式!
第二种
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
效率低,以后尽量少使用!
- HashMap数据结构?
是一个数组+链表的数据结构,内部定义了一个Entry数组,数组中的每一项又是一个链表
- HashMap源码理解
根据实际存储数据的长度,初始化HashMap容量,初始化的容量大小必须是2的n次方,尽量避免扩充容量
默认HashMap的初始化容量为16,负载因子为0.75,它是对时间和空间的平衡选择
快速失败策略,HashMap是非线程安全的,对数据进行迭代的时候其他线程试图修改map,会抛出ConcurrentModificationException异常
- HashMap如何put数据(从HashMap源码角度讲解)?
public V put(K key, V value) {
// HashMap允许存放null键和null值。
// 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据key的keyCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值在对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果i索引处的Entry为null,表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
添加到HashMap中的数据,先判断key值是否为null,key值为null直接将value值放置在数组的第一个位置
否则,计算key值的hashCode,同时定位数组中的位置,如果该hashCode已存在,那么将value值添加到该位置的链表上;否则,直接将value值添加到数组上
HashMap的实现原理
http://www.importnew.com/16301.html
- HashMap怎么手写实现?
public class HashMap<K,V>{
static HashMapEntry<K,V> implement Map.Entry<K,V>{
K key;
V value;
HashMapEntry<K,V> next;
int hash;
...
}
int DEFUALT_CAPACITY=16;//定义默认的容量大小
int DEFUALT_LOAD_FACTOR=0.75;//定义默认的加载因子
static final HashMapEntry<?,?> EMPTY_TABLE={};//定义默认的空数组
HashMapEntry<K,V>[] table=(HashMapEntry<K,V>[])EMPTY_TABLE;
public HashMap<K,V>(int capacity,int loadFactor){
this.DEFAULT_CAPACITY=capacity;
this.DEFAULT_LOAD_FACTOR=loadFactor;
if(table==EMPTY_TABLE){
table=new HashMapEntry[DEFAULT_CAPACITY*DEFAULT_LOAD_FACTOR];
}
}
public V put(K key,V value){
//计算key对应的hash值
int hash=key.hashCode();
int i=indexFor(hash,table.length);
//判断是否存在相同的key,存在,则覆盖
for(HashMapEntry<K,V> e=table[index];e!=null;e=e.next){
if(e.hash==hash&&(e.key==key||e.key.equals(key))){
int oldValue=e.value;
e.value=value;//覆盖旧value
return oldValue;
}
}
addEntry(hash,key,value,i);
return null;
}
int indexFor(int hash,int length){
return hash& (length-1);
}
void addEntry(int hash,V key,V value,int index){
...
}
}
- ConcurrentHashMap的实现原理
除了具备HashMap的特点外,ConcurrentHashMap是线程安全的,采用的是分段锁技术,比其他同步锁的方式(HashTable
、Collections.synchronizedMap()
)性能更高
分段锁技术,指的是ConcurrentHashMap加锁的是Map.Entry对象,在JDK_1.8.0_51版本,使用的是synchronized同步代码块,由JVM自动添加并释放锁;而在其它JDK版本也有使用Lock方式的
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
...
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;//Node继承自Map.Entry
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
...
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//使用synchronized同步代码块,加锁的是Node对象
synchronized (f) {
if (tabAt(tab, i) == f) {
...
}
}
...
}
}
addCount(1L, binCount);
return null;
}
http://www.importnew.com/16142.html
ConcurrentHashMap实现原理
http://blog.csdn.net/dingji_ping/article/details/51005799
- ArrayMap和HashMap的对比
ArrayMap的数据存储方式,使用的是两个小数组,一个数组按顺序存储key对应的hash值,一个数组根据key的顺序存储key-value值,查询的时候在第一个数组中获取hash值的索引,再由索引在后一个数组获取value值
HashMap的数据存储方式,使用的是数组+链表,根据key对应的hash值检索数组是是否存在对应的value值,如果不存在,直接将value存储到索引所在位置;如果存在,将放置在该位置的链表头部
区别:
ArrayMap数据的访问速度比HashMap更快,适合应用在数据量不多(1000以内),访问操作频繁,插入和删除较少的场景
- HashTable实现原理
HashTable,是以数组+链表的方式存储数据,数组存储的是key对应的hash值
HashTable的方法是同步的,说明它是线程安全的,继承自Dictionary,实现Map接口
HashTable默认容量大小为11,默认加载因子为0.75(分析JDK1.8_)
HashTable的key、value都不可以为null
Java 集合系列11之 Hashtable详细介绍(源码解析)和使用示例
http://www.cnblogs.com/skywang12345/p/3310887.html
- TreeMap具体实现
...
红黑树数据结构剖析
http://www.cnblogs.com/fanzhidongyzby/p/3187912.html红黑树系列集锦
http://blog.csdn.net/v_JULY_v/article/category/774945Java提高篇(二七)-----TreeMap
http://blog.csdn.net/chenssy/article/details/26668941
- HashMap和HashTable的区别
HashMap、HashTable存储数据的方式是一样的,都是数组+链表的方法
HashMap允许key、value为null,如果key为null,直接将value存储到数组的第一个位置;HashTable不允许key、value为null,如果value为null,抛出NullPointException异常
HashMap是非线程安全的;HashTable相关方法添加了synchronized同步锁,是线程安全的
HashMap快速失败机制,在遍历数据的时候其它线程试图修改、删除HashMap数据,会抛出ConcurrentModificationException异常
- HashMap与HashSet的区别
数据结构不一样。HashMap是以数组+链表的方式存储数据,数组存储的是HashEntry实体,每个HashEntry实体保存key和value,同时持有指向下一个元素的引用next;
HashSet的内部实现,实例化一个HashMap对象,将要存储的数据作为HashMap对象的key,将一个固定Object对象PRESENT
作为value
HashMap中不允许重复的键;HashSet不允许存储相同的对象,如果存储两个相同的对象,后存储的对象会覆盖已存储的对象
HashMap继承自AbstractMap,实现Map接口;HashSet继承自AbstractSet,实现Set接口
HashMap和HashSet的区别
http://www.importnew.com/6931.html
- HashSet与HashMap怎么判断集合元素重复?
比较集合中是否存在当前对象的hash值,如果已存在,再通过equals方法比较两个对象是否相同,如果hash值一样同时equals比较相同,则判断它们是重复的元素
所以,存储到HashSet和HashMap集合中的元素重写equals方法的同时需要重写hasCode方法,否则使用默认的equals方法和hashCode方法
- 集合Set实现Hash怎么防止碰撞
出现碰撞的原因,是因为存储到Set集合的对象定位到Entry数组相同的位置数组的index由存储对象的hash值和数组的length长度决定,即index=hash & (length-1)
优化过的hash值和2的n次方的length长度,使得元素的分布更加的均匀,发生碰撞的几率减少,从而有效地防止碰撞
- ArrayList和LinkedList的区别,以及应用场景
ArrayList继承自AbstractList,实现List接口、RandomAccessFile接口,以数组的方式存储数据
LinkedList继承自AbstractSequentialList,实现List接口、Deque接口,以链表的方式存储数据
数组的方式存储数据,方便快速查询元素,适合应用于查询多,删除和插入较少的场景
链表的方式存储数据,删除和删除元素时,不需要移动元素的位置,性能方面比ArrayList更优,适合应用于删除和插入较多的场景
- 数组和链表的区别
数组的方式存储数据,元素在内存中是连续存放,可以通过下标快速访问数组中任一元素,当插入或删除一个元素时,需要移动大部分的元素
链表的方式存储数据,元素在内存中不是顺序存放,一个元素持有下一个元素的引用,将指针指向下一个元素,依次类推,当查询元素时,需要依次遍历链表中的各个元素
- 二叉树的深度优先遍历和广度优先遍历的具体实现
深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。以上面二叉树为例,深度优先搜索的顺序为:ABDECFG。怎么实现这个顺序呢?深度优先搜索二叉树是先访问根结点,然后遍历左子树接着是遍历右子树,因此我们可以利用堆栈的先进后出的特点,现将右子树压栈,再将左子树压栈,这样左子树就位于栈顶,可以保证结点的左子树先与右子树被遍历。
public static void print(BinaryTreeNode node){
System.out.println(node.value);
}
public static void preOrder(BinaryTreeNode node){
if(node!=null{
print(node)
preOrder(node.left);
preOrder(node.right);
}
}
广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索,是从根结点开始沿着树的宽度搜索遍历,上面二叉树的遍历顺序为:ABCDEFG.
可以利用队列实现广度优先搜索
public static void levelOrderTranversal(BinaryTreeNode root){
Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
if(root!=null){
queue.add(root);
while(!queue.isEmpty){
BinaryTreeNode node=queue.poll();
print(node);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
}
}
树的深度优先遍历和广度优先遍历的原理和java实现代码
http://outofmemory.cn/code-snippet/4189/biinary-tree-java
二叉树的广度优先遍历、深度优先遍历的递归和非递归实现方式
https://www.cnblogs.com/gl-developer/p/7259251.html
- 堆的结构
堆的结构,是一颗完全二叉树
完全二叉树,是指除底层外,其余各层任意节点的子节点数都达到了最大数,底层的所有节点都连续集中在左边
基本数据结构——堆(Heap)的基本概念及其操作
https://www.cnblogs.com/JVxie/p/4859889.html
- 堆和树的区别
将满足结构性的树称为堆,堆也可以说是一种树
结构性,指的是除底层外,其余各层任意节点的节点数都达到了最大数,底层的所有节点都连续集合中左边
二叉堆,指的是满足堆的结构性,同时任意节点的值小于其所有子节点的值
- 堆和栈在内存中的区别是什么
堆,是jvm管理的最大一块内存,同时也是Java GC主要的区域,堆是用来存储对象实例和数组值,所有线程共享
栈,分为Native方法栈和JVM 栈,前者主要是存储Native方法的状态;后者是线程私有的,每个方法在调用的时候,都会创建一个栈帧,栈帧存储有局部变量等信息,方法被调用时,栈帧被压入JVM栈中,方法执行完成,栈帧出栈
JVM内存管理及GC机制
http://blog.csdn.net/suifeng3051/article/details/48292193
- 什么是深拷贝和浅拷贝
深拷贝也叫深克隆,将原对象的所有字段拷贝到副本中。不可是原对象的值类型字段,还是引用类型字段,在副本中都会被重新的创建并赋值,对副本值类型字段或引用类型字段的修改不会影响原类型,实现Cloneable接口,覆盖close方法
浅拷贝也叫浅克隆,将原对象的所有字段拷贝到副本中,对副本中值类型字段的修改不会影响原类型,但对副本中引用类型字段的修改会影响原类型,实现Cloneable接口,重写close方法
Java中的深拷贝和浅拷贝
http://blog.csdn.net/chjttony/article/details/7477346
- 手写链表逆序代码
public static Node reverseSingleList(Node node){
Node p1,p2=null;
p1=node;//记录node节点本身地址
while(node.next!=null){
p2=node.next;//记录node节点引用地址
node.next=p2.next;//记录新节点持有的引用地址
p2.next=p1;//改变指针指向
p1=p2;//记录新的节点本身地址
}
return p2;
}
java 实现单链表的逆序
http://blog.csdn.net/u012571415/article/details/46955535Java单链表的逆序
http://blog.csdn.net/wxm349810930/article/details/46724691链表逆序(JAVA实现)
https://www.cnblogs.com/jsczljh/p/3765720.html
- 讲一下对树,B+树的理解
树是一种由一个根节点和无数个子节点组成的数据结构,除根节点外,每一个子节点都拥有一个父节点和无数个子节点,常用的树的集合有TreeMap、TreeSet
B+树是其中一种...
从B树、B+树、B*树谈到R 树
http://blog.csdn.net/v_july_v/article/details/6530142B树和B+树的总结
https://www.cnblogs.com/George1994/p/7008732.html在线可视化树操作
https://www.cs.usfca.edu/~galles/visualization/BTree.html
- 讲一下对图的理解
...
- 判断单链表成环与否?
public class SingleList{
static class Node {
int value;
Node next;
public Node(int i){
this.value=i;
}
}
/**
*创建一条单链表
*@params head 表示单链表开始位置
*@params length 表示单链表的长度
*/
public Node createSingleList(Node head,int length){
if(head==null){
return null;
}
Node p1=head;//记录开始的内存地址
int i=0;
while(i<length){
Node node=new Node(i);
p1.next=node;//记录持有的引用地址
p1=node;//移动指针到下一个节点
i++;
}
return head;//返回开始的列表地址
}
/**
*判断一条单链表是否成环
*@params node 传入的单链表
*@return 成环,返回true;否则,返回false
*/
public boolean loopSingleList(Node node){
if(node==null||node.next==null){
return false;
}
Node p1,p2;//定义两个节点记录指针开始位置
p1=node;//指针p1每次向前移动一步
p2=node;//指针p2每次向前移动两步
Node last;
while((last=p2.next)!=null&&last.next!=null){
p1=p1.next;
p2=last.next;
//不断移动之后,找到两个地址一样的节点
if(p1==p2){
return true;
}
}
return false;
}
}
面试算法:链表成环的检测
https://www.jianshu.com/p/6ff4f6cef1d0判断单链表是否成环算法
http://blog.csdn.net/fu908323236/article/details/78205462
- 链表翻转(即:翻转一个单项链表)
pulibc void reverseSingleList(Node head){
Node p1,p2=null;
p1=head;//记录节点内存地址
while(head.next!=null){
p2=head.next;//记录节点持有的引用地址
head.next=p2.next;//记录下一个节点持有的引用地址
p2.next=p1;//改变节点的指针指向
p1=p2;//记录下一个节点内存地址
}
return p2;
}
- 合并多个单有序链表(假设都是递增的)
思路:依次比较两个有序单链表,将较小的单链表的节点提取出来,组成一个新链表,最后将没有遍历结束的链表的引用赋值给新链表
public static Node mergeSingleListOrdered(Node firstSingleListOrdered,Node secondSingleListOrdered){
Node p1=firstSingleListOrdered;
Node p2=secondeSingleListOrdered;
if(p1==null){
return p2;
}else if(p2==null){
return p1;
}
Node newHead=null;
if(p1.value<p2.value){
newHead=p1;//记录新链表开始位置
newHead.next=mergeSingleListOrdered(p1.next,p2);
}else{
newHead=p2;//新链表开始位置
newHead.next=mergeSingleListOrdered(p1,p2.next);
}
return newHead;
}
合并两个有序递增的链表,使得合并后新链表还是有序的
http://blog.csdn.net/jcm666666/article/details/52280623参考资料:《最全的BAT大厂面试题整理》
你可能感兴趣的文章
转载请注明出处: https://www.teachcourse.cn/2609.html ,谢谢支持!