目录
集合
◼ 集合的特点
不存放重复的元素
常用于去重
✓ 存放新增 IP，统计新增 IP 量
✓ 存放词汇，统计词汇量
✓ ……
◼ 思考：集合的内部实现能否直接利用以前学过的数据结构？
动态数组
链表
二叉搜索树（AVL树、红黑树）
集合的接口设计
@protocol LCSetProtocol <NSObject>
/// 清除所有元素
-(void)clear;
/// 元素的数量
-(int)size;
/// 是否为空
-(BOOL)isEmpty;
/// 是否包含某个元素
/// @param element 元素
-(BOOL)isContains:(nonnull id)element;
/// 添加元素到尾部
/// @param element 元素
-(void)add:(nonnull id)element;
/// 删除index位置的元素，并返回被删除的元素
/// @param element 元素
-(void)remove:(nonnull id)element;
/// 遍历结合
/// @param visitor 访问器
-(void)traversalWithVisitor:(Vistor)visitor;
@end
映射
◼ Map 在有些编程语言中也叫做字典（dictionary，比如 Python、Objective-C、Swift 等）
| key 键 | value 值 |
| 石 | 构成地壳的坚硬物质，是由矿物集合而成的 |
| 中 | 方位词，跟四周的距离相等 |
| Jack | 中国_广东_广州_天河区_天河路_229号 |
| class | 100 |
◼ Map 的每一个 key 是唯一的
◼ 类似 Set，Map 可以直接利用之前学习的链表、二叉搜索树（AVL树、红黑树）等数据结构来实现
如果用二叉搜索树来实现，需要外部传入一个比较器，或者使用默认的比较器
映射的接口设计
@protocol LCMapProtocol <NSObject>
+ (instancetype)treeMap;
+ (instancetype)treeMapWithComparator:(_Nullable id<LCComparator>)comparator;
/// 清除所有元素
-(void)clear;
/// 元素的数量
-(int)size;
/// 是否为空
-(BOOL)isEmpty;
/// 是否包含某个key
/// @param key key
-(BOOL)containsKey:(nonnull id)key;
/// 是否包含某个value
/// @param value value
-(BOOL)containsValue:(nullable id)value;
/// 添加或修改键值对，返回旧value
/// @param key key
/// @param value value
-(id)putWithKey:(nonnull id)key value:(nullable id)value;
/// 通过key，获得value
/// @param key key
-(id)getWithKey:(nonnull id)key;
/// 通过key移除键值对,返回移除的value
/// @param key key
-(id)removeWithKey:(nonnull id)key;
/// 遍历结合
/// @param visitor 访问器
-(void)traversalWithVisitor:(MapVistor)visitor;
@end
Map 与 Set
Map 与 Set
◼ Map 的所有 key 组合在一起，其实就是一个 Set
◼ 因此，Set 可以间接利用 Map 来作内部实现
用Map实现Set会造成内存的浪费
| key 键 | value 值 |
| 石 | NULL |
| 中 | NULL |
| Jack | NULL |
| class | NULL |
行者常至，为者常成！