近期浮毯，我們項(xiàng)目里面引入了IGListKit的第三方庫拳球，它是對(duì)collectionView的一層封裝倦西，主要用于feed流的實(shí)現(xiàn)，它的其中一個(gè)優(yōu)勢(shì)就是刷新視圖的時(shí)候并不是刷新的整個(gè)collectionView旅急，而是通過diff算法算出新老數(shù)組的差異逢勾，根據(jù)這個(gè)差異collectionView進(jìn)行部分更新牡整，這個(gè)更新的邏輯在UICollectionView+IGListBatchUpdateData.m這個(gè)分類中藐吮，函數(shù)如下：

- (void)ig_applyBatchUpdateData:(IGListBatchUpdateData *)updateData {
    [self deleteItemsAtIndexPaths:updateData.deleteIndexPaths];
    [self insertItemsAtIndexPaths:updateData.insertIndexPaths];

    for (IGListMoveIndexPath *move in updateData.moveIndexPaths) {
        [self moveItemAtIndexPath:move.from toIndexPath:move.to];
    }

    for (IGListMoveIndex *move in updateData.moveSections) {
        [self moveSection:move.from toSection:move.to];
    }

    [self deleteSections:updateData.deleteSections];
    [self insertSections:updateData.insertSections];
}

這個(gè)函數(shù)會(huì)在-performBatchUpdates:completion:的batchUpdatesBlock中被調(diào)用√颖矗可以看出谣辞，每次更新只會(huì)涉及到部分視圖的插入、刪除沐扳、移動(dòng)泥从，非常高效。下面分析這個(gè)diff算法是如何將這類差異算出來的沪摄。

前置工作

diff函數(shù)簡(jiǎn)化

整個(gè)diff算法相關(guān)的流程都放在IGListDiff.mm這個(gè)類里了躯嫉，其核心的函數(shù)的聲明如下：

static id IGListDiffing(BOOL returnIndexPaths,
                        NSInteger fromSection,
                        NSInteger toSection,
                        NSArray<id<IGListDiffable>> *oldArray,
                        NSArray<id<IGListDiffable>> *newArray,
                        IGListDiffOption option,
                        IGListExperiment experiments)

這個(gè)函數(shù)參數(shù)有點(diǎn)多，而實(shí)際上核心的兩個(gè)參數(shù)是oldArray和newArray杨拐，returnIndexPaths在一般情況下傳NO祈餐，可以用NO代替,而fromSection和toSection在分析算法中可以刪掉（默認(rèn)在同一個(gè)section上操作）option一般傳IGListDiffEquality，因此可以用IGListDiffEquality代替哄陶，而experiments整個(gè)流程都沒用到因此可以直接刪除帆阳，經(jīng)過一番代碼替換/刪除之后，這個(gè)函數(shù)的聲明就簡(jiǎn)化成了

static id IGListDiffing(NSArray<id<IGListDiffable>> *oldArray,
                        NSArray<id<IGListDiffable>> *newArray)

相關(guān)函數(shù)/結(jié)構(gòu)體/方法介紹

IGListIndexSetResult

這是函數(shù)的返回值（returnIndexPaths為NO的時(shí)候）其結(jié)構(gòu)如下

NS_SWIFT_NAME(ListIndexSetResult)
@interface IGListIndexSetResult : NSObject
///插入索引的集合（新數(shù)組的索引）
@property (nonatomic, strong, readonly) NSIndexSet *inserts;
///刪除索引的集合（舊數(shù)組的索引）
@property (nonatomic, strong, readonly) NSIndexSet *deletes;
///更新索引的集合（舊數(shù)組的索引）
@property (nonatomic, strong, readonly) NSIndexSet *updates;
///移動(dòng)索引的集合（from是舊數(shù)組的索引屋吨，to是新數(shù)組的索引）
@property (nonatomic, copy, readonly) NSArray<IGListMoveIndex *> *moves;
///是否改變過
@property (nonatomic, assign, readonly) BOOL hasChanges;

@end

NS_ASSUME_NONNULL_END

最后返回的結(jié)果需要給inserts蜒谤、deletes、updates至扰、moves賦值返回（初始化方法在IGListIndexSetResultInternal.h里面）

IGListMoveIndex

封裝一個(gè)移動(dòng)的操作鳍徽，其結(jié)構(gòu)如下：

NS_ASSUME_NONNULL_BEGIN

NS_SWIFT_NAME(ListMoveIndex)
@interface IGListMoveIndex : NSObject

@property (nonatomic, assign, readonly) NSInteger from;

@property (nonatomic, assign, readonly) NSInteger to;

@end

專門的初始化方法在IGListMoveIndexInternal.h里面

IGListDiffable

一個(gè)協(xié)議，數(shù)組里的對(duì)象都需要遵循這個(gè)協(xié)議才能有效地使用diff函數(shù)

NS_SWIFT_NAME(ListDiffable)
@protocol IGListDiffable

//返回對(duì)象唯一id敢课，在diff算法中以它作為元素存入哈希表的key
- (nonnull id<NSObject>)diffIdentifier;

//判斷兩個(gè)對(duì)象是否相等旬盯，在diff算法用這個(gè)方法判斷兩個(gè)對(duì)象是否是同一個(gè)對(duì)象
- (BOOL)isEqualToDiffableObject:(nullable id<IGListDiffable>)object;

@end

在IGListKit中，NSString和NSNumber默認(rèn)遵循了這個(gè)協(xié)議

IGListEntry

diff算法中用于標(biāo)記元素狀態(tài)的結(jié)構(gòu)體

struct IGListEntry {
    該元素在舊數(shù)組中出現(xiàn)的次數(shù)
    NSInteger oldCounter = 0;
    該元素在新數(shù)組中出現(xiàn)的次數(shù)
    NSInteger newCounter = 0;
    存放元素在舊數(shù)組中的索引，在算法中胖翰，可以保證棧頂是較小的索引
    stack<NSInteger> oldIndexes;
    這個(gè)元素是否需要更新
    BOOL updated = NO;
};

IGListRecord

封裝entry和它所在的索引接剩，主要用于插入和刪除（如果index有值，則代表該元素需要插入或者刪除萨咳，否則為NSNotFound）

struct IGListRecord {
    IGListEntry *entry;
    mutable NSInteger index;
    
    IGListRecord() {
        entry = NULL;
        index = NSNotFound;
    }
};

其它工具函數(shù)

還有其它的一些函數(shù)懊缺，在section/useIndexPath這些參數(shù)去掉之后，變得沒那么復(fù)雜了培他，下面統(tǒng)一列出來

///取元素在哈希表中的key鹃两，這里取的就是diffIdentifier
static id<NSObject> IGListTableKey(__unsafe_unretained id<IGListDiffable> object) {
    id<NSObject> key = [object diffIdentifier];
    NSCAssert(key != nil, @"Cannot use a nil key for the diffIdentifier of object %@", object);
    return key;
}

///判斷兩個(gè)值是否相等，這個(gè)函數(shù)在建無序哈希表的時(shí)候用到
struct IGListEqualID {
    bool operator()(const id a, const id b) const {
        return (a == b) || [a isEqual: b];
    }
};

///求元素的哈希值舀凛，這個(gè)函數(shù)在建無序哈希表的時(shí)候用到
struct IGListHashID {
    size_t operator()(const id o) const {
        return (size_t)[o hash];
    }
};

///給集合增加索引
static void addIndexToCollection( __unsafe_unretained id collection,NSInteger index) {
    [collection addIndex:index];
};

///向哈希表增加索引
static void addIndexToMap( NSInteger index, __unsafe_unretained id<IGListDiffable> object, __unsafe_unretained NSMapTable *map) {
    id value;
    value = @(index);

    [map setObject:value forKey:[object diffIdentifier]];
}

IGListDiffing函數(shù)的算法流程

下面開始逐步剖析IGListDiffing這個(gè)函數(shù)

變量的聲明

    const NSInteger newCount = newArray.count;
    const NSInteger oldCount = oldArray.count;
    
    NSMapTable *oldMap = [NSMapTable strongToStrongObjectsMapTable];
    NSMapTable *newMap = [NSMapTable strongToStrongObjectsMapTable];
    
    unordered_map<id<NSObject>, IGListEntry, IGListHashID, IGListEqualID> table;

newCount俊扳，oldCount方便后面使用，table是后面初始化的哈希表猛遍，為了方便講解把它挪到前面來馋记，它以diffIdentifier為鍵，entry為值懊烤，其查找復(fù)雜度為o(1)梯醒。而oldMap和newMap并不參與這個(gè)diff算法，它們到最后就是已數(shù)組的index為key,數(shù)組的元素為值的哈希表而已腌紧。不過因?yàn)閮?yōu)化算法(減少循環(huán)的次數(shù))而把它的初始化操作寫到diff算法的循環(huán)里面茸习。把初始化操作拎出來就是

     for (NSInteger i = 0; i < oldCount; i++) {
        addIndexToMap(i, oldArray[i], oldMap);
    }
    for (NSInteger i = 0; i < newCount; i++) {
        addIndexToMap( i, newArray[i], newMap);
    }

處理特殊情況

如果newCount或oldCount為0,則可以判斷為刪除所有舊元素或者增加所有新元素，就不需要走diff算法了

    if (newCount == 0) {
            [oldArray enumerateObjectsUsingBlock:^(id<IGListDiffable> obj, NSUInteger idx, BOOL *stop) {
                addIndexToMap( idx, obj, oldMap);
            }];
            return [[IGListIndexSetResult alloc] initWithInserts:[NSIndexSet new]
                                                         deletes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, oldCount)]
                                                         updates:[NSIndexSet new]
                                                           moves:[NSArray new]
                                                     oldIndexMap:oldMap
                                                     newIndexMap:newMap];
        
    }
    
    if (oldCount == 0) {
            [newArray enumerateObjectsUsingBlock:^(id<IGListDiffable> obj, NSUInteger idx, BOOL *stop) {
                addIndexToMap(idx, obj, newMap);
            }];
            return [[IGListIndexSetResult alloc] initWithInserts:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, newCount)]
                                                         deletes:[NSIndexSet new]
                                                         updates:[NSIndexSet new]
                                                           moves:[NSArray new]
                                                     oldIndexMap:oldMap
                                                     newIndexMap:newMap];
        
    }

diff算法Step1

遍歷新數(shù)組,為每個(gè)新數(shù)組的元素創(chuàng)建一個(gè)entry壁肋，并增加entry的newCounter

    vector<IGListRecord> newResultsArray(newCount);
    for (NSInteger i = 0; i < newCount; i++) {
        id<NSObject> key = IGListTableKey(newArray[i]);
        IGListEntry &entry = table[key];
        entry.newCounter++;
        
        //增加NSNotFound是為了防止oldIndexed為空号胚，NSNotFound相當(dāng)于棧底的標(biāo)志位
        entry.oldIndexes.push(NSNotFound);
        
        
        newResultsArray[i].entry = &entry;
    }

需要注意的是IGListEntry &entry = table[key]這句代碼返回的是entry的地址（如果沒有table里沒有這個(gè)key就創(chuàng)建）,如果數(shù)組中有相同的key的時(shí)候，newResultsArray存放的索引中的entry會(huì)指向同一個(gè)地址浸遗。

這一步過后猫胁，會(huì)建立一個(gè)用于存放IGListRecord的newResultsArray，每個(gè)IGListRecord的index仍未NSNotFound乙帮，entry為新創(chuàng)建的IGListEntry杜漠，其newCounter都是大于0的。

diff算法Step2

遍歷舊數(shù)組察净，為每個(gè)舊數(shù)組的元素創(chuàng)建entry驾茴，并增加它們的oldCounter，將對(duì)應(yīng)的索引壓入oldIndexes棧中氢卡。

    vector<IGListRecord> oldResultsArray(oldCount);
    for (NSInteger i = oldCount - 1; i >= 0; i--) {
        id<NSObject> key = IGListTableKey(oldArray[i]);
        IGListEntry &entry = table[key];
        entry.oldCounter++;
        
        // 將i入棧
        entry.oldIndexes.push(i);
        
        oldResultsArray[i].entry = &entry;
    }

這里的循環(huán)采用倒序的方式锈至，在多個(gè)key相同的時(shí)候，oldIndexes會(huì)有一系列的索引壓棧译秦，倒序就會(huì)確保棧頂?shù)乃饕亲钚〉摹?/p>

這一步過后峡捡，會(huì)建立一個(gè)用于存放IGListRecord的oldResultsArray击碗，每個(gè)IGListRecord的index仍未NSNotFound，對(duì)于oldResultsArray和newResultsArray其中的entry们拙，分三種情況：

• 該元素只有新數(shù)組有稍途，則entry的newCounter>0，oldCounter=0,oldIndexes棧頂為NSNotFound
• 該元素只有舊數(shù)組有砚婆，則entry的newCounter=0械拍，oldCounter>0,oldIndexes棧頂不為NSNotFound，而是元素在舊數(shù)組中的最小索引
• 該元素新舊數(shù)組有装盯，則entry的newCounter>0坷虑，oldCounter>0,oldIndexes棧頂不為NSNotFound，而是元素在舊數(shù)組中的最小索引,而oldResultsArray和newResultsArray都指向同一個(gè)entry

diff算法Step3

遍歷新數(shù)組埂奈，新舊數(shù)組都出現(xiàn)的元素迄损，其IGListRecord的index會(huì)賦上其在新/舊數(shù)組的索引

    for (NSInteger i = 0; i < newCount; i++) {
        IGListEntry *entry = newResultsArray[i].entry;
        NSCAssert(!entry->oldIndexes.empty(), @"Old indexes is empty while iterating new item %li. Should have NSNotFound", (long)i);
        ///拿到oldIndexes的棧頂，也就是拿到改元素在oldArray的第一個(gè)索引账磺，然后pop出來
        const NSInteger originalIndex = entry->oldIndexes.top();
        entry->oldIndexes.pop();
        
        if (originalIndex < oldCount) {
            const id<IGListDiffable> n = newArray[i];
            const id<IGListDiffable> o = oldArray[originalIndex];
            if (n != o && ![n isEqualToDiffableObject:o]) {
            //標(biāo)記為update的條件芹敌，只有在key相同且n和o不一樣且isEqualToDiffableObject不相同的時(shí)候
            //才會(huì)走進(jìn)這個(gè)條件
              entry->updated = YES;
            }
        }
        //給兩邊的index賦上對(duì)應(yīng)的索引，如果originalIndex是NSNotFound绑谣，則不會(huì)走到這個(gè)條件
        if (originalIndex != NSNotFound
            && entry->newCounter > 0
            && entry->oldCounter > 0) {
            
            newResultsArray[i].index = originalIndex;
            oldResultsArray[originalIndex].index = i;
        }
    }

PS: entry->updated = YES這個(gè)條件很難觸發(fā)党窜，而且觸發(fā)了也沒看出什么作用拗引，在前面的- (void)ig_applyBatchUpdateData:(IGListBatchUpdateData *)updateData中借宵，是沒有reload這個(gè)操作的，究其原因矾削，在前面_flushCollectionView的方法里面為了規(guī)避一個(gè)bug而將update的操作統(tǒng)一換成delete和insert了壤玫。

這一步主要的作用在于最后，這一步過后哼凯，如果一個(gè)元素兩邊的數(shù)組都存在欲间，newResultsArray中對(duì)應(yīng)的元素的index就會(huì)指向該元素在oldArray中的索引，oldResultsArray對(duì)應(yīng)的元素的index就會(huì)指向該元素在newArray中的索引断部。這個(gè)賦值主要是用于統(tǒng)計(jì)移動(dòng)元素的操作猎贴。

如果newArray和oldArray中又相同的元素，且出現(xiàn)了數(shù)次會(huì)怎么樣呢蝴光？在實(shí)際的IGListKit的使用中一般會(huì)規(guī)避這種情況她渴。如果真的發(fā)生了，分析這一步的算法不難發(fā)現(xiàn)：該元素在oldArray中的第i次出現(xiàn)的索引會(huì)跟在newArray中的第i次出現(xiàn)的索引相匹配蔑祟，這種算法得出來的結(jié)果并不是最佳的趁耗，這個(gè)在后面講。

diff算法Step4

接下來就是增刪改查數(shù)組的生成了疆虚，為了優(yōu)化算法苛败，IGListKit把這些算法都放在兩個(gè)循環(huán)里满葛，這里為了方便理解將其拆開。

首先罢屈，定義對(duì)應(yīng)的數(shù)組

    id mInserts, mMoves, mUpdates, mDeletes;

    mInserts = [NSMutableIndexSet new];
    mUpdates = [NSMutableIndexSet new];
    mDeletes = [NSMutableIndexSet new];
    mMoves = [NSMutableArray<IGListMoveIndex *> new];

delete數(shù)組的生成

    for (NSInteger i = 0; i < oldCount; i++) {
        const IGListRecord record = oldResultsArray[i];
        if (record.index == NSNotFound) {
            addIndexToCollection( mDeletes, i);
        }
    }

很好理解嘀韧，通過上面的操作，如果oldResultsArray的index還是NSNotFound缠捌，則說明newArray中沒有這個(gè)元素乳蛾，就代表需要?jiǎng)h除。

insert數(shù)組的生成

    for (NSInteger i = 0; i < newCount; i++) {
        const IGListRecord record = newResultsArray[i];
        if (record.index == NSNotFound) {
            addIndexToCollection(mInserts, i);
        } 
    }

這個(gè)也很好理解鄙币，通過上面的操作肃叶，如果newResultsArray的index還是NSNotFound，則說明oldArray中沒有這個(gè)元素十嘿，就代表需要添加因惭。

update數(shù)組的生成

    for (NSInteger i = 0; i < newCount; i++) {
        const IGListRecord record = newResultsArray[i];
        const NSInteger oldIndex = record.index;
        if (record.index == NSNotFound) {
        } else {
            if (record.entry->updated) {
                addIndexToCollection( mUpdates, oldIndex);
            }
        }
    }

之前已經(jīng)標(biāo)記過update的，就表示需要update绩衷。之所以是這個(gè)oldIndex應(yīng)該是跟collectionView的badgeUpdate的規(guī)則有關(guān)蹦魔，后面會(huì)將update替換成insert和delete。

moves數(shù)組生成

moves數(shù)組的核心實(shí)現(xiàn)如下：

        id move;
        move = [[IGListMoveIndex alloc] initWithFrom:oldIndex to:newIndex];          
        [mMoves addObject:move];

之前的算法中咳燕，oldIndex和newIndex都已經(jīng)得出了勿决，可以直接使用，但是招盲，在一些情況里面低缩，我們是不需要move操作的。比如：

oldArray = @[@"1",@"2",@"3"];
newArray = @[@"2",@"3"];

這個(gè)情況我們只需執(zhí)行一次delete操作就可以從oldArray變到newArray了曹货，同理咆繁，有些情況下只需要insert操作就行了，對(duì)于此顶籽，IGListKit引入了runningOffset,整體算法如下

    vector<NSInteger> deleteOffsets(oldCount), insertOffsets(newCount);
    NSInteger runningOffset = 0;
    for (NSInteger i = 0; i < oldCount; i++) {
        deleteOffsets[i] = runningOffset;
        //如果需要?jiǎng)h除玩般，則runningOffset++
        if (record.index == NSNotFound) {
            runningOffset++;
        }
    }
    runningOffset = 0;
    
    for (NSInteger i = 0; i < newCount; i++) {
        insertOffsets[i] = runningOffset;
        如果需要插入，則runningOffset++
        if (record.index == NSNotFound) {
            runningOffset++;
        }
    }
    for (NSInteger i = 0; i < newCount; i++) {
        const IGListRecord record = newResultsArray[i];
        const NSInteger oldIndex = record.index;
        if (record.index == NSNotFound) {
        } else {
            //對(duì)應(yīng)插入的偏移量
            const NSInteger insertOffset = insertOffsets[i];
          //對(duì)應(yīng)刪除的偏移量
            const NSInteger deleteOffset = deleteOffsets[oldIndex];
            if ((oldIndex - deleteOffset + insertOffset) != i) {
                id move;
                move = [[IGListMoveIndex alloc] initWithFrom:oldIndex to:i];         
                [mMoves addObject:move];
            }
        }
    }

大意就是礼饱，如果前面出現(xiàn)的刪除坏为，則后面元素的位置都是要往左移，如果前面出現(xiàn)了插入镊绪，后面元素的位置都是要往右移匀伏，oldIndex - deleteOffset + insertOffset是執(zhí)行了刪除，插入后元素的最新位置镰吆，如果它與i相等帘撰，則沒必要move了。

函數(shù)返回

    return [[IGListIndexSetResult alloc] initWithInserts:mInserts
                                                     deletes:mDeletes
                                                     updates:mUpdates
                                                       moves:mMoves
                                                 oldIndexMap:oldMap
                                                 newIndexMap:newMap];

算完diff之后万皿，每個(gè)數(shù)組的元素都有值了摧找，便可以封裝IGListIndexSetResult返回了核行。

數(shù)組含有多個(gè)相同元素的情況

前面說過，如果newArray和oldArray中又相同的元素蹬耘，且出現(xiàn)了數(shù)次芝雪，該元素在oldArray中的第i次出現(xiàn)的索引會(huì)跟在newArray中的第i次出現(xiàn)的索引相匹配。這種匹配方式并不是最佳的综苔，舉個(gè)例子：

oldArray = @[@"2",@"3",@"1"];
newArray = @[@"1"@"2",@"1"];

肉眼看惩系，oldArray只需delete @"3",insert @"1"到索引為0的位置就變成了newArray了，而這個(gè)diff算法則需要個(gè)操作（@"2"從0移到1如筛，@"1"從索引2移到0堡牡，刪除@"3",插入@"1"到索引2）這是因?yàn)?code>oldArray中的索引2跟newArray中的索引0匹配了，導(dǎo)致了@"1"進(jìn)行不必要的移動(dòng)杨刨。

實(shí)際開發(fā)中晤柄，我們也很少出現(xiàn)這種情況，IGListKit也不鼓勵(lì)這種情況出現(xiàn)（會(huì)作去重且assert掉）

總結(jié)

diff算法是一個(gè)非常高效的算法妖胀，如果不把關(guān)鍵的代碼抽出來芥颈，IGListDiffing只是進(jìn)行了5次for循環(huán)而已，時(shí)間復(fù)雜度和空間復(fù)雜度都是o(n)赚抡。在前面3次循環(huán)中將元素的狀態(tài)都標(biāo)記出來爬坑，后面兩次循環(huán)計(jì)算出數(shù)組從舊到新所需的操作。IGListKit使用它進(jìn)行collectionView的部分更新涂臣，也提升了app的性能盾计。