34-面经整理

人人网

首先两者都是List接口的不同实现,并且线程都是不安全的,ArrayList底层使用动态数组来存储元素,linkedList内部使用双向链表来存储元素;ArrayList占用的内存在声明的时候就已经确定了,默认为10当超出后,会自动扩容为原来的1.5倍,linkedList在声明的时候不需要指定大小,元素增加与删除的时候大小会随之改变

get()方法的时间复杂度为O(1),因为直接从底层数组下标获取,与数组长度无关

add()方法默认将元素添加到数组的末尾,但是需要考虑到数组的扩容情况,如果不需要扩容它的时间复杂度也是O(1),如果需要扩容的话内部执行的Arrays.copyof()方法是耗时的关键,需要把原有数组中的元素复制到扩容的新数组中;

add(int,E)方法将新的元素插入到指定的位置,考虑到需要复制底层的数组,根据最坏的打算,时间复杂度为O(n)

remove()方法将指定位置上的元素移除,因为需要复制底层的数组,所以时间复杂度也为O(n);

get方法的时间复杂度为O(n),因为遍历了整个链表,在下标小于链表长度一般的时候,从前往后,否则从后往前遍历,如果下标为0或者List.size()-1的话时间复杂度为O(1)

add方法默认添加到链表的尾部,时间复杂度为O(1)

add(int index,E ele)方法插入到指定位置,需要先查找再进行插入,所以也是O(n)

remove方法也是一样,需要先查找再进行删除,时间复杂度为O(n)

栈:先进后出,删除和增加操作只针对表头部

队列:先进先出,删除在表尾,增加在表头

数组+链表->数组+红黑树+链表

索引常用于实现数据的快速检索,在Mysql中有两种方式可以访问表的行数据:

顺序访问:从头到尾的变量,效率低下

索引访问:提前对某列建立一个索引,查找数据的时候可以根据该列上的索引找到对应行记录的位置,从而快速的查找到数据,索引存储了指定列数据值的指针,根据指定的排序顺序对这些指针进行排序

物理分类

B-数索引:采用B-树索引来存储,叶子节点包含的地址直接执行表中的数据行,并且叶子结点保存了指向下一个叶子节点的指针;分支节点:包含的条目指向索引里其他的分支节点或者叶子节点;Hash索引:把任意长度的输入通过散列算法变成固定长度的输入,输出就是散列值,只支持等值比较=,>=等,并且不支持键的部分匹配

唯一性索引:unique索引不允许索引列拥有相同值;

主键索引:不允许值重复或者为空

全文索引:用于varchar和text类型的列上创建,并且只能在MyISam引擎中创建

B+树中间节点没有存储数据记录只有索引,B树每个节点中的每个关键字都有数据记录,这就意味着相同大小的磁盘,对比每个节点B+树能存储更多的数据,B+树更加矮和胖,IO操作更少

也正因此B+树每次查找都需要找到叶子节点,性能稳定,B树情况号的时候是根节点,坏点的时候是叶子节点,性能不稳定

B树的范围查找需要不断的以来中序遍历,需要同时找到范围的上限和下限,整个过程比较耗时;B+树只需要找到范围的下限然后通过叶子节点的链表顺序遍历,直到找到上限就可以了

String类型:key-value类型,value不仅可以是String也可以是数字

Hash类型:适合用于存储对象>

List类型:底层是个链表

Set类型:相对于List可以自动排重

Sorted Set类型:每个元素都会关联一个double类型的分数,通过分数来进行大小排序

此外还有地理位置统计,Hyperloglog基数计算,BitMaps位图

 private static void quickSort(int[] arr){
        if(arr==null||arr.length==0)return;
        int begin=0;
        int end=arr.length-1;
        quickSortHelper(arr,begin,end);
    }

    private static void quickSortHelper(int[] arr, int begin, int end) {
        if(end<=begin)return;//递归终止条件
        int i=begin;
        int j=end;
        int index=arr[begin];//这样的写法index不能是随机数,只能是第一个
        while (i=index){
                j--;
            }
            arr[i]=arr[j];
            //再移动i
            while (i 
手撕冒泡? 
public static void bubbleSort(int[] arr) {
        int n=arr.length;
        int count=0;
        for (int i = 0; i < n; i++) {
            boolean swap=false;
            for (int j = 0; j < n - i - 1; j++) {
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    swap=true;
                }
            }
            if(!swap) break;//已经排好序了
        }

    }
 
手撕归并? 
    //两路归并算法，两个排好序的子序列合并为一个子序列
    public void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//辅助数组
        int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针

        while(p1<=mid && p2<=right){
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }

        while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=a[p2++];//同上

        //复制回原素组
        for (int i = left; i <=right; i++)
            a[i]=tmp[i];
    }

    public void mergeSort(int [] a,int start,int end){
        if(start 
快排和归并的区别? 
归并排序，简单来说就是先将数组不断细分成最小的单位，然后每个单位分别排序，排序完毕后合并，重复以上过程最后就可以得到排序结果。
 
快速排序，简单来说就是先选定一个基准元素，然后以该基准元素划分数组，再在被划分的部分重复以上过程，最后可以得到排序结果。