数据结构 --- 【Map 和 Set】详解

本章目标

1. 掌握 Map/Set 及实际实现类 HashMap/TreeMap/HashSet/TreeSet 的使用
2. 掌握 TreeMap 和 TreeSet 背后的数据结构搜索树的原理和简单实现
3. 掌握 HashMap 和 HashSet 背后的数据结构哈希表的原理和简单实现

1.Map 和 Set 的概念

Map 和 Set 是一种专门用来进行搜索的关联式容器或者数据结构；

• 关联式容是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高
• 键值对是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和value，key 代表键值，value 表示与 key 对应的信息

而 Map 中存储的就是 key-value 的键值对，Set 中只存储了 Key。

2.Map 的使用 

关于 Map 的说明

• Map 是一个接口类，该类没有继承自 Collection，该类中存储的是结构的键值对，并且 K 一定是唯一的，不能重复；value 是可以重复的
• Map 是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类 TreeMap 或者 HashMap
• 在内部