Collection 集合
集合接口有2个基本方法：
public interface Collection<E>
{
//向集合中添加元素。如果添加元素确实改变了集合就返回 true, 如果集合没有发生变化就返回 false
boolean add(E element);
//返回一个实现了Iterator接口的对象
Iterator<E> iterator();
}
Iterator接口包含4个方法：
public interface Iterator<E>
{
//返回将要访问的下一个对象。如果已经到达了集合的尾部，将拋出一个 NoSuchElementException。
E next();
//如果存在可访问的元素，返回 true。
boolean hasNext();
//删除上次访问的对象。这个方法必须紧跟在访问一个元素之后执行。如果上次访问之后，集合已经发生了变化，这个方法将抛出一个 IllegalStateException。
default void remove();
//为每个剩余元素执行给定的操作，直到处理完所有元素或操作引发异常为止
default void forEachRemaining(Consumer<? super E> action)
}
集合可以看作是一种容器，用来存储对象信息。所有集合类都位于java.util包下，但支持多线程的集合类位于java.util.concurrent包下。
图片出处：冰湖一角的博客
List 表
1. LinkedList 链表
- 有头节点和尾结点的双向链表。
- 实现了
Deque接口，可以作为双端队列。即既可以当做栈使用，也可以当做队列使用。 LinkedList和ArrayList一样也不是线程安全的，如果在对线程下面访问可以自己重写LinkedList，然后在需要同步的方法上面加上同步关键字synchronized。listIterator()方法返回一个实现了ListIterator接口的对象。ListIterator接口有两个方法可以用于反向遍历链表：E previous(); boolean hasPrevious();LinkedList的遍历方法：public class Test { public static void main(String[] args) { List<String> list=new LinkedList<>(); list.add("Hello"); list.add("World"); list.add("Are"); list.add("you"); list.add("OK?"); // 1. 转换到数组 String[] strArray=new String[list.size()]; list.toArray(strArray); for(String str:strArray){ System.out.println(str); } // 2. foreach循环 for(String str:list){ System.out.println(str); } // 3. 迭代器 Iterator itr = list.iterator(); while(itr.hasNext()) { System.out.println(itr.next()); } } }
2. ArrayList 动态数组
- 允许任何符合规则的元素插入甚至包括null。
- 如果在初始化
ArrayList的时候没有指定初始化长度的话，默认的长度为10。 ArrayList在增加新元素的时候如果超过了原始的容量的话，扩容方法public void ensureCapacity(int minCapacity)的方案为oldCapacity * 3/2 + 1，并保证满足参数minCapacity。ArrayList是线程不安全的，在多线程的情况下可以使用Vector，Vector是同步的。Vector是允许设置默认的增长长度，Vector的默认扩容方式为原来的2倍。ArrayList的遍历方法：public class Test { public static void main(String[] args) { List<String> array=new ArrayList<String>(); array.add("Hello"); array.add("World"); array.add("Are"); array.add("you"); array.add("OK?"); // 1. 转换到数组 String[] strArray=new String[array.size()]; array.toArray(strArray); for(String str:strArray){ //或是 for(int i=0;i<strArray.length;i++) System.out.println(str); } // 2. foreach循环 for(String str:array){ System.out.println(str); } // 3. 迭代器 Iterator itr = array.iterator(); while(itr.hasNext()) { System.out.println(itr.next()); } } }
Set 集
1. HashSet 无序散列表
- 集不允许重复元素。判断依据是
equals()。 - 实现了一个哈希表。内部基于
HashMap实现，因为Map里的Key不允许重复，天然就是一个Set。 - “如果存放自定义类，就要负责实现这个类的
hashCode()方法。注意，自己实现的hashCode()方法应该与equals()方法兼容，即如果a.equals(b)为true，a与b必须具有相同的散列码。”（出自《Java核心技术卷一》P.363）
“HashSet集合判断两个元素相等的标准是(1)两个对象通过equals()方法比较返回true；(2)两个对象的hashCode()方法返回值相等。因此，如果(1)和(2)有一个不满足条件，则认为这两个对象不相等，可以添加成功。”（出自冰湖一角的博客）
验证代码：public class Test { public static void main(String[] args) { Set<A> test = new HashSet<A>(); A a1 = new A(9); A a2 = new A(19); System.out.println(a1.equals(a2)); // true System.out.println(a1.hashCode()==a2.hashCode());// false test.add(a1); test.add(a2); System.out.println(test.size());// 2 } } - 如果两个对象的
hashCode()方法返回值相等，但是两个对象通过equals()方法比较返回false，HashSet会以链式结构将两个对象保存在同一位置，这将导致性能下降，因此在编码时应避免出现这种情况。 HashSet中仅允许存入一个null值。HashSet不是线程同步的。HashSet的遍历方法：public class Test { public static void main(String[] args) { Set<String> hs=new HashSet<String>(); hs.add("Hello"); hs.add("World"); hs.add("Are"); hs.add("you"); hs.add("OK?"); // 1. 转换到数组 String[] strArray=new String[hs.size()]; hs.toArray(strArray); for(String str:strArray){ //或是 for(int i=0;i<strArray.length;i++) System.out.println(str); } // 2. foreach循环 for(String str:hs){ System.out.println(str); } // 3. 迭代器 Iterator itr = hs.iterator(); while(itr.hasNext()) { System.out.println(itr.next()); } } }
2. LinkedHashSet
- 扩展(extends)了HashSet类。记住元素项的插入顺序。这样就可以避免在散列表中的项从表面上看是随机排列的。当条目插入到表中时，就会并入到双向链表中，如下图所示。由于LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet，但在迭代访问Set里的全部元素时由很好的性能。
（访问顺序可用于实现高速缓存的“ 最近最少使用” 原则，此处不详细展开。）
- 内部基于LinkedHashMap实现。在父类
HashSet中，专为LinkedHashSet提供的构造方法如下，该方法为包访问权限，并未对外公开。（出自smile2it的博客）/** * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 * * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。 * @param initialCapacity 初始容量。 * @param loadFactor 加载因子。 * @param dummy 标记。 */ HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor); }
3. TreeSet 有序树集
TreeSet内部基于TreeMap实现，原因前面讲过了。而TreeMap采用红黑树的数据结构来存储集合元素。- 元素的排序方法为：①默认是自然排序；②构造函数传入实现了Comparator接口的比较器（该比较器重写
int compare(T o1,T o2)）。
第①种情况下：所有插入到TreeSet的元素必须实现Comparable接口（实现了int compareTo(Object obj)方法），否则会抛出java.lang.ClassCastException异常；TreeSet会调用集合元素的compareTo方法来比较元素的大小关系（如果返回0则相等），然后将元素按照升序排列。 - Java常用类中已经实现了Comparable接口的类有以下几个：
- BigDecimal、BigDecimal以及所有数值型对应的包装类：按照它们对应的数值大小进行比较。
- Charchter：按照字符的unicode值进行比较。
- Boolean：true对应的包装类实例大于false对应的包装类实例。
- String：按照字符串中的字符的unicode值进行比较。
- Date、Time：后面的时间、日期比前面的时间、日期大。
TreeSet的遍历方法：同HashSet。
4. EnumSet 枚举集
EmimSet是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet内部用位序列实现。如果对应的值在集中，则相应的位被置为 1。EnumSet的集合元素也是有序的，EnumSet以枚举值在Enum类内的定义顺序来决定集合元素的顺序。EnumSet集合不允许加入null元素，如果试图插入null元素，EnumSet将抛出NullPointerException异常。EnumSet类没有公共的构造器。可以使用静态工厂方法构造这个集：enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY }; EnumSet<Weekday> always = EnumSet.allOf(Weekday.class); EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class); EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY); EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);- 可以使用 Set 接口的常用方法来修改 EnumSet。
Queue 队列
| Throws exception | Returns special value | |
| Insert | add(e) |
offer(e) |
| Remove | remove() |
poll() |
| Examine | element() |
peek() |
1. Deque 双端队列
Deque支持同时从两端添加或移除元素，因此Deque接口的实现可以被当作FIFO队列使用，也可以当作LIFO队列（栈）来使用。官方也是推荐使用 Deque 的实现来替代 Stack。LinkedList是双端队列的链表实现。ArrayDeque是双端队列的可变数组实现。ArrayDeque没有容量限制，可根据需求自动进行扩容。ArrayDeque不支持值为null的元素。ArrayDeque当做栈使用时可能比Stack要快，当做队列使用时可能比LinkedList要快。其大部分操作都是平摊常数时间。ArrayDeque的初始容量：- 默认是16；
- 构造函数传入
int numElements，如果numElements≤8，则初始容量为8；如果numElements>8，则初始容量为大于8的某个2^n； - 构造函数传入
Collection<? extends E> c，初始容量为≥c.size()的某个2^n。
ArrayDeque有三个重要数据域：Object[] elementsint headint tail- elements: 循环数组，大小总会是 2^n；
- head: 双端队列的头，出队或出栈时的元素位置，加入双端队列头端元素位置，表示当前头元素位置，初始为0；
- tail: 双端队列尾的下一个，入队或进栈时的元素位置，加入双端队列尾端的下个元素的索引，tail位总是空的，初始为0；
- isEmpty() 判空条件：head == tail；
- (tail = (tail + 1) & (elements.length - 1)) == head 时为满。满时自动容量翻倍，并重新组织元素到新数组头部。
理解：（出自Kyrie lrving 的博客）
length = 2^n，二进制表示为：第 n 位为1，低位 (n-1位) 全为0；
length - 1 = 2^n-1，二进制表示为：低位(n-1位)全为1；
如果 tail + 1 <= length - 1，则 位与 后低 (n-1) 位保持不变，高位全为0，此时tail和head都在数组中部相遇；
如果 tail + 1 = length，则位与后低 n 全为0，高位也全为0，结果为 0，此时tail和head都在数组下标0处相遇。
- 作为栈使用：
void push(E e)，E pop()，E peek() - 作为队列使用：
boolean offer(E e)，E poll()，E peek()
boolean add(E e)，E remove()，E element() Deque方法总结与对比。
| First Element (Head) | Last Element (Tail) | |||
| Throws exception | Special value | Throws exception | Special value | |
| Insert | addFirst(e) |
offerFirst(e) |
addLast(e) |
offerLast(e) |
| Remove | removeFirst() |
pollFirst() |
removeLast() |
pollLast() |
| Examine | getFirst() |
peekFirst() |
getLast() |
peekLast() |
Queue Method |
Equivalent Deque Method |
add(e) |
addLast(e) |
offer(e) |
offerLast(e) |
remove() |
removeFirst() |
poll() |
pollFirst() |
element() |
getFirst() |
peek() |
peekFirst() |
| Stack Method | Equivalent Deque Method |
push(e) |
addFirst(e) |
pop() |
removeFirst() |
peek() |
peekFirst() |
2. PriorityQueue 优先队列
- 基于priority heap，也就是说可以当做最小堆或最大堆来使用。
- 将堆（完全二叉树）存于数组内。默认的Capacity为11。
- 不允许
null。 - 默认自然排序，或者传入Comparator。（前面在
TreeSet已经介绍过） - 结构破坏时，调用私有方法
siftUp()和siftDown()维护结构。 PriorityQueue的peek()和element()操作是常数时间，add()、offer()、无参数的remove()以及poll()方法的时间复杂度都是log(N)。
Map 映射
Map是集合框架的一部分，但不继承Collection接口。
1. HashMap
- 默认情况下：初始容量为16，负载因子为0.75。
- 容量总会是 2^n。
- 位置索引的计算方法是哈希码（hashCode）对哈希表长求余。但是计算方法是位运算：
在length = 2^n 的情况下，有 h & (length-1) == h % length ，位运算比模运算快得多。 - 计算哈希码：
HashMap中的条目类Node<K,V>有自己的hashCode()方法，不过好像并未使用过。- 计算哈希值是使用
HashMap的int hash(key)方法：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }至于相关解释，可以看看这篇博客。（稍微有些晦涩，下次我整理一篇出来）
HashMap可以允许你在列表中放一个key值为null的元素，并且可以有任意多value为null。而Hashtable不允许键或者值为null。HashMap的遍历方法：（有一些奇奇怪怪的方法就不写了）public class Test { public static void main(String[] args) { String[] str = { "I love you", "You love he", "He love her", "hello" }; Map<Integer, String> m = new HashMap<Integer, String>(); for (int i = 0; i < str.length; i++) { m.put(i, str[i]); } // 0. 直接打印查看结果。 System.out.println(m.toString()); // 1. 使用keySet()： // 迭代器 Set<Integer> s1 = m.keySet(); Iterator<Integer> it1 = s1.iterator(); while (it1.hasNext()) { int key = it1.next(); System.out.println("Key = " + key + ", Value = " + m.get(key)); } // foreach for (Object key : m.keySet()) { System.out.println("Key = " + key + ", Value = " + m.get(key)); } // 2. 使用entrySet()： // 迭代器 Set<Entry<Integer, String>> s2 = m.entrySet(); Iterator<Map.Entry<Integer, String>> it2 = s2.iterator(); while (it2.hasNext()) { Map.Entry<Integer, String> entry = it2.next(); System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue()); } // foreach for (Map.Entry<Integer, String> entry : m.entrySet()) { System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue()); } // 3. 使用values()： // 迭代器 Collection<String> c = m.values(); Iterator<String> it3 = c.iterator(); while (it3.hasNext()) { System.out.println(it3.next()); } // foreach for(String s : m.values()) { System.out.println(s); } } }
2. TreeMap
TreeMap是一个红黑树的数据结构，每个key-value对作为红黑树的一个节点。TreeMap存储key-value对时，需要根据key对节点进行排序。TreeMap实现了SortedMap- 排序方式：
- 自然排序：TreeMap的所有key必须实现Comparable接口，而且所有的key应该是同一个类的对象，否则会抛出ClassCastException。
- 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。
TreeMap的遍历方法参考HashMap。
3. 其他
LinkedHashMap（链接散列映射），使用双向链表记住元素项的插入顺序。WeakHashMap（弱散列映射），使用弱引用（weak references）保存键。解决了有关不再引用的键的垃圾回收问题。EnumMap（枚举映射），是一个键类型为枚举类型的映射。它可以直接且高效地用一个值数组实现。在使用时，需要在构造器中指定键类型：EnumMap<Weekday, Employee> personInCharge = new EnumMap<>(Weekday.class);IdentityHashMap（标识散列映射）。
集合框架的遗留类
Vector作用与ArrayList一样，但Vector是线程安全的。Stack继承了Vector类，是线程安全的栈实现。Hashtable作用与HashMap一样，但HashTable是线程安全的。Properties类（属性映射）继承了Hashtable类，它相当于一个key、value都是String类型的Map，主要用于读取配置文件。Enumeration接口：Hashtable、Vector的element()方法产生一个用于描述表中各个枚举值的对象。
BitSet 位集
- Java平台的
BitSet类用于存放一个位序列（它不是数学上的集，称为位向量或位数组更为合适)。 - 如果需要高效地存储位序列（例如，标志）就可以使用位集。由于位集将位包装在字节里，所以，使用位集要比使用
Boolean对象的ArrayList更加高效。
（个人测试，速度上：boolean[] > BitSet > ArrayList） BitSet类提供了一个便于读取、设置或清除各个位的接口。使用这个接口可以避免屏蔽和其他麻烦的位操作。如果将这些位存储在int或long变量中就必须进行这些繁琐的操作。