数据结构 -- 哈希表及其应用

这篇主要用来记录一下学习到的关于哈希表的知识点。

文章结构

  1. 哈希表
  • 哈希表的定义
  • 哈希表的优缺点
  • 哈希碰撞
  • 负载因子
  • 扩容
  1. iOS中哈希表的引用
  • NSSet
  • NSDictionary
  • Associated Object
  • @synchronized
  • weak

哈希表的定义

哈希表是根据key值找到内存地址的数据结构。
它的本质是一个数组,数组中的每一个元素叫做箱子(Bin),箱子中存放的是键值对。根据下标index从数组中获取value值。
通过一个固定函数(哈希函数)将key转换成index。

哈希表优缺点

优点:

  • 可以提供快速的操作。

缺点:

  • 基于数组的难扩展。
  • 有序遍历困难。

Hash碰撞

通过哈希函数不同的key值也会得到相同hash值,这样就会造成哈希冲突(碰撞)的问题。

哈希碰撞的解决方案
  • 开放定址
    开放定址法是通过哈希函数计算的index值,如果发生碰撞,则将index++,直到找到那个未被使用的index。

  • 拉链法
    拉链法简单来说是数组+链表。数组中每个元素指向一个链表,链表中每个节点存储hash出来的索引值为节点下标的键值对。

拉链法数据结构.png
优缺点:
  • 拉链法指针需要额外空间,所以如果结点规模较小的时候适合用开放定址法
  • 结点规模大使用开放定址会造成堆积问题、浪费空间。
  • 拉链法处理冲突简单,容易删除节点,但节点是动态申请的,无法造表前确定表大小。

负载因子

负载因子 = 总键值数/数组的个数

负载因子是用来衡量哈希表的空/满程度的,负载因子大于(0.75)时,哈希表会自动扩容,一般会创建两倍于原数组长度。因此就算key值无变化,对数组取余后位置也会发生变化,这个过程称为重哈希(rehash)。

扩容

  • 数组较多的时候,重新哈希并移动数据,性能影响较大。
  • 若哈希函数设计不合理,使得计算的hash值都相同,这样即使扩容它们的位置也在同一个链表上,性能低。

iOS中对哈希表的使用

NSSet、NSDictionary

hash

OC 中有hash方法,通过hash方法计算hash值。通过hash值查找目标位置,如果发生冲突,就解决冲突的方式查找。
相等变量的hash结果总是相同的,不想等变量的hash结果也可能相同。
hash化是一个取得变量特征的过程,这个过程可以是取出变量的特征,也可能是一个计算。

hash方法的调用
Person *person1 = [Person personWithName:kName1 birthday:self.date1];
Person *person2 = [Person personWithName:kName2 birthday:self.date2];

NSMutableArray *array1 = [NSMutableArray array];
[array1 addObject:person1];
NSMutableArray *array2 = [NSMutableArray array];
[array2 addObject:person2];
NSLog(@"array end -------------------------------");

NSMutableSet *set1 = [NSMutableSet set];
[set1 addObject:person1];
NSMutableSet *set2 = [NSMutableSet set];
[set2 addObject:person2];
NSLog(@"set end -------------------------------");

NSMutableDictionary *dictionaryValue1 = [NSMutableDictionary dictionary];
[dictionaryValue1 setObject:person1 forKey:kKey1];
NSMutableDictionary *dictionaryValue2 = [NSMutableDictionary dictionary];
[dictionaryValue2 setObject:person2 forKey:kKey2];
NSLog(@"dictionary value end -------------------------------");

NSMutableDictionary *dictionaryKey1 = [NSMutableDictionary dictionary];
[dictionaryKey1 setObject:kValue1 forKey:person1];
NSMutableDictionary *dictionaryKey2 = [NSMutableDictionary dictionary];
[dictionaryKey2 setObject:kValue2 forKey:person2];
NSLog(@"dictionary key end -------------------------------");

重写hash方法:

- (NSUInteger)hash {
    NSUInteger hash = [super hash];
    NSLog(@"走过 hash");
    return hash;
}

打印结果:

array end -------------------------------
走过 hash
走过 hash
走过 hash
走过 hash
set end -------------------------------
dictionary value end -------------------------------
走过 hash
走过 hash
走过 hash
走过 hash
dictionary key end -------------------------------

hash方法只有在对象加入到NSSet和设置NSDictionary的key时调用。

NSSet

struct __CFSet {
    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 */
    const void **_keys;     /* can be NULL if not allocated yet */
};

通过数据结构,发现set内部使用指针数组保存keys。

基于不同的初始化,hash值存在不同的运算,如下源码可知。

static CFIndex __CFSetFindBucketsXX(CFSetRef set, const void *key) {
    CFHashCode keyHash = (CFHashCode)key;
    
    const CFSetCallBacks *cb = __CFSetGetKeyCallBacks(set);
    CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
    
    const void **keys = set->_keys;
    CFIndex probe = keyHash % set->_bucketsNum;
}

添加value时,回先判断key值是否存在,如果存在则什么都不做。所以set可以重复保存数据。
通过计算获取到的hash值获取value所在hash表的位置,如果发生冲突了采用开放定址法将指针++ ,来解决哈希冲突。

void CFSetAddValue(CFMutableSetRef set, const void *key) {
    // 通过 match、nomatch 判断Set是否存在key
    CFIndex match, nomatch;
    
    __CFSetFindBuckets2(set, key, &match, &nomatch);
    if (kCFNotFound != match) {
        // 存在key,则什么都不做
    } else {
        // 不存在,则添加到set中
        CF_OBJC_KVO_WILLCHANGE(set, key);
        CF_WRITE_BARRIER_ASSIGN(keysAllocator, set->_keys[nomatch], newKey);
        set->_count++;
        CF_OBJC_KVO_DIDCHANGE(set, key);
    }
}

static void __CFSetFindBuckets2(CFSetRef set, const void *key, CFIndex *match, CFIndex *nomatch) {
    const CFSetCallBacks *cb = __CFSetGetKeyCallBacks(set);
    // 获取hash值
    CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
    const void **keys = set->_keys;
    uintptr_t marker = set->_marker;
    CFIndex probe = keyHash % set->_bucketsNum;
    CFIndex probeskip = 1;  // See RemoveValue() for notes before changing this value
    CFIndex start = probe;
    *match = kCFNotFound;
    *nomatch = kCFNotFound;
    for (;;) {
    uintptr_t currKey = (uintptr_t)keys[probe];
    // 如果hash值对应的是空闲区域,那么标记nomatch,返回不存在key
    if (marker == currKey) {        /* empty */
        if (nomatch) *nomatch = probe;
        return;
    } else if (~marker == currKey) {    /* deleted */
        if (nomatch) {
        *nomatch = probe;
        nomatch = NULL;
        }
    } else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, set->_context))) {
        // 标记match,返回存在key
        *match = probe;
        return;
    }
    // 没有匹配,说明发生了冲突,那么将数组下标后移,知道找到空闲区域位置
    probe = probe + probeskip;
    
    if (set->_bucketsNum <= probe) {
        probe -= set->_bucketsNum;
    }
    if (start == probe) {
        return;
    }
    }
}

新增元素时,如果超过了阈值会调用扩容的方法。扩容后会重新计算hash值。

// 新增元素的时候会判断
void CFSetAddValue(CFMutableSetRef set, const void *key) {
        ...
    if (set->_count == set->_capacity || NULL == set->_keys) {
        // 调用扩容
        __CFSetGrow(set, 1);
    }
    ...
}

// 扩容
static void __CFSetGrow(CFMutableSetRef set, CFIndex numNewValues) {
    // 保存旧值key的数据
    const void **oldkeys = set->_keys;
    CFIndex idx, oldnbuckets = set->_bucketsNum;
    CFIndex oldCount = set->_count;
    CFAllocatorRef allocator = __CFGetAllocator(set), keysAllocator;
    void *keysBase;
    set->_capacity = __CFSetRoundUpCapacity(oldCount + numNewValues);
    set->_bucketsNum = __CFSetNumBucketsForCapacity(set->_capacity);
    set->_deletes = 0;
    void *buckets = _CFAllocatorAllocateGC(allocator, set->_bucketsNum * sizeof(const void *), (set->_xflags & __kCFSetWeakKeys) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED);
    // 扩容key
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, set, set->_keys, buckets);
    keysAllocator = allocator;
    keysBase = set->_keys;
    if (NULL == set->_keys) HALT;
    if (__CFOASafe) __CFSetLastAllocationEventName(set->_keys, "CFSet (store)");
    
    // 重新计算key的hash值,存放到新数组中
    for (idx = set->_bucketsNum; idx--;) {
        set->_keys[idx] = (const void *)set->_marker;
    }
    if (NULL == oldkeys) return;
    for (idx = 0; idx < oldnbuckets; idx++) {
        if (set->_marker != (uintptr_t)oldkeys[idx] && ~set->_marker != (uintptr_t)oldkeys[idx]) {
            CFIndex match, nomatch;
            __CFSetFindBuckets2(set, 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], set->_keys[match]);
            if (kCFNotFound != nomatch) {
                CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, set->_keys[nomatch], oldkeys[idx]);
            }
        }
    }
    CFAssert1(set->_count == oldCount, __kCFLogAssertion, "%s(): set count differs after rehashing; error", __PRETTY_FUNCTION__);
    _CFAllocatorDeallocateGC(allocator, oldkeys);
}

NSDictionary

字典的数据结构如下,它由两个指针数组分别保存keys和values。

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 */
    const void **_keys;     /* can be NULL if not allocated yet */
    const void **_values;   /* can be NULL if not allocated yet */
};

同样也是使用开放定址法来解决哈希冲突问题。如果使用拉链法key与value应该是一个存储结构。与集合不同的是,如果key存在的话需要覆盖旧值,添加新值。
而且开放定址法的查找算法接近O(1)。

void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
    // 通过match,nomatch来判断是否存在key
    CFIndex match, nomatch;
    __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
    。。。
    if (kCFNotFound != match) {
        // key已存在,覆盖newValue
    CF_OBJC_KVO_WILLCHANGE(dict, key);
    CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
    CF_OBJC_KVO_DIDCHANGE(dict, key);
    } else {
        // key不存在,新增value
    CF_OBJC_KVO_WILLCHANGE(dict, key);
    CF_WRITE_BARRIER_ASSIGN(keysAllocator, dict->_keys[nomatch], newKey);
    CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[nomatch], newValue);
    dict->_count++;
    CF_OBJC_KVO_DIDCHANGE(dict, key);
    }
}

// 查找key存储的位置
static void __CFDictionaryFindBuckets2(CFDictionaryRef dict, const void *key, CFIndex *match, CFIndex *nomatch) {
    const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
    // 获取hash值
    CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
    const void **keys = dict->_keys;
    uintptr_t marker = dict->_marker;
    CFIndex probe = keyHash % dict->_bucketsNum;
    CFIndex probeskip = 1;  // See RemoveValue() for notes before changing this value
    CFIndex start = probe;
    *match = kCFNotFound;
    *nomatch = kCFNotFound;
    for (;;) {
    uintptr_t currKey = (uintptr_t)keys[probe];
    // 空桶,返回nomatch,未匹配
    if (marker == currKey) {        /* empty */
        if (nomatch) *nomatch = probe;
        return;
    } else if (~marker == currKey) {    /* deleted */
        if (nomatch) {
        *nomatch = probe;
        nomatch = NULL;
        }
    } else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, dict->_context))) {
        // 匹配成功,返回match
        *match = probe;
        return;
    }
    
    // 未匹配,发生碰撞,将数组下标后移,直到找到空闲区域位置
    probe = probe + probeskip;
    
    if (dict->_bucketsNum <= probe) {
        probe -= dict->_bucketsNum;
    }
    if (start == probe) {
        return;
    }
    }
}

因为字典中key-value是一一对应的关系,所以要保证keys和values数组的长度要一致。所以扩容的时候需要一起扩容。

// setValue时判断
void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
    ...
    if (dict->_count == dict->_capacity || NULL == dict->_keys) {
         __CFDictionaryGrow(dict, 1);
    }
    ...
}

// 扩容
static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues) {
    // 保存旧值
    const void **oldkeys = dict->_keys;
    const void **oldvalues = dict->_values;
    CFIndex idx, oldnbuckets = dict->_bucketsNum;
    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;
    ...
    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;
    ...
    // 重新计算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]);
            }
        }
    }
    ...
}

dictionary之所以采用这种设计,其一出于查询性能的考虑;其二dictionary在使用过程中总是会很快的被释放,不会长期占用内存。

AssociatedObject关联对象

关联对象它实现了不通过继承来增加属性的需求。通过源码可以发现关联对象内部使用了嵌套map的结构实现了对象的扩展属性管理。也是采用了开放定址法。

void _object_set_associative_reference(id object, void *key, id value, uintptr_t policy) {
    /// 获取associated object全局map
    AssociationsManager manager;
    AssociationsHashMap &associations(manager.associations());
    
    /// DISGUISE宏定义获取对象的唯一值,等同于hash方法
    disguised_ptr_t disguised_object = DISGUISE(object);
    if (new_value) {
        AssociationsHashMap::iterator i = associations.find(disguised_object);
        if (i != associations.end()) {
        /// 结果不等于未匹配end()
            ObjectAssociationMap *refs = i->second;
            ObjectAssociationMap::iterator j = refs->find(key);
            if (j != refs->end()) {
                old_association = j->second;
                j->second = ObjcAssociation(policy, new_value);
            } else {
                (*refs)[key] = ObjcAssociation(policy, new_value);
            }
        } else {
        /// 对象未绑定过任何属性,新增map存储
            ObjectAssociationMap *refs = new ObjectAssociationMap;
            associations[disguised_object] = refs;
            (*refs)[key] = ObjcAssociation(policy, new_value);
            _class_setInstancesHaveAssociatedObjects(_object_getClass(object));
        }
    } else {
        AssociationsHashMap::iterator i = associations.find(disguised_object);
        /// 结果不等于未匹配end()
        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);
            }
        }
    }
}

ObjectAssociationMap是被上面嵌套的dictionary,这个结构存储了实际绑定的属性值。在我们调用objc_setAssociatedObject的时候,会将传入的key和value存储在这里面。

开放定址法在大量数据存储时,会造成大量空间占用。为什么要使用这种方案呢?因为虽然苹果使用了一个全局的AssociationsHashMap对象存储了全部的关联对象,但在对象dealloc时会移除这些数据,同一时间占用的内存也是可接受的。

@sychronized

@sychronized 采用了hash+linked实现结构,参照源码,实际上使用了拉链法解决碰撞问题。在代码编译时,转换成了以下函数调用:

int objc_sync_enter(id obj);
int objc_sync_exit(id obj);

相比一般拉链法的设计,@sychronized增加了缓存机制,下面是关键结构:

typedef struct SyncData {
    struct SyncData* nextData;
    id               object;
    int              threadCount;
    recursive_mutex_t        mutex;
} SyncData;
 
typedef struct {
    SyncData *data;
    OSSpinLock lock;
    
    char align[64 - sizeof (OSSpinLock) - sizeof (SyncData *)];
} SyncList __attribute__((aligned(64)));
 
#define COUNT 16
#define HASH(obj) ((((uintptr_t)(obj)) >> 5) & (COUNT - 1))
#define LOCK_FOR_OBJ(obj) sDataLists[HASH(obj)].lock
#define LIST_FOR_OBJ(obj) sDataLists[HASH(obj)].data
static SyncList sDataLists[COUNT];

在代码@synchronized(x)中一开始有一个结构体 struct SyncData,这个结构体中包括object就是传入的对象以及和x关联的锁mutex。结构体中还包括nextData这是明显的链表特征。threadCount记录对象被锁线程使用的数量,当threadCount=0的时候,可以拿出来复用,赋值给其他对象。

链表SyncList,里面有头节点SyncData,防止多线程修改链表头结点的自旋锁 OSSpinLock。这里可以看出@synchronized(x)是使用拉链法解决冲突的,因此设计了链表。

下面来看下hash算法HASH(obj),将对象的指针传入,然后向右位移5,和COUNT-1进行与运算,这样结果不会超过数组长度。那么下面两个宏就很好理解了LOCK_FOR_OBJ和LIST_FOR_OBJ,传入的对象进行HASH运算,算出0-15的一个index,然后数组直接指针偏移以O(1),直接拿出数据,如果不同对象放在同一个index,冲突就在一条链表中,继续遍历链表拿数据。

为什么同样是使用全局存储的方式@synchronized和associated采用的方式不一样。

其实主要是根据存储数据的生命周期和特性所决定的:

  • 开放定址法的存储属性基本是和key所属对象相关联的,一旦key所属对象发生变化时,其所存储的数据大概率也是要发生修改的。因此即便是开放定址法在使用全局实现时,对象释放时同样会清空所存储的内容,因此总体来说内存占用并不会过高。
  • 拉链法对于碰撞的处理方式更为简单,不用担心数据的堆积现象。另外如果存储的数据是通用类型数据,可以被反复利用。比如@synchronized是存储的锁是一种无关业务的实现结构,程序运行时多个对象使用同一个锁的概率相当的高,有效的节省了内存。

weak的实现

每次准备面试的时候背八股文的时候都说,weak修饰的对象是弱引用,引用计数不会+1,在释放的时候会自动置为nil。用weak修饰的对象,会以对象的指针为key,weak指针为value放在weak表中。释放的时候,找到通过对象地址找到weak指针,然后置为nil。这次有时间努力地学习了一下原理。

当然weak表也是用哈希表实现的,所以放到这篇一起介绍。

objc_initWeak方法

Person *object = [Person alloc];
id __weak objc = object;

当我们将对象赋值给weak修饰的对象时,会调用objc_initWeak方法。
该方法主要参数

  • location: weak指针地址,存储指针的地址,这样便可以在最后将其指向的对象置为nil。
  • newObj:引用的对象,就是例子中的obj。
id objc_initWeak(id *location, id newObj)
{
    if (!newObj) {
        *location = nil;
        return nil;
    }

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

objc_initWeak方法内部主要调用了storeWeak方法。

storeWeak

storeWeak的实现:

// Template parameters.
enum HaveOld { DontHaveOld = false, DoHaveOld = true };
enum HaveNew { DontHaveNew = false, DoHaveNew = true };
enum CrashIfDeallocating {
    DontCrashIfDeallocating = false, DoCrashIfDeallocating = true
};

template <HaveOld haveOld, HaveNew haveNew,
          CrashIfDeallocating crashIfDeallocating>
static id
storeWeak(id *location, objc_object *newObj)
{
    assert(haveOld  ||  haveNew);
    if (!haveNew) assert(newObj == nil);

    Class previouslyInitializedClass = nil;
    id oldObj;
    SideTable *oldTable;
    SideTable *newTable;

    // Acquire locks for old and new values.
    // Order by lock address to prevent lock ordering problems.
    // Retry if the old value changes underneath us.
 retry:
    if (haveOld) { // 如果weak ptr之前弱引用过一个obj,则将这个obj所对应的SideTable取出,赋值给oldTable
        oldObj = *location;
        oldTable = &SideTables()[oldObj];
    } else {
        oldTable = nil; // 如果weak ptr之前没有弱引用过一个obj,则oldTable = nil
    }
    if (haveNew) { // 如果weak ptr要weak引用一个新的obj,则将该obj对应的SideTable取出,赋值给newTable
        newTable = &SideTables()[newObj];
    } else {
        newTable = nil; // 如果weak ptr不需要引用一个新obj,则newTable = nil
    }
    
    // 加锁操作,防止多线程中竞争冲突
    SideTable::lockTwo<haveOld, haveNew>(oldTable, newTable);

    // location 应该与 oldObj 保持一致,如果不同,说明当前的 location 已经处理过 oldObj 可是又被其他线程所修改
    if (haveOld  &&  *location != oldObj) {
        SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
        goto retry;
    }

    // Prevent a deadlock between the weak reference machinery
    // and the +initialize machinery by ensuring that no
    // weakly-referenced object has an un-+initialized isa.
    if (haveNew  &&  newObj) {
        Class cls = newObj->getIsa();
        if (cls != previouslyInitializedClass  &&
            !((objc_class *)cls)->isInitialized())  // 如果cls还没有初始化,先初始化,再尝试设置weak
        {
            SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
            _class_initialize(_class_getNonMetaClass(cls, (id)newObj));
            // If this class is finished with +initialize then we're good.
            // If this class is still running +initialize on this thread
            // (i.e. +initialize called storeWeak on an instance of itself)
            // then we may proceed but it will appear initializing and
            // not yet initialized to the check above.
            // Instead set previouslyInitializedClass to recognize it on retry.
            previouslyInitializedClass = cls; // 这里记录一下previouslyInitializedClass, 防止改if分支再次进入

            goto retry; // 重新获取一遍newObj,这时的newObj应该已经初始化过了
        }
    }
    // Clean up old value, if any.
    if (haveOld) {
        weak_unregister_no_lock(&oldTable->weak_table, oldObj, location); // 如果weak_ptr之前弱引用过别的对象oldObj,则调用weak_unregister_no_lock,在oldObj的weak_entry_t中移除该weak_ptr地址
    }

    // Assign new value, if any.
    if (haveNew) { // 如果weak_ptr需要弱引用新的对象newObj
        // (1) 调用weak_register_no_lock方法,将weak ptr的地址记录到newObj对应的weak_entry_t中
        newObj = (objc_object *)
            weak_register_no_lock(&newTable->weak_table, (id)newObj, location,
                                  crashIfDeallocating);
        // weak_register_no_lock returns nil if weak store should be rejected
        
        // (2) 更新newObj的isa的weakly_referenced bit标志位
        // Set is-weakly-referenced bit in refcount table.
        if (newObj  &&  !newObj->isTaggedPointer()) {
            newObj->setWeaklyReferenced_nolock();
        }

        // Do not set *location anywhere else. That would introduce a race.
        // (3)*location 赋值,也就是将weak ptr直接指向了newObj。可以看到,这里并没有将newObj的引用计数+1
        *location = (id)newObj; // 将weak ptr指向object
    }
    else {
        // No new value. The storage is not changed.
    }
    
    // 解锁,其他线程可以访问oldTable, newTable了
    SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);

    return (id)newObj; // 返回newObj,此时的newObj与刚传入时相比,weakly-referenced bit位置1
}

下图可以比较清晰的描述了storeWeak的过程:


初始化弱引用对象流程.png
  • 维护了oldTable和newTable
  • 加锁处理
  • 调用weak_unregister_no_lock移除旧引用 和weak_register_no_lock添加新引用 这两个方法。而这两个方法都是操作的SideTable 这样一个结构的变量 。
  • 调用setWeaklyReferenced_nolock 方法修改weak新引用的对象的bit标志位

SideTable、weak_table_t、weak_entry_t

SideTable
struct SideTable {
    spinlock_t slock;
    RefcountMap refcnts;
    weak_table_t weak_table;
}

SideTable有三个成员:

  • slock: 自旋锁,用于上锁Si的Table
  • refcnts:用来存储OC对象的引用计数的 hash表(仅在未开启isa优化或在isa优化情况下isa_t的引用计数溢出时才会用到)。
  • weak_table 存储对象弱引用指针的hash表。是OC中weak功能实现的核心数据结构。
weak_table_t
struct weak_table_t {
    weak_entry_t *weak_entries;
    size_t    num_entries;
    uintptr_t mask;
    uintptr_t max_hash_displacement;
};

weak_table_t:

  • weak_entries : hash数组,用来存储弱引用对象的相关信息
  • num_entries:hash数组中的元素个数
  • mask:hash数组长度-1,会参与hash计算。(注意,这里是hash数组的长度,而不是元素个数。比如,数组长度可能是64,而元素个数仅存了2个)
  • max_hash_displacement:可能会发生的hash冲突的最大次数,用于判断是否出现了逻辑错误(hash表中的冲突次数绝不会超过改值)
weak_entry_t

weak_entry_t结构也是一个hash结构,其存储的元素是弱引用对象指针的地址。
定长数组inline_referrers的引用个数最大值为4
动态数组的默认长度是8,这里要考虑到entry->mask取值,一定是:0x111, 0x1111, 0x11111, ... ,因为数组每次都是*2增长,即8, 16, 32

#define WEAK_INLINE_COUNT 4
#define REFERRERS_OUT_OF_LINE 2

struct weak_entry_t {
    DisguisedPtr<objc_object> referent; // 被弱引用的对象
    
    // 引用该对象的对象列表,联合。 引用个数小于4,用inline_referrers数组。 用个数大于4,用动态数组weak_referrer_t *referrers
    union {
        struct {
            weak_referrer_t *referrers;                      // 弱引用该对象的对象指针地址的hash数组
            uintptr_t        out_of_line_ness : 2;           // 是否使用动态hash数组标记位
            uintptr_t        num_refs : PTR_MINUS_2;         // hash数组中的元素个数
            uintptr_t        mask;                           // hash数组长度-1,会参与hash计算。
            uintptr_t        max_hash_displacement;          // 可能会发生的hash冲突的最大次数,用于判断是否出现了逻辑错误
        };
        struct {
            // out_of_line_ness field is low bits of inline_referrers[1]
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };

    bool out_of_line() {
        return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
    }

    weak_entry_t& operator=(const weak_entry_t& other) {
        memcpy(this, &other, sizeof(other));
        return *this;
    }

    weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
        : referent(newReferent) // 构造方法,里面初始化了静态数组
    {
        inline_referrers[0] = newReferrer;
        for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
            inline_referrers[i] = nil;
        }
    }
};
  • weak_entry_t是一个联合体,在联合体内部有定长数组inline_referrers和动态数组weak_referrer_t存储弱引用对象的指针地址。
  • out_of_line()通过这个方法判断是哪种存储方式。
  • 当指针数少于WEAK_INLINE_COUNT时,使用定长数组。超过使用动态数组。

到这里我们知道了啥?
weak底层主要调用了storeWeak(),在这个方法中,维护了两个sidetable,带调用weak_unregister_no_lock 和weak_register_no_lock 这两个方法添加和移除弱引用。
弱引用表是一个哈希表,key是对象指针,value是弱引用指针地址的数组。

weak_register_no_lock 添加弱引用

参数解释:

  • weak_table:weak表
  • referent_id: 对象地址
  • *referrer_id: weak指针地址
  • crashIfDeallocating: 是否正在析构

这个方法主要做个几件事:

  1. 如果referent_id是空或采用了TaggedPointer计数方式,直接返回,不做任何操作
  2. 正在析构会抛异常
  3. 不能被弱引用,返回nil
  4. 调用 weak_entry_for_referent方法,根据对象地址查找weak_entry,然后调用append_referrer将weak指针地址加到数组中。
id 
weak_register_no_lock(weak_table_t *weak_table, id referent_id, 
                      id *referrer_id, bool crashIfDeallocating)
{
    objc_object *referent = (objc_object *)referent_id;
    objc_object **referrer = (objc_object **)referrer_id;

    // 如果referent为nil 或 referent 采用了TaggedPointer计数方式,直接返回,不做任何操作
    if (!referent  ||  referent->isTaggedPointer()) return referent_id;

    // 确保被引用的对象可用(没有在析构,同时应该支持weak引用)
    bool deallocating;
    if (!referent->ISA()->hasCustomRR()) {
        deallocating = referent->rootIsDeallocating();
    }
    else {
        BOOL (*allowsWeakReference)(objc_object *, SEL) = 
            (BOOL(*)(objc_object *, SEL))
            object_getMethodImplementation((id)referent, 
                                           SEL_allowsWeakReference);
        if ((IMP)allowsWeakReference == _objc_msgForward) {
            return nil;
        }
        deallocating =
            ! (*allowsWeakReference)(referent, SEL_allowsWeakReference);
    }
    // 正在析构的对象,不能够被弱引用
    if (deallocating) {
        if (crashIfDeallocating) {
            _objc_fatal("Cannot form weak reference to instance (%p) of "
                        "class %s. It is possible that this object was "
                        "over-released, or is in the process of deallocation.",
                        (void*)referent, object_getClassName((id)referent));
        } else {
            return nil;
        }
    }

    // now remember it and where it is being stored
    // 在 weak_table中找到referent对应的weak_entry,并将referrer加入到weak_entry中
    weak_entry_t *entry;
    if ((entry = weak_entry_for_referent(weak_table, referent))) { // 如果能找到weak_entry,则讲referrer插入到weak_entry中
        append_referrer(entry, referrer);   // 将referrer插入到weak_entry_t的引用数组中
    } 
    else { // 如果找不到,就新建一个
        weak_entry_t new_entry(referent, referrer);  
        weak_grow_maybe(weak_table);
        weak_entry_insert(weak_table, &new_entry);
    }

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

    return referent_id;
}
weak_entry_for_referent 取元素
static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
{
    assert(referent);
    weak_entry_t *weak_entries = weak_table->weak_entries;
    if (!weak_entries) return nil;
    size_t begin = hash_pointer(referent) & weak_table->mask;  // 这里通过 & weak_table->mask的位操作,来确保index不会越界
    size_t index = begin;
    size_t hash_displacement = 0;
    while (weak_table->weak_entries[index].referent != referent) {
        index = (index+1) & weak_table->mask;
        if (index == begin) bad_weak_table(weak_table->weak_entries); // 触发bad weak table crash
        hash_displacement++;
        if (hash_displacement > weak_table->max_hash_displacement) { // 当hash冲突超过了可能的max hash 冲突时,说明元素没有在hash表中,返回nil 
            return nil;
        }
    }
    return &weak_table->weak_entries[index];
}
append_referrer添加元素
  • 添加元素的时候,需要先确定是定长数组还是动态数组,如果weak_entry尚未使用动态数组则直接添加到数组中即可。
  • 如果inline_referrers已经满了,则需要转型到到动态数组
  • 如果动态数组“负载因子”大于3/4,需要动态扩容。
  • 采用开放定址法,发生哈希冲突时,将index++
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    if (! entry->out_of_line()) { // 如果weak_entry 尚未使用动态数组,走这里
        // Try to insert inline.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {
                entry->inline_referrers[i] = new_referrer;
                return;
            }
        }
        
        // 如果inline_referrers的位置已经存满了,则要转型为referrers,做动态数组。
        // Couldn't insert inline. Allocate out of line.
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // This constructed table is invalid, but grow_refs_and_insert
        // will fix it and rehash it.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[I];
        }
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

    // 对于动态数组的附加处理:
    assert(entry->out_of_line()); // 断言: 此时一定使用的动态数组

    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果动态数组中元素个数大于或等于数组位置总空间的3/4,则扩展数组空间为当前长度的一倍
        return grow_refs_and_insert(entry, new_referrer); // 扩容,并插入
    }
    
    // 如果不需要扩容,直接插入到weak_entry中
    // 注意,weak_entry是一个哈希表,key:w_hash_pointer(new_referrer) value: new_referrer
    
    // 细心的人可能注意到了,这里weak_entry_t 的hash算法和 weak_table_t的hash算法是一样的,同时扩容/减容的算法也是一样的
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask); // '& (entry->mask)' 确保了 begin的位置只能大于或等于 数组的长度
    size_t index = begin;  // 初始的hash index
    size_t hash_displacement = 0;  // 用于记录hash冲突的次数,也就是hash再位移的次数
    while (entry->referrers[index] != nil) {
        hash_displacement++;
        index = (index+1) & entry->mask;  // index + 1, 移到下一个位置,再试一次能否插入。(这里要考虑到entry->mask取值,一定是:0x111, 0x1111, 0x11111, ... ,因为数组每次都是*2增长,即8, 16, 32,对应动态数组空间长度-1的mask,也就是前面的取值。)
        if (index == begin) bad_weak_table(entry); // index == begin 意味着数组绕了一圈都没有找到合适位置,这时候一定是出了什么问题。
    }
    if (hash_displacement > entry->max_hash_displacement) { // 记录最大的hash冲突次数, max_hash_displacement意味着: 我们尝试至多max_hash_displacement次,肯定能够找到object对应的hash位置
        entry->max_hash_displacement = hash_displacement;
    }
    // 将ref存入hash数组,同时,更新元素个数num_refs
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    entry->num_refs++;
}

weak_unregister_no_lock 移除引用

调用weak_unregister_no_lock方法将旧的weak指针地址移除。

  • 先在table中entry
  • 找到后将referrer从entry中移除
  • 移除后需要判断entry是否还有值
  • 如果没有将entry从table中移除
void
weak_unregister_no_lock(weak_table_t *weak_table, id referent_id, 
                        id *referrer_id)
{
    objc_object *referent = (objc_object *)referent_id;
    objc_object **referrer = (objc_object **)referrer_id;

    weak_entry_t *entry;

    if (!referent) return;

    if ((entry = weak_entry_for_referent(weak_table, referent))) { // 查找到referent所对应的weak_entry_t
        remove_referrer(entry, referrer);  // 在referent所对应的weak_entry_t的hash数组中,移除referrer
       
        // 移除元素之后, 要检查一下weak_entry_t的hash数组是否已经空了
        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_t的hash数组已经空了,则需要将weak_entry_t从weak_table中移除
            weak_entry_remove(weak_table, entry);
        }
    }

到这里我们知道了啥?
知道了weak_register_no_lock添加弱引用,weak_unregister_no_lock移除弱引用,这两个方法的具体实现。
引用计数不会+1,只是在weak_table中添加entry。

dealloc

_objc_rootDealloc

当对象的引用计数为0时,底层会调用_objc_rootDealloc方法对对象进行释放,而在_objc_rootDealloc方法里面会调用rootDealloc方法。

inline void
objc_object::rootDealloc()
{
    if (isTaggedPointer()) return;  // fixme necessary?

    if (fastpath(isa.nonpointer  &&  
                 !isa.weakly_referenced  &&  
                 !isa.has_assoc  &&  
                 !isa.has_cxx_dtor  &&  
                 !isa.has_sidetable_rc))
    {
        assert(!sidetable_present());
        free(this);
    } 
    else {
        object_dispose((id)this);
    }
}
  • 首先判断对象是否是Tagged Pointer,如果是则直接返回。
  • 如果对象是采用了优化的isa计数方式,且同时满足对象没有被weak引用!isa.weakly_referenced、没有关联对象!isa.has_assoc 、没有自定义的C++析构方法!isa.has_cxx_dtor、没有用到SideTable来引用计数!isa.has_sidetable_rc则直接快速释放。
  • 调用object_dispose方法释放。
object_dispose
  • 如果有自定义的C++析构方法,则调用C++析构函数。
  • 如果有关联对象,则移除关联对象并将其自身从Association Manager的map中移除。
  • 调用clearDeallocating 方法清除对象的相关引用。
void *objc_destructInstance(id obj) 
{
    if (obj) {
        // Read all of the flags at once for performance.
        bool cxx = obj->hasCxxDtor();
        bool assoc = obj->hasAssociatedObjects();

        // This order is important.
        if (cxx) object_cxxDestruct(obj);
        if (assoc) _object_remove_assocations(obj);
        obj->clearDeallocating();
    }
    return obj;
}
clearDeallocating
  • 判断是否开启了isa优化,如果未开启需要清理引用计数表
  • 如果isa有辅助引用计数或有weak引用,调用clearDeallocating_slow方法
inline void 
objc_object::clearDeallocating()
{
    if (slowpath(!isa.nonpointer)) {
        // Slow path for raw pointer isa.
        sidetable_clearDeallocating();
    }
    else if (slowpath(isa.weakly_referenced  ||  isa.has_sidetable_rc)) {
        // Slow path for non-pointer isa with weak refs and/or side table data.
        clearDeallocating_slow();
    }

    assert(!sidetable_present());
}

NEVER_INLINE void
objc_object::clearDeallocating_slow()
{
    assert(isa.nonpointer  &&  (isa.weakly_referenced || isa.has_sidetable_rc));

    SideTable& table = SideTables()[this]; // 在全局的SideTables中,以this指针为key,找到对应的SideTable
    table.lock();
    if (isa.weakly_referenced) { // 如果obj被弱引用
        weak_clear_no_lock(&table.weak_table, (id)this); // 在SideTable的weak_table中对this进行清理工作
    }
    if (isa.has_sidetable_rc) { // 如果采用了SideTable做引用计数
        table.refcnts.erase(this); // 在SideTable的引用计数中移除this
    }
    table.unlock();
}
  • clearDeallocating_slow方法中如果isa有weak引用,调用weak_clear_no_lock对weak_table进行清理工作
weak_clear_no_lock
  • 获取动态和定长数组,并且获取数组个数
  • 遍历数组,取出weak指针地址,并设置为nil。
  • 将entry从weak表中删除。
void 
weak_clear_no_lock(weak_table_t *weak_table, id referent_id) 
{
    objc_object *referent = (objc_object *)referent_id;

    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent); // 找到referent在weak_table中对应的weak_entry_t
    if (entry == nil) {
        /// XXX shouldn't happen, but does with mismatched CF/objc
        //printf("XXX no entry for clear deallocating %p\n", referent);
        return;
    }

    // zero out references
    weak_referrer_t *referrers;
    size_t count;
    
    // 找出weak引用referent的weak 指针地址数组以及数组长度
    if (entry->out_of_line()) {
        referrers = entry->referrers;
        count = TABLE_SIZE(entry);
    } 
    else {
        referrers = entry->inline_referrers;
        count = WEAK_INLINE_COUNT;
    }
    
    for (size_t i = 0; i < count; ++i) {
        objc_object **referrer = referrers[i]; // 取出每个weak ptr的地址
        if (referrer) {
            if (*referrer == referent) { // 如果weak ptr确实weak引用了referent,则将weak ptr设置为nil,这也就是为什么weak 指针会自动设置为nil的原因
                *referrer = nil;
            }
            else if (*referrer) { // 如果所存储的weak ptr没有weak 引用referent,这可能是由于runtime代码的逻辑错误引起的,报错
                _objc_inform("__weak variable at %p holds %p instead of %p. "
                             "This is probably incorrect use of "
                             "objc_storeWeak() and objc_loadWeak(). "
                             "Break on objc_weak_error to debug.\n", 
                             referrer, (void*)*referrer, (void*)referent);
                objc_weak_error();
            }
        }
    }
    
    weak_entry_remove(weak_table, entry); // 由于referent要被释放了,因此referent的weak_entry_t也要移除出weak_table
}

到此我知道了啥?
知道了dealloc后,weak修饰的对象是怎么置为nil的。

objc_loadWeakRetained

当需要调用weak修饰的对象时,会调用objc_loadWeakRetained方法来对weak对象retain。
之前编译器会将weak修饰的对象加入到自动释放池中,现在是直接release。

{
  id __weak obj1 = obj;
  NSLog(@"%@", obj1);
}
/* iOS5及之前编译器做法 */
id obj1;
objc_initWeak(&obj1, obj);
id tmp = objc_loadWeakRetained(&obj1);
objc_autorelease(tmp);//错误!!!mistake
NSLog(@"%@", tmp);
objc_destroyWeak(&obj1);

/* 现在的编译器做法*/
id obj = objc_msgSend(NSObject, "new");
id obj1;
objc_initWeak(&obj1, obj);
id tmp = objc_loadWeakRetained(obj1);//objc_loadWeakRetained would increment the reference count to ensure that tmp is alive in the NSLog statement.
NSLog(@"%@", obj1);
objc_release(tmp);
objc_destroyWeak(&obj1);
objc_storeStrong(&obj, 0);//release

当需要调用weak修饰的对象时:

  • 首先调用initWeak方法获取weak对象
  • 调用objc_loadWeakRetained
  • 首先判断是否是isTaggedPointer,如果是直接返回对象
  • 判断isa是否有hasCustomRR,retain/release/autorelease/retainCount/_tryRetain/_isDeallocating/retainWeakReference/allowsWeakReference返回true,一般情况我们都不会重写这些方法,因此会返回false,取反就为true
  • 执行if (! obj->rootTryRetain()) {result = nil;}尝试对象进行retain
  • retain成功返回对象,失败返回nil
/*
  Once upon a time we eagerly cleared *location if we saw the object 
  was deallocating. This confuses code like NSPointerFunctions which 
  tries to pre-flight the raw storage and assumes if the storage is 
  zero then the weak system is done interfering. That is false: the 
  weak system is still going to check and clear the storage later. 
  This can cause objc_weak_error complaints and crashes.
  So we now don't touch the storage until deallocation completes.
*/

id
objc_loadWeakRetained(id *location)
{
    id obj;
    id result;
    Class cls;

    SideTable *table;
    
 retry:
    // fixme std::atomic this load
    obj = *location;
    if (!obj) return nil;
    if (obj->isTaggedPointer()) return obj;
    
    table = &SideTables()[obj];
    
    table->lock();
    if (*location != obj) {
        table->unlock();
        goto retry;
    }
    
    result = obj;

    cls = obj->ISA();
    if (! cls->hasCustomRR()) {
        // Fast case. We know +initialize is complete because
        // default-RR can never be set before then.
        assert(cls->isInitialized());
        if (! obj->rootTryRetain()) {
            result = nil;
        }
    }
    else {
        // Slow case. We must check for +initialize and call it outside
        // the lock if necessary in order to avoid deadlocks.
        if (cls->isInitialized() || _thisThreadIsInitializingClass(cls)) {
            BOOL (*tryRetain)(id, SEL) = (BOOL(*)(id, SEL))
                class_getMethodImplementation(cls, SEL_retainWeakReference);
            if ((IMP)tryRetain == _objc_msgForward) {
                result = nil;
            }
            else if (! (*tryRetain)(obj, SEL_retainWeakReference)) {
                result = nil;
            }
        }
        else {
            table->unlock();
            _class_initialize(cls);
            goto retry;
        }
    }
        
    table->unlock();
    return result;
}

realease调用时间:

  • 在ARC中编译器会在weak对象操作的下面插入一条release语句
  • 在MRC中,获取weak指向的对象时,并不会直接调用objc_loadWeakRetained,而是会调用objc_loadWeak,此方法的实现如下:利用自动释放池,对retain的对象进行release操作

学习链接

集合NSSet、字典NSDictionary的底层实现原理
更深层次的了解iOS内存管理
iOS开发 之 不要告诉我你真的懂isEqual与hash!
hash
NSDictionary和NSMutableArray底层原理(哈希表和环形缓冲区)
weak的实现原理
详解获取weak对象的过程
从一个crash理解weak的延迟释放

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,163评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,301评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,089评论 0 352
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,093评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,110评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,079评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,005评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,840评论 0 273
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,278评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,497评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,667评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,394评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,980评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,628评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,649评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,548评论 2 352

推荐阅读更多精彩内容