集合族谱核心成员
集合族谱核心成员
所有的集合类，都实现了Iterator接口，这是用于遍历集合中元素的接口；Java集合框架核心是两个类型的容器，一种是集合（Collection），存储单一元素，一种是图（Map），存储键值对；Collection有3个接口子类，List、Set和Queue，下面是一层抽象类，再下一层是实现类，包括常用的ArrayList，LinkedList，HashSet，HashMap等等。
集合遍历方式：
- Iterator 迭代输出
Iterator it = arr.iterator();
while(it.hasNext()){ object o =it.next(); ...}
- for 循环
for（int i=0;i<arr.size();i++）{...}
- foreach 增强循环
for（int i：arr）{...}
Collection接口
image.png
从结构上看包含了一般线性数据结构的的常用方法，比如size()，isEmpty()，add(E)，remove()，clear()，toArray()转数组等等。
List
继承与Collection的接口，一个允许重复的有序集合，有明星子类ArrayList和LinkedList。
ArrayList：
//最大长度为2的31次方-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList内部用数组存储元素的，这个数组可以动态创建，如果元素个数超过了数组的容量，那么就创建一个更大的新数组，并将当前数组中的所有元素通过Arrays.copy()复制到新数组中。
LinkedList：
链表和数组的最大区别在于它们对元素的存储方式的不同导致它们在对数据进行不同操作时的效率不同。
ArrayList和LinkedList的区别：
- ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于链表的数据结构；
- 对于查询操作，ArrayList要优于LinkedList，因为数组直接访问下标，链表需要从头开始移动指针逐个访问。
- 对于增删操作，LinkedList通常要优于ArrayList，因为数组添加数据，后续元素要逐个后移，链表不需要。
Arrays：
来自java.util.Arrays工具类。常用方法：
- asList：将数组转成集合
实现：
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
- binarySearch：在数组中查找某元素的位置
public static int binarySearch(int[] a, int fromIndex, int toIndex,
int key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
- copyOf和copyOfRange
复制前3位数返回数组
String[] names = { "Eric", "John", "Alan", "Liz" };
//[Eric, John, Alan]
String[] copy = Arrays.copyOf(names2, 3);
从第3个元素开始到结束复制返回数组
String[] names = { "Eric", "John", "Alan", "Liz" };
//[Eric, John, Alan]
String[] copy = Arrays.copyOf(names, 2,names.length);
Set
Set接口扩展自Collection，它与List的不同之处在于，规定Set的实例不包含重复的元素。Set接口有三个具体实现类，分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。
Queue
队列操作是先进后出（First In First Out），称为限制性线性表。数据插入只能在尾部，删除只能在头部。
队列方法：
image.png
按照以上方法，用数组模拟队列：
public class MyQueen<T> {
private T[] array;
private int max;
private int count;
private int head; //头位置
private int tail; //尾位置
public MyQueen(int length){
max = length;
array = (T[]) new Object[max];
head = -1;
tail = 0;
}
public boolean isEmpty(){
return count == 0;
}
public boolean isFull(){
return count == max;
}
public void add(T e){
if (tail == max - 1) {//已到实际队尾，从头开始
tail = -1;
}
//尾位置后移
tail++;
array[tail] = e;
//长度加一
count++;
}
public T remove(){
T first = array[head];
//头位置后移
head++;
//长度减一
count--;
if(head == tail){ //头尾重合，从头开始
head = 0;
}
return first;
}
public T head(){
return array[head];
}
public int length(){
return count;
}
}
包括添加，删除，判断空，获取长度，获取头元素等。
Map
Map，图，是一种存储键值对映射的容器类，在Map中键可以是任意类型的对象，但不能有重复的键，每个键都对应一个值。Map接口常用的有三个具体实现类，分别是HashMap、LinkedHashMap、TreeMap。
Map类结构：
image.png
HashMap的内部结构
HashMap是通过数组和指针链表两种数据结构共同实现的。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
内部结构图：
image.png
再来个具体值形象的：
image.png
内部部分实现：
transient Node<K,V>[] table;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
重要属性：
loadFactor ： 负载因子 默认0.75
initialCapacity ：初始化容量16，最大是（1 << 30）1073741824
table : Node<K,V>[] table 是用来存储数据的数组
Node<K,V> ：是HashMap的一个静态内部类，表示数组元素类型是，Node<K,V>继承自Map.Entry<K,V>，为键值对映射。
总结：
HashMap使用叫table的数组存放Node的元素。Node内部类存储key-value键值对。Node有next属性实现多个Node的单项链表。插入元素时，如果两条Key落在同一个桶，并且这两条key不equals,后入桶的Entry将next指向桶当前的Entry，否则后入桶的会将前面的给覆盖（确保key的唯一性）。
其他集合类
Vector
Vector与ArrayList基本一致，不同之处在于Vector使用了关键字synchronized将访问和修改向量的方法都变成同步的了。
①Vector所有方法都是同步，有性能损失。
②Vector早期版本出现的。
③Vector初始length是10 超过length时 以100%比率增长，相比于ArrayList更多消耗内存。
Stack
栈操作特点是后进先出（Last In First Out），就像家里叠盘子一样。栈的插入和删除数据元素的操作只能在栈顶进行。栈继承自类Vector：
public class Stack<E> extends Vector<E> {}
网友评论