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
上一篇: NIO例子
下一篇: 李智慧 - 架构师训练营 第一周