- Algorithm [劍指offer] 丑數(shù)
- Review Google如何跟蹤您的個(gè)人信息
- Tip TCP的TIME_WAIT機(jī)制
- Share ConcurrentHashMap1.8實(shí)現(xiàn)
Algorithm [劍指offer] 丑數(shù)
本題是來自鸥古客網(wǎng)的【劍指Offer】中的丑數(shù)，其在互聯(lián)網(wǎng)公司校招出現(xiàn)概率較大，建議嘗試做一做叉橱。
題目描述
把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6陋率、8都是丑數(shù)，但14不是秽晚，因?yàn)樗|(zhì)因子7瓦糟。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)赴蝇。
public int GetUglyNumber_Solution(int index) {
if(index <= 0)
return 0;
if(index == 1)
return 1;
int t2 = 0, t3 = 0, t5 = 0;
int [] res = new int[index];
res[0] = 1;
for(int i = 1; i<index; i++){
//下一個(gè)丑數(shù)肯定出現(xiàn)2 3 5 倍數(shù)中菩浙，取最小的
res[i] = Math.min(res[t2]*2, Math.min(res[t3]*3, res[t5]*5));
if(res[i] == res[t2]*2) t2++;
if(res[i] == res[t3]*3) t3++;
if(res[i] == res[t5]*5) t5++;
}
return res[index-1];
}
解題思路
我們只求丑數(shù)，不要去管非丑數(shù)句伶。每個(gè)丑數(shù)必然是由小于它的某個(gè)丑數(shù)乘以2劲蜻，3或5得到的，這樣我們把求得的丑數(shù)都保存下來考余，用之前的丑數(shù)分別乘以2先嬉，3，5楚堤，找出這三這種最小的并且大于當(dāng)前最大丑數(shù)的值疫蔓，即為下一個(gè)我們要求的丑數(shù)。這種方法用空間換時(shí)間身冬，時(shí)間復(fù)雜度為O(n)鳄袍。
Google如何跟蹤您的個(gè)人信息
每次互聯(lián)網(wǎng)搜索都包含關(guān)鍵字，而您剛剛輸入Google的關(guān)鍵字則由廣告客戶進(jìn)行爭奪吏恭。每個(gè)提供與您的關(guān)鍵字相關(guān)的產(chǎn)品的廣告客戶都希望看到并點(diǎn)擊其廣告。
點(diǎn)擊廣告后重罪，您的信息會(huì)傳遞給搜索引擎營銷人員樱哼，并將其永久存儲(chǔ)在AdWords帳戶中哀九，永遠(yuǎn)不會(huì)被刪除。
只要您使用Google搅幅，Google一直在為您構(gòu)建“公民資料”阅束。
搜索引擎營銷的圣杯：多設(shè)備歸屬。當(dāng)這項(xiàng)技術(shù)得以實(shí)現(xiàn)時(shí)茄唐，廣告將無縫地跟蹤搜索者 - 不僅跨渠道（例如息裸，社交，有機(jī)和電子郵件）沪编，而且跨設(shè)備（例如呼盆，從移動(dòng)設(shè)備到平板電腦，從筆記本電腦到電視再到桌面）蚁廓。
在手機(jī)上搜索產(chǎn)品访圃，然后親自走進(jìn)商店。按此順序執(zhí)行此操作相嵌，Google可能會(huì)使用您手機(jī)的GPS數(shù)據(jù)來關(guān)聯(lián)您的廣告點(diǎn)擊和店內(nèi)購買腿时。
今天，人們告訴谷歌他們在其他地方承認(rèn)的事情 - 不是他們的配偶饭宾，醫(yī)生或縮水批糟。但是如果谷歌用戶了解這個(gè)兔子洞有多遠(yuǎn)，他們就不會(huì)對(duì)搜索引擎這么直率看铆。有了我將提供的內(nèi)幕信息徽鼎，我希望讀者可以回到谷歌不是唯一可以告訴他們的恐懼，遺憾性湿，希望和夢想的地方纬傲。
TCP的TIME_WAIT機(jī)制
TIME_WAIT的產(chǎn)生條件：主動(dòng)關(guān)閉方在發(fā)送四次揮手的最后一個(gè)ACK會(huì)變?yōu)門IME_WAIT狀態(tài)，保留次狀態(tài)的時(shí)間為兩個(gè)MSL（linux里一個(gè)MSL為30s肤频，是不可配置的）
TIME_WAIT兩個(gè)MSL的作用：可靠安全的關(guān)閉TCP連接叹括。比如網(wǎng)絡(luò)擁塞，主動(dòng)方最后一個(gè)ACK被動(dòng)方?jīng)]收到宵荒，這時(shí)被動(dòng)方會(huì)對(duì)FIN開啟TCP重傳汁雷，發(fā)送多個(gè)FIN包，在這時(shí)尚未關(guān)閉的TIME_WAIT就會(huì)把這些尾巴問題處理掉报咳，不至于對(duì)新連接及其它服務(wù)產(chǎn)生影響侠讯。
MSL概念：MSL指的是報(bào)文段的最大生存時(shí)間，如果報(bào)文段在網(wǎng)絡(luò)活動(dòng)了MSL時(shí)間暑刃，還沒有被接收厢漩，那么會(huì)被丟棄。
TIME_WAIT占用的資源：少量內(nèi)存（查資料大概4K）和一個(gè)fd岩臣。
TIME_WAIT關(guān)閉的危害：
1溜嗜、 網(wǎng)絡(luò)情況不好時(shí)宵膨，如果主動(dòng)方無TIME_WAIT等待，關(guān)閉前個(gè)連接后炸宵，主動(dòng)方與被動(dòng)方又建立起新的TCP連接辟躏，這時(shí)被動(dòng)方重傳或延時(shí)過來的FIN包過來后會(huì)直接影響新的TCP連接；
2土全、 同樣網(wǎng)絡(luò)情況不好并且無TIME_WAIT等待捎琐，關(guān)閉連接后無新連接，當(dāng)接收到被動(dòng)方重傳或延遲的FIN包后裹匙，會(huì)給被動(dòng)方回一個(gè)RST包瑞凑，可能會(huì)影響被動(dòng)方其它的服務(wù)連接。
TCP: time wait bucket table overflow產(chǎn)生原因及影響：原因是超過了linux系統(tǒng)tw數(shù)量的閥值幻件。危害是超過閥值后﹐系統(tǒng)會(huì)把多余的time-wait socket 刪除掉拨黔，并且顯示警告信息，如果是NAT網(wǎng)絡(luò)環(huán)境又存在大量訪問绰沥，會(huì)產(chǎn)生各種連接不穩(wěn)定斷開的情況篱蝇。
解決辦法：
可以嘗試縮小它的設(shè)置，比如十秒徽曲，甚至一秒零截，具體設(shè)置成多少合適取決于網(wǎng)絡(luò)情況而定，當(dāng)然也可以參考相關(guān)的案例秃臣。
TIME_WAIT總是在關(guān)閉發(fā)起方產(chǎn)生涧衙，服務(wù)端資源有限，可能同時(shí)連接上萬個(gè)連接奥此，所以盡量由客戶端發(fā)起關(guān)閉請(qǐng)求弧哎，這樣產(chǎn)生的就都在客戶端
tcp_tw_recycle：顧名思義就是回收TIME_WAIT連接≈苫ⅲ可以說這個(gè)內(nèi)核參數(shù)已經(jīng)變成了大眾處理TIME_WAIT的萬金油撤嫩，如果你在網(wǎng)絡(luò)上搜索TIME_WAIT的解決方案，十有八九會(huì)推薦設(shè)置它蠢终，不過這里隱藏著一個(gè)不易察覺的陷阱：
當(dāng)多個(gè)客戶端通過NAT方式聯(lián)網(wǎng)并與服務(wù)端交互時(shí)序攘，服務(wù)端看到的是同一個(gè)IP，也就是說對(duì)服務(wù)端而言這些客戶端實(shí)際上等同于一個(gè)寻拂，可惜由于這些客戶端的時(shí)間戳可能存在差異程奠，于是乎從服務(wù)端的視角看，便可能出現(xiàn)時(shí)間戳錯(cuò)亂的現(xiàn)象祭钉，進(jìn)而直接導(dǎo)致時(shí)間戳小的數(shù)據(jù)包被丟棄瞄沙。參考：tcp_tw_recycle和tcp_timestamps導(dǎo)致connect失敗問題。
- tcp_max_tw_buckets：顧名思義就是控制TIME_WAIT總數(shù)。官網(wǎng)文檔說這個(gè)選項(xiàng)只是為了阻止一些簡單的DoS攻擊帕识，平常不要人為的降低它泛粹。如果縮小了它，那么系統(tǒng)會(huì)將多余的TIME_WAIT刪除掉肮疗，日志里會(huì)顯示：「TCP: time wait bucket table overflow」。
需要提醒大家的是物極必反扒接，曾經(jīng)看到有人把「tcp_max_tw_buckets」設(shè)置成0伪货，也就是說完全拋棄TIME_WAIT，這就有些冒險(xiǎn)了钾怔，用一句圍棋諺語來說：入界宜緩碱呼。
ConcurrentHashMap1.8實(shí)現(xiàn)
JDK1.8版本的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近HashMap，相對(duì)而言宗侦，ConcurrentHashMap只是增加了同步的操作來控制并發(fā)愚臀，從JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹,相對(duì)而言矾利，總結(jié)如下思考:
- JDK1.8的實(shí)現(xiàn)降低鎖的粒度姑裂，JDK1.7版本鎖的粒度是基于Segment的，包含多個(gè)HashEntry男旗，而JDK1.8鎖的粒度就是HashEntry（首節(jié)點(diǎn)）
- JDK1.8版本的數(shù)據(jù)結(jié)構(gòu)變得更加簡單舶斧，使得操作也更加清晰流暢，因?yàn)橐呀?jīng)使用synchronized來進(jìn)行同步察皇，所以不需要分段鎖的概念茴厉，也就不需要Segment這種數(shù)據(jù)結(jié)構(gòu)了，由于粒度的降低什荣，實(shí)現(xiàn)的復(fù)雜度也增加了
- JDK1.8使用紅黑樹來優(yōu)化鏈表矾缓，基于長度很長的鏈表的遍歷是一個(gè)很漫長的過程，而紅黑樹的遍歷效率是很快的稻爬，代替一定閾值的鏈表嗜闻，這樣形成一個(gè)最佳拍檔
- JDK1.8為什么使用內(nèi)置鎖synchronized來代替重入鎖ReentrantLock，我覺得有以下幾點(diǎn):
- 因?yàn)榱６冉档土艘蚱谙鄬?duì)而言的低粒度加鎖方式泞辐，synchronized并不比ReentrantLock差，在粗粒度加鎖中ReentrantLock可能通過Condition來控制各個(gè)低粒度的邊界竞滓，更加的靈活咐吼，而在低粒度中，Condition的優(yōu)勢就沒有了
- JVM的開發(fā)團(tuán)隊(duì)從來都沒有放棄synchronized商佑，而且基于JVM的synchronized優(yōu)化空間更大锯茄，使用內(nèi)嵌的關(guān)鍵字比使用API更加自然
- 在大量的數(shù)據(jù)操作下，對(duì)于JVM的內(nèi)存壓力，基于API的ReentrantLock會(huì)開銷更多的內(nèi)存肌幽，雖然不是瓶頸晚碾，但是也是一個(gè)選擇依據(jù)
參考文獻(xiàn)：
理解TIME_WAIT，徹底弄清解決TCP: time wait bucket table overflow
TIME_WAIT原理
TCP/IP詳解--TIME_WAIT狀態(tài)存在的原因
面試總結(jié)之time_wait狀態(tài)產(chǎn)生的原因喂急，危害格嘁，如何避免
ConcurrentHashMap1.8實(shí)現(xiàn)
ConcurrentHashMap1.7實(shí)現(xiàn)
為并發(fā)而生的 ConcurrentHashMap（Java 8）
