map和set--天然的搜索和查找语义

二分搜索树BST：TreeSet/TreeMap

哈希表：HashSet/HashMap

set	存储不重复的key值，使用set集合来进行去重处理
map	存储的是key = value键值对，根据key找到对应的value

一、map分类 

在hashMap中，元素的插入顺序和保存顺序无关。

若需要插入顺序和保存顺序相同，使用LinkedMap.

 1.在hashMap中，如果key相同，重复赋值，最后一次相当于更新操作

 2.hashMap中，key值不同的情况下，value可以不相同

 3.hashMap的key和value都可以为空。

   Treemap的key不能为空，否则会出现空指针异常

 总结：

	hashMap	TreeMap	LinkedHashMap
结构	基于哈希表+红黑树的结构	基于红黑树	在hashMap基础上违和了一个链表
保存顺序和元素插入顺序有关吗	无关	无关	有关，按照插入顺序
key和value可以为null吗	都可以	key不可以，value可以	都可以
使用时		元素必须是comparable子类

二、set集合：去重

遍历set集合，直接使用for - each循环即可

只要是Iterble接口的子类，都可以直接使用for-each循环来遍历。

遍历map集合的时候，需要将map 转为set进行for-each遍历。

for(Map.entry<具体类型>entry :entry.entrySet())

---

1.== 和equals的区别：

==比较两者的值是否相等

若比较的是两个基本类型，就是他们保存的数值是否一样。

若比较的是两个引用类型，引用类型保存的值就是一个地址而已。

equals方法用于比较两个对象是否想等，此时是否相等的条件就需要我们用户自定义。

2.comparable和compator有啥区别？

当一个类实现了comparable接口，说明该类具备了可比较的能力，类的本身具备可比较能力。

compator是当一个类不能进行比较时，我们另外写的一个方法用来比较它们，例如：

JDK的优先级队列，PriorityQueue传入的类本身实现了comparable接口 ->Freq或者传入一个比较器，

PriorityQueue<Freq>qu1  = new PriorityQueue<>():

PriorityQueue<FreqTwo> qu2 = new PriorityQueue<>(new FreqTwoDesc());

---

看到只输出一次，一般使用set

set和list有啥区别呢？set不能包含重复元素

---

二分搜索树：（一般不考虑值相等的情况，元素不重复）

1.是个二叉树（每个节点最多有两个结点）

2.对于这颗树中的结点的结点值，左子树的所有节点值<根节点<右子树的所有结点值

判断二分搜索树：对该树进行中序遍历，就可以得到一个升序集合。

对二分搜索树进行元素的查找过程实际上就是一个二分查找 （logN）->二分搜索树BST

看到logN联想到 “树”。

BST中新添加的元素一定添加到了叶子结点。

public void add(int val){
        root = add(root,val);
    }

    public TreeNode add(TreeNode root, int val){
        //向以root为根的BST中插入一个新的结点val
        //创建新节点
        TreeNode newNode = new  TreeNode(val);
        if(root == null){
            //当前的值就是要插入的根节点
            size++;
            return newNode;
        }
        if(val < root.val){
            //在左树插入
            root.left = add(root.left ,val);
        }else{
            //此时是大于根节点的情况
            root.right = add(root.right,val);
        }
        return root;
    }