欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020.7.29(Map、快速排序)

程序员文章站 2022-05-04 08:49:09
课前复习:1、集合框架常见接口及其特性常见接口:collection、List、Set、Mapcollection:无序、可重复List:有序、可重复Set:无序、不可重复Map:键值对2、集合框架常见实现类及特点ArrayList:底层是数组,遍历元素和改变值更快LinkedList:底层是双向链表,插入、删除更快HashSet:底层是HashMap的键,使用键的hash值来保证唯一性3、迭代器遍历的方式(写代码)、set和listIterator iterator = list....

课前复习:
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

相关标签: 笔记