66 java集合和泛型_16 _java集合类的原理总结

文章目录

• ​​一、Iterable接口​​
• ​​二、Collection接口​​
• ​​三、List接口​​

• ​​3.1ArrayList类【重点】​​
• ​​3.2linkedList 类【重点】​​
• ​​3.3Vector类​​

• ​​四、Set接口​​

• ​​4.1HashSet【重点】​​
• ​​4.2TreeSet【重点】​​
• ​​4.3LinkedHashSet​​

• ​​五、Map集合​​

• ​​5.1Entry类​​
• ​​5.2HashMap类【重点】​​
• ​​5.3TreeMap【重点】​​
• ​​5.4HashTable​​
• ​​5.5LinkedHashMap​​
• ​​5.6 Properties类​​

一、Iterable接口

定义了迭代集合的迭代方法

iterator()
forEach() 对1.8的Lambda表达式提供了支持

二、Collection接口

定义了集合添加的通用方法

int size();
boolean isEmpty();
boolean contains();
boolean add();
boolean addAll();
boolean remove();
removeAll();
Object[] toArray(); //等方法（可查看api学习）

三、List接口

• 有序、有下标、元素可重复

E get();
E set();
E indexOf();
int lastIndexOf();
ListIterator listIterator(); //等方法（可查看api学习）

3.1ArrayList类【重点】

线程不安全。

基于一个Object[]数组实现（底层就是一个数组），默认数组是个空数组，可以插入空数据，可以随机访问。如果要查找是否存在某个值，需要遍历数组匹配，时间复杂度是O(n)。由于通过存放的是动态数组，arrayList重写序列化方法readObject和writeObject，只序列化有值的数组位置。

transient Object[] elementData; //存放元素的数组

add(E e)添加元素方法： 会检查数组容量是否够存放新加的数据，判断如果不够存放就会进行扩容，首次扩容判断是否当前维护的数组是空数组，是的话初始化一个容量为10的数组，不是的话按照当前数组容量1.5倍扩容。

private static final int DEFAULT_CAPACITY = 10; //默认容量为10
/*
没有向集合添加元素时，容量为0，是一个空数组，
当添加任意一个元素后，就变成了10
每次扩容大小是原来的1.5倍
*/

transient Object[] elementData; //存放元素的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private int size;//实际的元素个数

//无参构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //空数组赋值为数组
}


//add() 方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!! 增加容量
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //（10，1）
}

ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// 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); //扩容1.5倍
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);
}

add(int index,E e)指定位置添加元素： 同样会检查容量，然后会基于system.arrayCopy数组复制将index位置开始的数据往后一位复制，最后将index位置的数据赋为e。

addList(Collection c) 添加一个集合，同样会检查容量，由于添加的是一个集合，1.5倍扩容可能不够存放即将存放的集合，这时判断不够存放，会将新数组的大小扩容为原数组大小加上c的大小。

remove(int index)方法也是基于数组复制，将index位置后面的数据往前一位复制，将index位置的数据顶掉。

foreach基于普通for循环实现的，建议用增强for循环效率高些。

3.2linkedList 类【重点】

线程不安全，有序的集合，按照插入顺序排序。

基于双向链表实现，查找数据的时候会判断index偏向尾节点还是头节点，偏向头节点则从头节点开始遍历查找，反之同样。通过空间换时间，查找时间复杂度o(n/2)。集合实现内部类node, 包含数据、指向上一节点的node对象和指向下一节点的node对象。集合维护起始节点和结束节点。

add(E e)方法 将现在的结尾节点下一个指向e,将e改为结尾节点，速度快。

transient int size = 0; //容量大小(节点个数)

transient Node<E> first;//链表的头节点

transient Node<E> last; //链表的尾节点

public LinkedList() { //无参构造
}

//add()方法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {

//获取最后一个元素
final Node<E> l = last;
//新创建一个节点，其尾结点为null
final Node<E> newNode = new Node<>(l, e, null);
//将last节点指向刚刚创建的新节点
last = newNode;
//如果此时集合为null，则令第一个节点也为该元素，否则就将这个元素的下一个节点设置为新创建的节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++; //节点数量增加
modCount++;
}
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;
}
}

add(int index,E e)指定位置添加元素

//LinkedList支持指定的索引处增加节点
public void add(int index, E element) {
//检查传入的索引是否符合要求
checkPositionIndex(index);
//如果这个索引是最后一个节点，则直接添加
if (index == size)
linkLast(element);
else
//否则
linkBefore(element, node(index));
}
//返回了指定下标的Node
Node<E> node(int index) {
// assert isElementIndex(index);
//如果此时的下标小于节点的一半，相当于一个二分查找的方法，
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//将需要插入的元素进行插入
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

/*
实现的思想可以归结为：每一次的插入或者移除，都是通过node()方法获取指定的Node节点，然后通过linkBefore或者linkLast这些方法来具体进行链表的操作。
/*

remove(int index) 需要先找到这个位置的节点花费o(n/2)，移动指针将该位置的节点e的上一个节点的next指向e的下一个节点，e的下一个节点的prev指向e的上一个节点。

3.3Vector类

线程安全，类似ArrayList加上了同步。

（底层也是一个数组）与ArrayList类似也是维护一个数组，但是Vector操作数组的方法都在方法上加上synchronized进行同步处理。

向量集合

底层是一个Object[]数组，初始容量为10，数组容量不够的时候自动扩容为原来的一倍

protected Object[] elementData; ///存放元素的数组

public Vector() { //初始容量为10
this(10);
}

int oldCapacity = elementData.length; //数组容量不够的时候自动扩容为原来的一倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);

四、Set接口

• 无序，无下标，元素不可重复（底层均为Map集合实现）

4.1HashSet【重点】

存储结构是哈希表（数组+链表+红黑树（jdk1.8之后））

底层基于​​HashMap​​，hashSet就是基于hashMap实现的，创建hashSet底层就是创建一个hashMap,存放数据基于hashMap的key不能重复，map的value存放一个固定的对象。hashSet的遍历就是基于hashMap的key集合进行遍历。(具体实现可看下面的 HashMap)

线程不安全，用于让存放的数据去重。

无序，无下标

private transient HashMap<E,Object> map;

//无参构造
public HashSet() {
map = new HashMap<>();
}

//add()方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

4.2TreeSet【重点】

存储结构是红黑树（平衡二叉查找树）

线程不安全

底层基于​​TreeMap​​，具体实现可看下面的 TreeMap

private transient NavigableMap<E,Object> m; //存放生成的TreeMap集合

// 作为值添加到TreeMap中，即每一个Entry的键不同但值相同，都是一个对象的地址
private static final Object PRESENT = new Object();

TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}

//无参构造
public TreeSet() {
this(new TreeMap<E,Object>());
}

//add()方法
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}

4.3LinkedHashSet

底层基于​​LinkedHashMap​​ 实现，通过LinkedHashMap中的方法实现了顺序存值。具体实现可看下面的LinkedHashMap

public LinkedHashSet() {
super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

五、Map集合

• 键值对的形式存储结构 ，键不可重复，无序，无下标

int size();
isEmpty();
containsKey();
containsValue();
get();
put();
remove(;
keyset();
values();
entrySet(); //等方法（可查看api学习）

5.1Entry类

• Map类的内部类，存储的就是键值对，用来获取所有的键值

5.2HashMap类【重点】

无序的

线程不安全，key value形式的集合。

JDK7和JDK8的区别是resize的方式不同（尾插法和头插法），hash冲突处理方式也不同，jdk7就是单纯的链表，JDK8链表长度大于等于8，并且数组元素个数大于等于64的时候，会转成红黑树，小于等于6时再退成链表。

hashmap基于数组和链表实现（jdk8加上了红黑树），数组默认容量是16，负载因子是0.75，当容量（总节点数）大于等于16 * 0.75=12时会发生扩容（扩容大小为原来的一倍），扩容的方式是创建一个新数组，将老数组的值都重新计算hash值存放进去。

hashmap通过与数组容量减1相与进行位运算，即hash % size = hash & size-1，实现和数组容量取余相同的效果，位运算性能会更好，但是也要求了数组大小是2的幂，如果不是2的幂减1就不是全是1的二进制数。如果创建hashMap指定的容量不是2的幂，会自动替换成大于这个容量的且最近这个容量的2的幂，比如设置9则会自动替换成16。

put（）方法，hashmap通过hash算法计算key的hashcode值，再与数组容量减1相与，得到数组下标，如果该数组下标没有存在数据，则直接存放进去，如果该位置已经存在数据，则以链表的形式将该位置的数据连接起来，jdk8在链表长度大于等于8，并且数组元素个数大于等于64的时候，会将链表转换成红黑树。在容量超过 容量*负载因子 时，会发生扩容，jdk7和jdk8扩容的方式不同。新数组冲突数据jdk7使用的是头插法和jdk8是尾插法，jdk7头插法会导致死循环。

jdk7的头插法，jdk8的尾插法，简单来说就是：当元素被放入时，通过计算要放在链表中，（头插法就是将该元素放在这个链表中第一个元素的前面，而尾插法就是将该元素放在这个链表中最后一个元素的后面）。

jdk8虽然通过尾插法解决了死循环的问题，但是hashMap追求的是高性能，并没有对共享变量做安全控制，在多线程环境下肯定会出现变量被覆盖，并发修改某个位置的值造成数据丢失各种问题，因此如果是多线程环境，要用concurrentHashMap。

get方法：通过计算key的hash值取余得到对应数组位置，取出该位置的数据并比较hash值,和==比较或equals比较，比较相同则返回，不同则判断是树节点还是普通节点，树节点通过遍历树节点判断，普通节点则遍历链表判断。

首次创建不会分配数组，put数据的时候发现为空才创建数组。

为什么设置成8转红黑树，因为红黑树查找平均时间复杂度为log(2)N，链表遍历平均是N/2,8以下的查找效率差不多，但是链表的插入效率会好很多，链表插入是o(1),红黑是树是log(2)N。为什么设置6转链表，与上面同理，不设置7是防止map频繁增加和删除，频繁转换节点结构。

5.3TreeMap【重点】

线程不安全

实现了有序

TreeMap是一个的有序的key——value集合，基于存放数据进行比较排序，继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口

底层由红黑树实现，不可以存放NULL。

构造函数可以接收一个Comparator比较器，用于自定义比较方法，如果没有设置Comparator则通过类本身实现的Comparable进行元素比较（如果类没有实现Comparable转换就报错了）。

get()方法，自上而下比较节点（二叉查找树规则）

put()方法先查找应该存放的位置，存放后校验是不是符合红黑树特性，不符合则进行变色旋转调整。

remove()方法，寻找到替换节点，将替换节点替换掉删除节点，然后判断被删除的节点是不是黑色，如果是的话说明此时红黑树已经不满足特性，需要旋转和变色重新调整树结构。

5.4HashTable

线程安全，与hashMap类似，但是方法上都加上了syschronized同步，不可以存放NULL。

默认大小11，总节点数（包含链表中的节点）超过容量*负载因子则扩容，扩容两倍+1扩容。基于数组和链表实现，类似jdk7 hashMap。

插入数据采用头插法。相同位置的节点，先进的会在链表后面。

5.5LinkedHashMap

继承hashMap,线程不安全。

有序的hashMap，

实际上存储还是和hashMap一致，但是底层类似LinkedList维护多一个双向链表用于保存节点的顺序，支持两种排序，一种是按照插入顺序排序成员变量accessOrder=false，一种是按照访问顺序排序成员变量accessOrder=true（访问顺序包括查询节点和修改已存在的key的节点，都会修改该节点的位置），默认accessOrder=false，即按照插入顺序排序。

内部封装了一个Entry，继承了HashMap的Node类，封装多了两个参数，before和after用于指向节点前后的数据（跟hashMap的Node节点的next不一样，next是存储hash冲突后链表的下一个节点，befor和after是全局的节点顺序）。代码如下：

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);
}
}

put方法，使用hashMap的put方法，但是重写了put方法调用到的几个方法，newNode、newTreeNode、afterNodeAccess、afterNodeInsertion。

newNode方法的改动：创建Node改为创建Entry。linkedHashMap内部维护两个成员变量，Entry head和 Entry tail，用于存放头节点和尾节点，创建第一个节点会设置成head和tail为该节点，之后每创建一个节点会修改尾节点tail为当前的节点，旧的尾节点after设置为当前节点，新的尾节点before设置成旧的尾节点。即head-><-node1-><-node2-><-tail,通过双向链表将所有节点连接起来。

newTreeNode方法和newNode加上一样的操作。（newNode是创建普通节点，newTreeNode是创建树节点）。

afterNodeAccess方法：hashMap在插入节点的时候如果当前的key已经存在会修改当前key对应的value，修改value后hashMap会调用afterNodeAccess方法。这个方法在hashMap中是一个空方法，LinkedHashMap实现了这个方法。在这个方法中判断如果accessOrder=true并且当前节点不是尾节点，则会将该节点移动到尾节点。具体操作就是移动该节点的前后节点的指针，把指向当前节点的after和before互连，然后把该节点替换成尾节点，旧的尾节点after指向该节点。（即按照访问顺序排序才会移动已存在的key节点）

afterNodeInsertion方法（用于给子类实现LRU）：hashMap在put方法的最后会调用这个方法，同样hashMap没有实现，LinkedHashMap实现了。但是在LinkedHashMap里面这个方法是没有任何意义的，这个方法的作用是移除头节点，但是移除前会调用removeEldestEntry方法判断要不要移除，LinkedHashMap这个方法固定会返回false，也就是永远不会移除。这样设计的目的是，如果开发者想要实现一种机制，当集合的总数达到一定数量后，把最早插入的节点移除或者把最近最少访问的节点移除(也就是移除头节点)，那么继承LinkedHashMap并重写这个方法就可以了，开发者可以在里面自定义策略返回true和false。

remove方法调用hashMap的remove,remove方法调用了afterNodeRemoval，LinkedHashMap实现这个方法删除双向链表中该节点。

get方法,LinkedHashMap自己实现了这个方法，获取节点和hashMap一样，加了一步判断accessOrder=true会把该节点移动到双向链表尾部。

entrySet遍历集合，封装了个内部迭代器，通过遍历双向链表实现。

5.6 Properties类

Java配置文件中用的居多

可以直接通过load方法加载配置文件，通过store方法存储配置文件

泛型锁定，为两个String类型

【文章转自防cc http://www.558idc.com/gfcdn.html 复制请保留原URL】