1、什么是雪花算法，簡單介紹一下？

文章參考：帶你入門java雪花算法原理

雪花算法是 Twitter 開源的分布式 ID 生成算法。是由 64bit 的 long 類型，生成的全局 ID，引入了 時間戳和 ID保持自增 的屬性。

64bit分為四個部分：

• 第一個部分是 1bit，沒有實際意義。
• 第二個部分是 41bit，由時間戳組成。
• 第三個部分是 10bit，工作機器 ID，里面分為兩個部分，5 個 bit 是的是機房號，代表最多有 2^5 即 32 個機房，5 個 bit 是指機器的ID，代表最多有 2^5 個機器，即 32 個機器。
• 第四部分是 12bit，代表是同一個毫秒類產生不同的 ID，區(qū)分同一個毫秒內產生的ID.

總的來說就是一個機房，一臺機器，在同一號毫秒時產生的 ID，可能在同一秒鐘產生不同的 ID，最后 12bit 序列號可以區(qū)分在同一秒鐘的不同 ID。

雪花算法保證:

1. 所生成的 ID 按時間遞增。
2. 整個分布式系統(tǒng)不會有重復的 ID。

2、請你分析一下紅黑樹的左右旋轉流程？

直接上圖，生動形象：

就以左旋為例，首先當前節(jié)點（N）所在位置被它的右子節(jié)點（R）替代，N 的左子樹仍然是它的左子節(jié)點（L），但是 R 節(jié)點此時將它的左子節(jié)點（RL）交給 N，使其成為 N 的右子節(jié)點，R 的右子節(jié)點還是原來的右子節(jié)點（RR）。

紅黑樹的完整文章，參考往期博客：HashMap底層紅黑樹實現(xiàn)(自己實現(xiàn)一個簡單的紅黑樹)

3、什么是DNS污染和DSN劫持？

什么是DNS劫持？

• DNS 劫持：就是指 DNS 服務器被劫持了，通過某些手段取得某域名的解析記錄控制權，進而修改此域名的解析結果，導致對該域名的訪問由原IP地址轉入到修改后的指定IP，其結果就是對特定的網(wǎng)址不能訪問或訪問的是假網(wǎng)址，從而實現(xiàn)竊取資料或者破壞原有正常服務的目的。DNS 劫持通過篡改 DNS 服務器上的數(shù)據(jù)返回給用戶一個錯誤的查詢結果來實現(xiàn)的。
• DNS 劫持癥狀：在某些地區(qū)的用戶在成功連接寬帶后，首次打開任何頁面都指向 ISP 提供的 “電信互聯(lián)星空”、“網(wǎng)通黃頁廣告” 等內容頁面。還有就是曾經出現(xiàn)過用戶訪問 Google 域名的時候出現(xiàn)了百度的網(wǎng)站。這些都屬于 DNS 劫持。

什么是DNS污染？

• DNS 污染：是一種讓一般用戶由于得到虛假目標主機 IP 而不能與其通信的方法，是一種 DNS 緩存投毒攻擊（DNS cache poisoning）。
• 其工作方式是：由于通常的 DNS 查詢沒有任何認證機制，而且 DNS 查詢通常基于的 UDP 是無連接不可靠的協(xié)議，因此 DNS 的查詢非常容易被篡改，通過對 UDP 端口 53 上的 DNS 查詢進行入侵檢測，一經發(fā)現(xiàn)與關鍵詞相匹配的請求則立即偽裝成目標域名的解析服務器（NS，Name Server）給查詢者返回虛假結果。
• DNS污染則是發(fā)生在用戶請求的第一步上，直接從協(xié)議上對用戶的DNS請求進行干擾。
• DNS污染癥狀：目前一些被禁止訪問的網(wǎng)站很多就是通過 DNS 污染來實現(xiàn)的，例如 YouTube、Facebook 等網(wǎng)站。

二者的解決方案：

對于DNS劫持，可以采用使用國外免費公用的DNS服務器解決。例如 OpenDNS（208.67.222.222）或 GoogleDNS（8.8.8.8）。

對于DNS污染，可以說，個人用戶很難單單靠設置解決，通常可以使用 VPN 或者域名遠程解析的方法解決，但這大多需要購買付費的 VPN 或 SSH 等，也可以通過修改 Hosts 的方法，手動設置域名正確的 IP 地址。

總結：

• DNS 劫持，就是指用戶訪問一個被標記的地址時，DNS 服務器故意將此地址指向一個錯誤的IP地址的行為。范例，網(wǎng)通、電信、鐵通的某些用戶有時候會發(fā)現(xiàn)自己打算訪問一個地址，卻被轉向了各種推送廣告等網(wǎng)站，這就是DNS劫持。
• DNS 污染，指的是用戶訪問一個地址，國內的服務器(非DNS)監(jiān)控到用戶訪問的已經被標記地址時，服務器偽裝成DNS服務器向用戶發(fā)回錯誤的地址的行為。范例，訪問 Youtube、Facebook 之類網(wǎng)站等出現(xiàn)的狀況。

4、說一說操作系統(tǒng)的虛擬內存？

4.1、虛擬內存介紹，什么是虛擬內存？

這個在我們平時使用電腦特別是 Windows 系統(tǒng)的時候太常見了。很多時候我們使用點開了很多占內存的軟件，這些軟件占用的內存可能已經遠遠超出了我們電腦本身具有的物理內存。

為什么可以這樣呢？ 正是因為 虛擬內存 的存在，通過 虛擬內存 可以讓程序可以擁有超過系統(tǒng)物理內存大小的可用內存空間。

另外，虛擬內存為每個進程提供了一個一致的、私有的地址空間，它讓每個進程產生了一種自己在獨享主存的錯覺（每個進程擁有一片連續(xù)完整的內存空間）。這樣會更加有效地管理內存并減少出錯。

虛擬內存是計算機系統(tǒng)內存管理的一種技術，我們可以手動設置自己電腦的虛擬內存。不要單純認為虛擬內存只是“使用硬盤空間來擴展內存“的技術。虛擬內存的重要意義是它定義了一個連續(xù)的虛擬地址空間，并且 把內存擴展到硬盤空間。

4.2、什么是局部性原理？

局部性原理是虛擬內存技術的基礎，正是因為程序運行具有局部性原理，才可以只裝入部分程序到內存就開始運行。

早在 1968 年的時候，就有人指出我們的程序在執(zhí)行的時候往往呈現(xiàn)局部性規(guī)律，也就是說在某個較短的時間段內，程序執(zhí)行局限于某一小部分，程序訪問的存儲空間也局限于某個區(qū)域。

局部性原理表現(xiàn)在以下兩個方面：

• 時間局部性 ：如果程序中的某條指令一旦執(zhí)行，不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，不久以后該數(shù)據(jù)可能再次被訪問。產生時間局部性的典型原因，是由于在程序中存在著大量的循環(huán)操作。
• 空間局部性 ：一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的地址，可能集中在一定的范圍之內，這是因為指令通常是順序存放、順序執(zhí)行的，數(shù)據(jù)也一般是以向量、數(shù)組、表等形式簇聚存儲的。

時間局部性是通過將近來使用的指令和數(shù)據(jù)保存到高速緩存存儲器中，并使用高速緩存的層次結構實現(xiàn)?？臻g局部性通常是使用較大的高速緩存，并將預取機制集成到高速緩存控制邏輯中實現(xiàn)。虛擬內存技術實際上就是建立了 “內存一外存”的兩級存儲器的結構，利用局部性原理實現(xiàn)髙速緩存。

4.3、虛擬存儲器(虛擬內存)

基于局部性原理，在程序裝入時，可以將程序的一部分裝入內存，而將其他部分留在外存，就可以啟動程序執(zhí)行。由于外存往往比內存大很多，所以我們運行的軟件的內存大小實際上是可以比計算機系統(tǒng)實際的內存大小大的。

**在程序執(zhí)行過程中，當所訪問的信息不在內存時，由操作系統(tǒng)將所需要的部分調入內存，然后繼續(xù)執(zhí)行程序。另一方面，操作系統(tǒng)將內存中暫時不使用的內容換到外存上，從而騰出空間存放將要調入內存的信息。**這樣，計算機好像為用戶提供了一個比實際內存大的多的存儲器——虛擬存儲器。

實際上，我覺得虛擬內存同樣是一種時間換空間的策略，你用 CPU 的計算時間，頁的調入調出花費的時間，換來了一個虛擬的更大的空間來支持程序的運行。不得不感嘆，程序世界幾乎不是時間換空間就是空間換時間。

4.4、虛擬內存技術實現(xiàn)

虛擬內存的實現(xiàn)需要建立在離散分配的內存管理方式的基礎上。 虛擬內存的實現(xiàn)有以下三種方式：

請求分頁存儲管理 ：建立在分頁管理之上，為了支持虛擬存儲器功能而增加了請求調頁功能和頁面置換功能。請求分頁是目前最常用的一種實現(xiàn)虛擬存儲器的方法。請求分頁存儲管理系統(tǒng)中，在作業(yè)開始運行之前，僅裝入當前要執(zhí)行的部分段即可運行。假如在作業(yè)運行的過程中發(fā)現(xiàn)要訪問的頁面不在內存，則由處理器通知操作系統(tǒng)按照對應的頁面置換算法將相應的頁面調入到主存，同時操作系統(tǒng)也可以將暫時不用的頁面置換到外存中。

請求分段存儲管理 ：建立在分段存儲管理之上，增加了請求調段功能、分段置換功能。請求分段儲存管理方式就如同請求分頁儲存管理方式一樣，在作業(yè)開始運行之前，僅裝入當前要執(zhí)行的部分段即可運行；在執(zhí)行過程中，可使用請求調入中斷動態(tài)裝入要訪問但又不在內存的程序段；當內存空間已滿，而又需要裝入新的段時，根據(jù)置換功能適當調出某個段，以便騰出空間而裝入新的段。

請求段頁式存儲管理

這里多說一下？很多人容易搞混請求分頁與分頁存儲管理，兩者有何不同呢？

請求分頁存儲管理建立在分頁管理之上。他們的根本區(qū)別是是否將程序全部所需的全部地址空間都裝入主存，這也是請求分頁存儲管理可以提供虛擬內存的原因，我們在上面已經分析過了。

它們之間的根本區(qū)別在于是否將一作業(yè)的全部地址空間同時裝入主存。請求分頁存儲管理不要求將作業(yè)全部地址空間同時裝入主存?；谶@一點，請求分頁存儲管理可以提供虛存，而分頁存儲管理卻不能提供虛存。

不管是上面那種實現(xiàn)方式，我們一般都需要：

• 一定容量的內存和外存：在載入程序的時候，只需要將程序的一部分裝入內存，而將其他部分留在外存，然后程序就可以執(zhí)行了；
• 缺頁中斷：如果需執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內存（稱為缺頁或缺段），則由處理器通知操作系統(tǒng)將相應的頁面或段調入到內存，然后繼續(xù)執(zhí)行程序；
• 虛擬地址空間 ：邏輯地址到物理地址的變換。

4.5、頁面置換算法

地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不在內存中，則發(fā)生缺頁中斷 。

注：缺頁中斷 就是要訪問的頁不在主存，需要操作系統(tǒng)將其調入主存后再進行訪問。 在這個時候，被內存映射的文件實際上成了一個分頁交換文件。

當發(fā)生缺頁中斷時，如果當前內存中并沒有空閑的頁面，操作系統(tǒng)就必須在內存選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法，我們可以把頁面置換算法看成是淘汰頁面的規(guī)則。

• OPT 頁面置換算法（最佳頁面置換算法） ：最佳(Optimal, OPT)置換算法所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時間內不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。但由于人們目前無法預知進程在內存下的若千頁面中哪個是未來最長時間內不再被訪問的，因而該算法無法實現(xiàn)。一般作為衡量其他置換算法的方法。
• FIFO（First In First Out） 頁面置換算法（先進先出頁面置換算法） : 總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面進行淘汰。
• LRU （Least Currently Used）頁面置換算法（最近最久未使用頁面置換算法） ：LRU算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的時間 T，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其 T 值最大的，即最近最久未使用的頁面予以淘汰。
• LFU （Least Frequently Used）頁面置換算法（最少使用頁面置換算法） : 該置換算法選擇在之前時期使用最少的頁面作為淘汰頁。

5、StringBuilder.append(“xxx”); 后創(chuàng)建新對象嗎？

• 看這一篇就夠了！String StringBuilder StringBuffer區(qū)別以及源碼分析

答案是，沒有創(chuàng)建新對象：

因為 StringBuilder，和 String 不同，它的 char[]數(shù)組沒有被 final 修飾，所以它可以在添加新char字符時，根據(jù)字符數(shù)組容量，進行動態(tài)擴容，而不需要新創(chuàng)建一個 StringBuilder 對象！

如圖所示：

StringBuilder.append()方法如下代碼所示：

// java.lang.StringBuilder 類中
@Override
public StringBuilder append(String str) {
    // 調用父類 AbstractStringBuilder 的append(String str) 方法
    super.append(str);
    return this;
}
// java.lang.AbstractStringBuilder 類中（有興趣可以自己點進去閱讀該類的源碼，還是很有收獲的，這里只作簡述！）
public AbstractStringBuilder append(String str) {
    if (str == null)
        return appendNull();
    int len = str.length();
    // 其成員屬性value[]數(shù)組擴容，類似于ArrayList 的擴容
    // 擴容算法：int newCapacity = (value.length << 1) + 2;
    // 注意容量有上限：MAX_ARRAY_SIZE
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;
}

注： 同理，StringBuffer 也是一樣的！

6、哈希沖突的幾種解決方案，各個優(yōu)缺點？

6.1、開放定址法

這種方法也稱再散列法，其基本思想是：當關鍵字 key 的哈希地址 p=H（key）出現(xiàn)沖突時，以 p 為基礎，產生另一個哈希地址 p1，如果 p1 仍然沖突，再以 p 為基礎，產生另一個哈希地址 p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數(shù)形式：

Hi=（H（key）+di）% m i=1，2，…，n

其中 H（key）為哈希函數(shù)，m 為表長，di 稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三種：

① 線性探測再散列

dii = 1，2，3，…，m-1

這種方法的特點是：沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。ThreadLocal 解決 hash 沖突就采用這種方法！

② 二次探測再散列

di = 12，-12，22，-22，…，k2，-k2 ( k<=m/2 )（2為2次方）

這種方法的特點是：沖突發(fā)生時，在表的左右進行跳躍式探測，比較靈活。

③ 偽隨機探測再散列

di = 偽隨機數(shù)序列

具體實現(xiàn)時，應建立一個偽隨機數(shù)發(fā)生器，（如i=(i+p) % m），并給定一個隨機數(shù)做起點。

例如，已知哈希表長度m=11，哈希函數(shù)為：H（key）= key % 11，則 H（47）=3，H（26）=4，H（60）=5，假設下一個關鍵字為69，則H（69）=3，與47沖突。

如果用線性探測再散列處理沖突，下一個哈希地址為 H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為 H2=（3 + 2）% 11 = 5，還是沖突，繼續(xù)找下一個哈希地址為 H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元。

如果用二次探測再散列處理沖突，下一個哈希地址為 H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希地址為 H2=（3 - 12）% 11 = 2，此時不再沖突，將69填入2號單元。

如果用偽隨機探測再散列處理沖突，且偽隨機數(shù)序列為：2，5，9，………，則下一個哈希地址為 H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址為 H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元。

6.2、再哈希法（再散列法）

這種方法是同時構造多個不同的哈希函數(shù)：

Hi=RH1（key） i=1，2，…，k

當哈希地址Hi=RH1（key）發(fā)生沖突時，再計算 Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

6.3、鏈地址法（拉鏈法）

這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經常進行插入和刪除的情況。

HashMap 解決 hash 沖突就采用的這種方式！

7、使用java如何對一個大的文本文件內容進行去重?

一般可能會想到一次將文本內容讀取到內存中，用 HashSet 對內容去重，但是很不幸這個過程 jvm 會內存溢出，無奈，只能另想辦法，首先將這個大文件中的內容讀取出來，對每行 String 的 hashCode 取模取正整數(shù)，可用取模結果作為文件名，將相同模數(shù)的行寫入同一個文件，再單獨對每個小文件進行去重，最后再合并。

8、MySQL如何優(yōu)化慢查詢？

首先可以通過 explain 命令查看 SQL 執(zhí)行狀態(tài)，如果是沒有加索引，則需要添加索引后再進行查詢。如果已經加了索引，但是表中數(shù)據(jù)量過多，這時候可以考慮水平分表，或者通過 limit 限制一次查詢的記錄總數(shù)。如果已經加了索引，表中數(shù)據(jù)量較少，但是表字段多，大字段檢索效率慢，這時候可以考慮垂直分表！

總結

本篇文章的內容就到這了，希望大家可以多多關注腳本之家的其他精彩內容！

最新評論