笔试题要点

JAVA

1、    String s = new String("asd");创建了几个对象？

两个  java中字符串存在与字符串池中，"asd" 是池中的一个对象，new String的时候，把池中的“asd”复制到了堆中，并且把对象的引用地址 交给了S

所以是两个String 对象，一个是pool 一个在堆中。

2、基本类型 由小到大

类型字节

boolean1

byte1

short2

char2

int4

float4

long8

double8

3、package是打包到target install 是打包到mvn 仓库

4、B树 B+树 红黑树 平衡二叉树之间的区别

树的演变  

    树 没有排序，查询数据一层一层的遍历节点

    BST 二叉查找树，插入时 左小右大的机制，方便查询，特殊情况下 会变成链表的形式，退化了。

    AVL树 最短子树和最长子树相差不能超过1，树越来越深。

    B树 多叉，degree节点限制，存储数据时候 非叶子节点也包含数据， 还是导致非索引的数据藏得比较深。

    B+树 只有叶子节点有数据，而且叶子节点包含指针 有利于范围搜索。

只有在关系型数据库 B+树比B树适合。

5、关于@order注解  spring 中控制类的加载和执行

6、面向对象的基本特征 抽象、继承、封装、多态；

重写和重载

重写(Override)

参数列表必须完全与被重写方法的相同。

返回类型与被重写方法的返回类型可以不相同，但是必须是父类返回值的派生类

重载(Overload)

重载(overloading) 是在一个类里面，方法名字相同，而参数不同。返回类型可以相同也可以不同。

每个重载的方法（或者构造函数）都必须有一个独一无二的参数类型列表。

https://www.runoob.com/java/java-override-overload.html

7、算法的重要特征

    ·有穷性：算法的有穷性是指算法必须在执行有限个步骤之后终止

    ·确切行：算法的每一步骤必须有确切的定义

    ·输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件

    ·输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的

    ·可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成。也叫做有效性

https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025#1

8、排序算法

https://www.cnblogs.com/onepixel/articles/7674659.html

https://blog.csdn.net/weixin_34221773/article/details/93177321

    1、冒泡排序（Bubble Sort）

描述：  

 ·比较相邻的元素。如果第一个比第二个大，就交换他们两个。

 ·对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

 ·针对所有的元素重复以上的步骤。            

private static void bubbleSort(int[] array) {

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

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

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

                int temp = array[j];

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

                array[j + 1] = temp;

            }

        }

    }

}

    2、选择排序（Selection Sort）

描述：

 ·初始状态：无序区为R[1..n]，有序区为空；

 ·第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

 ·n-1趟结束，数组有序化了。

private static void selectionSort(int[] array) {

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

        int index = i;

        for (int j = index; j < array.length - 1; j++) {

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

                index = j + 1;

            }

        }

        int temp = array[index];

        array[index] = array[i];

        array[i] = temp;

    }

}

    3、插入排序（Insertion Sort）

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

 ·从第一个元素开始，该元素可以认为已经被排序；

 ·取出下一个元素，在已经排序的元素序列中从后向前扫描；

 ·如果该元素（已排序）大于新元素，将该元素移到下一位置；

 ·重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

 ·将新元素插入到该位置后；

 ·重复步骤2~5。

private static void insertionSorter(int[] array) {

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

        int temp = array[i];

        int j = i;

        while (j > 0 && temp < array[j - 1]) {

            array[j] = array[j - 1];

            j--;

        //下标j表示当前的最小值

        }

        array[j] = temp;

    }

}

    4、希尔排序（Shell Sort）

 ·选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

 ·按增量序列个数k，对序列进行k 趟排序；

 ·每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

public static void shellSorter(int[] array) {

    for (int gap = array.length / 2; gap > 0; gap /= 2) {

        for (int i = gap; i < array.length; i++) {

            int temp = array[i];

            int j = i;

            if (array[j] < array[j - 1]) {

                while (j - gap >= 0 && temp < array[j - gap]) {

                    array[j] = array[j - gap];

                    j -= gap;

                }

                array[j] = temp;

            }

        }

    }

}

9、类加载的过程中类变量的初始化是 在哪个阶段

类的加载机制  准备阶段

平常使用的集合为 

    Collection 下的ArrayList、LinkedList。

    Set 下的HashSet

    Map 下的HashMap 和ConcurrentHashMap

ArrayList 作用的场景，

底层是数组,初始化时数据量是0，add 时候默认变成10。扩容：扩容每次是之前容量的1.5倍。

特点：查询速度快，删除效率低。

LinkedList的底层是带有头节点和尾节点的双向链表，提供了两种插入方式，头插，LinkedFirst和LinkedLast，

特点：适合经常增加、删除操作的场景；查询在量大的时候比较慢； （多大的时候）；

为什么慢：因为不是随机访问的，无法二分查找只能顺序遍历。

ArrayList根据脚标进行查询的所以速度快。（如果是按值查询，差不多，按位查询才有明显区别）

线程安全的情况下用一个list 怎么用。Vector和ArrayList一样底层是数组。大部分方法都是倍Synchronized关键字所修饰。线程安全的。

扩容的时候大小是默认的两倍。（写时拷贝）

HashMap

底层结构在1.7和1.8不一样

1.7底层是数组加单链表

1.8是数组加单链表加红黑树，单链表的长度大于等于8时，并且hash桶大于等于64时候，会将单链表转化为红黑树形式存储

红黑树节点小于等于6的时候，转化为链表结构。Hash桶的数量默认时16个，它的阈值时0.75 .

扩容：检测负载因子 0.75阈值 就是16*0.75 = 12 hash桶大于12的时候，触发扩容，会扩容成2倍* 2^N 。在把的老的元素进行rehash

put的时候 ，会造成数据覆盖

1.7在put的时候resize过程 （头插入法 ，会形成环形链表，造成死循环）。

1.8尾插。

如何保证线程安全，直接使用ConcurrentHashMap 保证线程安全，、

HashTable 就是简单的加上了Synchronized 效率很低。锁的粒度大。

1.7的时候ConCurrentHashMap 底层的分段数组，有一个分段锁。SegMent锁。继承RenTrantLock保证线程安全。每次只给一段加锁 ，保证并发

1.8的时候，改成和hashmap一样的数据结构 数组加链表加数据结构

放弃了分段锁使用了synchronized和CAS来操作。

如何找到具体的数字

CAS轻量级的加锁过程，查询再改 准备写之前再查询一次，比较和之前的结果有没有区别，乐观锁。自旋锁。

Compare and Swap 比较并替换

优缺点，优点：轻量级

缺点：并发大的时候对CPU的性能消耗比较大。

ABA 加一个版本号和标志。

Synchronizied 的使用方式： 方法的时候是 ACC_Sync

在 1.6的时候做了一个锁升级。

轻量级锁加锁：线程在执行同步块之前，JVM会先在当前线程的栈桢中创建用于存储锁记录的空间，并将对象头中的Mark Word复制到锁记录Lock Record中，官方称为Displaced Mark Word。然后线程尝试使用CAS将对象头中的Mark Word替换为指向锁记录的指针。如果成功，当前线程获得锁，如果失败，表示其他线程竞争锁，当前线程便尝试使用自旋来获取锁。

http://blog.sina.com.cn/s/blog_c038e9930102v2ht.html

锁升级过程图解

https://www.processon.com/view/5c25db87e4b016324f447c95

锁应用 static + synchronized 类锁 与创建对象无关，使用即同步。单独synchronized  如果访问不同对象 不会同步

https://www.cnblogs.com/houzheng/p/9084026.html

synchronized修饰方法和方法块的区别

https://www.jianshu.com/p/c3313dcf2c23

volatile 关键字

涉及java内存模型

由于volatile的mesi缓存一致性协议需要不断的从主内存嗅探和cas不断循环无效交互导致总线带宽达到峰值

解决办法：部分volatile和cas使用synchronize

线程之间的可间性 方法是 通过修改线程间的数据时象主内存立即刷新，cpu多核处理器，每个处理器 都有L1 L2 共享L3 缓存，

自己的缓存机制。volatile太多 频繁去通过总线嗅探机制，会占满总线的带宽 造成总线风暴。

HashMap 和 Hashtable

1、两者父类不同

hashMap 继承的是abstractMap 

hashTable 继承的是dictionary

不过都实现了 map、Cloneable（可复制）serializable（可序列化）三个接口

2、对外提供的接口不同

hashtable 比hashmap 多提供了elments 和contains两个方法

elements用于返回此hashtable的value的枚举

contains方法判断hashtable是否包含传入的value。

在实现上与hashmap的containsvalue一样。

3、对null的支持不同

hashtab：key value 都不能为空

4、安全性不同

hashMap是线程不安全的