2020.7.29(Map, 빠른 정렬)

수업 전 복습: 1. 집합 프레임워크의 흔한 인터페이스와 그 특성의 흔한 인터페이스:collection,List,Set,Map collection: 무질서,중복가능List: 질서,중복가능Set: 무질서,중복불가Map: 키 값 대2, 집합 프레임워크의 흔한 실현 유형과 특징Array List: 밑층은 수조로 요소와 변화 값을 옮겨다니며 더욱 빠른Linked List: 밑층은 양방향 체인표, 삽입,더 빠른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는 거의 차이가 없다.리스트 집합 유일한 루트 안전한 집합 클래스 Concurrent Linked List: 루트 안전한 체인 테이블 Set 인터페이스: Linked Hash Set: 순서가 있는 Hash Set, 다음 표시로 맵 인터페이스를 지정할 수 있습니다: Concurrent Hash Map 루트가 안전한 Hash Map, 그리고 정렬화된 Hash Table와 차이점: Hash Table의 모든 데이터가 잠겨 있습니다. 만약에 한 루트가 특정한 데이터에 접근한다면다른 사람들은 모든 데이터에 접근할 수 없습니다.모든 데이터 세그먼트에 잠금을 어떻게 해결하는지 집합 중의 라인 안전 문제를 해결하는지 라인 안전 집합을 사용합니다!!다중 스레드가 없는 상황에서 집합류를 사용합니다!!map은 k-v 키 값이 비치는 데이터에 대한 하위 클래스를 저장합니다:HashMap: 데이터 + 체인 테이블 (1.7) 그룹 + 체인 테이블 + 붉은 나무 (1.8) 링크드 HashMap: 체인 테이블 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 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     
    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
        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;
            }
        }
    }
}