Java的第一遍学习笔记 Collection集合

Collection集合

Collection接口由两个重要的子接口 List和Set，实现子类都是单列集合。

集合体系图

Collection常用方法（以ArrayList演示） 

Collection常用方法对于Collection以及下属子类都可以用。

1. add: 添加单个元素

        ArrayList a = new ArrayList();
        a.add(10); //注意放入的是Integer类，其余同理
        a.add(true);
        System.out.println(a); // [10, true]

2. remove：删除指定元素

3. contains：查找元素是否存在

4. size：获取元素个数

5. isEmpty：判断是否为空

6. clear：清空

        a.remove(true);
        System.out.println(a); // [10]
        System.out.println(a.contains(10)); //true
        System.out.println(a.size()); // 1
        System.out.println(a.isEmpty()); //false
        a.clear();

7. allAll：添加多个元素(Collection集合)

8. containsAll：查找多个元素是否都存在

9. removeAll：删除多个元素

        ArrayList a = new ArrayList();
        ArrayList b = new ArrayList();
        b.add(20);
        b.add(30);
        a.addAll(b);  //只能添加集合类
        System.out.println(a.contains(b));
        a.removeAll(b);

遍历方式

1. 使用Iterator迭代器

Iterator iterator = a.iterator(); //得到一个集合的迭代器

// hasNext() 判断是否还有下一个元素
// next() 1.将迭代器下移 2.将下移后迭代器指向位置上的元素返回（刚开始在第一个元素上面一格）

   迭代器while循环的构造快捷键—— itit

    public static void main(String[] args) {
        ArrayList a = new ArrayList();
        for(int i = 0;i<10;i++){
            a.add(i+10);
        }
        Iterator iterator = a.iterator(); //迭代器构造方法
        while (iterator.hasNext()) { //快捷键:itit
            Object obj =  iterator.next();
            System.out.println(obj);
        }
        //当while循环结束时,iterator指向最后一个元素
        iterator = a.iterator(); //重置迭代器
    }

2. 增强for循环(foreach)

  增强for循环的底层仍然是迭代器，因此可以理解成简化版本的迭代器遍历。快捷键：I 或者  集合名.for(推荐)。

  也可以对数组使用。

    public static void main(String[] args) {
        ArrayList a = new ArrayList();
        for(int i = 0;i<10;i++){
            a.add(i+10);
        }
        for (Object obj : a) {
            System.out.println(obj);
        }
    }

List集合 常用方法

注意这是List集合独有的方法，并且一旦涉及到范围(比如subList方法)，总是左闭右开的。

List不能单独声明，需要用到List的实现子类。

        List a = new ArrayList();
        List b = new linkedList();
        List c = new Vector();

注意事项 

1. ArrayList 可以加入多个null。

2. ArrayList 是由数组来实现数据存储的。

3. ArrayList 基本等同于Vector，但ArrayList是线程不安全的（没有synchronized）,在多线程情况下，不建议使用ArrayList。

ArrayList底层结构

1. ArrayList 中维护了一个Object类型的数组elementData。

trannsient Object[] elementData; // transient 表示瞬间，短暂的，表示该属性不会被序列化

2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍。

3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。

ArrayList底层源码 

   如果数组为初始分配数组，那么就返回最小需求容量和10之间的最大值（注意有初始化参数的并不是DEFAULTCAPACITY...这个数组）。否则返回最小需求容量。 

1. modCount 记录集合被修改的次数  2. 如果elementData的大小不够(目前的长度小于最小需求容量)，就调用grow方法去扩容。

     private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; //原先数组的长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);  
                        // >>1表示/2，把原数组长度*1.5，赋给newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //针对第一次，newCapacity为0（0 + 0*0.5），此时minCapacity为10
        if (newCapacity - MAX_ARRAY_SIZE > 0) 
                                    //如果超过了系统最大容量，用hugeCapacity判断
            newCapacity = hugeCapacity(minCapacity); 
        elementData = Arrays.copyOf(elementData, newCapacity); 
                                         //用Arrays类的copyOf方法（空余位置为null）
    }

扩容后Debug时看不到数组的null？把 Hide null elements in arrays and collections 和 Enable alternative view for Collections classes去掉。

Vector 基本介绍 

ArrayList和Vector比较 

linkedList

注：linkedList维护的双向链表没有头结点，第一个就是首元结点。remove方法默认删除第一个结点。里面的元素是linkedList类里定义的Node。

遍历方法有：迭代器，增强for与普通for循环。 

    public static void main(String[] args) {
        linkedList a = new linkedList();
        Iterator iterator= a.iterator();
        while (iterator.hasNext()) {  //迭代器
            Object next =  iterator.next();
            ...;
        }
        for (Object o : a) {  //增强for
            ...;
        }
        for(int i = 0;i

 初始化源码：

    void linkLast(E e) {
        final Node l = last; //保存尾指针
        final Node newNode = new Node<>(l, e, null); 
                                       //三个参数分别对应prior,data,next
        last = newNode; //更新尾指针
        if (l == null)
            first = newNode;  //如果原先尾指针为null，说明newNode为第一个结点，修改first
        else
            l.next = newNode; //否则把新结点接在最后一个结点后面
        size++;
        modCount++;
    }

ArrayList和linkedList比较 

set接口 基本介绍 

     注：取出的顺序是固定的，不会变。遍历方法：迭代器，增强for，不能用for循环因为没有索引，也没有get方法。   用HashSet演示。

HashSet

底层是HashMap   使用 Hash + equals 方法

    public HashSet() {
        map = new HashMap<>(); //创建一个HashMap
    }

HashSet的add方法大概思路：

   1. 先获取元素的哈希值(hashCode方法)  2. 对哈希值进行运算，得出一个索引值即为要存放在哈希表中的位置号。 3. 如果该位置上没有其他元素，则直接存放。4. 如果该位置上已经有其他元素，则需要进行equals判断，如果相等则不再添加。如果不相等，则以链表形式添加。  

其中PRESENT是一个Object对象，只起到占位的作用。

    key是输入的关键字，value就是PRESENT。hash方法计算出key的哈希值，注意并不是简单调用了hashCode方法，而是与 h>>>16进行了异或，计算的伪哈希值，最终在putVal方法中用 按位与 计算出索引。

 重点是理解 putVal这个方法，源码自己去看，这里只写说明。resize方法用于修改Node数组大小。afterNodeInsertion(evict) 无实际用处，是留给子类实现的方法。

    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;  
        //table是HashMap的属性，是放Node的数组。
        //刚开始table为null，resize对tab初始化，扩容到16个空间
        if ((p = tab[i = (n - 1) & hash]) == null) //计算出真正的索引，把对应位置赋给p
            tab[i] = newNode(hash, key, value, null); //如果p为空，说明没有元素，直接放
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        //准备添加的key的hash值与当前索引位置对应链表的第一个元素hash值相同。
        //并且满足下面两个条件之一:1. 准备加入的key和p指向的Node结点的key是同一个对象
                            2. p指向的Node结点的key的equals和准备加入的key比较后相同
        // 此时不能加入
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        // 如果p是红黑树，那么调用putTreeval方法加入
            else {
        // 最后一种情况，找链表 
        // 依次和该链表的每一个元素比较后，都不相同，则加入到该链表的最后
     //注意在把元素添加到链表后，立即判断该链表是否已经达到8个结点，如果已经达到，就调用treeifyBin()对当前这个链表进行树化(转成红黑树)   在转成红黑树时，要进行判断 if(tab == null || (n=tab.length)= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
         // 一次和该链表的每一个元素比较过程中，如果有相同情况，就直接break
                    p = e;
                }
            }
            if (e != null) { // 说明有重复元素
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue; //add失败(不是null)
            }
        }
        ++modCount; //记录修改次数
        if (++size > threshold) //threshold在resize方法中，是表的临界值(初始12)
            resize(); //扩容
        afterNodeInsertion(evict);//留给子类实现的方法，对HashMap来说是个空方法
        return null;//返回空 成功
    }

重写判断是否加入的方法

需要重写Employee类的equals方法和hashCode方法（直接输入equals）

注意这样生成的方法就是重写后的方法，不用更改。

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name);
    }

    @Override
    public int hashCode() { 
        return Objects.hash(name, age); //name,age等属性都被塞进一个object数组里
    }

       如果类里面有别的类属性(比如A里面有B类的对象)，那么B里面也要重写equals和hashCode方法 

linkedHashSet 

（结点应该放在绿色框里，这里画的不清楚）

1. linkedHashSet 加入顺序和取出元素的顺序一致。

2. linkedHashSet 底层维护的是一个linkedHashMap（是HashMap的子类）

3. linkedHashSet 底层结构—— 数组table + 双向链表

4. 添加第一次时，直接将数组table扩容到16，数组table是 HashMap$Node[]类型，但存放的结点类型是 linkedHashMap$Entry（多态），是Node的子类（可以从左下角的structure查看）

    static class Entry extends HashMap.Node {
        Entry before, after;
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }