数据结构 --- 【Map 和 Set】详解_set和map原理

本章目标

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
• 在内部，Map 中的元素总是按照键值 key 进行比较排序的
• Map 支持下标访问符，即在 [ ] 中放入 key，就可以找到与 key 对应的 value
• Map 通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))
• Map 中键值对的Key不能直接修改，value 可以修改，如果要修改 key，只能先将该 key 删除掉，然 后再来进行重新插入。

关于Map.Entry<K,V>的说明

Map.Entry<K,V>是 Map 内部实现的用来存放键值对映射关系的内部类，该内部类中主 要提供了的获取，value 的设置以及 Key 的比较方式。

注意：Map.Entry 并没有提供设置 Key 的方法

关于 Map 的常用方法说明

public class AboutMap {
    public static void main(String[] args) {
        // 书籍 -> 作者的映射关系
        Map<String, String> map1 = new TreeMap<>();     // String 是 Comparable 的
        System.out.println(map1);
        System.out.println(map1.size());
        System.out.println(map1.isEmpty());
 
        System.out.println(map1.keySet());
        System.out.println(map1.values());
        System.out.println(map1.entrySet());
 
        // key 不存在时，就是插入操作
 
        System.out.println("==========================");
        System.out.println(map1.put("朝花夕拾", "鲁迅"));
        System.out.println(map1.put("论持久战", "毛泽东"));
        System.out.println(map1.put("子夜", "矛盾"));
        System.out.println(map1.put("战争与和平", "托尔斯泰"));
 
        System.out.println(map1);
        System.out.println(map1.size());
        System.out.println(map1.isEmpty());
 
        System.out.println(map1.keySet());
        System.out.println(map1.keySet().getClass().getName());
        System.out.println(map1.values());
        System.out.println(map1.entrySet());
    }
}

3.Set 的使用 

关于 Set 的说明

• Set 是继承自 Collection 的接口类，Set 中只存储了 key，并且要求 key 一定要唯一
• Set 的底层是使用 Map 来实现的，其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的
• Set 最大的功能就是对集合中的元素进行去重
• Set 中不能插入 null 的 key

关于 Set 的常用方法说明

public class Main {
    public static void main(String[] args) {
        // 现在只需要知道 HashSet 是 Set 接口的一个实现类即可
        Set<Integer> set = new HashSet<>();
 
        System.out.println(set.add(1)); // true
        System.out.println(set.add(1)); // false，因为重复了
        System.out.println(set.add(11));    // true
        System.out.println(set.add(21));    // true
        System.out.println(set.add(31));    // true
 
        // 遍历 set，由于 Set 继承自 Collection，变相的继承自 Iterable
        // 支持 iterator() 方法
        // 使用迭代器遍历 set，但遍历顺序不是按照插入顺序，实际上什么顺序，现在不管
        Iterator<Integer> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
 
        System.out.println(set.contains(1));    // true
        System.out.println(set.contains(3));    // false
 
        System.out.println(set);
        System.out.println(set.remove(1));  // 删除 1 这个元素  true
        System.out.println(set.remove(3));  // 删除 3 这个元素  false
        System.out.println(set);
    }
}