Java集合-基础+源码分析

	以下分析学习内容仅是个人的学习总结，都是Java集合的**基础**内容，若有错误遗漏，欢迎指正，大家一起学习。环境为 jdk8，idea2020.3。

集合

一、相对数组等数据结构：
·动态保存
·提供了一系列方便操作对象的方法：add、remove、set、get等
·使用集合添加、删除新元素比较方便，代码简洁。

二、集合的框架体系

interable
	collection
		list
			arraylist
			linkedlist
			vector
		set
			hashset
			linkedhashset
			treeset
map
	hashmap
	linkedhashmap
	hashtable
	properties
	treemap

（1）、collection接口

方法
	add()：添加单个元素
	remove()：删除指定元素
	contains()：查找元素是否存在
	size()：获取元素个数
	isEmpty()：判断是否为空
	clear()：清空
	addAll()：添加多个元素
	containsAll()：查找多个元素是否存在
	removeAll()：删除多个元素

（2）、如何遍历集合中的元素

	1、使用iterator（迭代器）
		（1）、每个实现了collection接口的类都有Iterator方法，会返回一个interator对象，该对象可以遍历集合中的元素。 
		Iterator
			hashnext()
			next()
			remove()
			forEachRemaing()

		（2）、while遍历
			 while (iterator.hasNext()) {
       				 Object next =  iterator.next();
       			 }

		（3）、当一次遍历结束后，iterator迭代器的指针指向最后元素的位置，如果再次遍历，需要重置迭代器。没有重置执行next()会出NoSuchElementException。
		Iterator iterator = 集合.iterator();

	2、for循环增强
	for（元素类型 元素名：集合名或数组名）{
	}
		（1）、底层还是调用iterator迭代器，简化版的迭代器

（3）、List接口

	1、List集合中元素有序、可重复。
	2、元素有索引，支持索引。
	3、可以根据元素的序号直接对元素进行操作。
方法
	void add(int index, Object ele)
	boolean addAll(int index, Collection eles)
	Object get(int index)
	Object set(int index, Object ele)
	int indexOf(Object obj) 返回首次出现的位置
	int lastIndexOf(Object obj) 返回末次出现的位置
	Object remove(int index) 删除指定元素并返回该元素
	List subList(int fromIndex,int toIndex) 返回字串，前闭后开

遍历方式
	1、迭代器iterator
	2、for循环增强
	3、普通for循环

（3.1）、ArrayList

ArrayList
	1、arrayList 允许空值、多个控制null
	2、arrayList 底层实现为数组
	3、arrayList **线程不安全**，但执行效率高； Vector线程安全。
	

ArrayList 的底层结构：
	1、ArrayList 维护了一个Object类型的数组elementData。
		transient Object[] elementData；
	2、创建ArrayList 对象，使用无参构造器创建时，elementData初始容量为0，第一次添加扩容到10，之后需要再次扩容，会扩容到1.5倍。
	3、使用指定大小的构造器创建时，elementData初始容量为指定的大小，之后需要扩容会扩容到1.5倍。

========================================================================

ArrayList 的底层实现过程：
（1）、add（）
（一）、以无参构造器创建对象
创建空的Object类型的elementData[]数组，第一次add方法执行，首先将当前的minCapacity（目前需要的最小空间，size+1）和DEFAULT_CAPACITY（常量10）进行比较，选出最大值作为第一次扩容的大小（第一次扩容的大小为DEFAULT_CAPACITY=10决定的）。之后执行grow方法进行扩容，使用Arrays.copyOf()扩容复制到elementData数组，最后执行elemetData[size++] = e 赋值。扩容完成。
使用Arrays.copyOf()能够保存之前存在的数据。modCount记录对集合对象的操作次数。

+
（二）、有参构造（指定大小）创建对象
除了创建elementData数组的大小不同，其他与无参构造的过程大致相同。

========================================================================

（3.2）、Vector

	特性：底层也是Object类型的elementData数组，无参构造默认大小为10，之后扩容都为2倍。
	线程安全，每个方法都有synchronized修饰，但是效率不够ArrayList高。

·扩容方法：

（3.3）、linkedList

++++++++++++++++++
（3.3.1）、底层结构
·底层为双向链表+双端队列
·元素可重复、可为null、可添加任意元素。
·线程不安全。
++++++++++++++++
（3.3.2）、底层操作机制
·底层维护一个双向链表
·linkedList中维护了两个属性 first 和 last 分别指向头节点和尾节点，每个节点又维护了三个属性：prev、next、item。
·linkedList 元素的添加和删除，效率较高。
+++++++++++++++++
（3.3.3）、底层源码
·无参构造创建对象
linkedList list = new linkedList();

·add()方法
首先会对传入的参数进行装箱（如果需要的话）
执行 linkLast（）方法，将元素添加到表尾。

   void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

·remove（）方法
linkedList的remove（）方法会删除链表中的首节点；

public E remove() {
        return removeFirst();
    }

 public E removeFirst() {
        final Node f = first;
        if (f == null) //当链表为空链表时，报错
            throw new NoSuchElementException(); 
        return unlinkFirst(f);
    }

 private E unlinkFirst(Node f) {
        // assert f == first && f != null;
        final E element = f.item; //取出首节点的item，返回
        final Node next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

+++++++++++++++++++++
（3.3.4）、遍历
·迭代器
·增强for循环
·普通for循环
+++++++++++++++++++++

————————————————————————————————————————————
（4）、ArrayList 和 linkedList 如何选择
增删：linkedList
改查：ArrayList

（5）Set

	1、无序，没有索引。
	2、元素不可重复，null 只能有一个。
	3、遍历可以使用：迭代器iterator、增强for循环。

（5.1）HashSet 源码分析

（一）、构造器创建对象
底层为hashmap实现

  public HashSet() {
        map = new HashMap<>();
    }

（二）、add方法
* 注意add方法如何排除重复元素
* 注意hashcode的形成

//执行HashSet
  public HashSet() {
        map = new HashMap<>();
    }

//在add方法执行之前，如需要会先对元素进行装箱操作，对象为Object或者其子类

//执行add()
private static final Object PRESENT = new Object(); //主要的作用是 占位，因为HashSet底层是用HashMap实现的，的形式中Value被固定设定为PRESENT这个常量，Key即存储Set中的元素。
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

//
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        //key==null，hash为0；
        //key！=null，hash为h^(h>>>16).如何理解？
        //源码注释：计算 key.hashCode() 并将散列的较高位（异或）传播到较低位。
        //我的理解是：由于在计算index时，是使用（n-1）&hash的方式，所以index的值就只取决于hash值的低位，而计算hash值时，通过h^(h>>>16)，
        //将高位和低位进行异或，将高位的散列扩散到低位，就让hash值不仅仅是靠低位来决定，也有高位来进行干预。所以说：将散列的较高位异或传播到较低位。
        
    }
    
//这里示范进入的是Integer的hashcode方法，整形的hashcode就是自身。
@Override  
    public int hashCode() {
        return Integer.hashCode(value);
    }

//核心，计算index，然后赋值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;//临时辅助变量tab、p、n、i
        //table是HashMap中的一个属性，类型为 Node[]
        //如果当前table为null或者table大小为0，则进行第一次扩容，默认大小为16.
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
      //(1)根据key的hash值与table表的长度-1（16-1）进行&运算，获取index
      //(2)如果当前位置为null，则直接newNode传入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
      //当前位置不为空，进入else
        else {
            Node e; K k;
            //如果准备添加的元素的hash值与当前索引位置对应的链表的第一个元素的hash值相同，并且两者的key相同或者两者的key.equals，则不会添加新元素
            if (p.hash == hash && //这里有个疑问？到这步两者的hash值不是一定相同的吗？
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断当前索引的节点是不是红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            //不是红黑树，则是一个链表。
            //for循环依次与该链表的元素比较hash值和key，都不同就会添加到链表尾部，添加后会判断当前的链表的长度是否到达8个，是则会执行treeifyBin（）转化红黑树（但是在treeifyBin（）中会判断当前table的数组长度是否已经大于等于64，是则会转化，不是则会进行扩容连解决链表长度的问题，不会转化）。
            //
            else {
                for (int binCount = 0; ; ++binCount) {//死循环，要么添加，要么比较后相同不添加
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st；TREEIFY_THRESHOLD =8
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //threshold为resize()中的一个属性，用于hashmap的扩容缓冲，为12
        //threshold = newThr;
        //newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        //DEFAULT_LOAD_FACTOR =0.75; DEFAULT_INITIAL_CAPACITY=16.
        //***size=12 是指添加Node到HashSet的次数，而不是添加到table数组的次数。***
        if (++size > threshold) 
            resize();
        afterNodeInsertion(evict);//该方法时专为hashmap子类使用的
        return null;
    }

（三）、HashSet扩容和红黑树转化机制

（5.2） linkedHashSet

	·是HashSet 的子类。
	·底层实现是linkedHashMap ，底层维护了一个数组 + 双向链表。链表中维护了before、after等属性。
	·数组类型为 linkedHashMap$Node[]  ，但是数组中存放的元素/数据类型为 linkedHashMap$Entry 类型：static class Entry extends HashMap.Node ，该类型为linkedHashMap 的静态内部类，是HashMap.Node的子类。目前来看，Entry类型的作用是新增Entry before、after属性。
	·添加元素的顺序和双向链表中存储元素的顺序是一致的。（全部元素根据添加顺序组成一个双向链表，所以遍历顺序和插入顺序是一致的）

（5.2.1）源码分析

//无参构造
//add（）方法
//与hashset的add方法是一致的。
//但是hashset和linkedhashset的主要区别是什么呢？
//
public linkedHashSet() {
        super(16, .75f, true);
    }
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new linkedHashMap<>(initialCapacity, loadFactor);
    }

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

关于linkedHashMap和HashMap中的Entry
1、linkedHashMap中使用到的Entry是一个内部类，作用应该是新增节点的before、after属性，满足双向链表的顺序插入。
2、HashMap中使用到的Entry是一个接口，实现了存储key，value 的一种形式和操作方法。作用应该是方便遍历map中的元素，它封装了对key，value进行操作的方法。
为什么方便？
我理解的是：在EntrySet中存储的是Entry类型的数据，但是是Node类型通过多态向上转型而存储在Entry类型中……

(6) Map

	map接口特点：
	1、保存具有映射关系的数据：键值对

Java集合-基础+源码分析

Java相关栏目本月热门文章