[TOC]

runtime相關(guān)問題

• 面試題出自掘金的一篇文章《阿里泳叠、字節(jié)：一套高效的iOS面試題》
• 該面試題解答github 地址版本目前已經(jīng)完結(jié)，可自行下載pdf進(jìn)行閱讀告嘲，僅做參考，對于有問題的解答可提 issue，歡迎 star fork反浓。
• 調(diào)試好可運行的源碼 objc-runtime，官網(wǎng)找 objc4暇韧；
• 歡迎轉(zhuǎn)載勾习，轉(zhuǎn)載請注明出處：pmst-swiftgg

結(jié)構(gòu)模型

1. 介紹下runtime的內(nèi)存模型（isa、對象懈玻、類巧婶、metaclass、結(jié)構(gòu)體的存儲信息等）

2. 為什么要設(shè)計metaclass

3. class_copyIvarList & class_copyPropertyList區(qū)別

class_copyIvarList 獲取類對象中的所有實例變量信息涂乌，從 class_ro_t 中獲纫照弧：

Ivar *
class_copyIvarList(Class cls, unsigned int *outCount)
{
    const ivar_list_t *ivars;
    Ivar *result = nil;
    unsigned int count = 0;

    if (!cls) {
        if (outCount) *outCount = 0;
        return nil;
    }

    mutex_locker_t lock(runtimeLock);

    assert(cls->isRealized());
    
    if ((ivars = cls->data()->ro->ivars)  &&  ivars->count) {
        result = (Ivar *)malloc((ivars->count+1) * sizeof(Ivar));
        
        for (auto& ivar : *ivars) {
            if (!ivar.offset) continue;  // anonymous bitfield
            result[count++] = &ivar;
        }
        result[count] = nil;
    }
    
    if (outCount) *outCount = count;
    return result;
}

class_copyPropertyList 獲取類對象中的屬性信息， class_rw_t 的 properties湾盒，先后輸出了 category / extension/ baseClass 的屬性湿右，而且僅輸出當(dāng)前的類的屬性信息，而不會向上去找 superClass 中定義的屬性罚勾。

objc_property_t *
class_copyPropertyList(Class cls, unsigned int *outCount)
{
    if (!cls) {
        if (outCount) *outCount = 0;
        return nil;
    }

    mutex_locker_t lock(runtimeLock);

    checkIsKnownClass(cls);
    assert(cls->isRealized());
    
    auto rw = cls->data();

    property_t **result = nil;
    unsigned int count = rw->properties.count();
    if (count > 0) {
        result = (property_t **)malloc((count + 1) * sizeof(property_t *));

        count = 0;
        for (auto& prop : rw->properties) {
            result[count++] = ∝
        }
        result[count] = nil;
    }

    if (outCount) *outCount = count;
    return (objc_property_t *)result;
}

Q1: class_ro_t 中的 baseProperties 呢毅人？

Q2: class_rw_t 中的 properties 包含了所有屬性，那何時注入進(jìn)去的呢尖殃？ 答案見 5.

4. class_rw_t 和 class_ro_t 的區(qū)別

class_rw_t_class_ro_t.png

測試發(fā)現(xiàn)丈莺，class_rw_t 中的 properties 屬性按順序包含分類/擴(kuò)展/基類中的屬性。

struct class_ro_t {
    uint32_t flags;
    uint32_t instanceStart;
    uint32_t instanceSize;
#ifdef __LP64__
    uint32_t reserved;
#endif

    const uint8_t * ivarLayout;
    
    const char * name;
    method_list_t * baseMethodList;
    protocol_list_t * baseProtocols;
    const ivar_list_t * ivars;

    const uint8_t * weakIvarLayout;
    property_list_t *baseProperties;

    method_list_t *baseMethods() const {
        return baseMethodList;
    }
};

struct class_rw_t {
    // Be warned that Symbolication knows the layout of this structure.
    uint32_t flags;
    uint32_t version;

    const class_ro_t *ro;

    method_array_t methods;
    property_array_t properties;
    protocol_array_t protocols;

    Class firstSubclass;
    Class nextSiblingClass;

    char *demangledName;

#if SUPPORT_INDEXED_ISA
    uint32_t index;
#endif
}

5. category如何被加載的,兩個category的load方法的加載順序送丰，兩個category的同名方法的加載順序

... -> realizeClass -> methodizeClass(用于Attach categories)-> attachCategories 關(guān)鍵就是在 methodizeClass 方法實現(xiàn)中

static void methodizeClass(Class cls)
{
    runtimeLock.assertLocked();

    bool isMeta = cls->isMetaClass();
    auto rw = cls->data();
    auto ro = rw->ro;
    
    // =======================================
        // 省略.....
    // =======================================
  
    property_list_t *proplist = ro->baseProperties;
    if (proplist) {
        rw->properties.attachLists(&proplist, 1);
    }

    // =======================================
        // 省略.....
    // =======================================

    // Attach categories.
    category_list *cats = unattachedCategoriesForClass(cls, true /*realizing*/);
    attachCategories(cls, cats, false /*don't flush caches*/);

    // =======================================
        // 省略.....
    // =======================================
    
    if (cats) free(cats);

}

上面代碼能確定 baseProperties 在前缔俄，category 在后，但決定順序的是 rw->properties.attachLists 這個方法：

property_list_t *proplist = ro->baseProperties;
if (proplist) {
  rw->properties.attachLists(&proplist, 1);
}

/// category 被附加進(jìn)去
void attachLists(List* const * addedLists, uint32_t addedCount) {
        if (addedCount == 0) return;

        if (hasArray()) {
            // many lists -> many lists
            uint32_t oldCount = array()->count;
            uint32_t newCount = oldCount + addedCount;
            setArray((array_t *)realloc(array(), array_t::byteSize(newCount)));
            array()->count = newCount;
            
            // 將舊內(nèi)容移動偏移量 addedCount 然后將 addedLists copy 到起始位置
            /*
                struct array_t {
                        uint32_t count;
                        List* lists[0];
                        };
            */
            memmove(array()->lists + addedCount, array()->lists, 
                    oldCount * sizeof(array()->lists[0]));
            memcpy(array()->lists, addedLists, 
                   addedCount * sizeof(array()->lists[0]));
        }
        else if (!list  &&  addedCount == 1) {
            // 0 lists -> 1 list
            list = addedLists[0];
        } 
        else {
            // 1 list -> many lists
            List* oldList = list;
            uint32_t oldCount = oldList ? 1 : 0;
            uint32_t newCount = oldCount + addedCount;
            setArray((array_t *)malloc(array_t::byteSize(newCount)));
            array()->count = newCount;
            if (oldList) array()->lists[addedCount] = oldList;
            memcpy(array()->lists, addedLists, 
                   addedCount * sizeof(array()->lists[0]));
        }
    }

所以 category 的屬性總是在前面的，baseClass的屬性被往后偏移了俐载。

Q1：那么多個 category 的順序呢蟹略？答案見6

2020/03/18 補充下應(yīng)用程序 image 鏡像加載到內(nèi)存中時， Category 解析的過程遏佣，注意下面的 while(i--) 這里倒敘將 category 中的協(xié)議 方法 屬性添加到了 rw = cls->data() 中的 methods/properties/protocols 中挖炬。

static void 
attachCategories(Class cls, category_list *cats, bool flush_caches)
{
    if (!cats) return;
    if (PrintReplacedMethods) printReplacements(cls, cats);

    bool isMeta = cls->isMetaClass();

    // fixme rearrange to remove these intermediate allocations
    method_list_t **mlists = (method_list_t **)
        malloc(cats->count * sizeof(*mlists));
    property_list_t **proplists = (property_list_t **)
        malloc(cats->count * sizeof(*proplists));
    protocol_list_t **protolists = (protocol_list_t **)
        malloc(cats->count * sizeof(*protolists));

    // Count backwards through cats to get newest categories first
    int mcount = 0;
    int propcount = 0;
    int protocount = 0;
    int i = cats->count;
    bool fromBundle = NO;
    while (i--) {
        auto& entry = cats->list[i];

        method_list_t *mlist = entry.cat->methodsForMeta(isMeta);
        if (mlist) {
            mlists[mcount++] = mlist;
            fromBundle |= entry.hi->isBundle();
        }

        property_list_t *proplist = 
            entry.cat->propertiesForMeta(isMeta, entry.hi);
        if (proplist) {
            proplists[propcount++] = proplist;
        }

        protocol_list_t *protolist = entry.cat->protocols;
        if (protolist) {
            protolists[protocount++] = protolist;
        }
    }
    auto rw = cls->data();
        
    // 注意下面的代碼，上面采用倒敘遍歷方式贼急，所以后編譯的 category 會先add到數(shù)組的前部
    prepareMethodLists(cls, mlists, mcount, NO, fromBundle);
    rw->methods.attachLists(mlists, mcount);
    free(mlists);
    if (flush_caches  &&  mcount > 0) flushCaches(cls);

    rw->properties.attachLists(proplists, propcount);
    free(proplists);

    rw->protocols.attachLists(protolists, protocount);
    free(protolists);
}

6. category & extension區(qū)別茅茂，能給NSObject添加Extension嗎，結(jié)果如何

category:

• 運行時添加分類屬性/協(xié)議/方法
• 分類添加的方法會“覆蓋”原類方法太抓，因為方法查找的話是從頭至尾空闲，一旦查找到了就停止了
• 同名分類方法誰生效取決于編譯順序，image 讀取的信息是倒敘的走敌，所以編譯越靠后的越先讀入
• 名字相同的分類會引起編譯報錯碴倾；

extension:

• 編譯時決議
• 只以聲明的形式存在，多數(shù)情況下就存在于 .m 文件中掉丽；
• 不能為系統(tǒng)類添加擴(kuò)展

7. 消息轉(zhuǎn)發(fā)機(jī)制跌榔，消息轉(zhuǎn)發(fā)機(jī)制和其他語言的消息機(jī)制優(yōu)劣對比

8. 在方法調(diào)用的時候，方法查詢-> 動態(tài)解析-> 消息轉(zhuǎn)發(fā) 之前做了什么

9. IMP捶障、SEL僧须、Method的區(qū)別和使用場景

三者的定義：

typedef struct method_t *Method;

using MethodListIMP = IMP;

struct method_t {
    SEL name;
    const char *types;
    MethodListIMP imp;
};

Method 同樣是個對象，封裝了方法名和實現(xiàn)项炼，關(guān)于 Type Encodings担平。

-(void)hello:(NSString *)name encode 下就是 v@:@。

10. load锭部、initialize方法的區(qū)別什么暂论？在繼承關(guān)系中他們有什么區(qū)別

load 方法調(diào)用時機(jī)，而且只調(diào)用當(dāng)前類本身拌禾，不會調(diào)用superClass 的 +load 方法：

void
load_images(const char *path __unused, const struct mach_header *mh)
{
    // Return without taking locks if there are no +load methods here.
    if (!hasLoadMethods((const headerType *)mh)) return;

    recursive_mutex_locker_t lock(loadMethodLock);

    // Discover load methods
    {
        mutex_locker_t lock2(runtimeLock);
        prepare_load_methods((const headerType *)mh);
    }

    // Call +load methods (without runtimeLock - re-entrant)
    call_load_methods();
}

void call_load_methods(void)
{
    static bool loading = NO;
    bool more_categories;

    loadMethodLock.assertLocked();

    // Re-entrant calls do nothing; the outermost call will finish the job.
    if (loading) return;
    loading = YES;

    void *pool = objc_autoreleasePoolPush();

    do {
        // 1. Repeatedly call class +loads until there aren't any more
        while (loadable_classes_used > 0) {
            call_class_loads();
        }

        // 2. Call category +loads ONCE
        more_categories = call_category_loads();

        // 3. Run more +loads if there are classes OR more untried categories
    } while (loadable_classes_used > 0  ||  more_categories);

    objc_autoreleasePoolPop(pool);

    loading = NO;
}

+initialize 實現(xiàn)

void _class_initialize(Class cls)
{
    assert(!cls->isMetaClass());

    Class supercls;
    bool reallyInitialize = NO;

    // Make sure super is done initializing BEFORE beginning to initialize cls.
    // See note about deadlock above.
    supercls = cls->superclass;
    if (supercls  &&  !supercls->isInitialized()) {
        _class_initialize(supercls);
    }
    
    // Try to atomically set CLS_INITIALIZING.
    {
        monitor_locker_t lock(classInitLock);
        if (!cls->isInitialized() && !cls->isInitializing()) {
            cls->setInitializing();
            reallyInitialize = YES;
        }
    }
    
    if (reallyInitialize) {
        // We successfully set the CLS_INITIALIZING bit. Initialize the class.
        
        // Record that we're initializing this class so we can message it.
        _setThisThreadIsInitializingClass(cls);

        if (MultithreadedForkChild) {
            // LOL JK we don't really call +initialize methods after fork().
            performForkChildInitialize(cls, supercls);
            return;
        }
        
        // Send the +initialize message.
        // Note that +initialize is sent to the superclass (again) if 
        // this class doesn't implement +initialize. 2157218
        if (PrintInitializing) {
            _objc_inform("INITIALIZE: thread %p: calling +[%s initialize]",
                         pthread_self(), cls->nameForLogging());
        }

        // Exceptions: A +initialize call that throws an exception 
        // is deemed to be a complete and successful +initialize.
        //
        // Only __OBJC2__ adds these handlers. !__OBJC2__ has a
        // bootstrapping problem of this versus CF's call to
        // objc_exception_set_functions().
#if __OBJC2__
        @try
#endif
        {
            callInitialize(cls);

            if (PrintInitializing) {
                _objc_inform("INITIALIZE: thread %p: finished +[%s initialize]",
                             pthread_self(), cls->nameForLogging());
            }
        }
#if __OBJC2__
        @catch (...) {
            if (PrintInitializing) {
                _objc_inform("INITIALIZE: thread %p: +[%s initialize] "
                             "threw an exception",
                             pthread_self(), cls->nameForLogging());
            }
            @throw;
        }
        @finally
#endif
        {
            // Done initializing.
            lockAndFinishInitializing(cls, supercls);
        }
        return;
    }
    
    else if (cls->isInitializing()) {
        // We couldn't set INITIALIZING because INITIALIZING was already set.
        // If this thread set it earlier, continue normally.
        // If some other thread set it, block until initialize is done.
        // It's ok if INITIALIZING changes to INITIALIZED while we're here, 
        //   because we safely check for INITIALIZED inside the lock 
        //   before blocking.
        if (_thisThreadIsInitializingClass(cls)) {
            return;
        } else if (!MultithreadedForkChild) {
            waitForInitializeToComplete(cls);
            return;
        } else {
            // We're on the child side of fork(), facing a class that
            // was initializing by some other thread when fork() was called.
            _setThisThreadIsInitializingClass(cls);
            performForkChildInitialize(cls, supercls);
        }
    }
    
    else if (cls->isInitialized()) {
        // Set CLS_INITIALIZING failed because someone else already 
        //   initialized the class. Continue normally.
        // NOTE this check must come AFTER the ISINITIALIZING case.
        // Otherwise: Another thread is initializing this class. ISINITIALIZED 
        //   is false. Skip this clause. Then the other thread finishes 
        //   initialization and sets INITIALIZING=no and INITIALIZED=yes. 
        //   Skip the ISINITIALIZING clause. Die horribly.
        return;
    }
    
    else {
        // We shouldn't be here. 
        _objc_fatal("thread-safe class init in objc runtime is buggy!");
    }
}

void callInitialize(Class cls)
{
    ((void(*)(Class, SEL))objc_msgSend)(cls, SEL_initialize);
    asm("");
}

注意看上面的調(diào)用了 callInitialize(cls) 然后又調(diào)用了 lockAndFinishInitializing(cls, supercls)取胎。

摘自iOS App冷啟動治理 一文中對 Dyld 在各階段所做的事情：

最后 dyld 會調(diào)用 main() 函數(shù)盗尸，main() 會調(diào)用 UIApplicationMain()，before main()的過程也就此完成帽撑。

11. 說說消息轉(zhuǎn)發(fā)機(jī)制的優(yōu)劣

內(nèi)存管理

1.weak的實現(xiàn)原理泼各？SideTable的結(jié)構(gòu)是什么樣的

解答參考自瓜神的 weak 弱引用的實現(xiàn)方式 。

NSObject *p = [[NSObject alloc] init];
__weak NSObject *p1 = p;
// ====> 底層是runtime的 objc_initWeak
// xcrun -sdk iphoneos clang -arch arm64 -rewrite-objc -fobjc-arc -fobjc-runtime=ios-13.2 main.m 得不到下面的代碼亏拉，還是說命令參數(shù)不對扣蜻。
NSObject objc_initWeak(&p, 對象指針);

通過 runtime 源碼可以看到 objc_initWeak 實現(xiàn)：

id
objc_initWeakOrNil(id *location, id newObj)
{
    if (!newObj) {
        *location = nil;
        return nil;
    }

    return storeWeak<DontHaveOld, DoHaveNew, DontCrashIfDeallocating>
        (location, (objc_object*)newObj);
}

SideTable 結(jié)構(gòu)體在 runtime 底層用于引用計數(shù)和弱引用關(guān)聯(lián)表，其數(shù)據(jù)結(jié)構(gòu)是這樣：

struct SideTable {
    // 自旋鎖
    spinlock_t slock;
    // 引用計數(shù)
    RefcountMap refcnts;
    // weak 引用
    weak_table_t weak_table;
}

struct weak_table_t {
    // 保存了所有指向指定對象的 weak 指針
    weak_entry_t *weak_entries;
    // 存儲空間
    size_t    num_entries;
    // 參與判斷引用計數(shù)輔助量
    uintptr_t mask;
    // hash key 最大偏移值
    uintptr_t max_hash_displacement;
};

根據(jù)對象的地址在緩存中取出對應(yīng)的 SideTable 實例：

static SideTable *tableForPointer(const void *p)

或者如上面源碼中 &SideTables()[newObj] 方式取表及塘，這里的 newObj 是實例對象用其指針作為 key 拿到 從全局的 SideTables 中拿到實例自身對應(yīng)的那張 SideTable莽使。

static StripedMap<SideTable>& SideTables() {
    return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}

取出實例方法的實現(xiàn)中，使用了 C++ 標(biāo)準(zhǔn)轉(zhuǎn)換運算符 reinterpret_cast 笙僚，其表達(dá)方式為：

reinterpret_cast <new_type> (expression)

每一個 weak 關(guān)鍵字修飾的對象都是用 weak_entry_t 結(jié)構(gòu)體來表示芳肌，所以在實例中聲明定義的 weak 對象都會被封裝成 weak_entry_t 加入到該 SideTable 中 weak_table 中

typedef objc_object ** weak_referrer_t;

struct weak_entry_t {
    DisguisedPtr<objc_object> referent;
    union {
        struct {
            weak_referrer_t *referrers;
            uintptr_t        out_of_line : 1;
            uintptr_t        num_refs : PTR_MINUS_1;
            uintptr_t        mask;
            uintptr_t        max_hash_displacement;
        };
        struct {
            // out_of_line=0 is LSB of one of these (don't care which)
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
 }

舊對象解除注冊操作 weak_unregister_no_lock 和 新對象添加注冊操作 weak_register_no_lock ，具體實現(xiàn)可前往 runtime 源碼中查看或查看瓜的博文肋层。

weak_store_pic.png

weak 關(guān)鍵字修飾的對象有兩種情況：棧上和堆上亿笤。上圖主要解釋 id referent_id 和 id *referrer_id，

• 如果是棧上栋猖， referrer 值為 0x77889900净薛，referent 值為 0x11223344
• 如果是堆上 ， referrer 值為 0x1100000+ offset（也就是 weak a 所在堆上的地址）蒲拉，referent 值為 0x11223344肃拜。

如此現(xiàn)在類 A 的實例對象有兩個 weak 變量指向它，一個在堆上全陨，一個在棧上爆班。

void
weak_unregister_no_lock(weak_table_t *weak_table, id referent_id, 
                        id *referrer_id)
{
    objc_object *referent = (objc_object *)referent_id;   //  0x11223344
    objc_object **referrer = (objc_object **)referrer_id; //  0x77889900

    weak_entry_t *entry;

    if (!referent) return;
        
    // 從 weak_table 中找到 referent 也就是上面類A的實例對象
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        // 在 entry 結(jié)構(gòu)體中的 referrers 數(shù)組中找到指針 referrer 所在位置
        // 將原本存儲 referrer 值的位置置為 nil，相當(dāng)于做了一個解綁操作
        // 因為 referrer 要和其他對象建立關(guān)系了
        remove_referrer(entry, referrer);
        bool empty = true;
        if (entry->out_of_line()  &&  entry->num_refs != 0) {
            empty = false;
        }
        else {
            for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
                if (entry->inline_referrers[i]) {
                    empty = false; 
                    break;
                }
            }
        }

        if (empty) {
            weak_entry_remove(weak_table, entry);
        }
    }

    // Do not set *referrer = nil. objc_storeWeak() requires that the 
    // value not change.
}

weak 關(guān)鍵字修飾的屬性或者變量為什么在對應(yīng)類實例dealloc后會置為nil辱姨，那是因為在類實例釋放的時候柿菩，dealloc 會從全局的引用計數(shù)和weak計數(shù)表sideTables中，通過實例地址去找到屬于自己的那張表雨涛，表中的 weak_table->weak_entries 存儲了所有 entry 對象——其實就是所有指向這個實例對象的變量枢舶，weak_entry_t 中的 referrers 數(shù)組存儲的就是變量或?qū)傩缘膬?nèi)存地址，逐一置為nil即可替久。

關(guān)聯(lián)對象基本使用方法：

#import <objc/runtime.h>

static NSString * const kKeyOfImageProperty;

@implementation UIView (Image)

- (UIImage *)pt_image {
    return objc_getAssociatedObject(self, &kKeyOfImageProperty);
}

- (void)setPTImage:(UIImage *)image {
    objc_setAssociatedObject(self, &kKeyOfImageProperty, image,OBJC_ASSOCIATION_RETAIN);
}
@end

objc_AssociationPolicy 關(guān)聯(lián)對象持有策略有如下幾種 ：

摘自瓜地：OBJC_ASSOCIATION_ASSIGN類型的關(guān)聯(lián)對象和weak有一定差別右锨，而更加接近于unsafe_unretained括堤，即當(dāng)目標(biāo)對象遭到摧毀時，屬性值不會自動清空绍移。（翻譯自Associated Objects）

同樣是Associated Objects文中悄窃，總結(jié)了三個關(guān)于Associated Objects用法：

• 為Class添加私有成員：例如在AFNetworking中，在UIImageView里添加了imageRequestOperation對象蹂窖，從而保證了異步加載圖片轧抗。
• 為Class添加共有成員：例如在FDTemplateLayoutCell中，使用Associated Objects來緩存每個cell的高度（代碼片段1恼策、代碼片段2）鸦致。通過分配不同的key，在復(fù)用cell的時候即時取出涣楷，增加效率分唾。
• 創(chuàng)建KVO對象：建議使用category來創(chuàng)建關(guān)聯(lián)對象作為觀察者∈ǘ罚可以參考Objective-C Associated Objects這篇文的例子绽乔。

源碼實現(xiàn)非常簡單，我添加了完整注釋碳褒，對c++語法也做了一定解釋：

id _object_get_associative_reference(id object, void *key) {
    id value = nil;
    uintptr_t policy = OBJC_ASSOCIATION_ASSIGN;
    {
        AssociationsManager manager;
        // manager.associations() 返回的是一個 `AssociationsHashMap` 對象(*_map)
        // 所以這里 `&associations` 中用了 `&`
        AssociationsHashMap &associations(manager.associations());
        // intptr_t 是為了兼容平臺折砸，在64位的機(jī)器上，intptr_t和uintptr_t分別是long int沙峻、unsigned long int的別名睦授；在32位的機(jī)器上，intptr_t和uintptr_t分別是int摔寨、unsigned int的別名
        // DISGUISE 內(nèi)部對指針做了 ~ 取反操作去枷，“偽裝”？
        disguised_ptr_t disguised_object = DISGUISE(object);
        /*
         AssociationsHashMap 繼承自 unordered_map是复，存儲 key-value 的組合
         iterator find ( const key_type& key )删顶，如果 key 存在，則返回key對象的迭代器淑廊，
         如果key不存在逗余，則find返回 unordered_map::end；因此可以通過 `map.find(key) == map.end()`
         判斷 key 是否存在于當(dāng)前 map 中季惩。
         */
        AssociationsHashMap::iterator i = associations.find(disguised_object);
        if (i != associations.end()) {
            /*
                unordered_map 的鍵值分別是迭代器的first和second屬性录粱。
                所以說上面先通過 object 對象(實例對象or類對象) 找到其所有關(guān)聯(lián)對象
                i->second 取到又是一個 ObjectAssociationMap
                此刻再通過我們自己設(shè)定的 key 來查找對應(yīng)的關(guān)聯(lián)屬性值腻格，不過使用
                `ObjcAssociation` 封裝的
             */
            ObjectAssociationMap *refs = i->second;
            ObjectAssociationMap::iterator j = refs->find(key);
            if (j != refs->end()) {
                ObjcAssociation &entry = j->second;
                value = entry.value();
                policy = entry.policy();
                // 如果策略是 getter retain ，注意這里留個坑
                // 平常 OBJC_ASSOCIATION_RETAIN = 01401
                // OBJC_ASSOCIATION_GETTER_RETAIN = (1 << 8)
                if (policy & OBJC_ASSOCIATION_GETTER_RETAIN) {
                    // TODO: 有學(xué)問
                    objc_retain(value);
                }
            }
        }
    }
    if (value && (policy & OBJC_ASSOCIATION_GETTER_AUTORELEASE)) {
        objc_autorelease(value);
    }
    return value;
}

對應(yīng)的set操作實現(xiàn)同樣簡單啥繁，耐心看下源碼注釋荒叶，即使不同c++都沒問題：

void _object_set_associative_reference(id object, void *key, id value, uintptr_t policy) {
    // retain the new value (if any) outside the lock.
    ObjcAssociation old_association(0, nil);
    // 如果value對象存在，則進(jìn)行retain or copy 操作
    id new_value = value ? acquireValue(value, policy) : nil;
    {
        AssociationsManager manager;
        // manager.associations() 返回的是一個 `AssociationsHashMap` 對象(*_map)
        // 所以這里 `&associations` 中用了 `&`
        AssociationsHashMap &associations(manager.associations());
        // intptr_t 是為了兼容平臺输虱，在64位的機(jī)器上，intptr_t和uintptr_t分別是long int脂凶、unsigned long int的別名宪睹；在32位的機(jī)器上，intptr_t和uintptr_t分別是int蚕钦、unsigned int的別名
        // DISGUISE 內(nèi)部對指針做了 ~ 取反操作亭病，“偽裝”
        disguised_ptr_t disguised_object = DISGUISE(object);
        if (new_value) {
            // break any existing association.
            /*
             AssociationsHashMap 繼承自 unordered_map，存儲 key-value 的組合
             iterator find ( const key_type& key )嘶居，如果 key 存在罪帖，則返回key對象的迭代器，
             如果key不存在邮屁，則find返回 unordered_map::end整袁；因此可以通過 `map.find(key) == map.end()`
             判斷 key 是否存在于當(dāng)前 map 中。
             */
            AssociationsHashMap::iterator i = associations.find(disguised_object);
            // 這里和get操作不同佑吝，set操作時如果查詢到對象沒有關(guān)聯(lián)對象坐昙，那么這一次設(shè)值是第一次，
            // 所以會創(chuàng)建一個新的 ObjectAssociationMap 用來存儲實例對象的所有關(guān)聯(lián)屬性
            if (i != associations.end()) {
                // secondary table exists
                /*
                    unordered_map 的鍵值分別是迭代器的first和second屬性芋忿。
                    所以說上面先通過 object 對象(實例對象or類對象) 找到其所有關(guān)聯(lián)對象
                    i->second 取到又是一個 ObjectAssociationMap
                    此刻再通過我們自己設(shè)定的 key 來查找對應(yīng)的關(guān)聯(lián)屬性值炸客，不過使用
                    `ObjcAssociation` 封裝的
                 */
                ObjectAssociationMap *refs = i->second;
                ObjectAssociationMap::iterator j = refs->find(key);
                // 關(guān)聯(lián)屬性用 ObjcAssociation 結(jié)構(gòu)體封裝
                if (j != refs->end()) {
                    old_association = j->second;
                    j->second = ObjcAssociation(policy, new_value);
                } else {
                    (*refs)[key] = ObjcAssociation(policy, new_value);
                }
            } else {
                // create the new association (first time).
                ObjectAssociationMap *refs = new ObjectAssociationMap;
                associations[disguised_object] = refs;
                (*refs)[key] = ObjcAssociation(policy, new_value);
                // 知識點是：newisa.has_assoc = true;
                object->setHasAssociatedObjects();
            }
        } else {
            // setting the association to nil breaks the association.
            AssociationsHashMap::iterator i = associations.find(disguised_object);
            if (i !=  associations.end()) {
                ObjectAssociationMap *refs = i->second;
                ObjectAssociationMap::iterator j = refs->find(key);
                if (j != refs->end()) {
                    old_association = j->second;
                    refs->erase(j);
                }
            }
        }
    }
    // release the old value (outside of the lock).
    if (old_association.hasValue()) ReleaseValue()(old_association);
}

3. 關(guān)聯(lián)對象的如何進(jìn)行內(nèi)存管理的？關(guān)聯(lián)對象如何實現(xiàn)weak屬性

使用了 policy 設(shè)置內(nèi)存管理策略戈钢，具體見上痹仙。

4. Autoreleasepool的原理？所使用的的數(shù)據(jù)結(jié)構(gòu)是什么

5. ARC的實現(xiàn)原理殉了？ARC下對retain & release做了哪些優(yōu)化

6. ARC下哪些情況會造成內(nèi)存泄漏

其他

1. Method Swizzle注意事項
2. 屬性修飾符atomic的內(nèi)部實現(xiàn)是怎么樣的?能保證線程安全嗎
3. iOS 中內(nèi)省的幾個方法有哪些开仰？內(nèi)部實現(xiàn)原理是什么
4. class、objc_getClass宣渗、object_getclass 方法有什么區(qū)別?

NSNotification相關(guān)

認(rèn)真研讀抖所、你可以在這里找到答案輕松過面：一文全解iOS通知機(jī)制(經(jīng)典收藏)

1. 實現(xiàn)原理（結(jié)構(gòu)設(shè)計、通知如何存儲的痕囱、name&observer&SEL之間的關(guān)系等）
2. 通知的發(fā)送時同步的田轧，還是異步的
3. NSNotificationCenter接受消息和發(fā)送消息是在一個線程里嗎？如何異步發(fā)送消息
4. NSNotificationQueue是異步還是同步發(fā)送鞍恢？在哪個線程響應(yīng)
5. NSNotificationQueue和runloop的關(guān)系
6. 如何保證通知接收的線程在主線程
7. 頁面銷毀時不移除通知會崩潰嗎
8. 多次添加同一個通知會是什么結(jié)果傻粘？多次移除通知呢
9. 下面的方式能接收到通知嗎每窖？為什么

// 發(fā)送通知
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(handleNotification:) name:@"TestNotification" object:@1];
// 接收通知
[NSNotificationCenter.defaultCenter postNotificationName:@"TestNotification" object:nil];
復(fù)制代碼

Runloop & KVO

runloop

runloop對于一個標(biāo)準(zhǔn)的iOS開發(fā)來說都不陌生，應(yīng)該說熟悉runloop是標(biāo)配弦悉，下面就隨便列幾個典型問題吧

1. app如何接收到觸摸事件的
2. 為什么只有主線程的runloop是開啟的
3. 為什么只在主線程刷新UI
4. PerformSelector和runloop的關(guān)系
5. 如何使線程敝系洌活

KVO（Finished）

同runloop一樣，這也是標(biāo)配的知識點了稽莉，同樣列出幾個典型問題

1. 實現(xiàn)原理

KVO 會為需要observed的對象動態(tài)創(chuàng)建一個子類瀑志，以NSKVONotifying_ 最為前綴，然后將對象的 isa 指針指向新的子類污秆，同時重寫 class 方法劈猪，返回原先類對象，這樣外部就無感知了良拼；其次重寫所有要觀察屬性的setter方法战得，統(tǒng)一會走一個方法，然后內(nèi)部是會調(diào)用 willChangeValueForKey 和 didChangevlueForKey 方法庸推，在一個被觀察屬性發(fā)生改變之前常侦， willChangeValueForKey:一定會被調(diào)用，這就 會記錄舊的值贬媒。而當(dāng)改變發(fā)生后聋亡，didChangeValueForKey:會被調(diào)用，繼而 observeValueForKey:ofObject:change:context: 也會被調(diào)用掖蛤。

kvo.png

那么如何驗證上面的說法呢杀捻？很簡單，借助runtime 即可蚓庭，測試代碼請點擊這里:

- (void)viewDidLoad {
    [super viewDidLoad];
    self.person = [[Person alloc] initWithName:@"pmst" age:18];
    self.teacher = [[Teacher alloc] initWithName:@"ppp" age:28];
    self.teacher.work = @"數(shù)學(xué)";
    self.teacher.numberOfStudent = 10;
    
    NSKeyValueObservingOptions options = NSKeyValueObservingOptionNew | NSKeyValueObservingOptionOld;
    
    RuntimeUtil *utils = [RuntimeUtil new];
    [utils logClassInfo:self.person.class];
    [self.person addObserver:self forKeyPath:@"age" options:options context:nil];
    [utils logClassInfo:object_getClass(self.person)];
    
    
    [utils logClassInfo:self.teacher.class];
    [self.teacher addObserver:self forKeyPath:@"age" options:options context:nil];
    [self.teacher addObserver:self forKeyPath:@"name" options:options context:nil];
    [self.teacher addObserver:self forKeyPath:@"work" options:options context:nil];
    [utils logClassInfo:object_getClass(self.teacher)];
}

這里 object_getClass() 方法實現(xiàn)也貼一下致讥，如果直接使用 .class 那么因為被重寫過，返回的還是原先對象的類對象器赞，而直接用 runtime 方法的直接返回了 isa 指針垢袱。

Class object_getClass(id obj)
{
    if (obj) return obj->getIsa();
    else return Nil;
}

通過日志確實可以看到子類重寫了對應(yīng)屬性的setter方法：

2020-03-25 23:11:00.607820+0800 02-25-KVO[28370:1005147] LOG:(NSKVONotifying_Teacher) INFO
2020-03-25 23:11:00.608190+0800 02-25-KVO[28370:1005147] ==== OUTPUT:NSKVONotifying_Teacher properties ====
2020-03-25 23:11:00.608529+0800 02-25-KVO[28370:1005147] ==== OUTPUT:NSKVONotifying_Teacher Method ====
2020-03-25 23:11:00.608876+0800 02-25-KVO[28370:1005147] method name:setWork:
2020-03-25 23:11:00.609219+0800 02-25-KVO[28370:1005147] method name:setName:
2020-03-25 23:11:00.646713+0800 02-25-KVO[28370:1005147] method name:setAge:
2020-03-25 23:11:00.646858+0800 02-25-KVO[28370:1005147] method name:class
2020-03-25 23:11:00.646971+0800 02-25-KVO[28370:1005147] method name:dealloc
2020-03-25 23:11:00.647088+0800 02-25-KVO[28370:1005147] method name:_isKVOA
2020-03-25 23:11:00.647207+0800 02-25-KVO[28370:1005147] =========================

疑惑點：看到有文章提出 KVO 之后，setXXX 方法轉(zhuǎn)而調(diào)用 _NSSetBoolValueAndNotify港柜、_NSSetCharValueAndNotify请契、_NSSetFloatValueAndNotify、_NSSetLongValueAndNotify 等方法夏醉，但是通過 runtime 打印 method 是存在的爽锥，猜測 SEL 是一樣的，但是 IMP 被換掉了畔柔，關(guān)于源碼的實現(xiàn)還未找到氯夷。TODO下。

2. 如何手動關(guān)閉kvo

KVO 和 KVC 相關(guān)接口太多靶擦，實際開發(fā)中直接查看接口文檔即可腮考。

+(BOOL)automaticallyNotifiesObserversForKey:(NSString *)key{
    if ([key isEqualToString:@"name"]) {
        return NO;
    }else{
        return [super automaticallyNotifiesObserversForKey:key];
    }
}

-(void)setName:(NSString *)name{
    
    if (_name!=name) {
        
        [self willChangeValueForKey:@"name"];
        _name=name;
        [self didChangeValueForKey:@"name"];
    }
      
}

3. 通過KVC修改屬性會觸發(fā)KVO么

會觸發(fā) KVO 操作雇毫，KVC 時候會先查詢對應(yīng)的 getter 和 setter 方法，如果都沒找到踩蔚，調(diào)用

+ (BOOL)accessInstanceVariablesDirectly {
    return NO;
}

如果返回 YES棚放，那么可以直接修改實例變量。

• KVC 調(diào)用 getter 流程：getKEY馅闽，KEY飘蚯，isKEY, _KEY，接著是實例變量 _KEY,_isKEY, KEY, isKEY;

• KVC 調(diào)用 setter 流程：setKEY和 _setKEY福也，實例變量順序 _KEY,_isKEY, KEY, isKEY孝冒，沒找到就調(diào)用 setValue: forUndefinedKey:

4. 哪些情況下使用kvo會崩潰，怎么防護(hù)崩潰

1. dealloc 沒有移除 kvo 觀察者拟杉，解決方案：創(chuàng)建一個中間對象，將其作為某個屬性的觀察者量承，然后dealloc的時候去做移除觀察者搬设，而調(diào)用者是持有中間對象的，調(diào)用者釋放了撕捍，中間對象也釋放了拿穴，dealloc 也就移除觀察者了；
2. 多次重復(fù)移除同一個屬性忧风，移除了未注冊的觀察者
3. 被觀察者提前被釋放默色，被觀察者在 dealloc 時仍然注冊著 KVO，導(dǎo)致崩潰狮腿。 例如：被觀察者是局部變量的情況（iOS 10 及之前會崩潰） 比如 weak 腿宰；
4. 添加了觀察者，但未實現(xiàn) observeValueForKeyPath:ofObject:change:context:方法缘厢，導(dǎo)致崩潰吃度；
5. 添加或者移除時 keypath == nil，導(dǎo)致崩潰贴硫；

以下解決方案出自 iOS 開發(fā)：『Crash 防護(hù)系統(tǒng)』（二）KVO 防護(hù) 一文椿每。

解決方案一：

FBKVOController 對 KVO 機(jī)制進(jìn)行了額外的一層封裝，框架不但可以自動幫我們移除觀察者英遭，還提供了 block 或者 selector 的方式供我們進(jìn)行觀察處理间护。不可否認(rèn)的是，F(xiàn)BKVOController 為我們的開發(fā)提供了很大的便利性挖诸。但是相對而言汁尺，這種方式對項目代碼的侵入性比較大，必須依靠編碼規(guī)范來強(qiáng)制約束團(tuán)隊人員使用這種方式税灌。

解決方案二：

1. 首先為 NSObject 建立一個分類均函，利用 Method Swizzling亿虽，實現(xiàn)自定義的 BMP_addObserver:forKeyPath:options:context:、BMP_removeObserver:forKeyPath:苞也、BMP_removeObserver:forKeyPath:context:洛勉、BMPKVO_dealloc方法，用來替換系統(tǒng)原生的添加移除觀察者方法的實現(xiàn)如迟。

2. 然后在觀察者和被觀察者之間建立一個 KVODelegate 對象收毫，兩者之間通過 KVODelegate 對象 建立聯(lián)系。然后在添加和移除操作時殷勘，將 KVO 的相關(guān)信息例如 observer此再、keyPath、options玲销、context 保存為 KVOInfo 對象输拇，并添加到 KVODelegate 對象 中對應(yīng) 的 關(guān)系哈希表 中，對應(yīng)原有的添加觀察者贤斜。 關(guān)系哈希表的數(shù)據(jù)結(jié)構(gòu)：{keypath : [KVOInfo 對象1, KVOInfo 對象2, ... ]}

3. 在添加和移除操作的時候策吠，利用 KVODelegate 對象 做轉(zhuǎn)發(fā)，把真正的觀察者變?yōu)?KVODelegate 對象瘩绒，而當(dāng)被觀察者的特定屬性發(fā)生了改變猴抹，再由 KVODelegate 對象 分發(fā)到原有的觀察者上。

4. 添加觀察者時：通過關(guān)系哈希表判斷是否重復(fù)添加锁荔，只添加一次蟀给。

5. 移除觀察者時：通過關(guān)系哈希表是否已經(jīng)進(jìn)行過移除操作，避免多次移除阳堕。

6. 觀察鍵值改變時：同樣通過關(guān)系哈希表判斷跋理，將改變操作分發(fā)到原有的觀察者上。

解決方案三：

XXShield 實現(xiàn)方案和 BayMax 系統(tǒng)類似恬总。也是利用一個 Proxy 對象用來做轉(zhuǎn)發(fā)薪介， 真正的觀察者是 Proxy，被觀察者出現(xiàn)了通知信息越驻，由 Proxy 做分發(fā)汁政。不過不同點是 Proxy 里面保存的內(nèi)容沒有前者多。只保存了 _observed（被觀察者） 和關(guān)系哈希表缀旁，這個關(guān)系哈希表中只維護(hù)了 keyPath 和 observer 的關(guān)系记劈。

關(guān)系哈希表的數(shù)據(jù)結(jié)構(gòu)：{keypath : [observer1, observer2 , ...](NSHashTable)} 。

XXShield 在 dealloc 中也做了類似將多余觀察者移除掉的操作并巍，是通過關(guān)系數(shù)據(jù)結(jié)構(gòu)和 _observed 目木，然后調(diào)用原生移除觀察者操作實現(xiàn)的。

5. kvo的優(yōu)缺點

優(yōu)點：

1. 運用了設(shè)計模式：觀察者模式
2. 支持多個觀察者觀察同一屬性懊渡，或者一個觀察者監(jiān)聽不同屬性刽射。
3. 開發(fā)人員不需要實現(xiàn)屬性值變化了發(fā)送通知的方案军拟，系統(tǒng)已經(jīng)封裝好了，大大減少開發(fā)工作量誓禁；
4. 能夠?qū)Ψ俏覀儎?chuàng)建的對象懈息，即內(nèi)部對象的狀態(tài)改變作出響應(yīng)，而且不需要改變內(nèi)部對象（SDK對象）的實現(xiàn)摹恰；
5. 能夠提供觀察的屬性的最新值以及先前值辫继；
6. 用key paths來觀察屬性，因此也可以觀察嵌套對象俗慈；
7. 完成了對觀察對象的抽象姑宽，因為不需要額外的代碼來允許觀察值能夠被觀察

缺點：

1. 觀察的屬性鍵值硬編碼（字符串），編譯器不會出現(xiàn)警告以及檢查闺阱；
2. 由于允許對一個對象進(jìn)行不同屬性觀察炮车，所以在唯一回調(diào)方法中，會出現(xiàn)地獄式 if-else if - else 分支處理情況酣溃；

References：

• iOS底層原理總結(jié)篇-- 深入理解 KVC\KVO 實現(xiàn)機(jī)制
• iOS 開發(fā)：『Crash 防護(hù)系統(tǒng)』（二）KVO 防護(hù)
• ValiantCat / XXShield（第三方框架）
• JackLee18 / JKCrashProtect（第三方框架）
• 大白健康系統(tǒng) -- iOS APP運行時 Crash 自動修復(fù)系統(tǒng)

Block

1. block的內(nèi)部實現(xiàn)示血，結(jié)構(gòu)體是什么樣的
2. block是類嗎，有哪些類型
3. 一個int變量被 __block 修飾與否的區(qū)別救拉？block的變量截獲
4. block在修改NSMutableArray，需不需要添加__block
5. 怎么進(jìn)行內(nèi)存管理的
6. block可以用strong修飾嗎
7. 解決循環(huán)引用時為什么要用__strong瘫拣、__weak修飾
8. block發(fā)生copy時機(jī)
9. Block訪問對象類型的auto變量時亿絮，在ARC和MRC下有什么區(qū)別

多線程

主要以GCD為主

1. iOS開發(fā)中有多少類型的線程？分別對比
2. GCD有哪些隊列麸拄，默認(rèn)提供哪些隊列
3. GCD有哪些方法api
4. GCD主線程 & 主隊列的關(guān)系
5. 如何實現(xiàn)同步派昧，有多少方式就說多少
6. dispatch_once實現(xiàn)原理
7. 什么情況下會死鎖
8. 有哪些類型的線程鎖，分別介紹下作用和使用場景
9. NSOperationQueue中的maxConcurrentOperationCount默認(rèn)值
10. NSTimer拢切、CADisplayLink蒂萎、dispatch_source_t 的優(yōu)劣

視圖&圖像相關(guān)

1. AutoLayout的原理，性能如何
2. UIView & CALayer的區(qū)別
3. 事件響應(yīng)鏈
4. drawrect & layoutsubviews調(diào)用時機(jī)
5. UI的刷新原理
6. 隱式動畫 & 顯示動畫區(qū)別
7. 什么是離屏渲染
8. imageName & imageWithContentsOfFile區(qū)別
9. 多個相同的圖片淮椰，會重復(fù)加載嗎
10. 圖片是什么時候解碼的五慈，如何優(yōu)化
11. 圖片渲染怎么優(yōu)化
12. 如果GPU的刷新率超過了iOS屏幕60Hz刷新率是什么現(xiàn)象，怎么解決

性能優(yōu)化

1. 如何做啟動優(yōu)化主穗，如何監(jiān)控
2. 如何做卡頓優(yōu)化泻拦，如何監(jiān)控
3. 如何做耗電優(yōu)化，如何監(jiān)控
4. 如何做網(wǎng)絡(luò)優(yōu)化忽媒，如何監(jiān)控

開發(fā)證書

1. 蘋果使用證書的目的是什么
2. AppStore安裝app時的認(rèn)證流程
3. 開發(fā)者怎么在debug模式下把app安裝到設(shè)備呢

架構(gòu)設(shè)計

典型源碼的學(xué)習(xí)

只是列出一些iOS比較核心的開源庫争拐，這些庫包含了很多高質(zhì)量的思想，源碼學(xué)習(xí)的時候一定要關(guān)注每個框架解決的核心問題是什么晦雨，還有它們的優(yōu)缺點架曹，這樣才能算真正理解和吸收

1. AFN
2. SDWebImage
3. JSPatch隘冲、Aspects(雖然一個不可用、另一個不維護(hù)绑雄，但是這兩個庫都很精煉巧妙展辞，很適合學(xué)習(xí))
4. Weex/RN, 筆者認(rèn)為這種前端和客戶端緊密聯(lián)系的庫是必須要知道其原理的
5. CTMediator、其他router庫绳慎，這些都是常見的路由庫纵竖，開發(fā)中基本上都會用到
6. 請圈友們在評論下面補充吧

架構(gòu)設(shè)計

1. 手動埋點、自動化埋點杏愤、可視化埋點
2. MVC靡砌、MVP、MVVM設(shè)計模式
3. 常見的設(shè)計模式
4. 單例的弊端
5. 常見的路由方案珊楼，以及優(yōu)缺點對比
6. 如果保證項目的穩(wěn)定性
7. 設(shè)計一個圖片緩存框架(LRU)
8. 如何設(shè)計一個git diff
9. 設(shè)計一個線程池通殃？畫出你的架構(gòu)圖
10. 你的app架構(gòu)是什么，有什么優(yōu)缺點厕宗、為什么這么做画舌、怎么改進(jìn)

其他問題

1. PerformSelector & NSInvocation優(yōu)劣對比
2. oc怎么實現(xiàn)多繼承？怎么面向切面（可以參考Aspects深度解析-iOS面向切面編程）
3. 哪些bug會導(dǎo)致崩潰已慢，如何防護(hù)崩潰
4. 怎么監(jiān)控崩潰
5. app的啟動過程（考察LLVM編譯過程曲聂、靜態(tài)鏈接、動態(tài)鏈接佑惠、runtime初始化）
6. 沙盒目錄的每個文件夾劃分的作用
7. 簡述下match-o文件結(jié)構(gòu)

系統(tǒng)基礎(chǔ)知識

1. 進(jìn)程和線程的區(qū)別
2. HTTPS的握手過程
3. 什么是中間人攻擊朋腋？怎么預(yù)防
4. TCP的握手過程？為什么進(jìn)行三次握手膜楷，四次揮手
5. 堆和棧區(qū)的區(qū)別旭咽？誰的占用內(nèi)存空間大
6. 加密算法：對稱加密算法和非對稱加密算法區(qū)別
7. 常見的對稱加密和非對稱加密算法有哪些
8. MD5、Sha1赌厅、Sha256區(qū)別
9. charles抓包過程穷绵？不使用charles，4G網(wǎng)絡(luò)如何抓包

數(shù)據(jù)結(jié)構(gòu)與算法

對于移動開發(fā)者來說特愿，一般不會遇到非常難的算法仲墨，大多以數(shù)據(jù)結(jié)構(gòu)為主，筆者列出一些必會的算法揍障，當(dāng)然有時間了可以去LeetCode上刷刷題

1. 八大排序算法
2. 棧&隊列
3. 字符串處理
4. 鏈表
5. 二叉樹相關(guān)操作
6. 深搜廣搜
7. 基本的動態(tài)規(guī)劃題宗收、貪心算法、二分查找