1. 对Map和Set的理解

2. Map的使用

编辑

2.1 Map的常用方法

2.2 TreeMap和HashMap的区别

3. Set的使用

3.1 Set的常用方法

3.2 练习一下

3.3 TreeSet和HashSet的区别

4.二叉搜索树（Binary Search Tree）

4.1 概念

4.2 二叉搜索树 — 查找

4.3 二叉搜索树 — 插入（重点）

4.4 二叉搜索树 — 删除（难点）

5. 哈希表

5.1 哈希表的理解

5.2 哈希冲突

5.3 哈希冲突降低之哈希函数设计

5.4 哈希冲突降低之负载因子调节

5.5 哈希表冲突解决之闭散列

5.6 哈希表冲突解决之开散列

1. 对Map和Set的理解

（1）概念

Map和Set是一种专门用来进行搜索的容器或者数据结构，它的搜索效率与其具体的实例化例子有关。

Map和Set是动态查找相比较与静态查找（比如直接查找。二分查找等），其优点是可以在查找过程中对区间进行一些插入和删除的操作。

（2）模型

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

1. 纯 key 模型：Set中存储的就是key

比如查找某本书中是否有一个名词

2. Key-Value模型：Map中存储的就是key-value的键值对

比如统计某本书中某几个名词出现的次数

2. Map的使用

方法	作用
V get(Object key)	返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)	返回 key 对应的 value ， key 不存在，返回默认值
V put(K key, V value)	设置 key 对应的 value
V remove(Object key)	删除 key 对应的映射关系
Set<K> keySet()	返回所有 key 的不重复集合
Collection<V> values()	返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()	返回所有的 key-value 映射关系
boolean containsKey(Object key)	判断是否包含 key
boolean containsValue(Object value)	判断是否包含 value

2.1 Map的常用方法

这里用Map实现TreeMap的接口

（1）put（key，value）方法 设置 key 对应的 value

给里面放key一定要是可以比较类型，并且不能为null

如果放入同样的key，那就会覆盖之前的key的value

 public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        System.out.println(map1);
    }

Map里面重写了toString直接打印map1，可以看到打印出来的顺序，和输入的顺序是不一样的

这是因为TreeMap底层是一个搜索树，给搜索树中插入是需要比较大小的，同key来比较大小

这里最需要注意的是，如果插入自定义类型。那么自定义类型一定要是可以比较的，并且不能为null，不然会报错

还需要注意的是

    public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        map1.put("javase",66);
        System.out.println(map1);
    }

如果放入同样的key，那就会覆盖之前的key的value

（2）get（key）与getOrDefault（key，value）方法

打印key-value 和设置默认的key-value

public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        System.out.println(map1.get("javase"));
        System.out.println(map1.get("c++"));
        System.out.println(map1.getOrDefault("c++",45));
    }

get能够将put放入的key和Value都打印出来，如果没有就打印null

getOrDefault能够能够设置一个默认的key的value，如果之前没有put这个默认的key，那就打印出这个key和设置的value

如果之前有

（3）remove （key）删除 key 对应的映射关系

    public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        map1.remove("javaee");
        System.out.println(map1);
    }

（4）Set<K> keySet() 返回所有 key 的不重复集合

public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        Set<String> set = map1.keySet();
        System.out.println(set);
    }

（5）Collection<V> values() 返回所有 value 的可重复集合

 public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        Collection<Integer> collection= map1.values();
        System.out.println(collection);
    }

（6）Set<Map.Entry<K, V>> entrySet() 返回所有的 key-value 映射关系

 public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);

        Set<Map.Entry<String,Integer>> entrySet = map1.entrySet();
        for (Map.Entry<String,Integer> entry : entrySet) {
            System.out.println("key: " + entry.getKey() +
                    " val: " + entry.getValue());
        }
    }

2.2 TreeMap和HashMap的区别

1.Map是一个接口，不能直接实例化对象（要实例化对象可以实现类TreeMap或HashMap）

2.Map中存放键值对的key是唯一的，value是可以重复一样的

3.Map中key可以全部分离开，存储在Set中去进行访问（因为key不可以重复）

4.Map中value可以全部分离开，存储在Collection的任何一个子集合中（value可以重复）

5.Map中key不能直接修改，如果必须修改就要先删除key，在进行重新插入

6.HashMap的存储是根据底层的哈希函数和key，去找对应的位置的，

所以HashMap不是根据存储顺序打印的，而是根据一些映射关系等存储的，那么HashMap也可以存储null

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

3. Set的使用

TreeSet当中存储的元素，必须是可以比较的

方法	作用
boolean add(E e)	添加元素，但重复元素不会被添加成功
void clear()	清空集合
boolean contains(Object o)	判断 o 是否在集合中
Iterator<E> iterator()	返回迭代器
boolean remove(Object o)	删除集合中的 o

3.1 Set的常用方法

boolean add(key) 添加元素，但重复元素不会被添加成功

所以Set用在去掉重复的情况下

TreeSet中存储的元素必须是可以比较的

public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("qwe");
        set.add("asd");
        set.add("qwe");
        System.out.println(set);
    }

并且实现了SortedSet的接口，所以TreeSet中存储的元素必须是可以比较的

而且

其他方法和map使用方法类似

3.2 练习一下

1.现在有100w个数据，要把这100w个数据中重复的元素删除掉

可以直接存储在set中，因为set中存储元素是将元素去重之后存储的
public static void fun1(int[] array) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }
2.现在有100w个数据，要把这100w个数据中第一个重复的数据找出来

将元素给集合中存储，每次存储判断一下，集合中有没有，要是有就返回这个数字
 public static int fun2(int[] array) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(!set.contains(array[i])) {
                set.add(array[i]);
            }else {
                return array[i];
            }
        }
        System.out.println(set);
        return -1;
    }
3.现在有100w个数据，要把这100w个数据中每个数据出现的次数打印出来

将元素给集合中存储，先看key有没有，要是没有就存储key，value为1,；如果集合中有key，那就给value加1
 public static void fun3(int[] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
           int key = array[i];
           if(map.get(key) == null) {
               map.put(key,1);
           }else {
               int val = map.get(key);
               map.put(key, val + 1);
           }
        }
    }

3.3 TreeSet和HashSet的区别

1.Set继承于Collection的接口类

2.Set只存储key，并且key唯一

3.Set底层是Map实现的，其使用key于Object的一个默认对象作为键值对插入到map中、

4.Set的功能最重要的是集合中元素去重

5.Set中不能插入为null的key

6.Set中key不能修改，如必须修改，先删除，在重新插入

底层结构上的区别和Map类似

4.二叉搜索树（Binary Search Tree）

4.1 概念

二叉搜索树（二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）它的左、右子树也分别为二叉搜索树。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势

主要用于，在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作

前面都是比较正式的概念，我的理解二叉搜索树给它中序遍历他是顺序递增的

4.2 二叉搜索树 — 查找

先根据二叉搜索树写出它的结构

 static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

然后分析一下它的查找方法

 /**
     * @param key:
     * @return 找到了返回地址，没找到返回null
     * @description 查找key是否存在于二叉搜索树中
     */
    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < key) {
                cur = cur.right;
            }else if(cur.val > key) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

4.3 二叉搜索树 — 插入（重点）

 /**
     * @param key:
     * @return boolean
     * @description 插入
     */
    public boolean insert(int key) {
        //将k变成一个节点（万一树为空，那么插入这个节点，树中就有key的这个节点了）
        TreeNode node = new TreeNode(key);
        if(root == null) {
            root = node;
            return true;
        }
        TreeNode cur = root;
        //parent记录cur的父亲结点
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
            }else {
                //存在相同的元素不能插入成功
                return false;
            }
        }
        //cur一直走到最后cur为null
        if(parent.val < key) {
            parent.right = node;
        }else {
           parent.left = node;
        }
        return true;
    }

4.4 二叉搜索树 — 删除（难点）

和前面查找的步骤一样，看根节点是不是，然后进入到左右子树中去寻找所要删除的结点

下面分析一下要删除结点，会遇到的情况

（1）下面先分析一下，要删除结点如果一边为null，一边不为null的情况

（2）下面分析一下，两边都不为空的情况

将上面所有的删除情况写为一个方法

 /**
     * @param cur: 删除结点
     * @param parent:删除结点的父结点
     * @description 进行删除
     */
    private void removeNode(TreeNode cur, TreeNode parent) {
        if(cur.left == null) {
            if(cur == root) {
                root = root.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if (cur == root) {
                root = root.left;
            }else if(cur == cur.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(targetParent.left == target){
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

调用上面的删除方法

 /**
     * @param key:
     * @return void
     * @description 删除关键字为key的结点
     */
    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
            }else {
                //找到了，开始删除
                removeNode(cur,parent);
                return;
            }
        }
    }