2020.7.29（Map、快速排序）

课前复习：
1、集合框架常见接口及其特性
常见接口：collection、List、Set、Map
collection：无序、可重复
List：有序、可重复
Set：无序、不可重复
Map：键值对
2、集合框架常见实现类及特点
ArrayList：底层是数组，遍历元素和改变值更快
LinkedList：底层是双向链表，插入、删除更快
HashSet:底层是HashMap的键，使用键的hash值来保证唯一性
3、迭代器遍历的方式（写代码）、set和list
Iterator iterator = list.Iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
4、list和set如何实现元素的增删改查
增：add()
删：remove()
改：set(index,obj)
查：get(index)
set只有增，删
课堂笔记：
其他常用实现类：
List接口：Vector和ArrayList几乎没有差别，List集合唯一线程安全的集合类
ConcurrentLinkedList:线程安全的链式表
Set接口：LinkedHashSet:有顺序的HashSet，可以用下标指定
Map接口：ConcurrentHashMap线程安全的HashMap，并且还是序列化的
和HashTable的区别：HashTable所有数据都上锁，如果一个线程访问了某段数据，
其他人都不能访问所有数据。对所有数据分段上锁
如何解决集合当中线程安全的问题
使用线程安全的集合！！
不在多线程的情况下使用集合类！！
map存储的是k-v键值对映射的数据
实现子类：
HashMap：数据+链表（1.7） 数组+链表+红黑树（1.8）
LinkedHashMap：链表
TreeMap:红黑树

  基本api操作：
      增加：
          put（k,v）    添加元素
      查找：
          isEmpty      判断是否为空
          size        返回map的大小
          containsKey
          containsValue
          get
      删除：
          clear 清空集合中的所有元素
          remove:删除指定元素
 Map.entry:表示的是K-V组合的一组映射关系，key和value成组出现

 hashmap跟hashtable的区别：
  1、hashmap线程不安全，效率比较高，hashtable线程安全，效率低
  2、hashmap中key和value都可以为空,hashtable不允许为空


  hashmap初始值为2的N次幂，
      1、方便进行&操作，提高效率，&要比取模运算效率要高
          hash & (initCapacity-1)
      2、在扩容之后涉及到元素的迁移过程，迁移的时候只需要判断二进制的前一位是0或者是1即可
          如果是0，表示新数组和就数组的下标位置不变，如果是1，只需要将索引位置加上旧的数组的长度值即为新数组的下标
  1.7源码知识点：  数组+链表
      1、默认初始容量
      2、加载因子
      3、put操作
          1、设置值，计算hash
          2、扩容操作
          3、数据迁移的过程
  1.8源码知识点:   数组+链表+红黑树

TestMap:

package cn.kgc.kb09;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

/**
 * @Author: ChaoKeAiMuZhi
 * @Date: 2020/7/29 14:02
 * @Description:
 **/
public class TestMap {
    public static void main(String[] args) {
        HashMap map=new HashMap();
        //增加
        map.put("CN","中华人民共和国");
        map.put("UK","大不列颠联合王国");
        map.put("US","美利坚合众国");
        map.put("FU","大不列颠联合王国");
        System.out.println(map.get("FR"));//指向是空代表不存在
        //删
        /*map.remove("US");
        System.out.println(map.get("US"));
        map.remove("CN","ABC");
        System.out.println(map.get("CN"));*/
        map.containsKey("key");
        map.containsValue("value");
        //替换，改
        map.put("CN","中国");//最常用的就是put
        map.replace("CN","中国");//不常用
        //遍历的方式 map.entrySet()获取它的键值对，实际是一个Set
        /*Set entry = map.entrySet();//使用entrySet方法获取键值对的集合
        for (Object o : entry) {
            System.out.println(o);
        }*/
        //遍历key的方式
        Set keys = map.keySet();
        for (Object key : keys) {
            System.out.println(key+"："+map.get(key));
        }
        //通过迭代器实现遍历
        Iterator itr = keys.iterator();
        while (itr.hasNext()){
            System.out.println(itr.next());
        }
        //遍历value的方式，要注意value能不能重复的问题？可重复,纯粹打印出来的都是值
        //纯粹打印出来的都是值，但是没有对应，个别场景使用，不需要绑定的时候，只需要把值拿出来
        Collection values = map.values();
        for (Object value : values) {
            System.out.println(value);
        }


        System.out.println(map);//一样是可以打印出来结果，toString
        map.clear();
    }
}

Entry:

package cn.kgc.kb09;

/**
 * @Author: ChaoKeAiMuZhi
 * @Date: 2020/7/29 14:24
 * @Description:
 **/
public class Entry {
    Object key;
    Object value;

    public void put(Object key,Object value){
        this.key=key;
        this.value=value;
    }

    public Object get(Object key){
        return value;
    }

}

TestT:

package cn.kgc.kb09;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * @Author: ChaoKeAiMuZhi
 * @Date: 2020/7/29 14:57
 * @Description:
 **/
public class TestT {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        //list.add(1);
        list.add("ads");
        //list.add(new Entry());
        String s = list.get(0);
        for (String s1 : list) {
        }
        //泛型可以进行传递的
        Iterator<String> itr=list.iterator();
        while (itr.hasNext()){
            System.out.println(itr.next());
        }

        //在类上定义了这个T是可以影响到方法的，根据创建对象的实际类型
        //根据限定的入口，只能有一种体现，但主要还是在List Set Map中使用，本质是类型参数化
        //Dog<String> d=new Dog<>();
        //String test = d.getTest("abc");
    }
}

TestMap:

package cn.kgc.kb09;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @Author: ChaoKeAiMuZhi
 * @Date: 2020/7/29 15:04
 * @Description:
 **/
public class TestTMap {
    public static void main(String[] args) {
        HashMap<String,Entry> map=new HashMap<>();
        map.put("",new Entry());
        Set<Map.Entry<String,Entry>> entrys=map.entrySet();
        Set<String> keys=map.keySet();

        Collection<Entry> values=map.values();


    }

}

Dog:

package cn.kgc.kb09;

/**
 * @Author: ChaoKeAiMuZhi
 * @Date: 2020/7/29 15:08
 * @Description:比较特殊的泛型标记：
 * T:所有类+所有接口
 * E：所有元素（一般指所有Java本有类+接口）
 * K：键
 * V：值
 **/
public class Dog<T> implements Comparable<Dog>{

    int dogId;

    public Dog(int dogId) {
        this.dogId = dogId;
    }

    @Override
    public String toString() {
        return "Dog{" +
                "dogId=" + dogId +
                '}';
    }

    @Override
    public int compareTo(Dog o) {
        return this.dogId-o.dogId;
        //return -1;
    }

    //Dog<T>好处，可以自定义一些泛型方法，T作为返回值
    public T getTest(T t){
        return t;
    }
}

TestCollection:

package cn.kgc.kb09;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @Author: ChaoKeAiMuZhi
 * @Date: 2020/7/29 15:59
 * @Description:演示Collections类的工具方法
 **/
public class TestCollection {
    public static void main(String[] args) {
        //能用父类的所有方法，并能通过泛型去调用
        List list=new ArrayList();
        list.add("abc");
        list.add(123);
        list.add("hello");
        list.add(3.1415926);

        Collections.sort(list, new Comparator<Object>() {
            @Override
            public int compare(Object o1, Object o2) {
                return -1;
            }
        });
        System.out.println(list);

        List<Dog> dogList=new ArrayList<>();
        Dog d1=new Dog(1);
        Dog d2=new Dog(4);
        Dog d3=new Dog(3);
        Dog d4=new Dog(2);
        dogList.add(d1);
        dogList.add(d2);
        dogList.add(d3);
        dogList.add(d4);
        Collections.sort(dogList);
        System.out.println(dogList);

        Collections.shuffle(dogList);
        //复制内容， 不是复制地址
        //Collections.copy();
        //针对哪两个值进行交换
        //Collections.swap();

    }
}

QuickSort:

package cn.kgc.kb09.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @Author: ChaoKeAiMuZhi
 * @Date: 2020/7/29 16:28
 * @Description:
 **/
public class QuickSort {
    public static void quick(int[] a,int start,int end){
        //把首位定位标准位tmp
        int i=start,j=end;
        //i=start  j=end;
        //循环条件：i<j
        if(i>=j) return;
        int tmp=a[i];
        while (i<j){
            //循环内要有两个循环来重复i++和j--的过程
            while (a[j]>=tmp && i<j) j--;
            //不满足上一条循环条件的时候，则要进行对应赋值
            a[i]=a[j];
            //i++;
            while (a[i]<=tmp && i<j) i++;
            a[j]=a[i];
            //j--;
        }

        //出外层循环时，把标准位插入在i/j处
        a[i]=tmp;
        //递归调用（自己调自己）
        quick(a,start,i-1);
        quick(a,i+1,end);
    }

    public static int[] randomArray(int length){
        int[] a=new int[length];
        for (int i = 0; i < a.length; i++) {
            //随机数生成的方式
            Random r=new Random();
            a[i]=r.nextInt(1000000);
        }
        return a;
    }

    public static void main(String[] args) {
        int[] a=randomArray(1000000);
        //System.out.println(Arrays.toString(a));
        long now=System.currentTimeMillis();
        //maoPao(a);
        quick(a,0,a.length-1);
        //System.out.println(Arrays.toString(a));
        long used=System.currentTimeMillis()-now;
        System.out.println("花费："+used);


    }

    public static void maoPao(int[] a){
        for (int i = 0; i < a.length-1; i++) {
            boolean flag=false;
            for (int j = 0; j < a.length-i-1; j++) {
                if(a[j]>a[j+1]){
                    int tmp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=a[j];
                    flag=true;
                }
            }
            if(!flag){
                return;
            }
        }
    }
}

本文地址：https://blog.csdn.net/m0_48758256/article/details/107679295