想起以前做項(xiàng)目，用到了Rsync check 文件內(nèi)容双絮，未免以后忘記，現(xiàn)在整理下 大致邏輯

背景：

? ? ? ?我們新建一個(gè)文件，上傳囤攀，再改動(dòng)一點(diǎn)點(diǎn)東西软免，通用辦法就是，把改動(dòng)后的文件焚挠，上傳覆蓋以前的文件或杠，這樣不會(huì)錯(cuò)，但是有個(gè)問題宣蔚，如果這個(gè)文件很大向抢，那么整個(gè)上傳就會(huì)消耗大量的時(shí)間和流量，哪怕我們只是編輯了一個(gè)標(biāo)點(diǎn)符號(hào)胚委。

解決方案：

? ? ? ?那么有沒有什么辦法挟鸠，我只上傳編輯的部分，那就萬事大吉了亩冬，但是沒有編輯的部分艘希，我怎么告訴server 呢，我可以告訴server 硅急，我沒有改變的部分的 offset 覆享，比如： 0-121 byte，180- 300byte营袜，編輯的部分我上傳data撒顿，那么最后的結(jié)果是什么呢：

0-121byte（location），122-179byte（data）荚板，180-300 byte.

?????那么凤壁，我怎么找出編輯的部分呢，大致方案如下：

? ? 1. 我將原內(nèi)容分割成若干部分（具體每部分多大跪另，根據(jù)文件大小確定）拧抖，每部分通過算法，得到兩個(gè)值免绿，sha -> sum1唧席，md5 ->sum2?

? ? 2. 我將編輯后的文件，按照同樣大小嘲驾，分割淌哟，依次對(duì)比，如果發(fā)現(xiàn)sum1 和 sum2 都一樣距淫，那么我們認(rèn)為這部分是以前的內(nèi)容绞绒，記錄下來

? ? 3. 遇到sum1 不一致，或者sum1一致榕暇，sum2 不一致的內(nèi)容（這就是為什么要通過兩個(gè)算法去校驗(yàn)，sum2 準(zhǔn)確，但是消耗性能彤枢，sum1 性能消耗較低狰晚，但是不準(zhǔn)確），那么我們往后移動(dòng)一個(gè)byte缴啡，這一個(gè)byte 作為新增的內(nèi)容壁晒，記錄下位置，接著從移動(dòng)過后的位置對(duì)比

????4. 一個(gè)字節(jié)一個(gè)字節(jié)的添加太麻煩业栅，還有如果重用的部分是連續(xù)的秒咐，那么我們可以添加邏輯把連續(xù)新增的字節(jié)或者連續(xù)重用的字節(jié)連起來，最后上傳的時(shí)候碘裕，再上傳連起來的部分的offset 和data

? ? 大致的邏輯就是這樣携取，但是有個(gè)問題：

? ? 原內(nèi)容：[(sum1,sum2),(sum1,sum2),(sum1,sum2).......]

? ? 我們計(jì)算編輯后的文件的時(shí)候，拿到sum1 和sum2 帮孔，怎么去對(duì)比呢雷滋，要知道，上面的數(shù)組是相當(dāng)龐大的文兢，你要挨個(gè)去對(duì)比晤斩，我的天，性能災(zāi)難姆坚，得不償失澳泵。

? ? 有什么辦法呢，如果能想key 兼呵，value 這樣挨個(gè)對(duì)應(yīng)起來就好了烹俗，這樣，直接找key萍程，看value 是否有值幢妄。

? ??原內(nèi)容：[{sum1:{sum2:xxxxx,location :123-456}}.......]

? ? 但是，這樣有新的問題：

? ? ? ? ? ? 1. sum1 有可能碰撞（不精確）

? ? ? ? ? ? 2. sum1 還是很長茫负，key value 都很長蕉鸳，這樣的性能我們是無法接受的

? ? 如果有什么辦法，能夠?qū)um1 或者sum2 編程一個(gè)數(shù)字或者簡單的字符就好了忍法。

? ? 網(wǎng)上找找潮尝，果然有，將可以通過一個(gè)算法將sum1 變成一個(gè) 數(shù)字：

? ? ? ? ? ? ? ? f(sum1) -> 10233

? ? 我們?cè)贅?gòu)建一個(gè)hashtable 樣子饿序， 表的樣子是什么呢

? ? hashTable[10233] = i, i 表示在原文件中的第幾端勉失，至于其他的都設(shè)置成-1，最后結(jié)果

? ? hashTable[0] = -1,....hashTable[10233] = 0,......

? ? 我們拿到編輯后的文件段的sum1原探， 通過同樣的運(yùn)算乱凿， 獲得的值也是 10233顽素， 那么我們拿這個(gè)10233 反過來找hashTable， 發(fā)現(xiàn)value 不是-1徒蟆， 恭喜你可能找到了胁出，這時(shí)再對(duì)比下sum2，這樣就能最終確定了段审，這樣是不是性能提高了很多

? ? 但是還有一個(gè)問題全蝶，不同內(nèi)容的sum1 可能一樣啊，這咋整寺枉，也就是抑淫，可能第57 段和第89段的sum1都是10233，那么結(jié)果就是姥闪，后面的把前面的覆蓋始苇，結(jié)果就是 hashTabel[10233] = 89

? ? 這咋整？

? ? 我們想如果能記錄后一段甘畅，也就是在覆蓋前一段的時(shí)候能夠把前一段的location 記錄下來就好了埂蕊，ok，那么我們新定義一個(gè)變量chain疏唾，通常情況下蓄氧，chain值為-1，只有發(fā)現(xiàn)hashTable[10233]有值時(shí)槐脏，我們把后一個(gè)位置的chain 設(shè)置成前一個(gè)位置的location喉童，這樣是不是就不怕覆蓋了，結(jié)果就是顿天，假設(shè)第0堂氯，57，89 的結(jié)果都是10233牌废，那么：

hashTable[10233] = 89, data[89].chain = 57, data[57].chain = 0

代碼如下：

for I in 0..<count {

? ? ? ? ? ? ? ? let sumData = file.sums[I] ? ? ? ?

?????????? ? ? ?let t =self.getHashEntry( sum1: sumData.sum1,true)

? ? ? ? ? ? ? ? let subsum = file.sums[i]

? ? ? ? ? ? ? ? subsum.chain=hashTable[Int(t)]

? ? ? ? ? ? ? ? self.hashTable[Int(t)] = i

? ? ? ? ? ? }

perfect!