20191009205832202.png
集合框架的基本概念：
集合（存放数据的容器）：
1.集合用于动态存储多个对象（可以扩容）
2.集合只能存储引用数据类型（要想存储基本数据类型，就封装成包装类的对象）
集合 vs 数组：
区别1：集合是长度可变的序列，数组是长度固定的序列
区别2：集合中可以存放多种类型的元素，数组只能存放声明时定义类型的元素
注意：实际运用集合中，一个集合存放一种数据类型的元素，为了方便管理（泛型）
1.Collection 与 Map 的不同？
区别1：Collection存储单个值，Map存储两个值（K-V）
区别2：Collection可以直接遍历，Map不能直接遍历
2.理解无序：存入顺序与取出顺序不一致，无序不代表随机
3.HashSet底层由HashMap实现，TreeSet底层由TreeMap实现
****Collection集合/接口****
List集合/接口（extends Collection）
注意：此接口添加了对于下标进行操作的方法
特点：有序，且可重复
ArrayList
数据结构：**一维数组**
**ArrayList底层**
private transient Object[] elementData;//存放元素的数组
private int size;
public boolean add(E e) {
//是否扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
**LinkedList**（队列模式，栈模式）
数据结构：**双向链表**
------------------LinkedList.class---------------------
transient Node<E> first = null;
transient Node<E> last = null;
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
------------------LinkedList$Node.class---------------------
Node（节点类三个属性：prev上一个节点的地址，next下一个节点的地址，item元素）
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;
}
}
Vector（跟ArrayList相比较线程安全的，加的是synchronized锁）
数据结构：一维数组
Stack
数据结构：一维数组
注意：extends Vector
特点：栈模式（先进后出）
4.ArrayList vs LinkedList
区别1：LinkedList有栈、队列模式，ArrayList没有
ArrayList查改快，LinkedList增删快
区别2：效率问题
添加数据：ArrayList在不扩容的情况下快
插入数据：LinkedList快
删除数据：LinkedList快
修改数据：ArrayList快
查询数据：ArrayList快
**5.ArrayList、LinkedList在工作中的实际运用？**
在工作中，对于数据的操作-查询功能最为频繁，ArrayList查询更快，所以经常使用，
如果碰到队列模式或栈模式就是LinkedList
**6.ArrayList vs Vector**（Stack继承Vector，只是多了栈模式先进后出）
ArrayList ： 线程不安全
Vector ： 线程安全
Set集合接口（extends Collection）
特点：无序，且不可重复
HashSet
数据结构：hash数组
TreeSet
数据结构：二叉树
特点：自然排序
HashSet底层由HashMap实现，TreeSet底层由TreeMap实现
Map集合/接口
特点：键值对Key-Value
HashMap
特点：key的唯一性
数据结构：hash数组+单向链表+红黑树（链表长度达到8转换为红黑树，小于了6转回单向链表）
HashTable
数据结构：hash数组
ConcurrentHashMap
数据结构：hash数组
--------------------HashSet.class------------------------
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
--------------------HashMap.class------------------------
//hash数组是以entry[]映射关系为元素，再以key值的hash值确定数组中下标
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
public V put(K key, V value) {
//初始化Hash数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//判断key是否为null
if (key == null)
return putForNullKey(value);
//获取key对象的hash值
int hash = hash(key);
//通过key对象的hash值计算出在hash数组中的下标
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判断是否是同一个对象
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//判断数组是否扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
--------------------HashMap$Entry.class------------------------
//Entry也是一个类，其中的属性有（key，value，下一个entry的地址，key的hash）
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; ------ key
V value; ------ value
Entry<K,V> next; ----- 下一个映射关系的地址（所以是单向链表，相对于基于Node类而言）
int hash; ------ key对象的hash值
//形参：key对象的hash值、key、value、下一个映射关系的地址
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
8.HashMap vs Hashtable(遗留类) vs ConcurrentHashMap（是在MAP接口下，只是是在其实现接口 ConcurrentMap接口之下的）
共同点：操作一模一样
区别1：
HashMap：可以存空键空值
Hashtable、ConcurrentHashMap：不可以存空键空值
区别2：
HashMap：线程不安全
Hashtable：线程安全
ConcurrentHashMap：线程安全，分段式加锁，锁是加载Segment对象中的，分段式加锁效率更好
TreeMap
特点：key保证唯一性，对key进行排序
数据结构：二叉树（配合红黑树制衡（避免不断的从root循环比较，影响效率，制衡的话不断取平均数成为root，最终使遍历比较次数最小就能比较出结果））
----------------TreeSet.class-----------------------
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
----------------TreeMap.class-----------------------
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public V put(K key, V value) {
//获取根节点
Entry<K,V> t = root;
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
//比较结果
int cmp;
//记录父节点
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
9.Comparable vs Comparator
Comparable - compareTo()：类实现此接口里的排序方法（如果此类要想存入TreeSet或TreeMap就必须实现Comparable接口）
Comparator - compare()：不能改变元素所属类的排序规则时，在创建TreeSet或TreeMap时使用有参构造，重新定义排序规则
10.比较器的优先级别：Comparable < Comparator
原因是在穿件treeMap时是先判断Comparator是否为空，不为空就走Comparator规则去排序，为空才去走Comparable 规则去排序，所以优先级别：Comparable < Comparator
集合的应用场景
ArrayList：存数据
LinkedList：栈模式、队列模式
HashSet：去重复
HashMap：去重复、键值对
ConcurrentHashMap：线程安全的去重复、键值对
TreeSet：排序
TreeMap：针对key排序
总结
底层实现：一维数组，hash数组加单向链表+红黑树数据结构，双向链表（linkedList），二叉树+红黑树数据结构（tree）
