java集合（fromzero）-创新互联
单列集合：
顶层接口是collection集合，下分接口为List集合和Set集合，
List集合有序可重复有索引（有序指的是存和取的顺序一样，数据可以重复，可以通过索引取出任意一条数据）List下分实现类为ArrayList、LinkedList、Vector(淘汰),
Set集合无序不可重复无索引（存和取的顺序可能不一样，数据不重复，不能通过索引取出指定一条数据），Set下分实现类为HashSet、TreeSet，HashSet下分实现类有LinkedHashSet
单列集合-数据结构(栈、队列、数组、链表)
栈 先进先出 后进后出
队列 先进后出 后进先出
数组 查询快 增删慢 （内存连续 通过数组地址值+元素索引值查询）
链表-单向、双向 查询慢 增删快 （内存不连续 通过头节点往后遍历查询）
二叉树：每一个节点的子节点数<=2
二叉查找树 ：添加时比当前节点小的数去左边，比当前节点大的数去右边，不存相同的数
平衡二叉树 ：任何一个节点的左右子树高度差不超过1
左旋：从添加的节点开始向上找到第一个不满足平衡二叉树规则的节点作为支点，
支点的右孩子代替支点的位置，右孩子的左子树作为支点的右子树，支点变成右孩子的左子树
右旋：从添加的节点开始向上找到第一个不满足平衡二叉树规则的节点作为支点，
支点的左孩子代替支点的位置，左孩子的右子树代替支点的左子树，支点作为左孩子的右子树
红黑树（特殊的二叉查找树）：1.每一个节点不是黑色就是红色 2.根节点必须是黑色 3.叶子结点是黑色的 4.不能存在两个连续的红节点 5.每一个节点下的简单路径中黑节点数相同
添加操作（默认添加红节点）：
情况1.添加的是根节点 需要变黑色
情况2.添加的不是根节点，父节点为黑色 不需要操作
情况3.添加的不是根节点，父节点为红色，叔叔节点为红色
将父节点和叔叔节点都变成黑色，将祖父节点变成红色（如果祖父节点不是根节点），再判断祖父节点是否合理
情况4.添加的不是根节点，父节点为红色，叔叔节点为黑色，当前节点为左孩子
将父节点变成黑色，叔叔节点变成红色，以祖父节点为支点进行右旋
情况5.添加的不是根节点，父节点为红色，叔叔节点为黑色，当前节点为右孩子
将父节点作为支点进行左旋，再重新判断父节点是否合理
哈希表：jdk8之前是数组+链表;jdk8之后是数组+链表+红黑树
哈希值：对象的整数表现形式
没有重写hashCode方法（默认使用了地址值参与计算）,不同对象计算出的哈希值不同
重写了hashCode方法（使用属性值参与计算），不用对象只要属性值相同，计算出的哈希值就相同
存在不同属性值或者不同地址值计算出的哈希值相同的情况，哈希碰撞
添加操作（数组默认长度16，扩容因子0.75）：
通过哈希值&（数组长度-1）计算出元素的位置，判断该位置是否为null，为null直接存，
不为bull就判断是否相同，不相同放在原元素后面变成链表(jdk8之前是替代原元素位置，原元素向后移变成链表)，
当链表长度>8并且数组长度>=64时，链表转化为红黑树
集合中使用的是自定义对象时，要重写hashCode，equals方法，使其从判断地址值变成判断属性值是否相同。
HashSet: 无序 不重复 无索引
底层哈希表：jdk8之前是数组+链表;jdk8之后是数组+链表+红黑树
添加操作（数组默认长度16，扩容因子0.75）：
通过哈希值&（数组长度-1）计算出元素的位置，判断该位置是否为null，为null直接存，
不为null就判断是否相同，不相同则放在原元素后面变成链表(jdk8之前是替代原元素位置，原元素向后移变成链表)，
当链表长度>8并且数组长度>=64时，链表转化为红黑树
为什么存取顺序不一样：因为HashSet读取是从数组头依次遍历链表元素
为什么没有索引：存在链表结构，无法用数组的索引规定链表中具体元素的索引
去重机制：hashCode方法确定元素位置，equals方法比较元素属性值，因此当集合中使用的是自定义对象时，要重写hashCode，equals方法，使其从判断地址值变成判断属性值是否相同
LinkedHashSet: 有序 不重复 无索引
底层哈希表（数组+链表+红黑树）+双向链表
添加操作：同HashSet
为什么存取顺序一样：因为添加时额外生成一条双向链表，记录节点之间的前后顺序，读取时直接读这个双向链表
TreeSet: 可排序（默认从小到大） 不重复 无索引
底层红黑树
排序规则：
一.默认排序：（选，若无法满足需求则使用比较器排序）
1.整数类型、浮点数类型：直接比较
2.字符类型：按ASCLL码表中的顺序
3.自定义类型：需要自定义类实现Comparable接口，泛型为该自定义类型，并重写其中的compareTo方法，规定排序规则。不然会报错
@Override
public int compareTo(Student o){
//按照年龄升序
return this.getAge()-o.getAge();
}
二.比较器排序：创建集合时，自定义Comparator比较器对象，指定比较规则。
collection接口中包含的方法：
add() 向集合中添加一个元素（返回布尔类型）
clear() 清空集合中所有元素（返回void）
remove() 删除集合中的某一个元素（返回布尔类型）
contains() 判断集合中是否包含某一元素（返回值是布尔类型）
isEmpty() 判断集合是否为空（返回值是布尔类型，底层是判断元素个数是否为0）
size() 返回集合中元素的个数|集合的长度（返回值int类型）
ArrayList底层逻辑：数组结构
add过程：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//将元素e存到数组size的位置，size+1
return true;
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//若当前数组为空
return Math.max(DEFAULT_CAPACITY, minCapacity);返回默认数组容量与最小容量的大值赋值给minCapacity，
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//操作次数加1
// overflow-conscious code
if (minCapacity - elementData.length >0)//如果此时所需要的最小容量比数组长度大，数组需要扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//将数组长度赋值给老容量值
int newCapacity = oldCapacity + (oldCapacity >>1);//将老容量+老容量/2作为新容量值
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);//将原来的数组数据转移到扩容完成的数组中
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity< 0) // overflow
throw new OutOfMemoryError();
return (minCapacity >MAX_ARRAY_SIZE) ?//如果所需要的最小容量值比规定的大值大，新容量值就用更大的整数大值
Integer.MAX_VALUE ://反之则用数据大值
MAX_ARRAY_SIZE;
}LinkedList底层逻辑：双向链表结构
add过程：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Nodel = last;//将链表的最后一个结点last赋值给结点l
//创建一个新结点newNode,以l的地址值为prev值，以元素e作为element值,以null作为next值
final NodenewNode = new Node<>(l, e, null);
last = newNode;//将新结点赋值给last，作为链表的尾结点
if (l == null)//如果链表为空，将新结点赋值给first结点，作为头结点
first = newNode;
else//反之将结点l的指针指向新结点（next值改为newNode结点的地址值）
l.next = newNode;
size++;//链表长度+1
modCount++;//操作次数+1
}
private static class Node{
E item;//该结点的元素值
Nodenext;//该结点后一个结点的地址值
Nodeprev;//该结点前一个结点的地址值
Node(Nodeprev, E element, Nodenext) {
this.item = element;
this.next = next;
this.prev = prev;
}
} iterator底层逻辑：
public Iteratoriterator() {
return new Itr();
}
private class Itr implements Iterator{
int cursor; // 指针
int lastRet = -1; // 指针的上一个位置
int expectedModCount = modCount;//将集合的修改次数同步给迭代器
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//检查集合操作次数
int i = cursor;
if (i >= size)//如果指针所指位置超出集合大小，抛出没有元素异常
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//将集合重新赋值
if (i >= elementData.length)//如果此时指针超出集合长度，抛出并发修改异常
throw new ConcurrentModificationException();
cursor = i + 1;//指针后移
return (E) elementData[lastRet = i];//把指针的上一个位置赋值给lastRet并返回该位置的元素值
}
final void checkForComodification() {
if (modCount != expectedModCount)//如果此时集合修改次数与迭代器中修改次数不相等，抛出并发修改异常
throw new ConcurrentModificationException();
} 双列集合：
Map为顶层接口，下分实现类为HashMap、TreeMap，HashMap下分实现类为LinkedHashMap
Map集合特点：
每次存储都需要存一对数据，分为键和值；
一个集合中，键不可以重复，值可以重复；
键和值是一一对应的关系；
键和值合称为键值对，java中也叫做entry对象；
Map接口中的方法：
put() 集合中添加或者覆盖元素 （返回覆盖原键对应的值，若不存在相同的键则返回null）
remove() 删除该集合中的某个键值对 （返回删除键对应的值，类型由该值类型决定）
clear() 清空集合中的键值对（返回void）
containsKey() 判断集合中是否存在该键 (返回值为布尔类型，有就是true，没有就是false)
containsValue() 判断集合中是否存在该值 (返回值为布尔类型，有就是true，没有就是false)
isEmpty() 判断集合是否为空（返回类型为布尔类型，空为true，不空为false）
size() 返回集合中元素的个数|集合的长度 （返回类型为int类型）
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文标题：java集合（fromzero）-创新互联
文章出自：http://scyanting.com/article/gpipo.html
