目录
1、数组缺点
1.1、数组一旦初始化就不可以修改
1.2、数组中提供的方法的方法有限，效率低。
1.3、数据特点只能是有序可重复
2、Collection接口
单列数据，存储一组对象的方法的集合
- add(Object obj) addAll(Collection coll) 添加
- int size() 获取有效元素的个数
- void clear() 清空集合
- boolean isEmpty() 是否是空集合
- boolean contains(Object obj) boolean containsAll(Collection c) 是否是空集合
- boolean remove(Object obj) boolean removeAll(Collection coll) 删除
- boolean retainAll(Collection c) 取两个集合的交集
- boolean equals(Object obj) 集合是否相等
- Object[] toArray() 转成对象数组
- hashCode() 获取集合对象的哈希值
- iterator() 返回迭代器对象，用于集合遍历
2.1.1、List
有序可以重复的集合
2.1.1.1、ArrayList
底层结构Object[]数组、查询快、增删慢、不安全
// 源码分析:jdk7中
ArrayList list = new ArrayList(); // 底层创建长度为10的Object[] elementData数组
list.add("123"); // 向数组中添加元素
....
list.add("56"); // 如果添加元素导致数组容量不够则进行扩容
// 扩容机制：扩容为原来的1.5倍,同时将原来数组中的数据复制到新的数组中
// 注意：如果知道当前集合的大小，建议使用带参构造器
ArrayList list = new ArrayList(int capaticy) //提高扩容效率
// 源码分析:jdk8中
ArrayList list = new ArrayList(); //底层Object[] elementData初始化为{},没有创建长度为10的数组
list.add("123"); // 第一次add()时才创建长度为为10的数组,并添加当前元素。
// 后续操作与jdk类似2.1.1.2、LinkedList
底层结构双向链表、查询慢、增删快、不安全
// 源码分析
LinkedList linkedList = new LinkedList(); // 内部声明Node类型的first和last属性,默认值为null
linkedList.add(123); // 创建node对象并添加数据
// Node定义
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2.1.1.3、Vector
a、底层结构Object[]数组、查询慢、增删慢、安全(Synchronized修饰)
b、 jdk7和jdk8中通过Vector()构造器创建对象时，数组长度都为10。扩容默 认为原来2倍
2.1.2、List 常用方法
除了Collection中的方法，本身特有方法
- void add(int index, Object ele): 在index 位置插入ele
- boolean addAll(int index, Collection eles): 从index 位置开始将eles中所有元素添加进来
- Object get(int index): 获取指定index
- int indexOf(Object obj): 返回obj 在集合中首次出现的位置
- int lastIndexOf(Object obj): 返回obj 在当前集合中末次出现的位置
- Object remove(int index): 移除指定index 位置的元素，并返回此元素
- Object set(int index, Object ele): 设置指定index 位置的元素为ele
- List subList(int fromIndex, int toIndex): 返回从fromIndex 到toIndex位置的子集合
2.1.3、Set
无序不可以重复的集合
a、无序性：添加的时候元素位置无序，集合中的位置由元素的hashcode决定
b、不可重复性：先比较hashCode，如果不相等则直接添加，如果相等，再比较equals方法，如返回true，认为是同一对象，不添加，false则添加
2.1.3.1、HashSet
a、线程不安全，可以存储null值。底层hashmap(数组+链表)实现。
b、hashSet中的数据相当于hashMap中的key，value默认为Object对象
c、向Hashset中添加数据，其所在的类一定要重新equals()和hashCode()
2.1.3.2、LinkedHashSet
a、作为HashSet子类,。底层由LinkedList和HashMap维护
b、遍历数据时是按照添加的数据顺序有序遍历的。
既然是set的子类为什么会有序呢？
原因：set集合本身的无序性指的是添加元素存放数组位置无序，并非遍历的时候。而LinkedHashSet 添加数据的同时还维护了两个引用，记录前一个数据和后一个数据
2.1.3.3、TreeSet
a、底层是红黑树，有序，查询速度比list快
b、添加的数据要求是相同类的对象，会按照添加对象的属性进行排序
c、因为java中的对象默认只能进行 == 或者 != 进行比较。如果对对象进行排序则需要使用Comparable接口和Comparator接口
TreeSet treeSet= new TreeSet();
// 失败,不能添加不同类的对象(String类和Integer类)
treeSet.add(123);
treeSet.add("xhl");
// 自身会根据属性进行排序
treeSet.add(11);
treeSet.add(05);
treeSet.add(-12);
Iterator iterator = treeSet.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next()); // -12 5 11
}
// 如果对对象排序则需要使用Comparable或者Comparator进行排序,不然会报错。
// Comparable举例：User类需要实现Comparable接口，并重写compareTo方法进行排序
TreeSet treeSet1 = new TreeSet();
treeSet1.add(new User("zs",10));
treeSet1.add(new User("ls",20));
Iterator iterator1 = treeSet1.iterator();
while (iterator1.hasNext()) {
System.out.println(iterator1.next());
}2.1.4、集合遍历
public static void main(String[] args) {
Collection collection = new ArrayList();
collection.add("aaa");
collection.add(123);
/* 方式一 使用Iterator迭代器接口
注意点:
1、在调用it.next()方法之前必须要调用it.hasNext()进行检测。若不调用，且
下一条记录无效，直接调用it.next()会抛出NoSuchElementException异常
2、collection.iterator().hasNext()写法错误。集合对象每次调用iterator()方法都会
到一个新的迭代器对象，指向第一个元素之前，所以一直死循环遍历第一个元素
*/
Iterator iterator = collection.iterator();
//hasNext():判断是否还有下一个元素
while(iterator.hasNext()){
//next():①指针下移 ②将下移以后集合位置上的元素返回
System.out.println(iterator.next());
// 使用remove方法移除
/*if ("aaa".equals(iterator.next())) {
iterator.remove();
}*/
}
// 因为当前指针已经指向最后一个元素，所以需要重新获取当前集合
/* Iterator iterator1 = collection.iterator();
while (iterator1.hasNext()) {
System.out.println(iterator1.next());
}*/
// 方式二 使用foreach循环遍历
for (Object o : collection) {
System.out.println(o);
}
}3、Map接口
a、双列数据，具有映射关系的 key-value对的集合。
b、无序、key不可重复(添加时可以添加重复的key，只是值会覆盖)、value可以重复
3.1、HashMap
a、线程不安全、效率高、允许key或value为null
b、set存储key，key所在的类要重写equal()和hashcode()
HashMap源码分析
扩容：默认负载因子:0.75 默认初始长度:16 长度>16 × 0.75 会自动扩容(为原来的2倍)
/*
1、扩容为2的整数次幂原因:
1、太小影响扩容，太大浪费资源
2、可以为数组下标计算提供便利方式
2、负载因子0.75原因：
2.1、因为容量为2的幂，0.75×2的幂可以保证扩容长度为整数
2.2、负载因子越大,hash冲突概率越大。负载因子越小越浪费空间
3、初始化为16原因
数组下标=(table.length-1)&((h=key.hashCode())^(h >>> 16));table.length-1 = 16-1 =
1111(二进制);1111进行&操作可以保证计算后的下标既是奇数又是偶数,可以减少hash冲突
*/
jdk7：数组+单向链表(头插法)
// 实例化后,底层创建了长度为16的数组Entry[] table
HashMap hashMap = new HashMap();
/*
1、调用key所在类的hashcode()方法获取hash值,通过算法获取数组Entry[]存放位置。
如果key为null，则存在下标为0的位置
2、如果此位置的数据为空，则添加key-value到当前位置的Entry数组中
3、如果此位置的数据不为空。
3.1、如果key的hash值和存在数据的hash值不相同，则继续添加(使用链表方式(头插法))
3.2、如果key的hash值和存在数据的hash值相同
3.2.1、继续比较当前类key的equals(存在key)方法
3.2.1.1、如果equals()返回为false,继续添加(使用链表方式(头插法))
3.2.1.2、如果equals()返回为true,当前的value值替换原value值。
*/
hashMap.put(key,value);
jdk8：数组+单向链表(尾插法)+红黑树(链表长度>=8且数组长度>64)
如果<64可以扩容处理。如果链表长度<6,红黑树会转回链表
// 实例化后,底层没有创建长度为16的数组
HashMap hashMap = new HashMap();
// 首次调用put方法,底层创建长度为16的Node[] table数组。其它和jdk7类似
hashMap.put(key,value); 3.2、LinkedHashMap
保证变量map元素时，可以按照添加的顺序实现变量（适用于频繁的遍历操作）
3.3、Hashtable
线程安全(Sychornized)、效率低、不允许key或value为null
3.3.1、Properties
常用来处理配置文件。key和value都是String类型
Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);3.4、ConcurrentHashMap
线程安全、效率高。替代Hashtable
jdk7:
数据结构:ReentrantLock+Segment+HashEntry
1、ConcurrentHashMap使用分段锁计算,把数据分成n个段，每段都添加锁。
当其中一个线程占用锁访问其中一个段数据时,其它段的数据也能被其它线程访问。
2、定位一个元素的过程需要进行两次hash操作。第一次hash定位到Segment,
第二次定位到元素所在链表的头部
优点：写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment,并发能力提高
缺点：Hash的过程比普通的HashMap要长
jdk8:
数据结构:synchronized+CAS+HashEntry+红黑树
jdk8中彻底放弃了Segment转而采用的是Node。
Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性
优点：
1.取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构
2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自
ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁(Node)
4.链表转化为红黑树
5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。3.5、TreeMap
a、保证按照添加的key-value对进行排序，实现排序遍历。
b、对key的自然排序(Comparable接口)和定制排序(Comparator接口)。底层是红黑树
3.6、Map中常用的方法
添加、删除、修改操作：
Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key)：移除指定key的key-value对，并返回value
void clear()：清空当前map中的所有数据元素查询的操作：
Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：是否包含指定的key
boolean containsValue(Object value)：是否包含指定的value
int size()：返回map中key-value对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数对象obj是否相等原视图操作：
Set keySet()：返回所有key构成的Set集合
Collection values()：返回所有value构成的Collection集合
Set entrySet()：返回所有key-value对构成的Set集合Map map = new HashMap(); //map.put(..,..)省略 /*获取map的key或者value得到的是set/Collection,set是Collection的子类。 所以可以通过foreach或者Iterator遍历*/ Set keys = map.keySet();// HashSet for (Object key : keys) { System.out.println("key是：" + key + ", value是：" + map.get(key)); } Collection values = map.values(); Iterator iter = values.iterator(); while (iter.hasNext()) { System.out.println("value是:" + iter.next()); } // 映射关系的类型是Map.Entry类型，它是Map接口的内部接口 Set mappings = map.entrySet(); for (Object mapping : mappings) { Map.Entry entry = (Map.Entry) mapping; System.out.println("key是：" + entry.getKey() + ", value是：" + entry.getValue()); }
4、Collections
a、是一个操作 Set、List 和 Map 等集合的工具类
b、提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
排序操作：（均为static 方法）
reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换查找、替换
Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合 中的最大元素
Object min(Collection)
Object min(Collection，Comparator)
int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
void copy(List dest,List src)：将src中的内容复制到dest中
boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换List 对象所有旧值同步控制： 提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题
