Java集合
一、Colection接口1.1 List接口1.1.1 ArrayList1.1.2 LinkedList1.1.3 Vector1.1.4 三者的异同
1.2 Set接口1.2.1 HashSet1.2.2 LinkedHashSet1.2.3 TreeSet
1.3 Map接口1.3.1 HashMap1.3.2 ConcurrentHashMap1.3.3 LinkedHashMap1.3.4 TreeMap1.3.5 Hashtable1.3.6 Properties1.3.7 Collections工具类
一、Colection接口
Collection接口：单列集合，用来存储一个一个的对象
1.1 List接口
List接口：存储有序的、可重复的数据（“动态”数组）
常用方法
void add(int index
, E element
)
boolean addAll(int index
, Collection
<? extends E> c
)
E
get(int index
)
int indexOf(Object o
)
ListIterator
<E> listIterator()
ListIterator
<E> listIterator(int index
)
E
remove(int index
)
E
set(int index
, E element
)
List
<E> subList(int fromIndex
, int toIndex
)
1.1.1 ArrayList
List接口的主要实现类
ArrayList arrayList
= new ArrayList();
jdk1.6：
public ArrayList() {
this(10);
}
底层创建的是长度为10的Object[ ]数组elementData
jdk1.7：
private static final int DEFAULT_CAPACITY
= 10;
private static final Object
[] EMPTY_ELEMENTDATA
= {};
private transient Object
[] elementData
;
public ArrayList() {
super();
this.elementData
= EMPTY_ELEMENTDATA
;
}
public boolean add(E e
) {
ensureCapacityInternal(size
+ 1);
elementData
[size
++] = e
;
return true;
}
无参构造创建的是一个空的数组，在add方法中初始化的默认值为10
扩容
private void grow(int minCapacity
) {
int oldCapacity
= elementData
.length
;
int newCapacity
= oldCapacity
+ (oldCapacity
>> 1);
if (newCapacity
- minCapacity
< 0)
newCapacity
= minCapacity
;
if (newCapacity
- MAX_ARRAY_SIZE
> 0)
newCapacity
= hugeCapacity(minCapacity
);
elementData
= Arrays
.copyOf(elementData
, newCapacity
);
}
每次扩容长度为之前的1.5倍，同时将原数组中的数据复制到新的数组
结论：使用时经历避免使用空参构造器jdk1.8
private static final Object
[] EMPTY_ELEMENTDATA
= {};
private static final Object
[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA
= {};
public ArrayList() {
this.elementData
= DEFAULTCAPACITY_EMPTY_ELEMENTDATA
;
}
1.1.2 LinkedList
LinkedList linkedList
= new LinkedList();
其底层是双向链表，存储单元为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
;
}
}
1.1.3 Vector
List接口的古老实现类（JDK1.0），不太常用 它底层和Arraylist一样，是通过数组实现的，但是它支持线程的同步 默认扩容为2倍
public Vector() {
this(10);
}
1.1.4 三者的异同
ArrayList：
线程不安全，效率高底层使用Object[ ] elementData存储 LinkedList：
底层使用双向链表存储对于频繁的插入、删除操作，效率较高 Vector：
线程安全，效率低底层使用Object[ ] elementData存储 相同处：
三个类都是实现了List接口，存储数据的特点相同：存储有序的、可重复的数据
1.2 Set接口
存储无序的、不可重复的数据
无序性：数据在底层数组中并非按照数组索引的顺序添加，而是由hashcode决定数组的索引不可重复性：通过hashcode()和equals()判断是否重复，先判断hashcode()是否相等，相等就再判断equals()
1.2.1 HashSet
Set接口的主要实现类，线程不安全，可以存储null值，实际上底层是用hashmap实现的
public HashSet() {
map
= new HashMap<>();
}
1.2.2 LinkedHashSet
作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历 在HashSet的基础上添加了两个索引指针方便按添加遍历
1.2.3 TreeSet
底层使用的是红黑树存储，可以按照添加对象的指定属性进行排序
向TreeSet中添加的数据必须是相同的对象自定义的类型必须有排序的方法，用于比较，而不是使用equals()
1.3 Map接口
双列数据，存储key-value对的数据
1.3.1 HashMap
Map的主要实现类线程不安全效率高可以存储null的key和value底层：
数组+链表（jdk7之前）数组+链表+红黑树（jdk8） CRUD：
V put(K key, V value)void putAll(Map m)V remove(Object key)void clear()V get(Object key)int size()boolean containsKey(Object key)boolean containsValue(Object value)boolean equals(Object o) 遍历遍历key集合
Set set
= hashMap
.keySet();
Iterator iterator
= set
.iterator();
while (iterator
.hasNext()){
System
.out
.println(iterator
.next());
}
遍历value集合
Collection values
= hashMap
.values();
for (Object value
: values
) {
System
.out
.println(value
);
}
遍历所有的key-valueentrySet()
Set entrySet
= hashMap
.entrySet();
Iterator iterator1
= entrySet
.iterator();
while (iterator1
.hasNext()){
Object obj
= iterator1
.next();
Map
.Entry entry
= (Map
.Entry
) obj
;
System
.out
.println(entry
.getKey()+"----->"+entry
.getValue());
}
遍历key和value本质都是获取entrySet再获取key和value，所以其顺序是对应的JDK7
new HashMap()
底层创建了长度为16的一维Entry[ ] table map.put(key1,value1)
首先，调用key1所在类的hashcode() 计算key1的哈希值，以此得到在Entry数组中的位置。如果位置为空，则添加成功。如果不为空（此位置上有一个或者多个数据(链表)），则比较两者的哈希值：
如果key1的哈希值与已经存在的数据的哈希值不同，则key1-value1添加成功------情况2如果key1的哈希值与已经存在的某一个数据(key2-value2)的哈希值相同，则继续比较：调用key1所在类的euqals(key2)
如果equals()返回false：此时key1-value1添加成功------情况3如果equals()返回true：使用value1覆盖value2 情况2和情况3时key1-value1和原来的数据以链表的形式存储在添加的过程中，默认扩容为原来的2倍，并将原有的数据复制过来 JDK8
new HashMap()：底层没有创建长度为16的数组JDK8底层的数组是Node[ ]，而非Entry[ ]首次调用put()方法时，底层创建长度为16的数组JDK7底层只有：数组+链表。JDK8底层结构：数组+链表+红黑树。当数组的某一个索引位置上的元素以链表的形式存在的数据个数 > 8，且当前数组的长度 > 64时，此索引位置上的所以数据改为使用红黑树存储（二叉树能提高查找效率） 负载因子:
DEFAULT_LOAD_FACTOR
= 0.75f;
threshold = loadFactor * 容量,当已存入的数据个数>threshold时扩容
1.3.2 ConcurrentHashMap
1.3.3 LinkedHashMap
在HashMap的基础上添加了前后指针，能够按照添加的顺序遍历对于频繁的遍历操作，执行效率高于HashMap
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry
<K,V> before
, after
;
Entry(int hash
, K key
, V value
, Node
<K,V> next
) {
super(hash
, key
, value
, next
);
}
}
1.3.4 TreeMap
保证按照添加的key-value对进行排序，实现排序遍历底层使用红黑树自然排序定制排序
1.3.5 Hashtable
古老的实现类线程安全，效率低不能存储null的key和value
1.3.6 Properties
Hashtable的子类，常用于处理配置文件，key、value都是String常配合文件流读取配置文件
1.3.7 Collections工具类
Collections是操作Collection、Map的工具类Reverse（List）：逆序排序Shuffle（List）：打乱顺序Sort（List）：排序Swap(List,int,int)：交换
