lantingyue 2020-05-31
数组就是一种容器,可以在其中放置对象或基本数据类型。
Set没有顺序不可重复,list有顺序可以重复。
优势:是一种简单的线性序列,可以快速的访问数组元素,效率高。从效率和类型检查的角度讲,数组是最好的。
劣势:不灵活。容量事先定义好,不能随着需求的变化而扩容。
泛型是JDK1.5以后增加的,它可以帮助我们建立类型安全的集合。
相当于容器的标签。
泛型的本质就是数据类型的参数化,可以理解为占位符(形式参数),即告诉编译器,在调用泛型时必须传入实际类型。
一般用T,E,V三个
容器相关类都定义了泛型。
要导入:java.util.List
public static void main(String[] args) { MyCollection<String> mc = new MyCollection<String>(); mc.set("cdj", 0); mc.set("8888", 1); String a = mc.get(1); String b = mc.get(0); System.out.println(a); System.out.println(b); }?class MyCollection<E>{//MyCollection<String> mc = new MyCollection<String>();这里是啥类型,E就是啥类型 Object[] objs = new Object[5]; public void set(E e,int index){ objs[index] = e; } public E get(int index){ return (E)objs[index]; }}
Collection表示一组对象,他是集中、收集的意思。Collection接口的两个子接口是List、Set接口。
Collection<String> c = new ArrayList<String>(); System.out.println(c.size());//内容的大小 System.out.println(c.isEmpty());//判断容器是否为空 c.add("cdj");//容器添加元素 c.add("cdj2"); System.out.println(c);//默认toString System.out.println(c.size()); System.out.println(c.contains("cdj"));//判断容器中是否包含某个字符串 Object[] objs = c.toArray();//返回一个object数组 System.out.println(objs); c.remove("cdj2");//从容器中移除元素,并不是删除这个对象,但是这个对象还在 System.out.println(c); c.clear();//移除所有的元素 System.out.println(c);
ArrayList操作多个List-并集和交集
List<String> list01 = new ArrayList<String>(); list01.add("aa"); list01.add("bb"); list01.add("cc"); List<String> list02 = new ArrayList<String>(); list02.add("aa");// list02.add("dd");// list02.add("ee"); System.out.println("list01:"+list01); //把list02中所有的元素都放到了list01中了 //list01.addAll(list02); //把list01中与list02中的相同的元素去掉了 //list01.removeAll(list02); //把list01中与list02中的不同的元素去掉了 list01.retainAll(list02); System.out.println("list01:"+list01); //判断list01是否包含list02,是true,不是false System.out.println(list01.containsAll(list02));
ArrayList索引和顺序相关方法
List是有序、可重复的容器。
有序:List中每个元素都有索引标记,可以根据元素的索引标记(在List中的位置)访问元素,从而精确控制这些元素。
可重复:List允许加入重复的元素。List通常允许满足e1.equals(e2)的元素重复加入容器。
List接口常用的实现类有3个:ArrayList、LinkedList和Vector。
ArrayList底层是数组,LinkedList底层是链表,Vector的底层是数组,线程安全。
List<String> list = new ArrayList<String>(); list.add("A"); list.add("B"); list.add("C"); list.add("D"); //索引是从0开始的 System.out.println(list); //往索引为2的位置插入一个元素 list.add(2, "cdj"); System.out.println(list); //删除索引位置的元素 list.remove(2); System.out.println(list); //修改指定索引位置的元素 list.set(2, "cdj"); System.out.println(list); //获取指定索引位置处元素 System.out.println(list.get(2)); //返回指定元素第一次索引位置,查找不到返回-1 list.add("C"); list.add("B"); list.add("A"); System.out.println(list); System.out.println(list.indexOf("B")); System.out.println(list.indexOf("1B")); //返回指定元素最后一次索引位置,查找不到返回-1 System.out.println(list.lastIndexOf("B")); System.out.println(list.lastIndexOf("B1"));
ArrayList底层源码分析
ArrayList底层是用数组实现的存储。
特点:查询效率高,增删效率低,线程不安全。一般使用。
数组长度是有限的,而ArrayList是可以存放任意数量的对象,长度不受限制,采用数组扩容(定义一个更大的数组,把原内容拷贝到这个数组)的方式实现。
手工实现ArrayList:(暂时不做)
LinkedList底层用双向链表实现的存储。
特点查询效率低,增删效率高,线程不安全。
双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向前一个节点和后一个节点。所以,从双向链表中的任意一个节点开始,都可以很方便的找到所有节点。
每个节点有3部分内容
class Node{ Node previous; //前一个节点 Object element; //本节点保存的数据 Node next;//后一个节点 }
手工实现LinkedList(暂时不做)
底层是用数组实现的List,相关方法都加了同步检查,因此线程安全,效率低。比如indexOf方法就增加了synchronized同步标记。
需要线程安全用Vector,对象需要多个线程共享时使用。
不存在线程安全问题时,并且查找较多用ArrayList(一般使用)。
不存在线程安全问题时,增删元素较多用LinkedList。
Map就是用来存储“键-值对”的。
Map类中存储的“键值对”通过键来标识,所以“键对象”不能重复。
Map接口的实现类有HashMap、TreeMap、HashTable、Properties等。
Map接口常用方法:
Map<Integer,String> m1 = new HashMap<Integer,String>(); //添加元素 m1.put(1, "one"); m1.put(2, "two"); m1.put(3, "three"); //获取元素 System.out.println(m1.get(1)); //m1的大小 System.out.println(m1.size()); //判断m1是否为空 System.out.println(m1.isEmpty()); //判断m1中是否包含键值 System.out.println(m1.containsKey(1)); //判断m1中是否包含Value值 System.out.println(m1.containsValue("one")); Map<Integer,String> m2 = new HashMap<Integer,String>(); m2.put(4, "四"); m2.put(5, "五"); //把m2加入m1中 m1.putAll(m2); System.out.println(m1); //map中键不能重复,如果重复(是否重复是根据equals方法来判断的),则新的覆盖旧的。 m1.put(3, "三"); System.out.println(m1);
HashMap的底层原理-存储键值对底层过程
HashMap底层实现采用了哈希表,这是一种非常重要的数据结构。
哈希表的基本结构就是“数组+链表”。
Entry[] table 是HashMap的核心数组结构,称为位桶数组,JDK1.8位Node
一个Entry对象存储了:
key:键对象 value:值对象
next:下一个节点
hash:键对象的hash值
每一个Entry对象就是一个单向链表结构。
数组默认出始大小为16:0-15。
存储数据过程put(key,value):核心是如何产生hash值,该值用来对应数组的存储位置。
将“key-value两个对象”成对存放到HashMap的Entry[]数组中的步骤:
获得key对象的hashcode
首先调用key对象的hashcode()方法,获得hashcode。
根据hashcode计算出hash值(要求在[0,数组长度-1]区间)
hashcode是一个整数,我们需要将它转换成[0,数组长度-1]的范围。要求转化后的hash值尽量均匀的分布在0-1之间,减少“hash冲突”。
一种极端简单和低下的算法:hash值 = hashcode/hashcode 。hash值总是1。意味着,键值对象都会存储到数组索引1位置,这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”,HashMap也退化成了一个链表。
一种简单和常用的算法(相除取余算法):hash值 = hashcode%数组长度,可以让hash值均匀分布在0-1之间,早期的HashTable就是采用这种算法。
改进算法:hash值 = hashcode&(数组长度-1)
JDK1.8以后,长度大于8的,链表变成红黑树。
查找键值对过程:
获得key的hashcode,通过hash()散列算法得到hash值,进而定位到数组的位置。
在链表上挨个比较key对象。调用equals()方法,将key对象和链表上所有节点的key对象进行比较,直到碰到返回true的节点对象为止。
返回equals()为true的节点对象的value对象。
注:hashcode()和equals方法的关系:Java规定,两个内容相同(equals()为true)的对象必须具有相等的hashCode。因为如果equals()为true而两个对象的hashcode不同,那在整个存储过程中就发生了悖论。
扩容问题:位桶数组出始大小为16,实际使用时,大小可变。如果数组中的元素达到(0.75*数组 length),就重新调整数组大小变为原来2倍大小。扩容很耗时。扩容的本质是定义新的更大的数组,并将旧数组内容挨个拷贝到新数组中。
public static void main(String[] args) { Employee e1 = new Employee(1001, "cdj", 50000); Employee e2 = new Employee(1002, "cdj1", 5000); Employee e3 = new Employee(1003, "cdj2", 60000); Employee e4 = new Employee(1001, "cdj3", 6000); Map<Integer,Employee> map = new HashMap<>(); map.put(1001, e1); map.put(1002, e2); map.put(1003, e3); map.put(1001, e4); Employee emp = map.get(1001); System.out.println(emp.getEname()); System.out.println(map); }?class Employee{ private int id; private String ename; private double salary; public Employee(int id, String ename, double salary) { super(); this.id = id; this.ename = ename; this.salary = salary; } @Override public String toString() { return "id:"+id+"name:"+ename+"薪水:"+salary; } public int getId() { return id; } public void setId(int id) { this.id = id; } public