阿里一面面经（附答案）_阿里 算法 一面 面经

阿里一面：
1、先讲一下项目；
2、Hashmap的底层实现原理（问的特别深）
答：hashmap是基于哈希表的Map接口的非同步实现。实际上是一个“链表散列”的数据结构，即数组和链表的结合体。hashmap底层是一个数组结构，数组中的每一项又是一个链表。hashmap里面实现了一个静态内部类Entry，其重要的属性有key，value，next，从属性key，value，我们就能看出来Entry是hashmap键值对实现的一个基础bean，我们说hashmap的基础就是一个线性数组，其实这个数组就是Entry[]，map里面的内容都保存在Entry[]里面。
hashmap的存取实现：

// 存储时:
int hash = key.hashCode();
int index = hash % Entry[].length;
Entry[index] = value;

// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

1
2
3
4
5
6
7
8
9
10

当我们往hashmap里put一个Entry<key，value>，首先会通过hashcode方法计算key的hash值，然后通过hash%Entry[].length，计算出它在数组中的索引index，这时就会出现一个疑问，如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？
这里hashmap里面用到了链式数据结构的概念，上面我们提到，Entry类里面有一个next属性，作用是指向下一个Entry。举一个例子，第一个键值对A进来，通过计算key的hash值得到的index是1，记：Entry[1] = A。再进来一个键值对B，通过计算它的index也为1，hashmap会怎么存储呢，它会利用Entry类的next属性，B.next = A,Entry[1] = B，这样我们发现index = 0的地方其实存取了A,B两个键值对，他们通过next这个属性连接起来，数组中存储的是最后插入的元素，最先加入的元素在链表尾。
hashmap也实现了一些优化，比如：Entry[]的长度一定后，随着map里面的数据越来越长，这样同一个index的链就会很长，可能会影响性能，在hashmap中设置一个因子，随着map的size越来越大，Entry[]会以一定的规则加长长度。
get：

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        //先定位到数组元素，再遍历该元素处的链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

null key的存取：null key总是放在Entry[]数组的第一个元素。

private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
 
    private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

确定数组index：hashcode%table.length取模。算法如下：
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }
按位取并，作用上相当于取模mod或者取余%。这意味着数组下标相同，并不表示hashcode相同。

3、Arraylist和linkedlist的区别
(1) ArrayList是基于动态数组，LinkedList是基于链表结构（双向循环链表）。
(2)ArrayList是用于查操作，适用于随机访问；LinkedList适用于增删功能。
(3) LinkedList也实现了Java.util.Queue接口，所以可以直接通过LinkedList实例来实现队列的功能。
4、到底什么是高并发
高并发是互联网分布式系统架构设计中必须考虑的因素之一，通常指，通过设计保证系统能够同时并行处理很多请求。
提高系统并发能力的方式主要有两种：垂直扩展（Scale Up）与水平扩展（Scale Out）。前者垂直扩展可以通过提升单机硬件性能，或者提升单机架构性能，来级高并发性，但单机性能总是有限的，互联网分布式架构设计高并发终极解决方案还是水平扩展。
5、为什么会出现线程不安全
线程随机性原理，线程会被cpu随机切换，而线程访问的资源如果是堆或者是方法区的资源的话，那么每个线程都可以更改这个数据，外加上线程执行会被cpu随机切换。所以，共享资源被多线程访问当然不安全了。
6、怎么去避免线程不安全
线程安全的三个方面：
(1) 原子性：提供互斥访问，同一时刻只能有一个线程对数据进行操作（atomic，synchronized）
(2) 可见性：一个线程对主内存的修改可以及时地被其他线程看到（synchronized，volatile）
(3) 有序性：一个线程观察其他线程中的指令执行顺序，，由于指令重排序，该观察结果一般杂乱无序（happens-before原则）
1、创建不可变对象；2、县城封闭：把一个可变对象封装到一个线程内部，或者使用TheadLocal；3、使用volatile变量；4、使用final变量；5、使用锁（synchronized，可重入锁）
7、线程和线程之间为什么会出现不可见性
8、讲一下volatile
volatile的本质是告诉jvm当前变量在寄存器中的值是不确定的，需要从主存中读取；volatile只能使用在变量级别上，volatile只能保证可见性，不能保证原子性；这个关键字不会造成线程的阻塞，而且volatile标记的变量不会被编译器优化；
对于volatile关键字，当且仅当满足以下所有条件时可使用：
1、对变量的写入操作不依赖变量的当前值，或者可以确保只有单个线程更新变量的值；
2、该变量没有包含在具有其他变量的不变式中。
9、讲一下synchronize的底层实现原理
sychronized的语义底层是通过一个monitor对象来完成的。涉及到两条指令:
(1) monitorenter 每个对象都有一个监视器锁（monitor），当monitor被占用时就会处于锁定状态，线程执行monitorenter指令时尝试获取monitor的所有权；
(2) monitorexit 执行monitorexit的线程必须是monitor的所有者，如果显示计入数为0，则该线程退出monitor，其他被这个monitor阻塞的线程可以尝试去获取这个monitor的所有权。
相对于普通方法，其常量池中多了ACC_SYNCHRONIZED标识符，jvm就是根据该标识符实现方法的同步的：当方法被调用时，调用指令将会检查方法的ACC_SYNCHRONIZED访问标志是否被设置，如果设置了，执行线程将先获取monitor，获取成功后，才能执行方法体，执行完之后再释放monitor，在方法执行期间，其他任何线程都无法在获得同一个monitor对象。
10、用两个队列来实现一个栈
假设使用队列q1和队列q2模拟栈s，q1为入队列，q2为出队列。
实现思路：可以认为队列q1提供压栈的功能，队列q2提供弹栈的功能。
要压栈，入队列q1即可，而当弹栈的时候，出队列则需要分两种情况考虑：
1、若队列q1中只有一个元素，则让q1中的元素出队列并输出即可。
2、若队列q2中不只有一个元素，则让队列q1中所有元素出队列，入队列q2，最后一个元素不如q2，输出该元素，然后将q2中元素入q1.
11、栈与队列的区别
栈和队列都是受限制的线性表。栈是一种仅允许在表的一端（栈顶）进行插入和删除操作的数据结构，先进后出；队列只允许在表的头部进行删除操作，在表的尾部进行插入操作，先进先出。
12、给你11个数，求最大的10个数

13、讲一下小顶堆

public class HeapSort2 {
	public void maxheapsort(int[] arr){
		for(int i = arr.length/2-1;i >= 0;i--){
			//从第一个非叶子节点从下往上，从右至左构建大顶堆；
			maxheap(arr,i,arr.length);
		}
		for(int j = arr.length-1;j > 0;j--){
			swap(arr,0,j);//交换头尾元素；
			maxheap(arr,0,j);//重新构建大顶堆；
		}
	}
	public void maxheap(int[] arr,int l,int r){
		int temp = arr[l];
		for(int i = l*2+1;i < r;i = i*2+1){
			if(i+1 < r && arr[i] < arr[i+1]){
				i++;
			}
			if(arr[i] > temp){
				arr[l] = arr[i];
				l = i;
			}else{
				break;
			}
		}
		arr[l] = temp;
	}
	public void swap(int[] arr,int start,int end){
		int a = arr[start];
		arr[start] = arr[end];
		arr[end] = a;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

14、线程与进程之间的区别
进程中可以有多个线程，但至少有一个线程；
线程是调度与分配的独立单位，而进程是拥有系统资源的独立单位，线程可以共享进程中的所有资源；
处理机分配给线程，真正在处理机上运行的是线程；
线程是进程的一个执行单元，是进程的可调度实体；
创建一个进程开销大，创建一个线程开销小，线程被称为“轻量级进程”。
15、线程为什么不拥有系统资源
系统管理代码执行的单位是进程而不是线程，每次执行都是运行在独立的进程上，而每个进程又至少拥有一个线程，这些线程共享着进程中的所有资源。
16、线程之间是怎么通信的
wait(),notify(),notifyAll().
17、进程之间是怎么通信的
管道（Pipe）
18、有什么想对他说的，闲聊。