搜索树和哈希表

Map和Set

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。
以前常见的搜索方式有：

• 直接遍历：时间复杂度为O(N)，若元素较多的话，查询效率低。
• 二分查找：时间复杂度为O(logN),但搜索的前提要求数组为有序的。

上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：

1. 根据姓名查询考试成绩
2. 通讯录，即根据姓名查询联系方式
3. 不重复集合，即需要先搜索关键字是否已经在集合中
   可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，Map和Set是一种适合动态查找的集合容器。

模型

一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：

• 纯Key模型：比如，快速查找某个名字是否在通讯录中；
• Key-Value模型：比如统计文件中每个单词出现的次数；

Map

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

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

注意：Map.Entry<K,V>并没有提供设置Key的方法

package xsk;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ForkJoinPool;

public class Demo1 {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 3);
        map.put(2, 4);
        //getKey方法
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey());
        }
        //getValue方法
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getValue());
        }
        //setValue方法
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.setValue(5));
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getValue());
        }
    }
}

Map常用的方法

package xsk;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ForkJoinPool;

public class Demo1 {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 3);
        map.put(2, 4);
        map.put(3, 9);
        map.put(5, 10);
        //getKey方法
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey());
        }
        //getValue方法
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getValue());
        }
        //setValue方法
        //for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            //System.out.println(entry.setValue(5));
        //}
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getValue());
        }
        //get方法
        int ret = map.get(3);
        System.out.println(ret);

        //getOrDefault方法
        int ret1 = map.getOrDefault(1, 0);
        System.out.println(ret1);

        //remove方法
        map.remove(1);
        System.out.println(map.get(1));

        //KeySet方法
        Set<Integer> set =  map.keySet();
        
    }
}

注意：

• Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
• Map中存放键值对的Key是唯一的，value是可以重复的
• 在Map中插入键值对时，key不能为空，否则就会抛NullPointerException异常，但是value可以为空
• Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)
• Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)
• Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入

TreeMap和HashMap的区别

Map底层结构	TreeMap	HashMap
底层结构	红黑树	哈希桶
插入/删除/查找时间复杂度		O(1)
是否有序	关于Key有序	无序
线程安全	不安全	不安全
插入/删除/查找区别	需要进行元素比较	通过哈希函数计算哈希地址
比较与覆写	key必须能够比较，否则会抛出ClassCastException异常	自定义类型需要覆写equals和hashCode方法
应用场景	需要Key有序场景下	Key是否有序不关心，需要更高的时间性能

import java.util.TreeMap;
import java.util.Map;
    public static void TestMap1(){
        Map<String, String> m = new TreeMap<>();
        // put(key, value):插入key-value的键值对
        // 如果key不存在，会将key-value的键值对插入到map中,返回null
        m.put("林冲", "豹子头");
        m.put("鲁智深", "花和尚");
        m.put("武松", "行者");
        m.put("宋江", "及时雨");
        String str = m.put("李逵", "黑旋风");
        System.out.println(m.size());
        System.out.println(m);
        // put(key,value): 注意key不能为空，但是value可以为空
        // key如果为空，会抛出空指针异常
        //m.put(null, "花名");
        str = m.put("无名", null);
        System.out.println(m.size());
        // put(key, value):
        // 如果key存在，会使用value替换原来key所对应的value，返回旧value
        str = m.put("李逵", "铁牛");
        // get(key): 返回key所对应的value
        // 如果key存在，返回key所对应的value
        // 如果key不存在，返回null
        System.out.println(m.get("鲁智深"));
        System.out.println(m.get("史进"));
        //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在,返回一个默认值
        System.out.println(m.getOrDefault("李逵", "铁牛"));
        System.out.println(m.getOrDefault("史进", "九纹龙"));
        System.out.println(m.size());
        //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
        // 按照红黑树的性质来进行查找
        // 找到返回true，否则返回false
        System.out.println(m.containsKey("林冲"));
        System.out.println(m.containsKey("史进"));
        // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
        // 因为TreeMap是按照Key进行组织的，因此查找value时候就需要整体遍历
        // 找到返回true，否则返回false
        System.out.println(m.containsValue("豹子头"));
        System.out.println(m.containsValue("九纹龙"));
        // 打印所有的key
        // keySet是将map中的key防止在Set中返回的
        for(String s : m.keySet()){
            System.out.print(s + " " );
        }
        System.out.println();
        // 打印所有的value
        // values()是将map中的value放在collect的一个集合中返回的
        for(String s : m.values()){
            System.out.print(s + " ");
       }
        System.out.println();
        // 打印所有的键值对
        // entrySet(): 将Map中的键值对放在Set中返回了
        for(Map.Entry<String, String> entry : m.entrySet()){
            System.out.println(entry.getKey() + "--->" + entry.getValue());
       }
        System.out.println();
   }

Set

注意：
1. Set是继承自Collection的一个接口类
2. Set中只存储了key，并且要求key一定要唯一
3. Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7. Set中不能插入null的key。