关于散列表的研究以及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

是时候抛弃传统的软件测试用例了!

先给一个传统的测试用例的例子,作为讨论的上下文。

(传统的测试用例)先抛出本文的观点:是时候,抛弃传统的测试用例,即抛弃上述规范描写的测试用例(含有具体操作步骤等)。抛弃传统的测试用例,不意味着抛弃测试设计。测试设计是需要的,但可以用思维导图、矩阵、测试模型、测试场景、用户故事的验收标准等不同形式来描述测试设计,只是不用上述传统方式来描述。我也不是无视传统软件测试用例的价值,但在今天来看,这种价值已经很小了。虽然在我的教材中,可能还包含 “如何书写规范的测试用例”,让大学生来练习也许还有价值,至少先让他们了解传统的测试用例是如何写的。就像讲《软件工程》中敏捷开发模式之前,还是先要让同学们了解瀑布模型、V模型,这样才能更好理解敏捷模型。我也知道,当初为什么要写规范的测试用例,是因为:

  • 测试的依据,包括测试执行、评审、管理的基础;
  • 作为测试的主要文档,传递测试知识;
  • 测试设计、测试执行由不同的人执行;
  • 更容易通过CMMI/TMMI 认证;
  • ……

下面就一条一条来讨论,说明我们可以改变这些初心了。

一、详细的测试用例能不能成为测试的依据?直观上看,详细的测试用例是可以作为测试的依据,测试人员按照测试用例执行,心里感觉踏实;测试用例是白纸黑字,评审起来似乎也有根有据;测试用例是规范的文档,也符合维护、管理的要求。
但是,许多项目很难写出明确的期望标准,因为需求的标准就不明确,而是需要测试人员的综合判断,这时依赖测试用例很困难。基于用例来执行测试,容易限制测试人员的思维,甚至让许多测试人员不去思考,而测试用例自身又很难写得完整,需要不断完善。当测试用例写得越详细,其维护的工作量越大,人们就更不愿意去维护,时间长了,许多用例失效了,也没有得到修改。把大量时间花在写测试用例、维护测试用例上,投入产出比(RoI)低,不合算,测试人员有更重要的事情去做。如果评审几千条用自然语言写的详细测试用例,不仅工作量大,而且也不容易发现问题,因为不容易看到全局。如果把测试点、测试场景、测试数据很好地整理归纳在一张思维导图上,即使分解为几张思维导图,任何遗漏、不足之处倒是很容易发现。基于思维导图的测试设计评审更容易。花在重写测试用例步骤上的时间是否有价值?是不是更应该花在其他测试活动上?例如用于探索式测试方式测试新特性,用更多时间在测试分析上,测试分析比测试设计更有价值,首先要知道测试什么,然后再决定如何测。即使对一个优秀工程师,要确定清楚哪些要测,依旧有挑战,而如何测,倒是比较简单。

二、测试用例能很好传递测试知识吗?测试用例可以传递测试知识,但靠测试用例来传递,效率偏低。如果用单位时间能吸取多少知识来衡量,可以感觉出来,读了大量的测试用例获得的知识有限,还不如看几十页的图书。
作为一个公司或一个团队,在平时测试分析、设计和执行中要善于总结出知识、经验和优秀实践,用wiki或其它工具建立系统的、结构化的、规范的知识库,甚至形成一些内部的培训课程。在今天,我们是不是更应该建应用/业务领域的知识图谱,通过知识图谱更好地服务未来测试建模、业务依赖性分析等。

三、测试设计、测试执行该不该由不同的人执行?把测试设计和测试执行分开,是错误的做法,不仅增加了沟通成本,而且不能保证测试设计和执行的质量。一方面,测试人员通过测试执行可以更好地理解功能、产品、业务等,从而进一步完善测试设计。另方面,测试设计长期脱离测试的执行,对产品、特性的理解也会退化,自然对测试设计有不良影响。


有人说,我们有大量外包人员,他们流动快,主人翁意识不强,只能执行。你希望把他们当作测试工具、按部就班地执行测试用例吗?作为外包人员也乐意成为测试工具吗?如果是这样,为什么不直接写成自动化测试脚本?让工具执行还更靠谱、更快、成本更低。至于认证,你懂,一般只是一种政绩工程,或者是为了项目投标用。如果你要投标,要做外包,为了证明自己,写出规范的测试用例来交差,那就继续下去。今天,你如果是用敏捷开发模式,有了用户故事就是有了用户行为,只要追加“场景”,列出需要验证的测试场景,类似BDD的GWT描述。虽然测试场景还不是测试用例,不能执行,但离测试用例也就差一步,即加上测试数据,而这时测试数据可以自动生成。所以,在敏捷开发模式中,主要为每个用户故事给出场景列表,这个也容易评审,越简单的东西,一旦有问题,就越容易发现。越简单的东西,维护的成本也就越低。如果你不是用敏捷开发模式,而是用传统的开发模式,我倒是希望你画一张业务流程图,标上业务规则、业务角色,针对这个进行测试,更能保证业务覆盖,而业务覆盖才是最根本的。咱们一切工作都是为了业务,测试就是为了会更好地保障业务的质量。当我们谈覆盖率,实际包含了三个层次的覆盖率:代码、功能/非功能特性、业务。单元测试侧重代码覆盖率,而系统测试侧重功能/非功能特性覆盖。非功能特性,性能、安全性、可靠性等会单独去考虑,即我们常说的专项测试,而功能测试,完全可以被业务覆盖而覆盖,即E2E业务覆盖更彻底。今天来做测试,依旧建议新功能用探索式测试,就根本不写测试用例。而回归测试彻底实现自动化,也根本不写测试用例(千万不要先写测试用例,再翻译成测试脚本,这样更浪费时间!),直接写测试脚本。所以,今天可以彻底抛弃传统的测试用例,甚至连自动化测试都要抛弃传统的测试脚本,推行codeless自动化测试。