作者HYL (@Seattle)
看板Oversea_Job
標題Re: 請教一些面試問題
時間Fri Aug 24 19:33:13 2007
※ 引述《[email protected] (michaelz)》之銘言：
: ※ 引述《[email protected] (遺憾太常。)》之銘言：
: : 我會設計的方法：
: : URL的有效字元 A-Z a-z 加上一些符號，大概總共算是60個symbol，
: : n0*60^0+n1*60^1+n2*60^2+n3*60^3+n4*60^4+...+ni*60^i
: : 不過這個數字大的一塌糊塗，所以不是什麼好方法；
: : 如果不想要collision的話，資料量可能就是那麼大。
: : 至於partition的話，用開頭字母就可以作uniform dist.了。
: 用開頭字母的話大概會看到一堆http, www之類的東西..然後所有的東西都要放在同一個
: partition, 用整個url算hash code可能會好一點
理論上要產生兩個有一樣MD5 Hash Code的"有意義"文字是不可能的，
，可以把碰撞的狀況省下來，順便也不用存原始的 url進hashtable中
如果是我，會用 MD5-128來把 url編碼。一個 url指占 16 byte 的空
間，四十億個網頁大概是 59GByte ， 還塞得下硬碟空間。
考慮到讀取的效益，所以會把資料割成 1MB大小的檔案( 一個檔案存2^16
個 hashcode )，總共有59,000 個；再考量到 file system對同一目
錄底下若有大量檔案，開檔的效率會下降，所以分目錄除存
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 67.183.24.112
※ 編輯: HYL 來自: 67.183.24.112 (08/24 19:34)
1F：推 willieliao:如果這個問題真的是用來作search engine的話還要存上次 08/24 23:40
2F：→ willieliao:抓的時間，不然yahoo.com的內容會停在199x年xd 08/24 23:42