1.集合
Collection
Map
红色的表示接口，黑色的表示实现类。
-
ArrayList 、 LinkedList 、 Vector 的底层实现和区别
ArrayList: -
jdk>=7: int newCapacity = oldCapacity + (oldCapacity >> 1);
jdk<7: int newCapacity = (oldCapacity * 3)/2 + 1;
android: int newSize=oldSize+newPartSize
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
- elementData的容量默认是10,android中是12
- 提前预知性的设置一个大容量，可减少扩容的次数，从而提高性能
- 容量不足时，再添加原来的一半大小(JDK=8)
- Android扩容：newSize=oldSize+newPartSize ToRead:ArrayList 扩容 Android Java 真的不一样
- ArrayList的克隆函数，即是将全部元素克隆到一个数组中
- insert的index越小，需要复制的数据越多。
- indexOf(Object o)从小到大遍历，match则返回索引，否则返回-1
- ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”
- 举个例子
oldSzie=20 addAll(newPart) newPartSize=50;
JDK 中 old+old>>1=35 35<70 newSize=70 ---> Size=70
Android中
20+50 ---->70 70-1=69>6--->69+34=103 size=103 - Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍
LinkedList
-
- Entry是双向链表节点所对应的数据结构
- LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用，且是基于双向循环链表实现的
- LinkedList的查找是通过二分（简单的一次二分），所以index所对应的元素越靠近中间所费时间越长
- Deque的操作
boolean add(E e); // 插入队尾，要么返回true，要么抛出异常
boolean offer(E e);//插入队尾，插入成功true，插入失败false，其它抛出异常E remove(); //移除队头元素，并返回，空队列抛出异常
E poll(); //移除队头元素，并返回，空队列返回nullE element(); //获取但不移除队列头的元素，空队列抛出异常
E peek(); //获取但不移除队列头的元素，空队列返回nullremoveFirstOccurrence(Object)：从此双端队列移除第一次出现的指定元素
removeLastOccurrence(Object)：从此双端队列移除最后一次出现的指定元素
- HashMap 和 HashTable 的底层实现和区别，两者和 ConcurrentHashMap 的区别。
|HashTable|HashMap|
| -----|:----:| ----:|
|线程安全|非线程安全|
|不允许null|允许null(key只允许一个取null)|
|效率低|效率高|
|sychronized|无sychronized|
|11,old*2+1|16,空间左移1位至不小于实际需要的长度|
HashMap:
-
Java集合干货系列-（三）HashMap源码解析
- 默认初始容量 (16) 、默认加载因子 (0.75)
- modCount是用来实现fail-fast机制的(fail-fast:在使用迭代器的过程中有其他线程修改了map，会抛出ConcurrentModificationException——modCount到底是干什么的呢
- threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
- 扩容的时候将对每个元素全部重新计算index，而不是简单的把原table对应index位置元素简单的移动到新table对应位置
- HashMap线程安全化：
Map hashMap = new HashMap();
hashMap = Collections.synchronizedMap(hashMap);
Collections.synchronizedXXX:
对hashMap的操作全部重新封装，帮我们在操作HashMap时自动添加了synchronized来实现线程同步
- Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
- HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
ConcurrentHashMap
jdk<= 7 : ConcurrentHashMap 的结构示意图
-
Segment的个数是大于等于concurrencyLevel的第一个2的n次方的数
-
ConcurrentHashMap是基于lock操作，lock锁住的不是对象整体。
要填的坑：jdk=8:基于CAS算法 （乐观锁的应用） -
ConcurrentHashMap基于concurrentLevel划分出多个Segment来对key-value进行存储，从而避免每次锁定整个数组，在默认的情况下，允许16个线程并发无阻塞的操作集合对象，尽可能地减少并发是的阻塞现象。
悲观锁
lock();
some operation;
unlock();
乐观锁
do{
expected = resource；//获取一次预期值
some operation;
}while(resource == expected && 进行resource访问);
//while条件=如果实际值和预期值一样说明这期间没有其他人访问，则可以对资源进行修改
- HashMap 的 hashcode 的作用？什么时候需要重写？如何解决哈希冲突？查找的时候流程是如何？
- hashcode是用来查找的
- 当equals方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。（想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写hashcode()来找到桶，光重写equals()有什么用啊 ）
Arraylist 和 HashMap 如何扩容？负载因子有什么作用？如何保证读写进程安全？
略
TreeMap 、 HashMap 、 LinkedHashMap 的底层实现区别。
Collection 包结构的组成， Map 、 Set 等内部接口的特点与用法。
**2 ** **并发 **（ Executor 框架和多线程基础）：
Thread 与 Runable 如何实现多线程
线程同步的方法有什么；锁， synchronized 块，信号量等
锁的等级：方法锁、对象锁、类锁
生产者消费者模式的几种实现，阻塞队列实现， sync 关键字实现， lock 实现等
ThreadLocal 的设计理念与作用， ThreadPool 用法与优势（这里在 Android SDK 原生的 AsyncTask 底层也有使用）
线程池的底层实现和工作原理（建议写一个雏形简版源码实现）
几个重要的线程 api ， interrupt ， wait ， sleep ， stop 等等
**3 ** ** IO **（ IO,NIO ，目前 okio 已经被集成 Android 包）
IO 框架主要用到什么设计模式
NIO 包有哪些结构？分别起到的作用？
NIO 针对什么情景会比 IO 有更好的优化？
OKIO 底层实现
**4 ** **其他的 java ****语言特性 **：
反射机制
String 类内部实现，能否改变 String 对象内容，比较经典的 String 字面量笔试题
Object 有哪些公用方法？
try catch 块， try 里有 return ， finally 也有 return ，如何执行这类型的笔试题
Exception 与 Error 的区别
泛型的优缺点
另外就是关注最新版本 jdk 的新特性，例如 Lambda 表达式
**5 ** JVM
自动内存管理机制， GC 算法，运行时数据区结构，可达性分析工作原理，如何分配对象内存
类加载机制，反射机制，双亲委派机制，类加载器的种类
Jvm 内存模型，先行发生原则， violate 关键字作用
网友评论