JAVA 中常见的集合总结
使用集合的好处：
- 可以动态的保存任意多个对象，使用比较方便
- 提供了一些列方便的操作对象的方法：add, remove, set, get等
- 使用集合添加，删除元素的示意代码简洁明了
集合主要分为两种：
- 单列集合：集合中存放的是单个对象
- 双列集合：集合中存放的是键值对对象
Collection
Collection 集合的特点：
-
Collection的实现子类集合可以存放多个元素，每个元素可以是Object。
-
有些Collection实现的子类可以存放重复的元素，有些则不可以。
-
有些Collection实现的子类，有些是有序的（List），有些是无序的（Set）。
-
Collection接口没有直接的实现子类，是通过他的子接口Set接口和List接口实现的。
Collection 集合的常用方法，这里以ArrayList举例：
package com.cherry;
import java.util.*;
public class Collection_ {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
// add:添加元素
list.add("hello");
list.add("world");
list.add("cherry");
list.add("mitu");
list.add("outlook");
// 输出集合
System.out.println("list" + list);
// 删除指定元素
list.remove(0); // 根据索引删除
list.remove("cherry"); // 指定删除某个对象
System.out.println("list" + list);
// 查找某个元素是否存在
System.out.println("cherry是否存在集合中:" + list.contains("cherry"));
// 获取元素的个数(集合的大小)
System.out.println("list集合中的元素个数为:" + list.size());
// 判断集合当前是否为空
System.out.println("当掐集合是否为空:" + list.isEmpty());
// 清空集合
// list.clear();
// 添加爱多个元素
List list2 = new LinkedList<String>();
list2.add("sub1");
list2.add("sub2");
list2.add("sub3");
list.addAll(list2);
System.out.println("list:" + list);
// 判断多个元素是否存在
System.out.println("list是否包含list2的全部元素: " + list.containsAll(list2));
// 删除多个元素
list.removeAll(list2);
System.out.println("list:" + list);
}
}
Collection接口遍历元素的方式一：使用迭代器
-
Iterator对象成为迭代器，主要作用就是遍历迭代Collection集合中的元素。
-
所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了iterator接口的对象，即返回一个迭代器。
-
iterator仅用于遍历集合，iterator 本身不存放对象。
迭代器的执行原理：
Iterator iterator = collection.iterator(); // 得到一个集合的迭代器
hasNext(); // 判断是否还有下一个元素
while(iterator.hasNext()) {
Object o = next(); // 指针指向下一个元素，并将下移后的元素返回(o)
}
使用迭代器遍历集合的示例:
package com.cherry;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class CollectionIterator {
public static void main(String[] args) {
Collection<String> collection = new ArrayList<>();
collection.add("hello");
collection.add("world");
collection.add("cherry");
Iterator<String> iterator = collection.iterator();
while(iterator.hasNext()){
String str = iterator.next();
System.out.println(str);
}
}
}
hello
world
cherry
Process finished with exit code 0
当while循环推出后，如果继续使用iterator.next()，就会引发异常：NoSuchElementException，如果希望再次遍历该集合，需要重置迭代器，使用新的迭代器：iterator = collection.iterator();
Collection接口遍历元素的方式一：使用增强for循环
-
使用增强for循环，可以代替迭代器，其实就是简化版的迭代器，底层仍然是迭代器，本质上和迭代器是一样的。
-
基本语法：
for(元素类型 元素名 : 集合名或数组名){ 访问元素 }
如：
package com.cherry;
import java.util.ArrayList;
import java.util.Collection;
public class CollectionIterator2 {
public static void main(String[] args) {
Collection<String> collection = new ArrayList<>();
collection.add("hello");
collection.add("world");
collection.add("cherry");
for(String e:collection){
System.out.println(e);
}
}
}
List
List接口的基本介绍：
- List集合类中元素有序（即添加顺序和取出顺序是一致的），且可重复。
- List集合中的每个元素都有其对应的顺序索引，即支持索引，索引从0开始。
- List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
package com.cherry.list;
import java.util.ArrayList;
import java.util.List;
public class List_ {
public static void main(String[] args) {
List list = new ArrayList();
// List集合类中的元素有序（即添加顺序和取出顺序是一致的），且可重复
list.add("jack");
list.add("Tom");
list.add("cherry");
list.add("mitu");
list.add("cherry");
System.out.println("list= "+ list);
//List集合中的每个元素都有其对应的顺序索引，即支持索引
Object o = list.get(3);
System.out.println(o);
}
}
List接口中常用的方法：
package com.cherry.list;
import java.util.ArrayList;
import java.util.List;
public class ListMethod {
public static void main(String[] args) {
List list = new ArrayList();
// void add(int index, E element):在index位置处插入元素element
list.add("hello");
list.add("world");
list.add(1, "cherry");
System.out.println("list=" + list);
// boolean addAll(int index, Collection c):在index位置开始处将c集合中的元素加入进来
List list2 = new ArrayList();
list2.add("张三丰");
list2.add("灭绝师太");
list.addAll(2,list2);
System.out.println("list=" + list);
// list.get(int index):获取指定index位置的元素
// int indexOf(Object o);:返回obj在集合中首次出现的位置
int index = list.indexOf("灭绝师太");
System.out.println(index);
// int lastIndexOf(Object o):返回obj在集合中末次出现的位置
int lastIndex = list.lastIndexOf("world");
System.out.println(lastIndex);
// E remove(int index):移除指定index处的元素，并返回
Object removeElem = list.remove(2);
System.out.println(removeElem);
// E set(int index, E element);设置指定index位置处的元素为element
list.set(0,"newElement");
System.out.println("list=" + list);
// List<E> subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合(左闭右开原则)
// 返回的子集合 fromIndex <= subIndex < toIndex
List subList = list.subList(1, 3);
System.out.println("subList="+subList);
}
}
练习：
使用List的实现类添加几本书，要求价格实现从低到高排序（使用冒泡排序）并遍历输出：
package com.cherry.list;
import java.util.ArrayList;
import java.util.List;
public class ListExercise {
public static void main(String[] args) {
List<Book> list = new ArrayList<>();
list.add(new Book("红楼梦","曹雪芹",100));
list.add(new Book("西游记","吴承恩",10));
list.add(new Book("水浒传","施耐庵",80));
list.add(new Book("三国演义","罗贯中",90));
//对集合进行排序
sort(list);
System.out.println("排序后");
for(Book b:list){
System.out.println(b);
}
}
public static void sort(List list){
for (int i=0; i<list.size()-1;i++){
for(int j=0;j<list.size()-1-i;j++){
// 取出对象
Book book1 = (Book) list.get(j);
Book book2 = (Book) list.get(j+1);
if(book1.getPrice()>book2.getPrice()){
//进行交换
list.set(j, book2);
list.set(j+1, book1);
}
}
}
}
}
ArrayList
- ArrayList 的底层是由数组实现存储数据的。
- ArrayList基本上等同于Vector，ArrayList的执行效率比较高，但是线程不安全的，在多线程情况下不建议使用ArrayList，而是使用Vector，因为Vector是加了锁的。
首先做调试前的工作：
ArrayList底层源码分析
-
ArrayList底层维护了一个Object类型的数组elementData
transient Object[] elementData; //transient 瞬间的，短暂的，表示该属性不会被序列化 -
当创建ArrayList对象使用的是无参构造器时，则初始elementData数组的容量为0，第一次添加，则扩容elementData容量为10，如果需要再次扩容，则扩容elementData的1.5倍。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; private static final int DEFAULT_CAPACITY = 10; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 无参构造初始化ArrayList对象默认elementData容量为0 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 1. 首先是添加元素: private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); // 容量不够使用grow()方法扩容 elementData[s] = e; size = s + 1; } // 2. grow()方法 private Object[] grow() { return grow(size + 1); // 调用grow的有参构造方法 } // 3. grow的有参构造方法 private Object[] grow(int minCapacity) { // 调用数组复制方法,其中 newCapacity 为新数组的容量 return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity)); } // 4. newCapacity private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 新的容量为 = 旧容量 + （旧容量/2） int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity <= 0) { // 如果旧容量为0,则返回容量DEFAULT_CAPACITY为10： if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return minCapacity; } // 如果要申请的容量比最大容量 MAX_ARRAY_SIZE 还要大，则调用hugeCapacity()方法 return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity); } // 5. 调用hugeCapacity()方法,返回容量为 Integer.MAX_VALUE(2^31 -1) private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } -
如果使用的是指定大小的构造器，则初始化elementData容量为指定大小，后续扩容为elementData的1.5倍。
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
注意Arrays.copyOf()方法是调用更底层执行：
@HotSpotIntrinsicCandidate
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
LInkedLIst
LinkedList的底层数据结构：
- LInkedLIst的底层实现了双向链表和双端队列的特点
- 可以添加爱任意元素（元素也可以重复），包括null。
- 线程不安全，没有实现同步。
- LinkedList底层维护的是双向链表
链表结点的定义：
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;
}
}
在LinkedList中，定义了如下三个属性：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0; // 链表的结点书
transient Node<E> first; // 指向头结点
transient Node<E> last; // 指向尾结点
...
}
模拟一个简单的双向链表：
package com.cherry.list;
public class LinkedList_ {
public static void main(String[] args) {
Node_ jack = new Node_("jack");
Node_ tom = new Node_("tom");
Node_ cherry = new Node_("cherry");
// 建立引用
jack.next = tom;
tom.pre = jack;
tom.next = cherry;
cherry.pre = tom;
Node_ first = jack;
Node_ last = cherry;
Node_ first_ = first;
// 从头到尾遍历
while(first_ != null){
System.out.println(first_.item);
first_ = first_.next;
}
System.out.println("=======");
// 从尾到头遍历
Node_ last_ = last;
while(last_ != null){
System.out.println(last_.item);
last_ = last_.pre;
}
}
}
class Node_{
Node_ pre;
Node_ next;
Object item;
public Node_(Object item){
this.item = item;
}
@Override
public String toString() {
return "Node name = " + item;
}
}
在创建一个LinkedList对象时，只是调用了无参构造函数，什么都没做：
public LinkedList() { }
此时的first, last均为null, size = 0;
当调用add方法时，首先会将添加的元素进行装箱操作：
@HotSpotIntrinsicCandidate
public static Integer valueOf(int i) {
if (i >= IntegerCache.low && i <= IntegerCache.high)
return IntegerCache.cache[i + (-IntegerCache.low)];
return new Integer(i);
}
接着就会调用 add(E e)方法：c此时创建了一个新的结点，first和last指针都会指向该新结点
public boolean add(E e) {
linkLast(e);
return true;
}
// 进入到 linkLast(e)方法里:
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null); // 创建一个新的结点 newNode
last = newNode; // 此时last指向newNode
if (l == null) //如果当前尾结点尾空，说明此时创建的结点是第一个结点，则first和last都指向新的结点
first = newNode;
else // 此时尾结点不为空， 重新建立last的指向
l.next = newNode;
size++;
modCount++;
}
LInkedList删除
对于remove()无参构造方法，默认删除的是头结点：
public E remove() {
return removeFirst();
}
// 进入到removeFirst()方法中:
public E removeFirst() {
final Node<E> f = first;
if (f == null) // 如果当前链表尾空，则直接抛出异常
throw new NoSuchElementException();
return unlinkFirst(f); // 调用unlinkFirst(f)
}
// 进入到unlinkFirst(f)中(分析很简单):
private E unlinkFirst(Node<E> f) { // f 指向first结点
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
Vector
- Vector的底层也是一个对象数组:
protected Object[] elementData;
- Vector 是线程同步的，即线程安全的，Vector类的操作方法带有synchronized关键字。
- 在开发中，需要线程同步安全时，考虑使用Vector。
Vector 底层源码分析：
如果在创建Vector对象用的是无参构造函数，则初始容量为10：
public Vector() {
this(10);
}
如果在创建Vector对象用的是无参构造函数，则初始容量为在指定的容量：
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
当Vector对象维护的elementData数组空间满的时候，则每一新的容量为旧容量的2倍：
// 1. 空间满的时候，调用grow()无参方法
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
elementCount = s + 1;
}
// 2. 继续调用grow()的有参方法
private Object[] grow() {
return grow(elementCount + 1);
}
// 3. 其中的newCapacity为新的容量
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
}
// 4. newCapacity
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新空间为oldCapacity的2倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity <= 0) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
} // 申请巨大容量，参考上面的ArrayList中的hugeCapacity()
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
当然，也可以在初始化Vectir的时候使用有参构造函数指定capacityIncrement，此时Vector对象扩容的时候就是：
int newCapacity = oldCapacity + capacityIncrement;
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
Set
Set接口的基本特点：
- 无序（添加和取出的顺序不一致，没有索引）
- 不允许存放重复的元素，最多包含一个null
- 尽管Set对象的添加顺序和取出顺序是不一样的，但取出的顺序是固定的
- Set接口不能通过索引来获取对象，因此在遍历Set集合对象的时候不能使用普通的for循环
Set集合的遍历可以使用迭代器遍历和增强for循环遍历。
HashSet
HashSet实际上就是HashMap，可以存放null值，但是只能有一个null，
public HashSet() {
map = new HashMap<>();
}
- HashSet不保证元素有序，取决于hash后，再确定索引的结果（不保证取出元素的顺序和存入的顺序一致）。
- 不能有重复元素/对象，在前面的Set接口中以及提及到。
自定义一个链表+数组实现简单的HashMap
package com.cherry.set;
// 模拟一个HashMap底层结构
public class HashSetStructure {
public static void main(String[] args) {
// 创建一个数组，数组类型为Node_
Node_ [] table = new Node_[16];
System.out.println("table=" + table);
// 创建结点
Node_ john = new Node_("john",null);
table[2] = john;
System.out.println("table=" + table);
Node_ jack = new Node_("jack", null);
john.next = jack; // 将jack挂载到john下
System.out.println("table=" + table);
Node_ rose = new Node_("rose", null);
jack.next = rose;
System.out.println("table=" + table);
}
}
// 结点，用于存放数据和指向下一个结点
class Node_{
Object item;
Node_ next;
public Node_(Object item, Node_ next) {
this.item = item;
this.next = next;
}
}
HashSet添加元素流程：
-
HashSet底层是HashMap
public HashSet() { map = new HashMap<>(); } -
添加一个元素时，会得到hash值，然后转为索引值
-
找到存储数据表table，查看这个索引是否已经存在元素
-
如果没有直接加入。
-
如果有，调用equals()方法（比较的是内容）进行比较，如果相同，就放弃添加，如果不相同，则添加到最后
-
在Java8当中，如果一条链表的元素个数超过8个，并且table表的大小超过64个，则会将结构转为红黑树。
添加方法的源码：
// 1. 首先调用add有参构造方法
public boolean add(E e) {
return map.put(e, PRESENT)==null; // PRESENT作用就是占位的作用
}
// 2. put()方法:key 为要插入的值， value是占位变量
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 3. hash(key)会计算出key的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 4. 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为空，就初始化table，进行第一次扩容到16个空间（默认的散列因子为0.75:当使用到16*0.75=12时就准备提前扩容）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据传入的key得到哈希值去计算该key在table数组的哪个索引处
// 并判断该位置是否存在元素，如果当前位置没有元素，则创建一个新的结点newNode
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 传入的key经过哈希计算发现在table数组中发生了碰撞(和已存在的索引相同)!!!
Node<K,V> e; K k;
// 如果当前索引位置对应的链表第一个元素和转被插入的元素的哈希值相同并且指向的是同一个对象
// 或者table数组发生冲突的所索引位置对应的Node结点中key的equals()和要加入的key的equals()一样
// 则不允许添加，认为是同一个对象。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// p 是不是一颗红黑树，是的话就按照红黑树进行比较
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 如果当前table数组对应的索引位置已经是一个链表了，使用for循环依次比较：
// 1.依次和该链表的每一个元素比较，如果都不相同，则添加到该链表的尾端;
// 2. 如果相同，则认为该链表已经存在了该元素，直接跳出循环。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 注意：在添加元素到链表尾部后，判断当前链表的总结点数是否达到8个结点，若已达到，则要对当前链表进行树化（红黑树化）
// 在转成红黑树时，还要判断table数组的长度是否小于54：
// 如果小于64,则对该数组进行扩容
// 只有上述两者两条件同时成立，才会进行树化
if (binCount >= TREEIFY_THRESHOLD(8) - 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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
练习：
定义一个Employee对象，该类包括name和age，要求当name和age相同就认为是相同员工，不能添加到HashSet中
package com.cherry.set;
import java.util.HashSet;
import java.util.Objects;
public class HashSet_ {
public static void main(String[] args) {
HashSet<Employee> set = new HashSet<>();
set.add(new Employee("cherry",20));
set.add(new Employee("mitu",20));
set.add(new Employee("cherry",20));
System.out.println("set=" + set);
}
}
class Employee {
private String name;
private int age;
public Employee(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Employee{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
// 如果name和age值相同，则调用equals()时返回true
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return age == employee.age && Objects.equals(name, employee.name);
}
// 如果name和age值相同，则调用hashCode()方法计算hashCode时返回相同的结果
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
LInkedHashSet
LinkedHashSet是HashSet的子类，
public class LinkedHashSet<E>
extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { ... }
LinkedHashSet的底层是一个LinkedHashMap，LinkedHashMap底层维护了一个数组+双向链表。
LinkedHashSet 根据元素的hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入的顺序保存的。
LInkedHashSet不允许添加重复元素。
- 在LinkedHashSet中维护的是一个哈希表和一个双向链表。
- 每一个结点都有before和after属性，这样可以i形成双向链表。
- 在添加一个元素时，先求hash值，再求索引，确定该元素在table中的位置，然后将添加的元素加入到双向链表中（如果已经存在，则不添加，原则上和hashset一样）
- 由于双向链表的存在，我们遍历LinkedHashSet也能确保插入顺序和遍历顺序一致
如下面的示例代码：
package com.cherry.set;
import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSet_ {
public static void main(String[] args) {
Set set = new LinkedHashSet();
set.add(new String("AAA"));
set.add(456);
set.add(456);
set.add(128);
set.add("cherry");
for(Object o:set){
System.out.println(o);
}
}
}
首先查看LinkedHashSet的无参构造方法：默认初始化数组容量为16
public LinkedHashSet() {
super(16, .75f, true);
}
其中链表存储的结构就是：
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after; // before和after结点
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
LinkerHashSet添加元素和HashSet添加元素是一样的逻辑。
TreeSet
TreeSet中存放的元素都是有序的，按照ASCII进行排序，那么我们如何自定义排序规则呢？我们可以自定义比较器来自定义排序规则，例如下面的例子：(根据字符串长度进行排序)
public class TreeSet_ {
public static void main(String[] args) {
TreeSet<String> set = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});
set.add("hello");
set.add("wor");
set.add("z");
set.add("wo");
System.out.println(set);
}
}
运行结果如下：
[z, wor, wo, hello]
TreeSet 保证排序有序的规则：
-
构造器会把传入的比较器对象传递给TreeSet底层的TreeMap的属性comparator
public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } -
在调用set.add方法时, 在底层会执行到：
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths // 自定义的comparator（动态绑定） Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else // 如果想等，返回0，这个key就无法加入到set集合中 return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
Map
Map接口实现的特点：
- Map与Collection并列存在，用于保存具有映射关系的数据key-value
- Map中的key和value可以是任意引用数据类型的数据，会封装到HashMap$Node对象中
- Map中的key不允许重复，原因和HashSet一样
- Map中的value可以重复
- Map中的key可以为null，value也可以为null, 注意key为null只能有一个, 而value为空可以有多个
- 常用String类作为Map的key
- key和value之间存在单向一一对应的关系，即可以通过指定的key总能找到对应的value.
- HashMap 没有实现线程同步，因此是线程不安全的
package com.cherry.map;
import java.util.HashMap;
import java.util.Map;
public class Map_ {
public static void main(String[] args) {
// Map接口实例化特点
Map map = new HashMap();
map.put("no1","cherry");
map.put("no2","lily");
map.put("no1","lily"); // 当存在同的k时，相时相当于替换
map.put(null,null);
map.put(null,"空");
map.put(new Object(), "error");
System.out.println(map);
}
}
Map接口存放数据的key-value示意图如下：一对k-v是放在一个Node结点中，又因为Node实现了Entry接口，所以也可以认为一对k-v就是一个Entry
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
为了方便开发者们对Map遍历，Map还会在底层创建一个EntrySet集合,该集合中存放的元素类型是Entry,而一个Entry对象就包含了k,v。
EntrySet集合其实就是：EntrySet<Entry<k,v>>：
transient Set<Map.Entry<K,V>> entrySet;
entrySet 中，定义的类型是Map.Entry，但实际上存放的是 HashMap\(Node。这是因为HashMap\)Node implement Map.Entry.
当把HashMap$Node对象存放到entrySet就很方便我们的遍历，因为 Map.Entry 提供了重要方法：K getKey();和V getValue()两个方法。
除此之外还可以通过getSet()方法将map中的key封装到一个集合里；通过values()方法可以将所有的value封装到一个集合中。
Map接口的常用方法：
-
put：添加元素
-
remove：根据key删除映射关系
-
get：根据key获取value
-
size：获取元素个数
-
isEmpty：判断集合中的元素个数是否为空
-
clear：清除
-
containsKey：查找key是否存在于集合中
-
...
Map的六大遍历方法：
package com.cherry.map;
import java.util.*;
public class MapFor {
public static void main(String[] args) {
Map map = new HashMap();
map.put("no1","juc");
map.put("no2","rpc");
map.put("no3","nginx");
map.put("no4","mq");
map.put("no5","netty");
map.put("no6","spring");
// 第一组遍历方法：先取出所有的key,再通过key取出对应的value
Set keySet = map.keySet();
//(1)增强for循环
for(Object key:keySet){
System.out.println(key+" "+map.get(key));
}
System.out.println("==========");
//(2)使用迭代器
Iterator iterator = keySet.iterator();
while (iterator.hasNext()){
Object key = iterator.next();
System.out.println(key+" "+map.get(key));
}
System.out.println("==========");
// 第二组遍历方式:把所有的values值取出
Collection valCon = map.values();
//(3)for循环
for(Object v:valCon){
System.out.println(v);
}
System.out.println("==========");
//(4)迭代器
Iterator iterator1 = valCon.iterator();
while(iterator1.hasNext()){
System.out.println(iterator1.next());
}
System.out.println("==========");
// 第二组遍历方式:通过EntrySet来获取key-value
Set entrySet = map.entrySet();
//(5)for循环
for(Object o:entrySet){
//将object类型转为Map.Entry类型
Map.Entry entry = (Map.Entry)o;
System.out.println(entry.getKey()+" "+entry.getValue());
}
System.out.println("==========");
//(6)使用迭代器
Iterator iterator2 = entrySet.iterator();
while (iterator2.hasNext()){
//将Map.Node转为Map.Entry方便遍历
Map.Entry next = (Map.Entry)iterator2.next();
System.out.println(next.getKey()+" "+next.getValue());
}
System.out.println("==========");
}
}
HashMap
HashMap 底层源码剖析：
-
（k, v）是一个 Node 实现了 Map.Entry<k, V>， 查看 HashMap 的源码可以看到
-
JDK7的HashMap底层是由数组+链表实现的，而jdk8以后HashMap底层是由数组+链表+红黑树实现的（如果数组上的某一元素所组成的链表结点数大于8且数组长度大于64，就会将链表进行树化）。
HashMap的扩容机制和HashSet完全相同：
- HashMap 底层维护了Node类型的数组table，默认为null
- 当创建对象时，将加载因子loadFactory初始化为0.75
- 当添加k-v时，通过k的哈希值得到在table中的索引，然后判断该索引位置是否有元素，如果没有元素，则直接添加；如果该索引位置有元素，则继续判断该元素的k和准备加入的k是否想等，如果想等则直接替换掉v，如果不想等，还需要判断是树结构还是链表结构，做出相应的处理。如果添加时发现容量不够，则需要扩容。
- 第一次添加，则需要扩容至16, 临界值为12
- 以后再次扩容，则需要扩容table的容量为原来的2倍，临界值为当前容量 * 加载因子，依次类推
- 在java8中，如果一条链表上的元素个数超过8，不并且table数组的大小超过64时，则会进行树化（红黑树）。
HashTable
HashTable 的基本介绍：
- 存放的元素是键值对：即 K-V
- HashTable的k,v都不能为null，否则会抛出空指针异常
- HashTable的使用方法基本和HashMap一样
- HashTable是线程安全的（synchronized），而HashMap是线程不安全的
HashTable的底层简单总结：
-
HashTable的table数组初始化大小为11
public Hashtable() { this(11, 0.75f); } -
数组中的类型为HashTable$Entry
private static class Entry<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Entry<K,V> next; ...... }
HashTable的扩容机制：
public synchronized V put(K key, V value) {
// Make sure the value is not null
// 值为空抛出空指针异常
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
进入到addEntry方法中：
private void addEntry(int hash, K key, V value, int index) {
Entry<?,?> tab[] = table;
// 如果当前table数组的长度大于临界值，则进行扩容--> rehash()
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
modCount++;
}
rehash()方法：
protected void rehash() {
// 拿到当前table的长度
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 新的容量 = 旧容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
LinkedHashMap
TreeMap
TreeMap使用默认的无参构造器默认是无序的（输入顺序和输出顺序不一致）。在有参构造函数中可以自定义比较器实现排序。
例如按照传入的key的字符串大小进行排序：
public class TreeMap_ {
public static void main(String[] args) {
TreeMap<String, Object> map = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
});
}
}
按照传入的key的字符串长度进行排序：
public class TreeMap_ {
public static void main(String[] args) {
TreeMap<String, Object> map = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});
}
}
-
在使用有参构造器，会将自定义的构造器传递给TreeMap的构造器。
-
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { // 第一次添加，会将k,v封装到Entry对象中，然后放入到root中 compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths // 第二次及以后添加k,v Comparator<? super K> cpr = comparator; if (cpr != null) { do { // 遍历所有已经存在的k,v组成的Entry中的而k,本质上就是找到合适的位置 parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else // 如果遍历过程中发现准备加入的key和当前已有的key相等，就直接返回，不添加该元素 return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
Properties
- Properties类继承自Hashtable类并实现了Map接口，也是一种使用键值对的形式来保存数据。
- Properties类的使用和Hashtable类似
- Properties类还可以从xxx.properties文件中将数据加载到Properties类的对象中，并进行读取和修改等
Properties类的基本使用：
public class Properties_ {
public static void main(String[] args) {
Properties prop = new Properties();
// 添加元素
prop.put("userName","cherry");
prop.put("passwd","123456");
prop.put("applicationName","propertiesProject");
// 通过key设置当前的值
prop.remove("applicationName");
// 设置已知的属性
prop.setProperty("passwd","987654321");
// 通过key获取对应的值（修改）
prop.get("userName");
System.out.println(prop);
}
}
Properties来还有一个作用是读取外部的配置文件（以xxx.properties结尾的文件），读取方式有三种：
- 通过了类加载器ClassLoader读取配置文件
- 通过InputStream输入流读取配置文件
- 使用JDK自带的资源捆绑类REsourceBoundle 读取配置文件
用法如下：
首先在resources目录下创建配置文件：application.properties
username = cherry
passwd = 123456789
log_open = true
使用java代码获取配置文件中的内容：
开发中集合的选择
在开发中，选择什么类型的集合，主要取决于业务操作的特点，然后根据集合的特点选择合适的集合：
- 首先判断存储类型（一组对象还是一组键值对）
- 一组对象：Collection接口
- 允许重复: List
- 增删多：LinkedList [底层维护了一个双线链表]
- 查询多：ArrayList [底层维护了一个可变数组]
- 不允许重复: Set
- 无序：HashSet [底层是HashMap, 维护了一个哈希表（数组+链表——红黑树）]
- 排序：TreeSet
- 插入和取出顺序一致：LinkedHashSet[底层是LinkedHashMap的底层是HashMap，维护的是数组+双向链表]
- 允许重复: List
- 一组键值对: Map接口
- 键无序：HashMap [底层是 哈希表 jdk7: 数组+链表，jdk8: 数组+链表+红黑树]
- 键有序：TreeMap
- 键插入和取出顺序一致：LinkedHashMap
- 读取文件：Properties类
Collections工具类
Collections 是一个操作Set, List, 和Map等集合的工具类
Collections集合提供了一系列静态方法对集合元素进行排序，查询，修改等操作。
如：``
- reverse(List): 反转List集合中的元素
- shuffle(List)：对List集合中的元素进行随机排序
- sort(List)：根据元素的自然顺序对指定的List集合元素按照升序排序
- sort(List, Comparator)：根据指定的Comparator产生的顺序对List集合元素进行排序
- swap(List, i, j)：将指定的List集合中的i元素和j元素进行交换
- Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
- Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中最大的元素
- Object min(Collection)：根据元素的自然顺序，返回给定集合中的最小元素
- Object min(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中最小的元素
- int frequency(Collection, Object)：返回指定集合中指定元素在集合中出现的次数
- void copy(List dest, List src)：将 src集合中的内容复制到dst集合中
- boolean replaceAll(List list, Object oldValue, Object newValue):：使用新值替换掉集合中原来所有的旧值