《恋上数据结构与算法一》笔记（十四）映射

一映射(Map)

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

key（键）- value（值）

Map 的每一个 key 是唯一的

二 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老师的恋上数据结构与算法

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

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

最后编辑于：2020.03.14 17:36:14