ARTS第一周

A:本周因?yàn)楣敬a需要，主要參考研究了暴雪的hash算法

你有一個(gè)非常大的字符串?dāng)?shù)組A，現(xiàn)在又有一個(gè)字符串B，需要你去檢測(cè)B是否存在于A中。最簡(jiǎn)單粗暴的方法是遍歷整個(gè)A，但是這個(gè)方法投入到實(shí)際應(yīng)用時(shí)的運(yùn)行速度是難以接受的。在沒有與其他所有字符串比較前怎么知道該字符串是否存在呢？

解決方法是使用哈希表，即用較小的數(shù)據(jù)類型來代表較大的數(shù)據(jù)類型，例如：用數(shù)字來代表字符串。你可以存儲(chǔ)哈希值與字符串一一對(duì)應(yīng)，當(dāng)需要檢測(cè)一個(gè)字符串時(shí)，就用哈希算法計(jì)算其哈希值，然后與存儲(chǔ)的哈希值比較級(jí)可以得出結(jié)果，使用這一方法根據(jù)數(shù)組的大小和字符串長(zhǎng)度提升速度大約100倍。

 1 unsigned long HashString(char *lpszString)
 2 {   
 3     unsigned long ulHash = 0xf1e2d3c4;        
 4     while (*lpszString != 0)    
 5     {        
 6         ulHash <<= 1;       
 7         ulHash += *lpszString++;      
 8     }   
 9     return ulHash;
10 }

View Code

上述代碼演示了一個(gè)簡(jiǎn)單的哈希算法。該函數(shù)在遍歷整個(gè)字符串時(shí)，將ulHash左移一位再叫上字符值。使用這個(gè)算法 ，"arr\units.dat" 的哈希值是0x5A858026，字符串"unit\neutral\acritter.grp" 的哈希值是0x694CD020。但是這個(gè)算法沒有什么使用價(jià)值，因?yàn)樗a(chǎn)生的哈希值是可以預(yù)測(cè)的，可能使不同的字符產(chǎn)生相同的哈希值，從而產(chǎn)生碰撞。

要解決這一問題方法，網(wǎng)上流傳最神的是MPQ，源自于暴雪公司的文件打包管理，用于Blizzard游戲的數(shù)據(jù)文件，包括圖形，聲音，等級(jí)等數(shù)據(jù)，該算法能夠壓縮，解密，文件分割等功能。詳情見維基：http://en.wikipedia.org/wiki/MPQ。

該算法產(chǎn)生的哈希值完全無法預(yù)測(cè)，非常高效，被稱為"One-Way Hash"( A one-way hash is a an algorithm that is constructed in such a way that deriving the original string (set of strings, actually) is virtually impossible)。

unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{   
    unsigned char *key = (unsigned char *)lpszFileName;   
    unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;   
    int ch;

    while(*key != 0)       
    {      
        ch = toupper(*key++);   
        seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);       
        seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;       
    }   
    return seed1;  
}

View Code

嘗試在前面的示例中使用相同索引，您的程序一定會(huì)有中斷現(xiàn)象發(fā)生，而且不夠快。如果想讓它更快，您能做的只有讓程序不去查詢數(shù)組中的所有散列值。或者您可以只做一次對(duì)比就可以得出在列表中是否存在字符串。聽起來不錯(cuò)，真的么？不可能的啦

    一個(gè)哈希表就是以字符串的哈希值作為下標(biāo)的一類數(shù)組。我的意思是，哈希表使用一個(gè)固定長(zhǎng)度的字符串?dāng)?shù)組（比如1024，2的偶次冪）進(jìn)行存儲(chǔ)；當(dāng)你要看看這個(gè)字符串是否存在于哈希表中，為了獲取這個(gè)字符串在哈希表中的位置，你首先計(jì)算字符串的哈希值，然后哈希表的長(zhǎng)度取模。這樣如果你像上一節(jié)那樣使用簡(jiǎn)單的哈希算法，字符串"arr\units.dat" 的哈希值是0x5A858026,偏移量0x26（0x5A858026 除于0x400等于0x16A160，模0x400等于0x26）。因此，這個(gè)位置的字符串將與新加入的字符串進(jìn)行比較。如果0X26處的字符串不匹配或不存在，那么表示新增的字符串在數(shù)組中不存在。下面是示意的代碼：

1 int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
2 {   
3     int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;       
4     if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))       
5         return nHashPos;   
6     else        
7         return -1; //Error value   
8 }

View Code

上面的說明中存在一個(gè)缺陷。當(dāng)有沖突（兩個(gè)不同的字符串有相同的哈希值）發(fā)生的時(shí)候怎么辦？顯而易見的，它們不能占據(jù)哈希表中的同一個(gè)位置。通常的解決辦法是為每一個(gè)哈希值指向一個(gè)鏈表，用于存放所有哈希沖突的值；

MPQs使用一個(gè)存放文件名的哈希表來跟蹤文件內(nèi)部，但是表的格式與通常方法有點(diǎn)不同，首先不像通常的做法使用哈希值作為偏移量，存儲(chǔ)實(shí)際的文件名。MPQs 根本不存儲(chǔ)文件名，而是使用了三個(gè)不同的哈希值：一個(gè)用做哈希表偏移量，兩個(gè)用作核對(duì)。這兩個(gè)核對(duì)的哈希值用于替代文件名。當(dāng)然從理論上說存在兩個(gè)不同的文件名得到相同的三個(gè)哈希值，但是這種情況發(fā)送的幾率是：1:18889465931478580854784,這應(yīng)該足夠安全了。

MPQ's的哈希表的實(shí)現(xiàn)與傳統(tǒng)實(shí)現(xiàn)的另一個(gè)不同的地方是，相對(duì)與傳統(tǒng)做法（為每個(gè)節(jié)點(diǎn)使用一個(gè)鏈表，當(dāng)沖突發(fā)生的時(shí)候，遍歷鏈表進(jìn)行比較），看一下下面的示范代碼，在MPQ中定位一個(gè)文件進(jìn)行讀操作：

 1 int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
 2 {   
 3     const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;    
 4     int nHash = HashString(lpszString, HASH_OFFSET),nHashA = HashString(lpszString, HASH_A),nHashB = HashString(lpszString, HASH_B), nHashStart = nHash % nTableSize,nHashPos = nHashStart;
 5     while (lpTable[nHashPos].bExists)
 6     {
 7         if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
 8             return nHashPos;
 9 
10         else
11             nHashPos = (nHashPos + 1) % nTableSize;
12             if (nHashPos == nHashStart)
13                 break;
14     }
15     return -1; //Error value
16 
17 }

View Code

無論代碼看上去有多么復(fù)雜，其背后的理論并不難。讀一個(gè)文件的時(shí)候基本遵循下面這樣一個(gè)過程：

1、計(jì)算三個(gè)哈希值（一個(gè)哈希偏移量和兩個(gè)驗(yàn)證值）并保存到變量中；

2、移動(dòng)到哈希偏移量對(duì)應(yīng)的值；

3、對(duì)應(yīng)的位置是否尚未使用？如果是，則停止搜尋，并返回"文件不存在"；

4、這兩個(gè)驗(yàn)證值是否與我們要找的字符串驗(yàn)證值匹配，如果是，停止搜尋，并返回當(dāng)前的節(jié)點(diǎn)；

5、移動(dòng)到下一個(gè)節(jié)點(diǎn)，如果到了最后一個(gè)節(jié)點(diǎn)則返回開始；

6、如果移動(dòng)到了相同的偏移值（遍歷了整個(gè)哈希表），則停止搜尋，并返回"文件不存在"；

7、回到第3步；

如果你注意的話，可能已經(jīng)從我們的解釋和示例代碼注意到，MPQ的哈希表已經(jīng)將所有的文件入口放入MPQ中；那么當(dāng)哈希表的每個(gè)項(xiàng)都被填充的時(shí)候，會(huì)發(fā)生什么呢？答案可能會(huì)讓你驚訝：你不能添加任何文件。有些人可能會(huì)問我為什么文件數(shù)量上有這樣的限制（文件限制），是否有辦法繞過這個(gè)限制？就此而言，如果不重新創(chuàng)建MPQ 的項(xiàng)，甚至無法調(diào)整哈希表的大小。這是因?yàn)槊總€(gè)項(xiàng)在哈希表中的位置會(huì)因?yàn)樘l尺寸而改變，而我們無法得到新的位置，因?yàn)檫@些位置值是文件名的哈希值，而我們根本不知道文件名是什么。

如果想要深入了解MPQ入此坑： http://sfsrealm.hopto.org/inside_mopaq/index.htm

R:　　閱讀部分kafaka的英文文檔，另外由于公司是外企，公司的相關(guān)技術(shù)文檔也是英文的

T:　　本周在學(xué)習(xí)公司技術(shù)文檔的時(shí)候，發(fā)現(xiàn)流程圖很多細(xì)節(jié)自己不清楚，然后就去學(xué)習(xí)了設(shè)計(jì)模式里的UML設(shè)計(jì)圖，

　　　UML（Unified Modeling Language）是一種統(tǒng)一建模語言，為面向?qū)ο箝_發(fā)系統(tǒng)的產(chǎn)品進(jìn)行說明、可視化、和編制文檔的一種標(biāo)準(zhǔn)語言。

　　　由于自己目前還未整理好相關(guān)內(nèi)容，這里貼一下原文地址：http://www.rzrgm.cn/jiangds/p/6596595.html

S:　　基于現(xiàn)在很多公司都是敏捷項(xiàng)目管理，學(xué)習(xí)了敏捷的相關(guān)流程。

　　1.相關(guān)介紹
　　Scrum (英式橄欖球爭(zhēng)球隊(duì)), 軟件開發(fā)模型是敏捷開發(fā)的一種，在最近的一兩年內(nèi)逐漸流行起來。
　　Scrum的基本假設(shè)是：
　　開發(fā)軟件就像開發(fā)新產(chǎn)品，無法一開始就能定義軟件產(chǎn)品最終的規(guī)程，過程中需要研發(fā)、創(chuàng)意、嘗試錯(cuò)誤，所以沒有一種固定的流程可以保證專案成功。Scrum 將軟件開發(fā)團(tuán)隊(duì)比擬成橄欖球隊(duì)，有明確的最高目標(biāo)，熟悉開發(fā)流程　　中所需具備的最佳典范與技術(shù)，具有高度自主權(quán)，緊密地溝通合作，以高度彈性解決各種挑戰(zhàn)，確保每天、每個(gè)階段都朝向目標(biāo)有明確的推進(jìn)。

　　Scrum 開發(fā)流程通常以 30 天(或者更短的一段時(shí)間)為一個(gè)階段，由客戶提供新產(chǎn)品的需求規(guī)格開始，開發(fā)團(tuán)隊(duì)與客戶于每一個(gè)階段開始時(shí)挑選該完成的規(guī)格部分，開發(fā)團(tuán)隊(duì)必須盡力于 30 天后交付成　　果，團(tuán)隊(duì)每天用 15 分鐘開會(huì)檢查每個(gè)成員的進(jìn)度與計(jì)劃，了解所遭遇的困難并設(shè)法排除。

　　2.Scrum較傳統(tǒng)開發(fā)模型的優(yōu)點(diǎn)

　　Scrum模型的一個(gè)顯著特點(diǎn)就是響應(yīng)變化，它能夠盡快地響應(yīng)變化。下面的圖片使用傳統(tǒng)的軟件開發(fā)模型(瀑布模型、螺旋模型或迭代模型)。隨著系統(tǒng)因素（內(nèi)部和外部因素）的復(fù)雜度增加，項(xiàng)目成功　　的可能性就迅速降低。

　　3.Scrum的過程簡(jiǎn)單介紹
　　（1） 將整個(gè)產(chǎn)品的backlog分解成Sprint Backlog,這個(gè)Sprint Backlog是按照目前的人力物力條件可以完成的。
　　（2）召開sprint planning meeting，劃分，確定這個(gè)Sprint內(nèi)需要完成的任務(wù)，標(biāo)注任務(wù)的優(yōu)先級(jí)并分配給每個(gè)成員。注意這里的任務(wù)是以小時(shí)計(jì)算的，并不是按人天計(jì)算。
　　（3） 進(jìn)入sprint開發(fā)周期，在這個(gè)周期內(nèi)，每天需要召開Daily Scrum meeting。
　　（4）整個(gè)sprint周期結(jié)束，召開Sprint review meeting，將成果演示給Product Owner.
　　（5）團(tuán)隊(duì)成員最后召開Sprint retrospective meeting，總結(jié)問題和經(jīng)驗(yàn)。
　　（6）這樣周而復(fù)始，按照同樣的步驟進(jìn)行下一次Sprint.

　　4.敏捷強(qiáng)調(diào)的重點(diǎn)

　　（1）敏捷強(qiáng)調(diào)，客戶們需要在開發(fā)過程中自始至終都和項(xiàng)目緊密配合。擁抱變更，且非常歡迎客戶的反饋。在項(xiàng)目所有的“檢核和適應(yīng)”這一環(huán)節(jié)上，都期望客戶能夠參與并提供寶貴意見，降低風(fēng)險(xiǎn)，為客戶和利益相關(guān)者提供選擇　　空間。它強(qiáng)調(diào)當(dāng)項(xiàng)目的需求發(fā)生了變化，團(tuán)隊(duì)能夠迅速適應(yīng)。主要靠頻繁地小規(guī)模發(fā)布軟件，也就是短的迭代完成的，敏捷方法在幾周或者幾個(gè)月的時(shí)間內(nèi)就完成相對(duì)較小的功能，盡早將盡量小的可用的功能交付使用，并在整個(gè)　　項(xiàng)目周期中持續(xù)改善和增強(qiáng)。

　　（2）敏捷強(qiáng)調(diào)，面對(duì)面的交流，而不是用多而復(fù)雜的文檔。“客戶需要的是支持，而不是文檔。很多時(shí)候我們有一個(gè)錯(cuò)誤的理解，文檔等于支持，但事實(shí)上，文檔并不等于支持。”

　　（3）敏捷強(qiáng)調(diào)，計(jì)劃會(huì)議上，客戶應(yīng)該和開發(fā)負(fù)責(zé)人一起定義User Story，并在計(jì)劃會(huì)議上給出詳細(xì)說明。

　　（4）敏捷強(qiáng)調(diào)，客戶應(yīng)該和開發(fā)負(fù)責(zé)人一起為Backlog定出優(yōu)先級(jí)。

　　（5）  敏捷強(qiáng)調(diào)，客戶和利益相關(guān)者要參與Sprint尾聲的產(chǎn)品演示。根據(jù)客戶和產(chǎn)品負(fù)責(zé)人的關(guān)系，客戶甚至可以參加Sprint回顧會(huì)議。