iOS·数据结构方案选型：在某数据结构中避免重复字符串元素（NSArray，NSSet，NSDictionary）

场景需求：

解析某博客或者者书籍网站数据时：已知它的书籍首页URL地址，这个首页含有它的书籍目录及其章节的链接，APP想拉取它的目录节点，然而，该目录页面里面的章节可能有重复的内容，那么解析后，我们向内存中保存章节信息的时候，需要过滤。

过滤的标准：假如某数据结构中含有重复的url，就不再重复保存。

数据结构选型：

• 数组：查询复杂度O(N)
  • NSArray
• 哈希表：查询复杂度O(1)
  • NSSet
  • NSDictionary

1. 数组方案

1.1 原生containsObject:方案

• 过滤引擎

- (NSString *)fileterUrl{  //...  if ([self.sectionUrlArr containsObject:sectionUrlStr]) {        return nil;  }  [self.sectionUrlArr addObject:sectionUrlSt];  //...

• 解析引擎

sectionUrlStr = [FilterEngine filterUrl];if (sectionModel.sectionUrlStr) {   [sectionArr addObject:sectionModel];}

• 试验结果

过滤成功。

1.2 自己设置类改写isEqual方案

数组的containsObject:只能检测 内存地址相同 的对象，并不能检测 内存不同但字符串内容相 的NSString对象。

• 自己设置EqualString.m

#import "EqualString.h"@implementation EqualString- (BOOL)isEqual:(id)object {    if (self == object) {        return YES;    }        if (![object isKindOfClass:[NSString class]]) {        return NO;    }        NSString *strEntity = (NSString *)object;        if ([strEntity isEqualToString:self]) {        return YES;    } else {        return NO;    }}@end

• 试验结果

过滤成功。

1.3 分类改写isEqual方案

除了自己设置NSSting类，再考察用分类NSString+Equal重写isEqual的方案。

• 分类NSString+Equal.m

#import "NSString+Equal.h"@implementation NSString (Equal)- (BOOL)isEqual:(id)object {    if (self == object) {        return YES;    }        if (![object isKindOfClass:[NSString class]]) {        return NO;    }        NSString *strEntity = (NSString *)object;        if ([strEntity isEqualToString:self]) {        return YES;    } else {        return NO;    }}@end

• 试验结果

这种方案最后无效。

• 缺点

除了方案不成功，另外很怪异的是，这样写分类并拖到到工程，会对全局的NSString都有影响。即便没有任何地方import该分类。

2. 哈希表结构

其实，对于上述的数组类型的数据结构，假如要查询一个元素，时间复杂度是比较高的，由于它必需遍历才能实现查询操作。

而实际应使用中，查询效率比较高的是哈希表，这种结构在OC开发中有两种常见形式，一种是字典，一种是集合。集合每个元素只要要一样值就可，而字典每个元素则需要存储两种数据，键和值。

另外，哈希结构在Android开发中对应的形式则相似下面的：

private static HashSet<String> sectionUrlSet = new HashSet<>();

2.1 NSSet方案

• 代码

- (NSMutableSet *)sectionUrlSet {    if(!_sectionUrlSet){        _sectionUrlSet = [NSMutableSet set];    }    return _sectionUrlSet;}

• 解析引擎

if ([self.sectionUrlSet containsObject:sectionUrlStr]) {    return nil;}[self.sectionUrlSet addObject:sectionUrlStr];

• 试验结果

过滤成功。

2.2 NSDictionary方案

• 试验代码

- (NSMutableSet *)sectionUrlDict {    if(!_sectionUrlDict){        _sectionUrlDict = [NSMutableDictionary dictionary];    }    return _sectionUrlDict;}

• 解析引擎

if ([[self.sectionUrlDict allKeys] containsObject:sectionUrlStr]) {    return nil;}[self.sectionUrlDict setObject:@"" forKey:sectionUrlStr];

• 试验结果

过滤成功。