场景需求:
解析某博客或者书籍网站数据时:已知它的书籍首页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];
- 实验结果
过滤成功。