Java学习记录8 容器
1. 容器架构介绍
容器
数组就是一种容器，可以在其中放置对象或基本数据类型。
Set没有顺序不可重复，list有顺序可以重复。
数组的优劣势
优势：是一种简单的线性序列，可以快速的访问数组元素，效率高。从效率和类型检查的角度讲，数组是最好的。
劣势：不灵活。容量事先定义好，不能随着需求的变化而扩容。
2. 泛型概念-自定义泛型
泛型是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]; }}
3. Collection接口
Collection表示一组对象，他是集中、收集的意思。Collection接口的两个子接口是List、Set接口。
ArrayList的常用方法，set和list方法一致
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
LinkedList底层用双向链表实现的存储。
特点查询效率低，增删效率高，线程不安全。
双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。所以，从双向链表中的任意一个节点开始，都可以很方便的找到所有节点。
每个节点有3部分内容
class Node{ Node previous; //前一个节点 Object element; //本节点保存的数据 Node next;//后一个节点 }手工实现LinkedList(暂时不做)
Vector向量
底层是用数组实现的List，相关方法都加了同步检查，因此线程安全，效率低。比如indexOf方法就增加了synchronized同步标记。
需要线程安全用Vector，对象需要多个线程共享时使用。
不存在线程安全问题时，并且查找较多用ArrayList（一般使用）。
不存在线程安全问题时，增删元素较多用LinkedList。
4. map接口
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