近期，我們項目里面引入了IGListKit的第三方庫，它是對collectionView的一層封裝，主要用于feed流的實現(xiàn)，它的其中一個優(yōu)勢就是刷新視圖的時候并不是刷新的整個collectionView，而是通過diff算法算出新老數(shù)組的差異，根據(jù)這個差異collectionView進行部分更新，這個更新的邏輯在UICollectionView+IGListBatchUpdateData.m這個分類中，函數(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];
}

這個函數(shù)會在-performBatchUpdates:completion:的batchUpdatesBlock中被調用?？梢钥闯?，每次更新只會涉及到部分視圖的插入、刪除、移動，非常高效。下面分析這個diff算法是如何將這類差異算出來的。

前置工作

diff函數(shù)簡化

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

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

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

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

相關函數(shù)/結構體/方法介紹

IGListIndexSetResult

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

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;
///移動索引的集合（from是舊數(shù)組的索引，to是新數(shù)組的索引）
@property (nonatomic, copy, readonly) NSArray<IGListMoveIndex *> *moves;
///是否改變過
@property (nonatomic, assign, readonly) BOOL hasChanges;

@end

NS_ASSUME_NONNULL_END

最后返回的結果需要給inserts、deletes、updates、moves賦值返回（初始化方法在IGListIndexSetResultInternal.h里面）

IGListMoveIndex

封裝一個移動的操作，其結構如下：

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

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

NS_SWIFT_NAME(ListDiffable)
@protocol IGListDiffable

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

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

@end

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

IGListEntry

diff算法中用于標記元素狀態(tài)的結構體

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

IGListRecord

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

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

其它工具函數(shù)

還有其它的一些函數(shù)，在section/useIndexPath這些參數(shù)去掉之后，變得沒那么復雜了，下面統(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;
}

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

///求元素的哈希值，這個函數(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這個函數(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為值，其查找復雜度為o(1)。而oldMap和newMap并不參與這個diff算法，它們到最后就是已數(shù)組的index為key,數(shù)組的元素為值的哈希表而已。不過因為優(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ù)組,為每個新數(shù)組的元素創(chuàng)建一個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相當于棧底的標志位
        entry.oldIndexes.push(NSNotFound);
        
        
        newResultsArray[i].entry = &entry;
    }

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

這一步過后，會建立一個用于存放IGListRecord的newResultsArray，每個IGListRecord的index仍未NSNotFound，entry為新創(chuàng)建的IGListEntry，其newCounter都是大于0的。

diff算法Step2

遍歷舊數(shù)組，為每個舊數(shù)組的元素創(chuàng)建entry，并增加它們的oldCounter，將對應的索引壓入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)采用倒序的方式，在多個key相同的時候，oldIndexes會有一系列的索引壓棧，倒序就會確保棧頂?shù)乃饕亲钚〉摹?/p>

這一步過后，會建立一個用于存放IGListRecord的oldResultsArray，每個IGListRecord的index仍未NSNotFound，對于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都指向同一個entry

diff算法Step3

遍歷新數(shù)組，新舊數(shù)組都出現(xiàn)的元素，其IGListRecord的index會賦上其在新/舊數(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的第一個索引，然后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]) {
            //標記為update的條件，只有在key相同且n和o不一樣且isEqualToDiffableObject不相同的時候
            //才會走進這個條件
              entry->updated = YES;
            }
        }
        //給兩邊的index賦上對應的索引，如果originalIndex是NSNotFound，則不會走到這個條件
        if (originalIndex != NSNotFound
            && entry->newCounter > 0
            && entry->oldCounter > 0) {
            
            newResultsArray[i].index = originalIndex;
            oldResultsArray[originalIndex].index = i;
        }
    }

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

這一步主要的作用在于最后，這一步過后，如果一個元素兩邊的數(shù)組都存在，newResultsArray中對應的元素的index就會指向該元素在oldArray中的索引，oldResultsArray對應的元素的index就會指向該元素在newArray中的索引。這個賦值主要是用于統(tǒng)計移動元素的操作。

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

diff算法Step4

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

首先，定義對應的數(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中沒有這個元素，就代表需要刪除。

insert數(shù)組的生成

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

這個也很好理解，通過上面的操作，如果newResultsArray的index還是NSNotFound，則說明oldArray中沒有這個元素，就代表需要添加。

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)標記過update的，就表示需要update。之所以是這個oldIndex應該是跟collectionView的badgeUpdate的規(guī)則有關，后面會將update替換成insert和delete。

moves數(shù)組生成

moves數(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"];

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

    vector<NSInteger> deleteOffsets(oldCount), insertOffsets(newCount);
    NSInteger runningOffset = 0;
    for (NSInteger i = 0; i < oldCount; i++) {
        deleteOffsets[i] = runningOffset;
        //如果需要刪除，則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 {
            //對應插入的偏移量
            const NSInteger insertOffset = insertOffsets[i];
          //對應刪除的偏移量
            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之后，每個數(shù)組的元素都有值了，便可以封裝IGListIndexSetResult返回了。

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

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

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

肉眼看，oldArray只需delete @"3",insert @"1"到索引為0的位置就變成了newArray了，而這個diff算法則需要個操作（@"2"從0移到1，@"1"從索引2移到0，刪除@"3",插入@"1"到索引2）這是因為oldArray中的索引2跟newArray中的索引0匹配了，導致了@"1"進行不必要的移動。

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

總結

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