目录

• 映射
• Map的接口设计
• TreeMap分析
• 代码实现

一 映射(Map)

• Map 在有些编程语言中也叫做字典（dictionary，比如 Python、Objective-C、Swift 等）

key（键）- value（值）

• Map 的每一个 key 是唯一的

二 Map的接口设计

• Map

@interface Map : NSObject

- (int)size;

- (BOOL)isEmpty;

- (void)put:(id)key value:(id)value;

- (void)get:(id)key;

- (void)remove;

- (BOOL)containsKey:(id)key;

- (BOOL)containsValue:(id)value;

@end

• 类似 Set，Map 可以直接利用之前学习的链表、二叉搜索树（AVL树、红黑树）等数据结构来实现

三 TreeMap分析

• 时间复杂度（平均）
  添加、删除、搜索：O(logn)

• 特点
  1.Key 必须具备可比较性
  2.元素的分布是有顺序的

• 在实际应用中，很多时候的需求
  1.Map 中存储的元素不需要讲究顺序
  2.Map 中的 Key 不需要具备可比较性

• 不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1)
  1.那就是采取哈希表来实现 Map

四 代码实现

4.1 定义节点

• Node

typedef enum : NSUInteger {
    red = 0,
    black = 1,
} ColorType;

@interface Node: NSObject
/** key */
@property(nonatomic,strong)id key;
/** value */
@property(nonatomic,strong)id value;
/** bool */
@property(nonatomic,assign)ColorType color;
/** left */
@property(nonatomic,strong)Node *left;
/** right */
@property(nonatomic,strong)Node *right;
/** parent*/
@property(nonatomic,strong)Node *parent;

- (instancetype)initWithKey:(id)key value:(id)value parent:(Node *)parent;

// 是否是叶子节点
- (BOOL)isLeaf;

- (BOOL)hasTwoChildren;

- (BOOL)isLeftChild;

- (BOOL)isRightChild;

// 返回兄弟节点
- (Node *)sibling;

@end

4.2 映射 TreeMap

• TreeMap

@interface TreeMap()
/** red*/
@property(nonatomic,assign)BOOL red;
/** black*/
@property(nonatomic,assign)BOOL black;
/** size*/
@property(nonatomic,assign)int size;
/** root */
@property(nonatomic,strong)Node *root;

- (int)size;

- (BOOL)isEmpty;

- (void)clear;

- (void)put:(id)key value:(id)value;

- (id)get:(id)key;

- (BOOL)containsKey:(id)key;

- (BOOL)containsValue:(id)value;

@end

4.3 测试代码

- (void)test1 {
    TreeMap *map = [[TreeMap alloc] init];
    [map put:@"c" value:@2];
    [map put:@"a" value:@5];
    [map put:@"b" value:@6];
    [map put:@"a" value:@8];
    
    [map traversal];
}

• 运行结果如下

2020-03-01 14:10:43.294267+0800 14_Map[99580:5046625] c_2
2020-03-01 14:10:43.294447+0800 14_Map[99580:5046625] b_6
2020-03-01 14:10:43.294542+0800 14_Map[99580:5046625] a_5

项目链接地址 - 14_Map

本文参考 MJ老师的 恋上数据结构与算法

《恋上数据结构与算法一》笔记

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏与点赞是对我最大的支持和鼓励。