数据结构：Map 与 Set 结构详解

数据结构：Map 与 Set 结构详解

一、接口的实现

接口是在实现类子类里完整实现的。

1. 方法上

接口处在被使用范围下时，在意义编译的要求下，一定要被连接有此接口的实现类赋值向上转型，使得里面的抽象方法都被重写。因为这些抽象方法都无方法体，每个抽象方法设置有点意义的也就只有形参类型、返回值类型，无完整意义的，所以抽象方法的完整实现是在实现类子类里完成的。

2. 成员上

接口里一般不会定义成员变量，更多时候成员变量都是在实现类子类这边结合临摹要实现的抽象方法，在可创建的各样对象中根据具体需求选择针对性地自定义实现的，从而达到接口实现的多样化。所以接口设置成在实现类里面创建成员变量是接口能多样化实现的保障。

二、Map 的内外双接口结构

public interface Map<K, V> {
    // 外部 Map 整体接口
    // Map 接口临摹 从外部、握整体操作包装节点
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    
    interface Entry<K, V> {
        // 内部 Entry 局部接口
        // Entry 接口临摹 每个包装节点对象自己对自身的操作
        K getKey();
        V getValue();
        V setValue(V value);
    }
}

1. 实现

1.1 外部 Map 接口的实现

1.1.1 临摹整体

外部 Map 整体接口的抽象方法临摹着从外部、握整体地能操作着所有键值成对包装单位体。

1.1.2 外部类实现整体

对应到具体实现类那边，外部 Map 整体接口的实现类果真就额外有操作所有包装单位整体的入口成员变量，再配着重写着的操作整体的实现方法。外部 Map 整体接口的实现类（即实现类整体中不包含内部 Entry 实现类的外部 Map 实现类部分）实现了对包装单位从整体的操作。

1.2 内部 Entry 接口的实现

1.2.1 临摹内部

内部 Entry 局部接口的抽象方法临摹着从内部包装单位体自身对自己范围内的内部操作。

1.2.2 内部类实现内部

对应到具体实现类那边，内部 Entry 局部接口实现类就额外有包装单位自身的组成信息成员变量，配合着重写着的包装单位自身内部操作实现方法。内部 Entry 局部接口实现类就也实现了它每创的包装单位对象都能实现对自身信息的操作。

2. 关系

在每个 Map 实现类中，向整体 Map 接口向上转型间接实例的从整体操作所有包装单位的实例对象就只有它一个，而由它的内部类向上转型 Entry 接口间接实例化的包装单位对象创建得可就多了，即外部实现类 Map 一个实例对象管理着内部类 Entry 的许多实例对象。

3. 意义

3.1 逻辑内聚

接口里面装内部接口，内部接口 Entry 能访问外部接口 Map 就直接固定设置成相同的泛型参数 K、V，直接保证上从整体视角与个体视角管理包装单位都要的类型恒统一。

3.2 访问封装

内部接口加层封装于外部使用者接口里面，使内部接口受正确限访问，包装得更加针对且安全。

3.3 成套对应

外部接口实例化时，由于抽象相关的在去使用了的范围内必须要重写实现上其意义，因此外部接口的实现类也同时要求着去重写实现有内部接口相关的所有抽象的东西，即也要求同时有去实例化内部接口也实现它的意义，所以这也就使得有内部接口的接口实例化需要对应有内部类的实现类来实现，接口与类对应着实现的（接口的实例化都是间接的）。

三、Map 实现类的存储结构

在 Map 对应实现类的引用管理对象体系中，最上层 Map 实现类的实例对象通过分层向下管理来组织基本节点对象的数据组织结构，或者由基本对象节点自连串自己组织成数据组织结构，实现着最上层类引用对象管理着成组织数据结构中的每个单位基本节点对象。

1. 包装节点对象

Map 数据结构里面的基本操作单位是关键字对象与值对象对应两合并成的一个键值对包装对象（String 与 Integer 两合并包装成一个对象），而其它数据结构的基本操作单位都是一个底层直接对象（以 Integer 一个对象为基本操作单位）。

2. 数据组织结构

2.1 数组 + 链表/红黑树

2.1.1 结构

HashMap 用数组 + 链表/红黑树的数据组织结构组织包装节点对象：

• 将包装节点的键值通过哈希函数计算映射到数组索引来确定存放，每个数组元素哈希桶里面都是存放包装节点自实现作的一个链表头节点或者根节点。

包装节点映射到数组同一位置时，节点会自连接组织连接进桶里存放，到链表过长时此数组元素哈希桶里面的链表节点都会通过 Node 类 extend 继承扩展转为 TreeNode 类全部转为红黑树节点转化成装红黑树的哈希桶结构（提高查询效率）来继续存放在此数组索引位置。

2.1.2 顺序

通过哈希函数计算映射索引来确定元素在数组位置的，元素们用此函数来确定的位置之间是无序的。

2.1.3 复杂度

一次哈希函数计算映射就能锁定元素位置，数据操作查插删的时间复杂度都是 O(1)，哈希结构的存储能实现数据的极速操作。

2.2 红黑树

2.2.1 结构

TreeMap 中，通过在包装单位里面定义自己自连串组织结构，包装单位们能自组织成红黑树的结构（一种自平衡的二叉搜索树）。

2.2.2 顺序

包装单位按照键值的顺序有序地在树中存储。

2.2.3 复杂度

通过比较搜索来确定元素的，数据操作查插删的时间复杂度都是 O(logN)，即树的高度次。

四、Map 接口里的方法使用

Map 接口里只有抽象方法的临摹，抽象方法的实现、成员变量的定义存在、数据结构的组织都是在实现类 TreeMap、HashMap 中才有去实现的。

1. 外接口 Map

外部接口对应实现的外部类完成从外部整体对自己里面创建的所有包装节点的整体操作：

1.1 查询

1.1.1 键查询值 (无默认值):

map.get(Object key);
// -> return V
// 键查询获取 此 map 实现类创建的 包装节点数据组织结构里 某键值对象对应的 包装节点里的值

1.1.2 键查询值 (有默认值):

map.get(Object key, V defaultValue);
// -> return V
// 键查询获取 此 map 实现类里面的 此键对应的包装节点的值，如果此创建的数据节点结构中 没有此键值的包装节点，则返回默认值

1.2 修改:

map.put(K key, V value);
// -> return V
// 修改设置 实现类 map 里面创建存储的 某键对应的 包装节点里的值

1.3 删除:

map.remove(Object key)
// -> return V
// 键查询删除 map 里面对应的包装节点，并将此包装节点里的值对象返回

1.4 判断

1.4.1 判断键存在:

map.containsKey(Object key);
// -> return boolean
// 判断 map 实现类里面创建的 所有包装节点中是否含有此键对象

1.4.2 判断值存在:

map.containsValue(Object value);
// -> return boolean
// 判断 map 实现类里面创建的 所有包装节点中是否含有此值对象

1.5 获取

1.5.1 获取所有键:

map.keySet();
// -> return Set<K>
// 将 map 实现类里面创建的 所有包装节点的键对象 存放在 Set 集合中返回获取

1.5.2 获取所有值:

map.values();
// -> return Collection<V>
// 将 map 实现类里面创建的 所有包装节点的值对象 存放在 Collection 集合中返回获取（Set 集合里面不会存放重复的值，value 的值是可有重复的，就不要用 Set 集合接收 来用 Collection 集合接收了）

1.5.3 获取所有包装节点:

map.entrySet();
// -> return Set<Map.Entry<K,V>>
// 将 map 实现类里面创建的 所有包装节点向上转型回 接口类型的包装节点，存放在 Set 集合中返回获取

2. 内接口 Entry

内部接口对应实现的内部类完成从内部每个包装节点对自身的操作，HashMap 实现类里面用 Node 内部类对应实现 Entry 内部接口，TreeMap 实现类里面用 Entry 内部类来对应实现 Entry 内部接口：

2.1 获取

2.1.1 获取节点的键:

entry.getKey();
// -> return K
// 获取该包装节点里面装的键对象

2.1.2 获取节点的值:

entry.getValue();
// -> return V
// 获取该包装节点里面装的值对象

2.2 修改:

entry.setValue(V value);
// -> return V
// 将该包装节点里面的值对象 修改设置为指定值对象

五、Set 接口

1. 复用性

Set 与 Map 结构都是一样的，只是 Set 使用时它的基本节点键值包装对象里面的值对象统一设置成了 Object 类对象来填充，相当于不管查询意义的 Object 连着存储，实现的也就是只针对键对象的 不重复数据的存储，它里面的元素 实际上就是包装节点下的键值。

2. 定义分类

Set 实现类的底层也都是复用 Map 实现类的那套，定义的基本操作对象也都还是包装节点，但已忽略掉了值对象，相当于只存一个不会重复的 键对象节点了，所以在集合中把它单独定义分类出来 视为元素了，所以在集合中它的接口 Set、它的实现类 TreeSet、TreeMap 都是定义在 Collection 接口下的。

六、Set 接口里的方法使用

Set 接口里也是只有抽象方法的临摹，方法的具体实现、方法的操作对象也都在实现类 TreeSet、TreeMap 中 定义进行的。

1. 获取

1.1 获取所有元素:

set.toArray();
// -> return Object[]
// 将此 set 集合中的所有元素 装到数组中返回

1.2 获取元素个数:

set.size();
// -> return int
// 获取此 set 集合中的元素个数

1.3 获取迭代器:

set.iterator();
// -> return Iterator<E>
// 获取对应迭代此 set 集合元素的迭代器

2. 添加

2.1 添加一个元素:

set.add(E e);
// -> return boolean
// 往此 set 实现类里面 添加存储一个元素，如果在实现类里面 元素已存储有，则不会添加成功

2.2 添加集合元素:

set.addAll(Collection<? extends E> c);
// -> return boolean
// 将集合 c 中的元素 全部添加到此 set 集合中，可以达到去重效果

3. 删除:

set.remove(Object o);
// -> return boolean
// 删除 set 实现的集合中的 o 对象元素

4. 判断

4.1 判断是否空:

set.isEmpty();
// -> return boolean
// 判断此 set 集合是否为空

4.2 判断一个元素存在:

set.contains(Object o);
// -> return boolean
// 判断此 set 集合中是否有 o 对象元素

4.3 判断集合元素存在:

set.containsAll(Collection<?> c);
// -> return boolean
// 判断此 set 集合中 是否全部包含 集合 c 里面的所有元素

5. 清空:

set.clear();
// -> return void
// 清空此 set 集合