筆試題要點(diǎn)

JAVA

1、? ? String s = new String("asd");創(chuàng)建了幾個(gè)對(duì)象？

兩個(gè)? java中字符串存在與字符串池中怀浆，"asd" 是池中的一個(gè)對(duì)象，new String的時(shí)候，把池中的“asd”復(fù)制到了堆中退个，并且把對(duì)象的引用地址 交給了S

所以是兩個(gè)String 對(duì)象，一個(gè)是pool 一個(gè)在堆中调炬。

2语盈、基本類型 由小到大

類型字節(jié)

boolean1

byte1

short2

char2

int4

float4

long8

double8

3、package是打包到target install 是打包到mvn 倉(cāng)庫(kù)

4缰泡、B樹(shù) B+樹(shù) 紅黑樹(shù) 平衡二叉樹(shù)之間的區(qū)別

樹(shù)的演變??

? ? 樹(shù) 沒(méi)有排序刀荒，查詢數(shù)據(jù)一層一層的遍歷節(jié)點(diǎn)

?? ?BST 二叉查找樹(shù)，插入時(shí) 左小右大的機(jī)制匀谣，方便查詢照棋，特殊情況下 會(huì)變成鏈表的形式，退化了武翎。

? ? AVL樹(shù) 最短子樹(shù)和最長(zhǎng)子樹(shù)相差不能超過(guò)1烈炭，樹(shù)越來(lái)越深。

? ? B樹(shù) 多叉宝恶，degree節(jié)點(diǎn)限制符隙，存儲(chǔ)數(shù)據(jù)時(shí)候 非葉子節(jié)點(diǎn)也包含數(shù)據(jù)， 還是導(dǎo)致非索引的數(shù)據(jù)藏得比較深垫毙。

? ? B+樹(shù) 只有葉子節(jié)點(diǎn)有數(shù)據(jù)霹疫，而且葉子節(jié)點(diǎn)包含指針 有利于范圍搜索。

只有在關(guān)系型數(shù)據(jù)庫(kù) B+樹(shù)比B樹(shù)適合综芥。

5丽蝎、關(guān)于@order注解? spring 中控制類的加載和執(zhí)行

6、面向?qū)ο蟮幕咎卣?抽象、繼承屠阻、封裝红省、多態(tài)；

重寫(xiě)和重載

重寫(xiě)(Override)

參數(shù)列表必須完全與被重寫(xiě)方法的相同国觉。

返回類型與被重寫(xiě)方法的返回類型可以不相同吧恃，但是必須是父類返回值的派生類

重載(Overload)

重載(overloading) 是在一個(gè)類里面，方法名字相同麻诀，而參數(shù)不同痕寓。返回類型可以相同也可以不同。

每個(gè)重載的方法（或者構(gòu)造函數(shù)）都必須有一個(gè)獨(dú)一無(wú)二的參數(shù)類型列表蝇闭。

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

7、算法的重要特征

? ? ·有窮性：算法的有窮性是指算法必須在執(zhí)行有限個(gè)步驟之后終止

? ? ·確切行：算法的每一步驟必須有確切的定義

? ? ·輸入項(xiàng)：一個(gè)算法有0個(gè)或多個(gè)輸入丁眼，以刻畫(huà)運(yùn)算對(duì)象的初始情況筷凤，所謂0個(gè)輸入是指算法本身定出了初始條件

? ? ·輸出項(xiàng)：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果藐守。沒(méi)有輸出的算法是毫無(wú)意義的

? ? ·可行性：算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步驟，即每個(gè)計(jì)算步驟都可以在有限時(shí)間內(nèi)完成惠啄。也叫做有效性

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）

描述：??

?·比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)狼渊。

?·對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)亏较；

?·針對(duì)所有的元素重復(fù)以上的步驟巡通。? ???? ??? ?

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）

描述：

?·初始狀態(tài)：無(wú)序區(qū)為R[1..n]籽暇，有序區(qū)為空惶看；

?·第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí)纬黎，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]冠息，將它與無(wú)序區(qū)的第1個(gè)記錄R交換挪凑，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；

?·n-1趟結(jié)束逛艰，數(shù)組有序化了躏碳。

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）

一般來(lái)說(shuō)散怖，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)菇绵。具體算法描述如下：

?·從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序镇眷；

?·取出下一個(gè)元素咬最，在已經(jīng)排序的元素序列中從后向前掃描；

?·如果該元素（已排序）大于新元素欠动，將該元素移到下一位置永乌；

?·重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置具伍；

?·將新元素插入到該位置后翅雏；

?·重復(fù)步驟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--;

?? ??? ?//下標(biāo)j表示當(dāng)前的最小值

????????}

????????array[j] = temp;

????}

}

? ? 4人芽、希爾排序（Shell Sort）

?·選擇一個(gè)增量序列t1枚荣，t2，…啼肩，tk橄妆，其中ti>tj，tk=1祈坠；

?·按增量序列個(gè)數(shù)k害碾，對(duì)序列進(jìn)行k 趟排序；

?·每趟排序赦拘，根據(jù)對(duì)應(yīng)的增量ti慌随，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序躺同。僅增量因子為1 時(shí)阁猜，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度蹋艺。

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剃袍、類加載的過(guò)程中類變量的初始化是 在哪個(gè)階段

類的加載機(jī)制? 準(zhǔn)備階段

平常使用的集合為?

? ? Collection 下的ArrayList、LinkedList捎谨。

? ? Set 下的HashSet

? ? Map 下的HashMap 和ConcurrentHashMap

ArrayList 作用的場(chǎng)景民效，

底層是數(shù)組,初始化時(shí)數(shù)據(jù)量是0憔维，add 時(shí)候默認(rèn)變成10。擴(kuò)容：擴(kuò)容每次是之前容量的1.5倍畏邢。

特點(diǎn)：查詢速度快业扒，刪除效率低。

LinkedList的底層是帶有頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的雙向鏈表舒萎，提供了兩種插入方式程储，頭插，LinkedFirst和LinkedLast臂寝，

特點(diǎn)：適合經(jīng)常增加虱肄、刪除操作的場(chǎng)景；查詢?cè)诹看蟮臅r(shí)候比較慢交煞； （多大的時(shí)候）；

為什么慢：因?yàn)椴皇请S機(jī)訪問(wèn)的斟或，無(wú)法二分查找只能順序遍歷素征。

ArrayList根據(jù)腳標(biāo)進(jìn)行查詢的所以速度快。（如果是按值查詢萝挤，差不多御毅，按位查詢才有明顯區(qū)別）

線程安全的情況下用一個(gè)list 怎么用。Vector和ArrayList一樣底層是數(shù)組怜珍。大部分方法都是倍Synchronized關(guān)鍵字所修飾端蛆。線程安全的。

擴(kuò)容的時(shí)候大小是默認(rèn)的兩倍酥泛。（寫(xiě)時(shí)拷貝）

HashMap

底層結(jié)構(gòu)在1.7和1.8不一樣

1.7底層是數(shù)組加單鏈表

1.8是數(shù)組加單鏈表加紅黑樹(shù)今豆，單鏈表的長(zhǎng)度大于等于8時(shí)，并且hash桶大于等于64時(shí)候柔袁，會(huì)將單鏈表轉(zhuǎn)化為紅黑樹(shù)形式存儲(chǔ)

紅黑樹(shù)節(jié)點(diǎn)小于等于6的時(shí)候呆躲，轉(zhuǎn)化為鏈表結(jié)構(gòu)。Hash桶的數(shù)量默認(rèn)時(shí)16個(gè)捶索，它的閾值時(shí)0.75 .

擴(kuò)容：檢測(cè)負(fù)載因子 0.75閾值 就是16*0.75 = 12 hash桶大于12的時(shí)候插掂，觸發(fā)擴(kuò)容，會(huì)擴(kuò)容成2倍* 2^N 腥例。在把的老的元素進(jìn)行rehash

put的時(shí)候 辅甥，會(huì)造成數(shù)據(jù)覆蓋

1.7在put的時(shí)候resize過(guò)程 （頭插入法 ，會(huì)形成環(huán)形鏈表燎竖，造成死循環(huán)）璃弄。

1.8尾插。

如何保證線程安全构回，直接使用ConcurrentHashMap 保證線程安全谢揪，蕉陋、

HashTable 就是簡(jiǎn)單的加上了Synchronized 效率很低。鎖的粒度大拨扶。

1.7的時(shí)候ConCurrentHashMap 底層的分段數(shù)組凳鬓，有一個(gè)分段鎖。SegMent鎖患民。繼承RenTrantLock保證線程安全缩举。每次只給一段加鎖 ，保證并發(fā)

1.8的時(shí)候匹颤，改成和hashmap一樣的數(shù)據(jù)結(jié)構(gòu) 數(shù)組加鏈表加數(shù)據(jù)結(jié)構(gòu)

放棄了分段鎖使用了synchronized和CAS來(lái)操作仅孩。

如何找到具體的數(shù)字

CAS輕量級(jí)的加鎖過(guò)程，查詢?cè)俑?準(zhǔn)備寫(xiě)之前再查詢一次印蓖，比較和之前的結(jié)果有沒(méi)有區(qū)別辽慕，樂(lè)觀鎖。自旋鎖赦肃。

Compare and Swap 比較并替換

優(yōu)缺點(diǎn)溅蛉，優(yōu)點(diǎn)：輕量級(jí)

缺點(diǎn)：并發(fā)大的時(shí)候?qū)PU的性能消耗比較大。

ABA 加一個(gè)版本號(hào)和標(biāo)志他宛。

Synchronizied 的使用方式：?方法的時(shí)候是 ACC_Sync

在 1.6的時(shí)候做了一個(gè)鎖升級(jí)船侧。

輕量級(jí)鎖加鎖：線程在執(zhí)行同步塊之前，JVM會(huì)先在當(dāng)前線程的棧楨中創(chuàng)建用于存儲(chǔ)鎖記錄的空間厅各，并將對(duì)象頭中的Mark Word復(fù)制到鎖記錄Lock Record中镜撩，官方稱為Displaced Mark Word。然后線程嘗試使用CAS將對(duì)象頭中的Mark Word替換為指向鎖記錄的指針队塘。如果成功袁梗，當(dāng)前線程獲得鎖，如果失敗憔古，表示其他線程競(jìng)爭(zhēng)鎖围段，當(dāng)前線程便嘗試使用自旋來(lái)獲取鎖。

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

鎖升級(jí)過(guò)程圖解

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

鎖應(yīng)用 static + synchronized 類鎖 與創(chuàng)建對(duì)象無(wú)關(guān)投放，使用即同步奈泪。單獨(dú)synchronized? 如果訪問(wèn)不同對(duì)象 不會(huì)同步

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

synchronized修飾方法和方法塊的區(qū)別

http://www.reibang.com/p/c3313dcf2c23

volatile 關(guān)鍵字

涉及java內(nèi)存模型

由于volatile的mesi緩存一致性協(xié)議需要不斷的從主內(nèi)存嗅探和cas不斷循環(huán)無(wú)效交互導(dǎo)致總線帶寬達(dá)到峰值

解決辦法：部分volatile和cas使用synchronize

線程之間的可間性 方法是 通過(guò)修改線程間的數(shù)據(jù)時(shí)象主內(nèi)存立即刷新，cpu多核處理器灸芳，每個(gè)處理器 都有L1 L2 共享L3 緩存涝桅，

自己的緩存機(jī)制。volatile太多 頻繁去通過(guò)總線嗅探機(jī)制烙样，會(huì)占滿總線的帶寬 造成總線風(fēng)暴冯遂。

HashMap 和 Hashtable

1、兩者父類不同

hashMap 繼承的是abstractMap?

hashTable 繼承的是dictionary

不過(guò)都實(shí)現(xiàn)了 map谒获、Cloneable（可復(fù)制）serializable（可序列化）三個(gè)接口

2蛤肌、對(duì)外提供的接口不同

hashtable 比hashmap 多提供了elments 和contains兩個(gè)方法

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

contains方法判斷hashtable是否包含傳入的value壁却。

在實(shí)現(xiàn)上與hashmap的containsvalue一樣。

3裸准、對(duì)null的支持不同

hashtab：key value 都不能為空

4展东、安全性不同

hashMap是線程不安全的