不同的编程思想

一、面向对象编程(OOP)

简述

面向对象的特点就是:封装、多态、继承。通过封装数据和其他方法,面向对象的编程使软件开发更加以人为中心,符合人类的直觉。在面向对象编程世界里,一切皆为对象,对象是程序的基本单元,对象把程序与数据封装起来提供对外访问的能力,提高软件的重用性,灵活性和扩展性

继承与多态都是后来不断发展的过程中加入进去的。从某种意义上说,多态性是继承性的泛化,因为并不是原始方法或对象的所有属性都需要传输到新实体。相反,还可以选择重写一些属性。

与此同时,继承性和多态性并不是面向对象编程所特有的。真正的区别在于封装数据及其包含的方法。

【扩展】:面向对象编程的基本原则「开闭原则」具有两个主要特征:

(1)对于扩展是开放的(Open for extension)。这意味着模块的行为是可以扩展的。当应用的需求改变时,我们可以对模块进行扩展,使其具有满足那些改变的新行为。也就是说,我们可以改变模块的功能。

2)对于修改是关闭的(Closed for modification)。对模块行为进行扩展时,不必改动模块的源代码或者二进制代码。

问题

面向对象变成是我们非常容易理解的编程方式,继承和多态更丰富了其内容,但是随之而来也造成了不少的困扰,面向对象编程的问题大多都是由此而来的。

  1. 香蕉猴子丛林问题

    这个问题可以简述为:这个类可能是另一个类的子类,因此你需要将它的父类也包含在内。然后你会发现,这个父类可能也是另一个类的子类,以此类推,最后要面对一堆代码。由此产生大量的多余内容也会造成性能问题,特别是在系统规模变得越来越大时,问题也越发严重。
  2. 脆弱的基类

    你的子类越多,继承的越多,你的基类越难以修改。
  3. 菱形继承问题

    利用继承可以将一类中的属性传递给其他类,但是你无法混合两个不同类的属性,起码常规方法是做不到的。
  4. 层级问题

    类上堆积的属性越多,建立适当的层次结构就越困难。在你所处理的属性集群中,可能A类共享了B类的一些属性,但不是全部属性,反之亦然。在大型复杂项目中,层次结构的问题会导致很大的混乱。
    对于层级问题,我们可能会想到进行没有层次结构的面向对象编程。我们可以使用属性集群,并根据需要继承、扩展或重写属性。也许这有点混乱,但的确可以解决一些问题。
    但是这里还存在一个问题:封装的全部目的是使数据片段彼此之间保持安全,从而使计算效率更高,但没有严格的层次结构,这是行不通的。
  5. 引用问题

    引用问题更像是香蕉猴子问题的延伸,当你只需要一个香蕉,但是却拿到了整片森林时,这片森林已经不再安全了,封装已经被破坏,你可以任意处置其中的数据。
  6. 类库庞大

    当系统越来越庞大时,我们的类库越来越多,且单个库也会越来越大,越来越不易阅读和掌握,潜在隐患增多,我们无法保证类库中的每个类在各种环境中百分之百的正确。

二、面向协议编程(POP)

简述

简单来说,协议就是一张代码实现蓝图,我们可以在这张蓝图上勾勒出可能需要实现的方法、属性和其他满足特定任务的功能模块。而类、结构或枚举都可以通过这张蓝图(协议)来提供对这些需求的实际实现。而任何满足协议要求的类型都被认为符合该协议,都需要实现该协议规定必须实现的方法和属性。

其实我们使用面向协议编程的方式,很大程度上就是为了弥补上述面向对象编程中遇到的问题。

抽象一点,协议仅仅是实现多态的代码的一种方式,其他很多方式也都可以实现:继承、泛型、值、函数等等。值是最简单的方法;函数比值的方式复杂一点,但是仍然很简单;泛型(无约束)也比协议简单。但完整地说,协议通常比类的继承结构要简单。

这里有一点启发性的建议:仔细考虑你的协议是塑造数据模型还是行为模型。对于数据,结构类型可能更容易。对于复杂的行为(例如具有多个方法的委托),协议通常更容易。(标准库中的集合协议有点特殊:它们并不真的描述数据,而是在描述数据处理。)

也就是说,尽管协议非常有用,但是不要为了面向协议而使用协议。首先检视你的问题,并且尽可能地尝试用最简单的方法解决。通过问题顺藤摸瓜找到解决办法,不要背道而驰。面向协议编程并没有好坏之分,跟其他的技术(函数编程、面向对象、依赖注入、类的继承)一样,它能解决一些问题,但我们不应盲目,要择其善者而从之。有时候使用协议,但通常还有更简单的方法。

参考【为什么我们应该批评使用协议】

关于面向协议编程的示例

三、面向过程编程(POP)

简述

面向过程编程就是一种线性思想,按照步骤一步步的去解决问题,也就是面向过程的。对应到代码层面就是一个步骤一个函数。特点是简单,适用于逻辑比较简单的业务。

这里不多做赘述。

四、面向切面编程(AOP)

简述

主要是因为面向对象编程的主要思想就是封装,而封装就要求将功能分散到不同的对象中去,这在软件设计中往往称为职责分配。实际上也就是说,让不同的类设计不同的方法。这样代码就分散到一个个的类中去了。这样做的好处是降低了代码的复杂程度,使类可重用,但是同时也增加了代码的重复性,两个分装好的内容再想去做同一件事,只能加入重复的代码,而如果不这么做,选择再封装一个独立的方法让他们去调用,就产生了藕合,会影响原有的两个类。因此就希望有没有什么办法,能让我们在需要的时候,随意地加入代码呢?这种在运行时,动态地将代码切入到类的指定方法、指定位置上的编程思想就是面向切面的编程。不够除了运行时,还可以在编译期、类加载期织入如前文所述也可以通过协议的方式来解决此问题

AOP像OOP一样,只是一种编程范式,AOP并没有规定说,实现AOP协议的代码,要用什么方式去实现。不过从技术上来说,面向切面编程基本上都是通过代理机制实现的,对面向对象编程来说是一种十分有益的补充。

关于AOP面向切面编程的详细讲解

五、链式编程

简述

链式编程是指将多个操作(多行代码)通过点号(.)链接在一起成为一句代码,使代码可读性好。例如:a(1).b(2).c(3),

  • 代表:Masonry框架

链式编程其实就两个要点:

  • Block 作为当前对象的属性。
  • Block 返回值是当前对象。

关于链式编程的详细

链式编程的一个简单示例

六、响应式编程

响应式编程是指不需要考虑调用顺序,只需要知道考虑结果,类似于蝴蝶效应,产生一个事件,会影响很多东西,这些事件像流一样的传播出去,然后影响结果,借用面向对象的一句话,万物皆是流。

  • 代表:KVO运用

响应式编程的详细

七、函数式编程

函数式编程是把操作尽量写成一系列嵌套的函数或者方法调用。

  • 函数式编程特点:1、可以把函数作为参数传递给另一个函数,也就是所谓的高阶函数。2、可以返回一个函数,这样就可以实现闭包或者惰性计算
  • 代表:AF的网络回调
  • 以上两个特点还仅仅是简化了代码。从代码的可维护性上讲,函数式编程最大的好处是引用透明,即函数运行的结果只依赖于输入的参数,而不依赖于外部状态,因此,我们常常说函数式编程没有副作用。没有副作用有个巨大的好处,就是函数内部无状态,即输入确定,输出就是确定的,容易测试和维护。

以上我们看到,函数式和链式编程实现原理是一样的,都是在调用方法的时候返回一个对象,利用这个返回的对象去调用下一个方法。只不过链式编程在定义的时候是返回一个 【返回值为对象的block

函数式编程初探

函数式编程入门

总结:

我们要知道, 编程语言不过就是工具,编程思想就是操作工具的方法,没有最好的编程语言和最好的编程思想能够解决所有场景的问题,哪门编程思想解决现实问题越快,代码越容易维护,就去使用它,重要的不是用什么编程思想,而是锻炼自己理解现实需求和抽象代码的能力,这才是最优的方式

关于散列表的研究以及NSDictionary底层探索

关于散列表的研究以及NSDictionary底层探索

有道笔记链接:https://note.youdao.com/s/FsSLFw9k

众所周知,在iOS开发当中便利一个数组,去不断匹配value是一种很低效的方式,但是如果直接通过NSarry的index(索引)去取值,则会快很多,但是字典是无序的,也就是没有一个对外暴露的索引,我们该如何通过字典的key去快速定位Value呢?

在了解这些之前,我们就必须要了解散列表,即哈希表(Hash table)。

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

所以我们知道哈希表底层其实是一个数组,那么只要我们通过一定的算法将key值转化为数组中index和value的对应关系就可以极大的提升字典差值的效率了。

话不多说,开搞!

已知Key对象的值为0b0000 0001(计算机储存的所有对象都为二进制数据),当我们设定这个key的时候,我们会通过一个hash函数去生成一个特定索引。这个函数可能是用“&”与运算符,也可能用“%”取余,不同平台的算法各不相同,但都是相通的。

比如我们定义一个mask,值为:0b0000 1111(取余即为15);我们用key1 & mask,如下:

//通过“&”运算符,我们得到一个明确的索引,即1。
  0b0000 0001
& 0b0000 1111
--------------
  0b0000 0001

哈希表对应分布如下:

索引value
0NULL
1buket(key1,value2)
2NULL
3NULL
4NULL
5NULL

如果我们继续往字典储存新值,如key2为:0b0000 0010

//通过“&”运算符,我们得到一个明确的索引,即2。
  0b0000 0010
& 0b0000 1111
--------------
  0b0000 0010

哈希表对应分布如下:

索引(地址)value
0NULL
1buket(key1,value2)
2buket(key2,value2)
3NULL
4NULL
5NULL

以此类推,我们将会得到一个Array,所以了解了这些后,我们很容易就明白,当我们传入一个key时,字典并不是通过key去循环便利去找出我们想要的value,而是通过一个函数去生成value的一个索引,从而更精准的定位我们想要的value,如传入:(0b0000 0001),我们就得到了索引为1,再通过索引1,直接拿到Value。

那么新问题产生了!

在上面我们定义了一个mask为0b0000 1111的值,根据“&”运算的逻辑,值都为1才为1,只要其中有一个为0,则为0。所以我们得到的索引最大值都不会超过mask,即15。即数组内储存的元素最多不能超过15条。

  1. 那么一旦超过呢?没错,字典底层为我们编写了“扩容”的操作。(源码如下)
  2. 如果生成的索引index已经被占用了呢?这时候iOS底层源码编写了向前/向后查找,直到查找到存在空位时,储存(但是实际开发中,冲突很麻烦,甚至会影响散列表的查找速度,所以应该采用最大限度减少冲突的散列函数)。

下面时iOS中字典扩容的源码,有兴趣的可以看一下。 iOS CFDictionary源码

//字典结构体
struct __CFDictionary {
    CFRuntimeBase _base;
    CFIndex _count;		/* number of values */
    CFIndex _capacity;		/* maximum number of values */
    CFIndex _bucketsNum;	/* number of slots */
    uintptr_t _marker;
    void *_context;		/* private */
    CFIndex _deletes;
    CFOptionFlags _xflags;      /* bits for GC */
    //保留的所有的key
    const void **_keys;		/* can be NULL if not allocated yet */
    //保存了所有value
    const void **_values;	/* can be NULL if not allocated yet */
};
static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues) {
    //获得原有的keys和values
    const void **oldkeys = dict->_keys;
    const void **oldvalues = dict->_values;
    //原来插槽数
    CFIndex idx, oldnbuckets = dict->_bucketsNum;
    //原来字典中的values
    CFIndex oldCount = dict->_count;
    CFAllocatorRef allocator = __CFGetAllocator(dict), keysAllocator, valuesAllocator;
    void *keysBase, *valuesBase;
    dict->_capacity = __CFDictionaryRoundUpCapacity(oldCount + numNewValues);
    dict->_bucketsNum = __CFDictionaryNumBucketsForCapacity(dict->_capacity);
    dict->_deletes = 0;
    if (_CFDictionaryIsSplit(dict)) {   // iff GC, use split memory sometimes unscanned memory
    unsigned weakOrStrong = (dict->_xflags & __kCFDictionaryWeakKeys) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
    void *mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, mem);
        keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;  // GC: avoids write-barrier in weak case.
        keysBase = mem;
    
        weakOrStrong = (dict->_xflags & __kCFDictionaryWeakValues) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
    mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_values, mem);
        valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
        valuesBase = mem;
    } else {
        //扩容成原先大小的两倍
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, _CFAllocatorAllocateGC(allocator, 2 * dict->_bucketsNum * sizeof(const void *), AUTO_MEMORY_SCANNED));
        dict->_values = (const void **)(dict->_keys + dict->_bucketsNum);
        keysAllocator = valuesAllocator = allocator;
        keysBase = valuesBase = dict->_keys;
    }
    if (NULL == dict->_keys || NULL == dict->_values) HALT;
    if (__CFOASafe) __CFSetLastAllocationEventName(dict->_keys, "CFDictionary (store)");
    // 重新计算keys数据的hash值,存放到新的数组中
    for (idx = dict->_bucketsNum; idx--;) {
        dict->_keys[idx] = (const void *)dict->_marker;
        dict->_values[idx] = 0;
    }
    if (NULL == oldkeys) return;
    for (idx = 0; idx < oldnbuckets; idx++) {
        if (dict->_marker != (uintptr_t)oldkeys[idx] && ~dict->_marker != (uintptr_t)oldkeys[idx]) {
            CFIndex match, nomatch;
            __CFDictionaryFindBuckets2(dict, oldkeys[idx], &match, &nomatch);
            CFAssert3(kCFNotFound == match, __kCFLogAssertion, "%s(): two values (%p, %p) now hash to the same slot; mutable value changed while in table or hash value is not immutable", __PRETTY_FUNCTION__, oldkeys[idx], dict->_keys[match]);
            if (kCFNotFound != nomatch) {
                CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, dict->_keys[nomatch], oldkeys[idx]);
                CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, dict->_values[nomatch], oldvalues[idx]);
            }
        }
    }
    CFAssert1(dict->_count == oldCount, __kCFLogAssertion, "%s(): dict count differs after rehashing; error", __PRETTY_FUNCTION__);
    _CFAllocatorDeallocateGC(allocator, oldkeys);
    if (_CFDictionaryIsSplit(dict)) _CFAllocatorDeallocateGC(allocator, oldvalues);
}

但是扩容有一个很明显的缺点,就是会让字典的容量越来越大,甚至产生很多空间的浪费。所以哈希表是一种用空间换效率的技术。(会空闲一部分内存)

总结一下,所以散列表的核心是散列函数,大致可以用如下函数表示,不管是用“%”取余,还是用与运算符“&”,我们所定义的mask都决定了散列表的容量大小,所以应尽可能优化散列函数,避免mask的频繁变动和散列表数据的冲突,保证散列表查询的效率。以上就是我对于散列表的理解和研究,如果错漏,还请大家踊跃提出,共同交流。

f(key) == index

下面补充几个网上推荐的hash表函数:

相关参考文档补充 iOS字典底层原理:https://www.jianshu.com/p/0d7cd6341f65 iOS 用OC简单还原hash值生成

—–zhaohanjun