《每日一道面试题》—— 第四期

码仔，今天就给大家带来了《每日一道面试题》的第四期：

01

简述HashMap工作原理 

HashMap是基于hashing算法的原理，通过put(key，value)和get(key)方法储存和获取值的。

存：我们将键值对K/V 传递给put()方法，它调用K对象的hashCode()方法来计算hashCode从而得到bucket位置，之后储存Entry对象。（HashMap是在bucket中储存 键对象 和 值对象，作为Map.Entry）

取：获取对象时，我们传递 键给get()方法，然后调用K的hashCode()方法从而得到hashCode进而获取到bucket位置，再调用K的equals()方法从而确定键值对，返回值对象。

碰撞：当两个对象的hashcode相同时，它们的bucket位置相同，‘碰撞’就会发生。如何解决，就是利用链表结构进行存储，即HashMap使用LinkedList存储对象。但是当链表长度大于8（默认）时，就会把链表转换为红黑树，在红黑树中执行插入获取操作。

扩容：如果HashMap的大小超过了负载因子定义的容量，就会进行扩容。默认负载因子为0.75。就是说，当一个map填满了75%的bucket时候，将会创建原来HashMap大小的两倍的bucket数组（jdk1.6，但不超过最大容量），来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

02

谈谈ArrayList和LinkList的区别 

因为 Array 是基于索引 (index) 的数据结构，它使用索引在数组中搜索和读取数据是很快的。Array 获取数据的时间复杂度是 O(1), 但是要删除数据却是开销很大的，因为这需要重排数组中的所有数据。

相对于 ArrayList , LinkedList 插入是更快的。因为LinkedList不像ArrayList 一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是 ArrayList 最坏的一种情况，时间复杂度是 O(n) ，而 LinkedList 中插入或删除的时间复杂度仅为 O(1) 。ArrayList 在插入数据时还需要更新索引（除了插入数组的尾部）。

类似于插入数据，删除数据时，LinkedList 也优于 ArrayList 。

LinkedList 需要更多的内存，因为 ArrayList 的每个索引的位置是实际的数据，而 LinkedList 中的每个节点中存储的是实际的数据和前后节点的位置( 一个LinkedList实例存储了两个值Node first 和 Node last 分别表示链表的其实节点和尾节点，每个 Node 实例存储了三个值：E item,Node next,Node pre)。

什么场景下更适宜使用LinkedList，而不用ArrayList

1. 你的应用不会随机访问数据 。因为如果你需要LinkedList中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。

2. 你的应用更多的插入和删除元素，更少的读取数据。因为插入和删除元素不涉及重排数据，所以它要比ArrayList要快。

3. 以上就是关于ArrayList和LinkedList的差别。你需要一个不同步的基于索引的数据访问时，请尽量使用ArrayList。ArrayList很快，也很容易使用。但是要记得要给定一个合适的初始大小，尽可能的减少更改数组的大小。

03

ListView为何不过时 

ListView采用的是RecyclerBin的回收机制,在一些轻量级的List显示时效率更高.

• 在处理少量数据使用 ListView

• 在处理大量数据的时候使用 RecyclerView

04

快速查找1000万个数中最大的100个 

1. 假设数组为 array[N] (N = 1 000万)，首先利用quicksort的原理把array分成两个部分，左边部分比 array[N - 1] (array中的最后一个值，即pivot) 大， 右边部分比pivot 小。然后，可以得到array[array.length - 1] (即 pivot) 在整个数组中的位置，假设是 k.

2. 如果 k 比 99 大，原数组变成了 array [0, ... k - 1]， 然后在数组里找前 100 最大值。 （继续递归）

3. 如果 k 比 99 小， 原数组变成了 array [k + 1, ..., N ]， 然后在数组里找前 100 - (k + 1) 最大值。（继续递归）

4. 如果 k == 99, 那么数组的前 100 个值一定是最大的。

时间复杂度：平均时间复杂度是 O(N)，但是最差是O(N^2)

public class QuickSort {

public static void main(String[] args) {
// the size of the array
int number = 100000000;
// the top k values
int k = 100;
// the range of the values in the array
int range = 1000000001;


int[] array = new int[number];
Random random = new Random();
for (int i = 0;i < number;i++){
array[i] = random.nextInt(range);
System.out.println(array[i]);
}

// start time
long t1 = System.currentTimeMillis();
tophundred(array,0,array.length - 1,k);
// end time
long t2 = System.currentTimeMillis();

System.out.println("The total execution time " +
"of quicksort based method is " + (t2 - t1) +" millisecond!");

// print out the top k largest values in the top array
System.out.println("The top "+ k + " largest values are:");

for (int i = 0; i < k; i++) {
System.out.println(array[i]);
}
}

private static void tophundred(int[] array,int start,int end,int k) {
int switchPointer = start;
int pivot = array[end];// array最后一个值作为pivot
for (int i = start;i < end;i++) {
if (array[i] >= pivot) {
swap(array,switchPointer,i);
switchPointer++;
}
}
swap(array,end,switchPointer);//交换2后，array左边的值比pivot大，右边的值比pivot小

if (switchPointer < k - 1){
tophundred(array,switchPointer+1,end,k - switchPointer - 1); // 比pivot大的部分不够99个，所以从后面再找100-（左边的部分）
} else if(switchPointer == k - 1) {
return;
} else {
tophundred(array,0,switchPointer - 1,k);
}

}

private static void swap(int[] array,int i,int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}

05

谈谈工厂模式 

定义一个用于创建对象的接口，让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。

1. 何时使用

1. 用户需要一个类的子类的实例，但不希望与该类的子类形成耦合

2. 用户需要一个类的子类的实例，但用户不知道该类有哪些子类可用

2. 优点

1. 使用工厂方法可以让用户的代码和某个特定类的子类的代码解耦

2. 工厂方法使用户不必知道它所使用的对象是怎样被创建的，只需知道该对象有哪些方法即可。

• 简单工厂模式

  简单工厂模式又称静态工厂方法模式。它存在的目的很简单：定义一个用于创建对象的接口。

  如果一个一些对象（产品），已经确定了并不易改变和添加新的产品，那么就可以使用简单工厂模式

interface Phone {
void call();
}

class HwMobilePhone implement Phone {
@Override
public void call() {
System.out.println("Hw make a call");
}
}

class OnePlusMobilePhone implement Phone {
@Override
public void call() {
System.out.println("OnePlus make a call");
}
}

class Factory {
Phone produce(String product) {
if(product.equals("Hw"))
return new HwMobilePhone();
else if(product.equals("OnePlus"))
return new OnePlusMobilePhone();
else throw new IllegalArgumentException("No such product");
}
}

public class SimpleFactoryPattern {
public static void main(String args[]) throws Exception{
Factory factory = new Factory();
factory.produce("Hw").call();
factory.produce("OnePlus").call();
}
}

• 可以看出，简单工厂模式是不易维护的，如果需要添加新的产品，例如要增加一个 MiMobilePhone，则整个系统都需要修改。

• 工厂方法模式

  工厂方法模式去掉了简单工厂模式中工厂方法的静态属性，使得它可以被子类继承。这样在简单工厂模式里集中在工厂方法上的压力可以由工厂方法模式里不同的工厂子类来分担。

  interface Phone {
  void call();
  }
  
  class HwMobilePhone implement Phone {
  @Override
  public void call() {
  System.out.println("Hw make a call");
  }
  }
  
  class OnePlusMobilePhone implement Phone {
  @Override
  public void call() {
  System.out.println("OnePlus make a call");
  }
  }
  
  interface IFactory {
  Phone produce();
  }
  
  class HwFactory implement IFactory {
  @Override
  public Phone produce() {
  return new HwMobilePhone();
  }
  }
  
  class OnePlusFactory implement IFactory {
  @Override
  public Phone produce() {
  return new OnePlusMobilePhone();
  }
  }
  
  public class FactoryPattern {
  public static void main(String args[]) {
  IFactory factory;
  factory = new HwFactory();
  factory.produce().call();
  factory = new OnePlusFactory();
  factory.produce().call();
  }
  }

工厂方法模式和简单工厂模式在定义上的不同是很明显的。工厂方法模式的核心是一个抽象工厂类,而不像简单工厂模式, 把核心放在一个实类上。工厂方法模式可以允许很多实的工厂类从抽象工厂类继承下来, 从而可以在实际上成为多个简单工厂模式的综合,从而推广了简单工厂模式。 反过来讲,简单工厂模式是由工厂方法模式退化而来。设想如果我们非常确定一个系统只需要一个实的工厂类, 那么就不妨把抽象工厂类合并到实的工厂类中去。而这样一来,我们就退化到简单工厂模式了

06

结束语 

如果你有好的答案可以提交至：

https://github.com/codeegginterviewgroup/CodeEggDailyInterview

往期文章：