Map和Set

Map 是一个接口类，该类没有继承自 Collection ，该类中存储的是 <K,V> 结构的键值对，并且 K 一定是唯一的，不能重复 。

 map.put(1,"hello");
 map.put(2,"world");
 
//结果：{1=hello, 2=world}

map.get(1)；
 
//结果：hello

String str=map.getOrDefault(2,"hi");
String str1=map.getOrDefault(3,"hi");
 
//结果：
//str  world  
//str1 hi

map.remove(1);
System.out.println(map);
 
//结果：{2=world}

 map.put(1,"hi");
 map.put(2,"thanks");
 map.put(2,"what");
 map.put(3,"how");
 System.out.println(map.keySet());
 
//结果：[1, 2, 3]

map.put(1,"hi");
map.put(2,"thanks");
map.put(3,"how");
for(Map.Entry<Integer, String> entry : map.entrySet()){
        System.out.println(entry.getKey() + "--->" + entry.getValue());
   }
   System.out.println();
 
//结果：
1--->hi
2--->thanks
3--->how

     boolean containsValue (Object value)   //判断是否包含 value

 map.put(1,"hi");
 map.put(2,"thanks");
 map.put(3,"how");
 map.containsKey(1);//true
 map.containsKey(5);//false
 map.containsValue("hi");//true
 map.containsValue("hello");//false

1. Map 是一个接口，不能直接实例化对象 ，如果 要实例化对象只能实例化其实现类 TreeMap 或者 HashMap 。

3. 在 Map 中插入键值对时， key 不能为空，否则就会抛 NullPointerException 异常 ，但是 value可以为空 。

6. Map中键值对的 Key 不能直接修改， value 可以修改，如果要修改 key ，只能先将该 key删除掉，然后再来进行 重新插入。

Set 与 Map 主要的不同有两点： Set 是继承自 Collection 的接口类， Set 中只存储了 Key 。

      Set<Integer> set=new HashSet<>();
      set.add(1);
      set.add(2);
      set.add(3);
      boolean flg=set.add(1);
      System.out.println(flg);
      System.out.println(set);
 
//结果
//false
//[1, 2, 3]

2、boolean contains(Object o)   //判断 o 是否在集合中

      boolean flg=set.contains(1);//true
      boolean flg1=set.contains(6);//false

3、Iterator<E> iterator()   //返回迭代器

      set.add(1);
      set.add(2);
      set.add(3);
      Iterator it= set.iterator();
      while(it.hasNext()){
        System.out.print(it.next()+" ");
      }
 
//结果：1  2  3

4、boolean remove(Object o)  //删除集合中的 o

      set.add(1);
      set.add(2);
      set.add(3);
      boolean flg2=set.remove(1);
      System.out.println(flg2);//true
      System.out.println(set);//[2, 3]

5、int size()  //返回set中元素的个数

      set.add(1);
      set.add(2);
      set.add(3);
      System.out.println(set.size());//3

6、boolean isEmpty()   //检测set是否为空，空返回true，否则返回false

7、Object[] toArray()   //将set中的元素转换为数组返回

      Set<Object> set1=new HashSet<>();
      Object[] array1=set1.toArray();
 
      Set<Integer> set2=new HashSet<>();//指定类型
      Integer[] array=set2.toArray(new Integer[0]);
 

5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础 上维护了一个双向链表来记录元素的插入次序。

🌲例题

1、在1_0000个数据里面找重复的数据

public  static Map<Integer,Integer> func(int[] array){
        //判断array中的元素是否在map中，如果不在就是1，如果在就在原来的基础上加1
        Map<Integer,Integer> map=new HashMap<>();
        for(int x:array){
            if(map.get(x)==null){
                map.put(x,1);
            }else{
                int val=map.get(x);
                map.put(x,val+1);
            }
        }
        return map;
    }
 
    public static void main(String[] args) {
        int[] array=new int[10000];
        Random random=new Random();
        for(int i=0;i< array.length;i++){
            array[i]=random.nextInt(1000);//生成的随机数在0-1000之间，一定有重复的元素
        }
        Map<Integer,Integer> map=func(array);
        System.out.println(map);
        String str="array";
        System.out.println(str.toCharArray());
    }

2、将10000个数据去重

 public static Set<Integer> func(int[] array){
        Set<Integer> set=new HashSet<>();
        for (int x:array) {
            set.add(x);
        }
        return set;
    }
 
 public static void main(String[] args) {
        int[] array=new int[10000];
        Random random=new Random();
        for (int i = 0; i < array.length; i++) {
            array[i]=random.nextInt(1000);
        }
        Set<Integer> set=func(array);
        System.out.println(set);
       int ret=func1(array);
        System.out.println(ret);
    }

🥬二叉搜索树

 🍌查找

 在二叉搜索树中查找某个值key，就用key和根节点比较，key更大，在右子树查找，key更小，在左子树查找。

代码示例：

    public Node search(int key){
      Node cur=root;
      while(cur!=null){
          if(key>cur.val){
              cur=cur.right;
          }else if(key<cur.val){
              cur=cur.left;
          }else{
              return cur;
          }
      }
      return null;//没找到
    }

🍌插入

在二叉搜索树中插入某个结点，要不破坏它的性质，所以要先找到合适插入的位置，然后再插入

   public boolean insert(int val){
       //空树情况下
        if(root==null){
            root=new Node(val);
            return true;
        }
 
       //找到要插入的位置      
        Node cur=root;
        Node parent=null;//记录父节点
        while(cur!=null) {
            if (val > cur.val) {
                parent = cur;
                cur = cur.right;
            } else if (val < cur.val) {
                parent = cur;
                cur = cur.left;
            } else {
                return false;//不能有相同数据
            }
        }
 
        //插入
            Node tmp=new Node(val);
            if(val<parent.val){
                parent.left=tmp;
            }else{
                parent.right=tmp;
            }
        return true;
    }

🍌删除

删除二叉搜索树中某个结点，先找到要删除的位置，在进行删除

 代码示例：

  public void remove(int key){
      Node cur=root;
      Node parent=null;
      //找到要删除结点位置
        while(cur!=null){
          if(cur.val==key){
              removeNode(cur,parent);
              break;
          }else if(cur.val<key){
              parent=cur;
              cur=cur.right;
          }else{
              parent=cur;
              cur=cur.left;
          }
        }
    }
  
  //删除
  public void removeNode(Node cur,Node parent){
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }else if(cur==parent.right){
                parent.right=cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=root.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }else if(cur==parent.right){
                parent.right=cur.left;
            }
        }else{
            //右数找最小值，左数找最大值
            Node targetParent=cur;
            Node target=cur.right;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            //找到了右树最小值
            cur.val=target.val;
            if(target==targetParent.left){
                targetParent.left=target.right;
            }else{
                targetParent.right=target.left;
            }
        }
    }

🥬哈希表

理想的搜索方法：可以 不经过任何比较，一次直接从表中得到要搜索的元素。  如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

该方式即为哈希( 散列 ) 方法， 哈希方法中使用的转换函数称为哈希 ( 散列 ) 函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

 🍌哈希冲突

我们可以看到4和14通过相同哈希函数找到了相同的位置，发生了冲突。

此时不同的关键字通过相同的哈希函数有可能找到相同的位置。此时的情况就叫: 哈希冲突/哈希碰撞。

🍌避免冲突