数组不足的地方
长度开始时必须指定，而且一旦指定不能更改
保存的必须为同一类型的元素
使用数组进行增加元素的示意代码–比较麻烦
写出Person数组扩容示意代码
Person[] per = new Person[1];
per[0] = new Person();
增加新的Person对象
Person[] per2 = new Person[per.length + 1];//创建新数组
for(){}//拷贝per数组的元素到per2
per2[per2.length - 1] = new Person();//添加新的对象
集合
可以动态保存任意多个对象，使用起来比较方便提供了一系列方便的操作对象的方法：add/remove/get/set等使用集合添加，删除元素的示意代码–简介了 集合框架体系
主要分为两大类
Collection(单列集合)
list
arrayListlinkedListvector Set
HashSetTreeSet
Map（双列集合）
HashMapTreeMapHashTableProperties
package com.lyn.collection_;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Collection_ {
public static void main(String[] args) {
//一、集合主要是两组（单列集合，双列集合）
// Collection：接口有两个重要的子接口，List,Set，他们的实现子类都是单列集合
// Map：接口的实现子类是双列集合，存放的K-V
List list = new ArrayList();
list.add("jack");
list.add("tom");
Map hashMap = new HashMap();
hashMap.put("a", "b");
hashMap.put("c", "d");
}
}
Collection接口和常用方法
collection接口实现类的特点
- collection实现子类可以存放多个元素，每个元素可以是object有些collection的实现类，可以存放重复的元素，有些不可以有些collection的实现类，有些是有序的（List），有些不是有序（Set）Collection接口没有直接的实现子类，是通过它的子接口set和list来实现的
基本介绍
Iterator对象称为迭代器，主要用于遍历Collection集合中的元素
所有实现了Collection接口的集合类都有一个Iterator()方法，用于返回一个实现了Iterator接口的对象，即可以返回一个迭代器
Iterator的结构
Iterator iterator = coll.Iterator();//用于得到一个集合的迭代器
hasNext();用于判断是否还有下一个元素
while(iterator.hasNext()){
//next();①指针下移 ② 将下移以后集合位置上的元素返回
iterator.next();
}
注意：在调用it.next()方法之前必须要调用it.hasNext进行检测，若不调用，且下一条记录无效，直接调用会抛出异常
Iterator仅用于遍历集合，Iterator本身并不存放对象
Collection接口遍历对象方式2-for循环增强
增强for循环，可以代替iterator迭代器，特点：增强for就是简化版的iterator，本质一样，只能用于遍历集合或数组
基本语法
for(元素类型 元素名 : 集合名或数组名){
访问元素
}
List接口和常用方法
List接口基本介绍（List接口是Collection接口的子接口）
List集合类中元素有序（即添加顺序和取出顺序一致）、且可重复
List集合中的每个元素都有其对应的顺序索引，即支持索引
List容器中的元素都有对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素
package com.lyn.collection_;
import java.util.ArrayList;
import java.util.List;
public class List_ {
public static void main(String[] args) {
//List集合类中元素有序（即添加顺序和取出顺序一致）、且可重复
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
System.out.println("list=" + list);
//List集合中的每个元素都有其对应的顺序索引，即支持索引
System.out.println(list.get(3));
}
}
List接口的常用方法
void add（int index,Object ele）；在index位置插入ele元素boolean addAllObject getint indexOf(Object obj);返回obj在集合中首次出现的位置int lastIndexOf返回末次出现的位置Object removeObject setList subList
ArrayList得注意事项
permits all elements, including null, ArrayList可以加入null，并且多个
ArrayList是由数组来实现数据存储得
ArrayList基本等同于Vector，除了ArrayList是线程不安全（执行效率高）看源码。在多线程情况下，不建议使用ArrayList
//ArrayList是线程不安全得，可以看源码，没有synchronized
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ArrayList底层结构和源码分析（重点，难点）
ArrayList中维护了一个Object类型得数组elementData
transient Object[] elementData;//transient表示瞬间，短暂得，表示该属性不会被序列化
当创建对象时，如果使用得是无参构造器，则初始elementData容量为0（jdk7是10）
当添加元素时，先判断是否需要扩容，如果需要扩容，则调用grow方法，否则直接添加元素到合适位置
如果使用得是无参构造器，如果第一次添加，需要扩容得话，则扩容elementData为10，如果需要再次扩容得话，则扩容elementData为1.5倍
如果使用得是指定容量capacity得构造器，则初始elementData容量为capacity
如果使用得是指定容量capacity得构造器，如果需要扩容，则直接扩容elementData为1.5倍
package com.lyn.collection_;
import java.util.ArrayList;
import java.util.List;
public class ArrayListSource {
public static void main(String[] args) {
//使用无参构造器创建对象
List list = new ArrayList();
// List list = new ArrayList(8);
//使用for给list集合添加0~9数据
for (int i = 0; i < 10; i++) {
list.add(i);
}
//使用for给list集合添加9~15数据
for (int i = 9; i < 16; i++) {
list.add(i);
}
list.add(100);
list.add(200);
list.add(null);
}
}
Vector底层结构和源码
Vector得基本介绍
Vector类得定义说明
public class Vectorextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
Vector底层也是一个对象数组， protected Object[] elementData
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
Vector是线程同步得，即线程安全， Vector类得操作方法带有synchronized
在开发中，需要线程同步安全时，考虑使用Vector
Vector 底层结构和ArrayList得比较
Vector 和ArrayList得比较
| 底层结构 | 版本 | 线程安全（同步）效率 | 扩容倍数 | |
|---|---|---|---|---|
| ArrayList | 可变数组 | jdk1.2 | 不安全，效率高 | 如果有参构造1.5倍 如果无参构造 一、第一次10 二、第二次以及后开始按照1.5扩容 |
| Vector | 可变数组 | jdk1.0 | 安全，效率不高 | 如果是无参，默认10，满后，就按2倍扩容 如果指定大小，则每次直接按2倍扩容 |
linkedList得全面说明
linkedList实现了双向链表和双端队列特点可以添加任意元素（元素可以重复），包括null线程不安全，没有实现同步
linkedList得底层操作机制
linkedList底层维护了一个双向链表
linkedList中维护了两个属性first和last分别指向首节点和尾节点
每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表
所以linkedList得元素得添加和删除，不是通过数组完成得，相对来说效率较高
模拟一个简单得双向链表
package com.lyn.collection_;
public class linkedList01 {
public static void main(String[] args) {
//模拟一个简单得双向链表
Node test = new Node("test");
Node tom = new Node("tom");
Node jack = new Node("jack");
//连接三个节点，形成双向链表
test.next = tom;
tom.next = jack;
jack.pre = tom;
tom.pre = test;
Node first = test;//让first引用指向test，就是双向链表得头节点
Node last = jack;//让last引用指向jack，就是双向链表得尾节点
//演示从头到尾进行遍历
while (true) {
if (first == null) {
break;
}
//输出first信息
System.out.println(first);
first = first.next;
}
//演示从尾到头遍历
while (true) {
if (last == null) {
break;
}
//输出first信息
System.out.println(last);
last = last.pre;
}
}
}
class Node {
public Object item;//真正存放数据得地方
public Node next;//指向下一个节点
public Node pre;//指向上一个节点
public Node(Object name) {
this.item = name;
}
@Override
public String toString() {
return "Node Name=" + item;
}
}
ArrayList和linkedList比较
| 底层结构 | 增删得效率 | 改查得效率 | |
|---|---|---|---|
| ArrayList | 可变数组 | 较低 数组扩容 | 较高 |
| linkedList | 双向链表 | 较高 通过链表追加 | 较低 |
如何选择ArrayList和linkedList
如果我们改查得操作多，选择ArrayList如果我们增删得操作多，选择linkedList一般来说，在程序中，80%~90%都是查询，因此大部分情况下会选择ArrayList在一个项目中，根据业务灵活选择，也可能这样，一个模块使用得是ArrayList,另一个模块是linkedList Set接口和常用方法
无序（添加和取出得顺序不一致），没有索引不允许重复元素，所以最多包含一个nullSet接口得常用方法
和List一样 Set接口得遍历方式
同Collection得遍历方式一样，因为set接口是Collection接口得子接口
可以使用迭代器增强for不能使用索引得方式来获取 Set接口实现类–HashSet
实现了Set接口
HashSet实际上是HashMap
public HashSet() {
map = new HashMap<>();
}
可以存放null值，但是只能有一个null
HashSet不保证元素是有序得，取决于Hash后，在确定索引得结果
不能有重复元素/对象
HashSet底层机制说明
分析HashSet底层是HashMap,HashMap底层是（数组+链表+红黑树）
package com.lyn.collection_;
public class HashSetStructure {
public static void main(String[] args) {
//模拟一个HashSet底层（HashMap得底层结构）
//一、创建一个数组，数组得类型是Node1[]
//二、有些人，直接把Node[]数组称为表
Node1[] table = new Node1[16];
System.out.println("table=" + table);
//三、创建节点
Node1 john = new Node1("john", null);
table[2] = john;
Node1 jack = new Node1("jack", null);
john.next = jack;//将jack节点挂载到john
Node1 rose = new Node1("rose", null);
jack.next = rose;//将rose节点挂载到jack
System.out.println("table=" + table);
}
}
class Node1 {//节点，存储数据，可以指向下一个节点，从而形成链表
Object item;//存放数据
Node1 next; //指向下一个节点
public Node1(Object item, Node1 next) {
this.item = item;
this.next = next;
}
}
分析HashSet得添加元素底层是如何实现得（Hash() + equals）
HashSet底层是HashMap添加一个元素时，先得到hash值，会转成索引值找到存储数据表table，看这个索引位置是否存放得有元素如果没有，直接加入如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则添加到最后在java8中，如果一条链表得元素个数到TREEIFY_THRESHOLD（默认是8），并且table得大小大于等于MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）
HashSet源码解读
一、执行HashSet()
public HashSet() {
map = new HashMap<>();
}
二、执行add()
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
三、执行put()，该方法会执行hash(key)得到key对应得hash值，算法(h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//key：值，value：private static final Object PRESENT = new Object(); 共享，占位作用
return putVal(hash(key), key, value, false, true);
}
四、执行putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;//定义了辅助变量
//table就是HashMap得一个数组，类型是Node[]
//if语句表示如果当前table是null，或者大小等于0，就是第一次扩容，到16个空间
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据key得到hash值去极化该key应该存放到table表得那个索引位置，并且把这个位置得对象，赋给p
//判断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 e; K k;
//如果当前索引位置对应得链表得第一个元素和准备添加得key得hash值一样
//并且满足，下面两个条件之一
//准备加入得key和p指向得Node节点得key是同一个对象
//p指向得Node节点得key得equals()和准备加入得key比较后相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//在判断p是不是一颗红黑树
//如果是一颗红黑树，就调用putTreeval，来进行添加
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
else {
//如果table对应得索引位置，已经是一个链表，就使用for循环比较
//一、依次和该链表得每一个元素比较后，都不相同，则加入到该链表得最后
// 注意在把元素添加到链表后，立即判断该链表是否已经达到八个节点
// ，如果达到，就调用treeifyBin(tab, hash);对当前这个链表进行树化（转成红黑树）
// 注意：在转成红黑树时，要进行判断，if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY（64）)resize();，如果条件成立，先table扩容，只有条件不成立时，才进行转成红黑树
//二、依次和该链表得每一个元素比较过程中，如果有相同情况，就直接break
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//size就是我们每加入一个节点Node(K,V,H,NEXT)
if (++size > threshold)
resize();//扩容
afterNodeInsertion(evict);
return null;
}
HashSet底层机制说明
HashSet底层时HashMap,第一次添加时，table数组扩容到16，临界值（threshold）时16×加载因子（loadFactor）是0.75=12如果table数组使用到了临界值12，就会扩容到16×2 =32，新的临界值就是32×0.75=24，依此类推在java8中，如果一条链表得元素个数到达TREEIFY_THRESHOLD(默认是8)，并且table得大小 >= MIN_TREEIFY_CAPACITY(默认是64)，就会进行树化（红黑树），否则仍然采用数组扩容机制 linkedHashSet
linkedHashSet得全面说明
linkedHashSet是HashSet得子类linkedHashSet底层是一个linkedHashMap，底层维护了一个数组+双向链表linkedHashSet根据元素得hashCode值来决定元素得存储位置，同时使用链表维护元素得次序，这使得元素看起来是以插入顺序保存得linkedHashSet不允许添重复元素 Map接口和常用方法（注意：这里讲的是JDK8得Map接口特点）
Map与Collection并列存在，用于保存具有映射关系得数据，key–value
Map中得key与value可以是任何引用类型得数据，会封装到HashMap$Node对象中
Map中得key不允许重复，原因和HashSet一样
Map中得value可以重复
Map得key可以为null，value也可以为null，注意key为null，只能有一个，value为null，可以多个
常用String类作为Map得key
key和value之间存在单项一对一关系，即通过指定key总能找到对应得value
package com.lyn.collection_;
import java.util.HashMap;
import java.util.Map;
public class Map_ {
public static void main(String[] args) {
Map map = new HashMap();
map.put("no1", "no1");//k-v
map.put("no2", "no2");//k-v
map.put("no2", "no3");//当有相同得k，就等价于替换
map.put("no3", "no3");
map.put(null, null);
map.put(null, "no4");//等价替换
map.put("no4", null);
map.put("no5", null);
System.out.println(map);
}
}
Map接口得特点
一对k-v是放在一个Node中为了方便程序员得遍历，还会创建EntrySet集合，该集合存放得元素得类型Entry，而一个Entry对象就有K–V EntrySet Map接口常用方法 put：添加remove：删除get：根据键获取值size：获取元素个数isEmpty：判断个数是否为0clear：清楚containsKey：查找键是否存在 Map接口遍历方法 containsKey：查找键是否存在 keySet：获取所有得键 entrySet：获取所有得关系 values：获取所有得值 存放得元素是键值对：即 K-VHashTable得键值对都不能为nullHashTable使用方法基本上和HashMap一样HashTable是线程安全得，hashMap是线程不安全得底层
底层有数组 HashTable$Entry[] 初始化大小为11临界值 threshold（8） = 11 * 0.75扩容：按照自己得扩容机制来进行扩容即可执行 方法 addEmtry 添加K-V 封装到Entry当if(count >= threshold)满足时，就进行扩容按照 int newCapacity = (oldCapacity << 1) + 1;得大小扩容
HashMap和HashTable对比
基本介绍
Properties类继承自HashTable类并实现了Map接口，也是使用一种键值对得形式来保存数据他的使用特点和HashTable类似Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象并进行读取和修改说明：xxx.properties文件通常作为配置文件
总结：开发中如何选择集合实现类（记住）
在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下 先判断存储得类型（一组对象(单列)或一组键值对（双列）） 一组对象：Collection接口 一组键值对：Mappackage com.lyn.collection_;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class Map_ {
public static void main(String[] args) {
Map map = new HashMap();
map.put("no1", "no1");
map.put("no2", "no2");
map.put("no3", "no3");
map.put(null, null);
map.put("no4", null);
map.put("no5", null);
//第一组：先取出所有得key，通过key取出对应得value
Set keySet = map.keySet();
//一、增强for
System.out.println("------第一种方式-----");
for (Object key : keySet) {
System.out.println(key + "_" + map.get(key));
}
//二、迭代器
System.out.println("------第二种方式-----");
Iterator it = keySet.iterator();
while (it.hasNext()) {
Object key = it.next();
System.out.println(key + "_" + map.get(key));
}
//第二组：把所有得value取出
Collection values = map.values();
//这里可以使用所有得Collection使用得遍历方式
for (Object value : values) {
System.out.println(value);
}
Iterator iterator = values.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
//第三组：通过entrySet来获取k--v
Set entrySet = map.entrySet();//EntrySet
HashMap小结
Map接口得常用实现类：HashMap、HashTable和PropertiesHashMap是Map接口使用频率最高得实现类HashMap是以K-V对得方式来存储数据key不能重复，但是值可以重复，允许使用null键和null值如果添加相同得key，则会覆盖原来得K-V，等同于修改与HashSet一样，不保证映射得顺序，因为底层是以hash表得方式来存储得HashMap没有实现同步，因此是线程不安全得
HashTable得基本介绍
Properties
版本 线程安全（同步） 效率 允许null键null值 HashMap 1.2 不安全 高 允许 HashTable 1.0 安全 较低 不允许
允许重复：List
增删多：linkedList(底层维护了一个双向链表)改查多：ArrayList（底层维护Object类型得可变数组）
不允许重复：Set
无序：HashSet（底层是HashMap，维护了一个哈希表，即【数组+链表+红黑树】）排序：TreeSet插入和取出顺序一致：linkedHashSet，维护数组+双向链表
键无序：HashMap键排序：TreeMap键插入和取出顺序一致：linkedHashMap读取文件Properties
package com.lyn.collection_;
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSet_ {
public static void main(String[] args) {
// TreeSet treeSet = new TreeSet();
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return (((String) o1).compareTo((String) o2));
}
});
//添加数据
treeSet.add("jack");
treeSet.add("tom");
treeSet.add("ss");
treeSet.add("a");
}
}
