java day09
集合
- 可以动态保存任意多个对象，使用比较方便
- 提供了一系列方便的操作对象的方法：add、remove、set、get等
- 使用集合添加，删除新元素的示意代码
Collection
体系图
Collection接口和常用方法
接口实现类的特点
public interface Collection extends Iterable
- Collection实现子类可以存放多个元素，每个元素可以是Object
- 有些Collection的实现类，可以存放重复的元素，有些不可以
- 有些Collection的实现类，是有序的（list）,有些不是有序（Set）
- Collection接口没有直接的实现子类，是通过它的子接口Set和List来实现的
常用方法：
- add:添加单个元素
- remove:删除指定元素
- contains:查找元素是否存在
- size:获取元素个数
- isEmpty:判断是否为空
- clear：清空
- addAll:添加多个元素
- containsAll:查找多个元素是否存在
- removeAll：删除多个元素
Iterator接口的方法
- hasNext():判断是否还有下一个元素
- newt(): 1下移、2将下移以后集合位置上的元素返回
- remove():移除
注意：调用next()方法之前必须调用hasNext()进行检测，否则遇到无效记录将抛出异常
// 集合主要是两组（单列集合、双列集合）
// Collection 接口有两个重要子接口 List Set,他们实现子类都是单列集合
Collection col = new ArrayList();
col.add(new Book("三国","罗贯中"));
col.add(new Book("红楼","曹雪芹"));
System.out.println(col);
/***************************遍历方式一 while***************************/
// Iterator遍历col集合
Iterator iterator = col.iterator();
while(iterator.hasNext()){ //先判断是否还有数据
Object next = iterator.next(); //返回object类型数据
System.out.println(next);
}
// 当迭代器推出while，此时iterator指向最后元素
// 若再次遍历需要重置迭代器
iterator = col.iterator();//二次遍历
while(iterator.hasNext()){ //先判断是否还有数据
Object next2 = iterator.next(); //返回object类型数据
System.out.println(next2);
}
/****************************遍历方式二 for***************************/
// 增强for循环
for(Object book : col){
System.out.println(book);
}
// Book类
class Book类(){
private String name;
private String author;
public Book(String name,String author){
this.name = name;
this.author = author;
}
}
List接口
List接口是Collection接口的子接口
- List集合类种元素有序
- List集合中的每个元素都有其对应的顺序索引
- List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可根据序号存取容器中的元素
List list = new ArrayList();
list.add("jack");
list.add("tom");
list.add("tom"); //可重复
System.out.println(list); //添加顺序和取出顺序一致
System.out.println(list.get(1));//支持索引取出
List常用方法：
/*******************************常用方法***********************/
List list = new ArrayList(); // new Vector() , new LinkedList()效果一样
list.add("jack");
list.add("tom");
//在索引1的位置插入
list.add(1,"zs");//不加1，默认追加在最后
List list2 = new ArrayList();
list2.add("jack2");
list2.add("tom2");
list2.addAll(1,list);//[jack2,jack,tom,zs,tom2]
list.indexof("tom");// 1 ,第一次出现的位置
list.lastIndexof("tom");//最后一次出现位置
list.remove(0);//移除
list.set(1,"mali");//替换，索引必须存在
list.subList(0,2);//返回0到1的位置子集合，[0，2)
/***********************三种遍历方式****************************/
//方式一 迭代
Iterator iterator = list.iterator();
while(iterator.hasNext()){
Object next = iterator.next();
System.out.println(next);
}
//方式二 增强for
for(Object o : list){
System.out.println(o);
}
//方式三 普通for
for(int i= 0;i<list.length;i++){
System.out.println(list.get(i));
}
ArrayList
ArrayList说明
- ArrayList 可以加入null，并且多个
- ArrayList 是由数组来实现数据存储的
- ArrayList 基本等同Vector，除了ArrayList是线程不安全（执行效率高），多线程下不建议使用
ArrayList arrayList = new ArrayList();
arrayList.add(null);
arrayList.add("d");
arrayList.add(null);
System.out.print(arrayList);//[null,d,null]
ArrayList底层结构
- ArrayList中维护了一个Object类型的数组elementData
- 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如需再次扩容，则扩容elementData为1.5倍
- 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍
- 使用的是无参构造器时底层结构 :
Vector
Vector底层是一个对象数组，线程同步，Vector类的操作方法带有synchronized
Vector vector = new Vector();//无参构造
for(int i=0;i<10;i++){
vector.add(i);
}
Vector vector = new Vector(8);//有参构造
for(int i=0;i<10;i++){
vector.add(i);
}
其他与无参相同
LinkedList
LinkedList说明
- LinkedList实现了双向链表和双端队列特点
- 可以添加任意元素（元素可以重复），包括null
- 线程不安全，没有实现同步
LinkedList底层结构
- LinkedList底层维护了一个双向链表
- LinkedList中维护了两个属性frist和last分别指向首节点和尾节点
- 每个节点（node对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表
- LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
//源码
/*
1、LinkedList linkedList = new LinkedList();
public LinkedList(){}
2、这时 linkedList 的属性 first = null last=null
3、执行add
public boolean add(E e){
linkLast(e);
return true;
}
4、执行linkLast(e),将新节点，加入到双向链表的最后;
void linkLast(E e){
final Node<E> l = last;
final Node<E> newNode = new Node<>(l,e,null);
last = newNode;
if(l == null){
first = newNode;
}else{
l.next = newNode;
}
size++;
modCount++;
}
*/
linkedList.remove();//默认删除第一个
/**源码
1、执行
public E remove{
return removeFirst();
}
public E removeFirst{
final Node<E> f = first;
if(f == null){
throw new NoSuchElementException();
}
return unlinkFirst(f);
}
2、执行删除 unlinkFirst(f)
public E unlinkFirst<Node<E> f>{
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null;
first = next;
if(next == null){
last = null;
}else{
next.prev = null;
}
size--;
modCount++;
return element;
}
*/
linkedList.set(1,8); //修改
linkedList.get(1);//获取
//循环参考List,..........
Set接口
Set接口基本介绍
- 无序，没有索引
- 不允许重复元素，最多只有一个null
- 常用实现类用：HashSet、TreeSet
Set接口常用方法
和List接口一样，Set也是Collection的子接口，因此常用方法与Collection接口基本一致（没有get()方法，因为没有索引），接口遍历方式也一样
// set 接口实现类 HashSet
Set set = new HashSet(); // new TreeSet();
// 注意 取出的顺序不是添加的顺序，但是它是固定的
HashSet
HashSet说明
- HashSet实现了Set接口
- HashSet实际上是HashMap
- 可以存放null值，但只能有一个
- HashSet 不保证元素是有序的，取决于hash后，再确定索引的结果
- 不能有重复元素/对象
// Set hashSet = new HashSet();
HashSet hashSet = new HashSet();
hashSet.add(null);//只能有一个，在执行add方法后，就会返回一个Boolean值
hashSet = new HashSet();
//不能有重复元素/对象？
hashSet.add("cy");//添加成功
hashSet.add("cy");//加入不了
hashSet.add(new Dag("tm"));//可以加入
hashSet.add(new Dag("tm"));//可以加入
//加深
hashSet.add(new String("tom")); // ok
hashSet.add(new String("tom")); // 加入不了，底层机制
System.out.print(hashSet);
// 定义一个dog类
class Dog{
private String name;
public Dog(String name){
this.name = name;
}
}
HashSet底层机制
- HashSet底层机制是HashMap，HashMap的底层是HashSet （数组+链表+红黑树）
- 添加一个元素时，先得到hash值，会转成 ，索引值
- 找到存储数据表table，看这个索引位置是否已经存放的元素
- 若没有，直接加入
- 若有，调用equals比较，若相同，就放弃添加，若不同则添加在最后
- 在Java8中，若一条链表的元素个数 >= TREEIFY_THRESHOLD(默认8)，并且table的大小 >= MIN_TREEIFY_CAPACITY（默认64）就会进行树化（红黑树）
//创建一个数组，数组类型是Node[]
Node[] table = new Node[16];
// 创建节点
Node john = new Node("john",null);
table[2] = john;
john.next = jack;
Node jack = new Node("jack",null);
john.next = jack;//将jack 挂载到john
Node rose = new Node("rose",null);
jack.next = rose;//将rose挂载到jack
Node lc = new Node("lc",null);
table[3] = lc
/Node类
class Node{ //节点存储数据，可以指向下一个节点，从而形成链表
Object item;//存储数据
Node next; //指向下一个节点
public Node(Object item, Node next){
this.item= item;
this.next = next;
}
}
//源码解读
HashSet hashSet = new HashSet();
hashSet.add("cy");
hashSet.add("php");
hashSet.add("cy");
//1、执行 HashSet();
public HashSet(){ map = new HashMap<>(); }
//2、执行add()
public boolean add(E e){
return map.put(e,PRESENT) == null; //(static)PRESENT = new Object()
}
//3、执行put(),会执行hash(key)
public V put(K key,V value){ // key = "cy" value = PRESENT
return putVal(hash(key),key,value,false,false)
}
//4、hash(key),得到对应key的hash值 算法(h=key.hashCode())^(h>>>16)
static final int hash(Object key){
int h;
return (key == null) ?0:(h=key.hashCode())^(h>>>16);
}
//5、执行putVal()
final V putVal(int hash, K key, V value,boolean onlyIfAbsent,boolean evict){
Node<K,V>[] tab; Node<K,V> p; int n,i; //定义辅助变量
// table 就是HashMap的一个数组，类型Node[]
// 若table是null，或者 大小 = 0 ，就是第一次扩容，到16个空间
if((tab = table) == null ||(n = tab.length) == 0){
n = (tab = resize()).length; // resize()
}
// 根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
// 并且把这个位置的对象，赋给 p
// 判断 p 是否为空，若空表示未存放数据，就创建一个node
// 存放tab[i] = newNode(hash,key,value,null);
if((p = tab[i=(n-1) & hash]) == null){
tab[i] = newNode(hash,key,value,null);
}else{
Node<K,V> e; K k; //定义辅助变量
// 若当前索引位置对应链表对应第一个元素和准备添加的key的hash一样
// 并且满足，以下两个条件就不能加入：
// (1)准备加入的key和p 指向的Node节点的key是同一个对象
// (2)p指向的node节点的key的equals 和准备加入的key内容相同
if(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
}else if(p instanceof TreeNode){
//再判断p是不是一颗红黑树
//如果是，就调用putTreeVal(),进行添加
e = ((TreeNode<K,v>p)).putTreeVal(this,tab,hash,key,value);
}else{
//若当前table对应索引位置，已经是一个链表，就是用for循环比较
for(int binCount = 0;;++binCount){
//依次和该链表的每一个元素比较后，都不相同，就挂载该链表的最后
if((e = p.next) == null){
p.next = newNode(hash,key,value,null);
// 元素添加到链表后，立即判断该链表是否已经达到8个节点
// 就调用treeifyBin(),对当前链表进行树化（红黑树）
// 在转红黑树时，进行判断，
// if(tab == null ||(n= tab.length) < MIN_TREEIFY_CAPACITY){resize()}
// 成立就扩容，否则才进行红黑树
if(binCount >= TREEIFY_THRESHOLD -1){
treeifyBin(tab,hash);
}
break;
}
//比较过程中有相同，就直接break
if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
}
if(e != null){
V oldValue = e.value;
if(!onlyIfAbsent || oldValue == null){
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// size 就是每加入一个节点node，size就会++
if(++size > threshold){
resize();
}
afterNodeInsertion(evict);
return null;
}
/*
HashSet底层机制是HashMap，第一次添加时，table 数组扩容到16 ，
临界值是 16 * 加载因子（loadfactor）0.75 = 12
如果table 数组使用到了临界值 12 ，就会扩容到 16 *2 =32，新的
临界值就是 32 * 0.75 =24，依次类推
*/
LinkedHashSet
- LinkedHashSet 继承了HashSet ;
- LinkedHashSet 底层是一个LinkedHashMap， 底层维护了一个数组 + 双向链表
- LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序（图），使得元素看起来是以插入顺序保存的
- LinkedHashSet 不允许重复元素
Set set = new LinkedHashSet();
set.add(new String("AA"));
set.add(456);
set.add(456);
set.add("HSP");
/*
在 LinkedHashSet 中维护了一个hash表和双向链表（LinkedHashSet有head 和 tail）
每一个节点有 before 和 after 属性，这样可以形成双向链表
在添加一个元素时，先求hash值，在求索引，确定该元素在table的位置，然后将元素加入到双向链表（如果已经存在，不添加）
遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致
*/
// 添加第一次时，直接将数组table扩容到16 ，存放的节点类型LinkedHashMap$Entry
// 数组是 HashMap$Node[] 存放的元素/数据是LinkedHashMap$Entry类型
/*
// 继承关系是在内部类完成
static class Entry<K,V> extends HashMap.Node<K,V>{
Entry<K,V> before , after;
Entry<int hash, K key, V value, Node<K,V> next){
super(hash,key,value,next);
}
}
*/
版权声明：本文为MrGeng原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。