大数据面试题-JavaSE

1、String是字符串常量， StringBuffer、StringBuilder是字符串变量

2、StringBuffer线程安全(方法用了synchronized修饰)、StringBuilder线程不安全

3、底层都是char[]，String用了final 修饰，后二者初始容量是16+字符串的长度，追加前都会检查是否应该扩容，扩容原则 newCapacity-(oldCapacity*2+2)>0 ? newCapacity : oldCapacity*2+2

1、Set 无序去重 ,List 有序可重复

2、HashMap线程不安全，允许有null的键和值

Hashtable线程安全（方法用了synchronized修饰），不允许有null的键和值

3、Vector 线程安全（方法用了synchronized修饰）

ArrayList、LinkedList线程不安全

ArrayList:底层数据结构是数组，查询快，增删慢

LinkedList:底层数据结构是链表，查询慢，增删快

字节流：

InputStream、FileInputStream、 BufferedInputStream

OutputStream、FileOutputStream、 Buffered Out putStream

字符流：

FileReader、BufferedReader、InputStreamReader

FileWriter、PrintWriter、OutputStreamWriter

JAVA反射机制是在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意一个方法和属性；这种动态获取的信息以及动态调用对象的方法的功能称为java语言的反射机制；

gc即垃圾收集机制是指jvm用于释放那些不再使用的对象所占用的内存。java语言并不要求jvm有gc，也没有规定gc如何工作。不过常用的jvm都有gc，而且大多数gc都使用类似的算法管理内存和执行收集操作。

?垃圾收集的目的在于清除不再使用的对象。gc通过确定对象是否被活动对象引用来确定是否收集该对象。gc首先要判断该对象是否是时候可以收集。两种常用的方法是引用计数和对象引用遍历。

1.引用计数

引用计数存储对特定对象的所有引用数，也就是说，当应用程序创建引用以及引用超出范围时，jvm必须适当增减引用数。当某对象的引用数为0时，便可以进行垃圾收集。

2.对象引用遍历

早期的jvm使用引用计数，现在大多数jvm采用对象引用遍历。对象引用遍历从一组对象开始，沿着整个对象图上的每条链接，递归确定可到达（reachable）的对象。如果某对象不能从这些根对象的一个（至少一个）到达，则将它作为垃圾收集。在对象遍历阶段，gc必须记住哪些对象可以到达，以便删除不可到达的对象，这称为标记（marking）对象。

下一步，gc要删除不可到达的对象。删除时，有些gc只是简单的扫描堆栈，删除未标记的未标记的对象，并释放它们的内存以生成新的对象，这叫做清除（sweeping）。这种方法的问题在于内存会分成好多小段，而它们不足以用于新的对象，但是组合起来却很大。因此，许多gc可以重新组织内存中的对象，并进行压缩（compact），形成可利用的空间。

为此，gc需要停止其他的活动活动。这种方法意味着所有与应用程序相关的工作停止，只有gc运行。结果，在响应期间增减了许多混杂请求。另外，更复杂的gc不断增加或同时运行以减少或者清除应用程序的中断。有的gc使用单线程完成这项工作，有的则采用多线程以增加效率

常见垃圾回收算法：标记-清除、复制、标记-整理、分代收集

加载、验证、准备、 解析、 初始化 。

一、类加载机制中的第一步加载。

在这个阶段，JVM主要完成三件事：

1、通过一个类的全限定名（包名与类名）来获取定义此类的二进制字节流（Class文件）。

2、将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构。

3、在内存中生成一个代表这个类的java.lang.Class对象，

二、类的连接

类的加载过程后生成了类的java.lang.Class对象，

接着会进入连接阶段，连接阶段负责将类的二进制数据合并入JRE（Java运行时环境）中。

类的连接大致分三个阶段。

1、验证：验证被加载后的类是否有正确的结构，

2、准备：为类的静态变量（static filed）在方法区分配内存，并赋默认初值。

3、解析：将类的二进制数据中的符号引用换为直接引用。

三、类的初始化。

类的初始化的主要工作是为静态变量赋程序设定的初值。

自动作业处理：比如定期备份日志、数据库什么的。

页面异步处理：比如大批量数据的核对工作。（有10W个手机号码，核对那些是已有用户）

数据库的数据分析（待分析的数据太多）、迁移等。

多步骤任务的处理，可根据步骤特征选用不同个数和特征的线程来协作处理。

这些大多用在后台服务程序里面。Swing编程有时也能用到。

并发控制，一般采用线程池技术。

线程同步，则越简单越好。

线程安全在三个方面体现1.原子性 2.可见性 3.有序性

1.原子性：提供互斥访问，同一时刻只能有一个线程对数据进行操作

???Java中提供了很多atomic类，AtomicInteger，AtomicLong，AtomicBoolean等 。

???JDK 提供了两种锁：Synchronized是一种同步锁，通过锁实现原子操作，修饰的对象有四种：（1）修饰代码块（2）修饰方法（3）修饰静态方法（4）修饰类。另一种是LOCK，是JDK提供的代码层面的锁。

2.可见性：一个线程对主内存的修改可以及时的被其他线程看到

对于可见性，JVM提供了synchronized和volatile.

volatile的可见性是通过内存屏障和禁止重排实现的，volatile会在写操作时，在写操作后加一条store屏障指令，将本地内存中给共享变量值刷新到主内存。

Volatile在进行读操作时，会在读操作前加一条load指令，从内存中读取共享变量。

但是volatile不是原子性操作，对++操作不是安全的，不适合计数。Volatile适用于状态标记量。

3.有序性：一个线程观察其他线程中的指令执行顺序，由于指令重排序，改观察结果一般杂乱无序。可以通过volatile、synchronized、lock保证有序性。

??Happens-before原则：

(1)程序次序规则：在一个单独的线程中，按照程序代码书写的顺序执行

(2)锁定规则：一个unlock操作happen-before后面对同一个锁的lock操作

(3)Volatile变量规则：对一个volatile变量的血操作happen-befor后面对该变量的读操作

(4)线程启动规则：Tread对象的start()方法happen-before此线程的每一个动作

(5)线程终止规则：线程的所有操作都happen—before对此线程的终止检测，可以通过Thread.join()方法结束、Thread.isAlive()的返回值等手段检测到线程已经终止执行。

(6)线程中断规则：对线程interrupt()方法的调用happen—before发生于被中断线程的代码检测到中断时事件的发生。

(7)对象终结规则：一个对象的初始化完成（构造函数执行结束）happen—before它的finalize()方法的开始。

(8)传递性：如果操作A happen—before操作B，操作B happen—before操作C，那么可以得出A happen—before操作C。

所谓的保证每次读取的数据都是最新的，即需要保证多线程之间的数据一致性。JVM通过程序正确同步来保证数据一致性

当程序未正确同步时，就会存在数据竞争。java内存模型规范对数据竞争的定义如下：

?在一个线程中写一个变量

?在另一个线程读同一个变量

?而且写和读没有通过同步来排序

当代码中包含数据竞争时，程序的执行往往产生违反直觉的结果（Java指令重排序 这篇文章里的代码正是如此）。如果一个多线程程序能正确同步，这个程序将是一个没有数据竞争的程序。

JVM对正确同步的多线程程序的内存一致性做了如下保证：

?如果程序是正确同步的，程序的执行将具有顺序一致性（sequentially consistent）—-即程序的执行结果与该程序在顺序一致性内存模型中的执行结果相同。

这里的同步是指广义上的同步，包括对常用同步原语（lock，volatile和final）的正确使用。

对于未同步或未正确同步的多线程程序，JVM只提供最小安全性：线程执行时读取到的值，要么是之前某个线程写入的值，要么是默认值（0，null，false），JVM保证线程读操作读取到的值不会无中生有（out of thin air）的冒出来。

为了实现最小安全性，JVM在堆上分配对象时，首先会清零内存空间，然后才会在上面分配对象（JVM内部会同步这两个操作）。因此，在以清零的内存空间（pre-zeroed memory）分配对象时，域的默认初始化已经完成了。

JVM不保证未同步程序的执行结果与该程序在顺序一致性模型中的执行结果一致。因为未同步程序在顺序一致性模型中执行时，整体上是无序的，其执行结果无法预知。保证未同步程序在两个模型中的执行结果一致毫无意义。

和顺序一致性模型一样，未同步程序在JVM中的执行时，整体上也是无序的，其执行结果也无法预知。

产生死锁必须同时满足以下四个条件,只要其中任一条件不成立,死锁就不会发生.通常破坏循环等待是最有效的方法。

?

互斥条件：线程要求对所分配的资源进行排他性控制,即在一段时间内某 资源仅为一个进程所占有.此时若有其他进程请求该资源.则请求进程只能等待.

不剥夺条件：进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的线程自己来释放（只能是主动释放).

请求和保持条件：线程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他线程占有,此时请求线程被阻塞,但对自己已获得的资源保持不放.

循环等待条件：存在一种线程资源的循环等待链,链中每一个线程已获得的资源同时被链中下一个线程所请求。

设计模式 一共有23种，这些设计模式又分为三类：创建型模式、结构型模式、行为性模式

创建型模式：工厂模式、抽象工厂模式、单列模式、建造者模式。原型模式

结构型模式：适配器模式、桥接模式、过滤器模式、组合模式、装饰器模式、外观模式、享元模式、代理模式

行为性模式：责任链模式、命令模式、解释器模式、迭代器模式、中介者模式、备忘录模式、观察者模式、状态模式、空对象模式、策略模式、模板模式、访问者模式

常用的设计模式：单例模式、工厂模式、策略模式、观察者模式、装饰者模式等

?

动态代理的作用 ：主要用来做方法的增强，在不改变源码的情况下，对方法的功能进行增强。

动态代理的实现 ：1、JDK实现动态代理（基于接口） ?2、cglib动态代理（基于基础）

二分查找：

public ? static ? int ?biSearch( int ?[]array, int ?a){

???????? int ?lo=0;

???????? int ?hi=array.length-1;

???????? int ?mid;

???????? while (lo<=hi){

????????????mid=(lo+hi)/2;

???????????? if (array[mid]==a){

???????????????? return ?mid+1;

????????????} else ? if (array[mid]<a){

????????????????lo=mid+1;

????????????} else {

????????????????hi=mid-1;

????????????}

????????}

???????? return ?-1;

????}

冒泡：

public ? static ? int [] bubble( int [] array) {

for ?( int ?i = 0; i < array.length - 1; i++) {

for ?( int ?j = 0; j < array.length - 1 - i; j++) {

if ?(array[j] > array[j + 1]) {

int ?temp = array[j];

array[j] = array[j + 1];

array[j + 1] = temp;

}

}

}

return ?array;

}

快排：

public static int getIndex(int[] arr,int left,int right){

//找一个基准点 ?nlog(n) ?冒泡排序：n^2

int key= arr[left];

//int left=0; ?//初始的左循环的下标

//int right=arr.length-1; ?//初始的右循环的下标

while(left<right){//循环嵌套 ?外层循环一次 ?内层循环所有

//从右向左循环 ?循环条件 ???大 ??不变 ???小 ?交换

while(arr[right]>=key&&left<right){

right--;

}

//出了循环 ?证明arr[right]<key ?交换

arr[left]=arr[right];//arr[right]=key

//从左向右循环 ??小 ??大 交换

while(arr[left]<=key&& left<right){

left++;

}

//出了这个循环arr[left]>key

arr[right]=arr[left];

}

//出了外层循环 ??left=right

//给分界点位置赋值

arr[left]=key;

return left;

}

//排序过程

public static void QuickSort(int[] arr,int left,int right){

//出口

if(left>=right){

return;

}

//找分界点的 ?下标

int index=getIndex(arr, left, right);

//以下标为分界进行左侧 ?右侧分别排序 ??递归调用的过程

//先对左侧进行排序

QuickSort(arr, left, index-1);

//对右侧进行排序

QuickSort(arr, index+1, right);

?

}

public class Singleton{

?private static Singleton instance;

?private Singleton(){}

?public static synchronized Singleton getInstance(){

??if(instance==null){

???instance=new Singleton();

??}

?return instance;

?}

}

快速排序也是分治法思想的一种实现，他的思路是使数组中的每个元素与基准值（Pivot，通常是数组的首个值，A[0]）比较，数组中比基准值小的放在基准值的左边，形成左部；大的放在右边，形成右部；接下来将左部和右部分别递归地执行上面的过程：选基准值，小的放在左边，大的放在右边。。。直到排序结束。

?

步骤：

1.找基准值，设Pivot = a[0]

2.分区（Partition）：比基准值小的放左边，大的放右边，基准值(Pivot)放左部与右部的之间。

3.进行左部（a[0] - a[pivot-1]）的递归，以及右部（a[pivot+1] - a[n-1]）的递归，重复上述步骤。

public class OneMoney2 {

?public static void main(String[] args) {

??int a, b, c, d, e, f, j;

??int n = 0;

??for (a = 0; a < 2; a++) {

???for (b = 0; b <= (100 - 100 * a) / 50; b++) {

????for (c = 0; c <= (100 - 50 * b) / 20; c++) {

?????for (d = 0; d <= (100 - 50 * b - 20 * c) / 10; d++) {

??????for (e = 0; e <= (100 - 50 * b - 20 * c - 10 * d) / 5; e++) {

???????for (f = 0; f <= (100 - 50 * b - 20 * c - 10 * d - 5 * e) / 2; f++) {

????????for (j = 0; j <= (100 - 50 * b - 20 * c - 10 * d - 5 * e - 2 * f); j++) {

?????????if (100 == 100 * a + 50 * b + 20 * c + 10 * d + 5 * e + 2 * f + j) {

??????????n++;

??????????System.out.println("一元硬币个数" + a + " 五角硬币个数" + b + " 贰角硬币个数" + c + " 一角硬币个数" + d

????????????+ " 五分硬币个数" + e + " 二分硬币个数" + f + " 一分硬币个数" + j);

?????????}

????????}

???????}

??????}

?????}

????}

???}

??}

??System.out.println(n);

?}

}

重写hashcode方法()(如：hash(id) % 100)，重复的值一定会在同一个hash散列中，这样就把范围缩小了100倍，再调用equal()方法判断是否相等。

按照url的hash(url)%1000值，将1000亿个url存储到1000个小文件中。对于每个小文件，可以构建一个url作为key，出现次数作为value的hash_map，并记录当前出现次数最多的100个url地址。 然后找出上一步求出的数据中重复次数最多的100个就是所求。

public class Bonus {

????public static void main(String[] args) {

????????int[][] arr1 = {{1,2,4,500},{8,3,3,2},{4,5,6,8},{1,3,4,6}};

????????System.out.println(getMost(arr1));

????}

????public static int getMost(int[][] board) {

????????int[][] arr = new int[board.length][board[0].length];

????????for(int i = 0;i<board.length;i++){

????????????for(int j = 0;j<board[0].length;j++){

????????????????int b = board[i][j];

????????????????if(i==0&&j==0)

????????????????????arr[i][j] = b;

????????????????else if(i==0){

????????????????????arr[i][j] = arr[i][j-1]+b;

????????????????}else if (j==0) {

????????????????????arr[i][j] = arr[i-1][j]+b;

????????????????}else{

????????????????????arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j])+b;

????????????????}

????????????????System.out.println(arr[i][j] +"/t"+b + "/t"+ i +"/t" + j);

????????????}

????????}

????????return arr[board.length-1][board[0].length-1];

????}

}

首先我们的思路就是利用哈希进行文件的切分，我们把100G大小的logfile分为1000份，那么下来差不多没一个文件就是100M左右，然后再利用哈希函数除留余数的方法分配到对应的编号文件中，然后再进行全局排序

class Demo {

boolean tag = false;

public synchronized void showA() {

if (tag == true) {

try {

wait();

} catch (InterruptedException e) {

e.printStackTrace();

}

}

System.out.println("1");

tag = true;

notify();

}

public synchronized void showB() {

if(tag == false) {

try {

wait();

} catch (InterruptedException e) {

e.printStackTrace();

}

}

System.out.println("2");

tag = false;

notify();

}

}

?

class ThreadDemo1 implements Runnable {

Demo demo;

ThreadDemo1(Demo demo) {

this.demo = demo;

}

int i = 1;

public void run() {

for(; i <= 10; i++) {

demo.showA();

}

}

}

class ThreadDemo2 implements Runnable {

Demo demo;

ThreadDemo2(Demo demo) {

this.demo = demo;

}

int i = 1;

public void run() {

for(; i <= 10; i++) {

demo.showB();

}

}

}

public class TestThread {

public static void main(String[] args) {

Demo demo = new Demo();

ThreadDemo1 d1 = new ThreadDemo1(demo);

ThreadDemo2 d2 = new ThreadDemo2(demo);

Thread t1 = new Thread(d1);

Thread t2 = new Thread(d2);

t1.start();

t2.start();

}

}