迭代器

/*Itr迭代器通常使用fail-fast中断处理机制*/
    
/*判断如何发生其他进程修改集合*/

private class Itr implements Iterator<E> {
        
        int cursor = 0;

        int lastRet = -1;

    	// 这里是核心：modCount是当前集合的修改次数，expectedModCount用于迭代器记录当前修改次数
        int expectedModCount = modCount;

    	// 我们会使用hasNext和next方法进行迭代器foreach
        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                // 注意：我们在每次处理时，都会调用一次checkForComodification()来判断expectedModCount = modCount？
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

    	// 当modCount != expectedModCount就说明有集合发生了变化，我们就会直接抛出异常
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

/*COWIterator迭代器采用的fail-safe处理方法*/

static final class COWIterator<E> implements ListIterator<E> {
        
    	// 这里就是核心：snapshot用于储存当前集合的所有元素
        private final Object[] snapshot;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
    
    	// 源码我没有找到，大致意思就是：
    	/*
    	COWIterator对应集合当进行add添加时
    	我们首先直接采用getArray获得snapshot里面的元素，采用geiSize获得原集合的大小
    	然后根据size直接创建一个新的集合，并将snapshot的元素复制进去，再将修改内容修改到新集合中
    	同时COWIterator遍历旧集合，两者之间互不影响
    	*/
    }

/*ArrayList底层*/

ArrayList底层是采用数组完成的

/*ArrayList创建*/

当无参创建时，ArrayList会默认创建一个长度为0的数组
    
当有参创建时，ArrayList会默认创建一个长度为10的数组
    
/*ArrayList扩容阈值add*/
    
ArrayList的第一个阈值为10，每次扩容就会扩容当前阈值的1.5倍
    
扩容值计算：首先将当前阈值位运算向右一次，然后将当前阈值加上刚刚运算的数即可
    
当无参构建时，长度默认为0，当add第一个元素后，会自动扩容到第一个阈值10
    
当超过阈值10时，这时会默认扩容到第二个阈值15
    
/*ArrayList扩容阈值addAll*/
    
addAll方法会一次添加多个数据
    
当采用addAll时的扩容阈值更新规则如下：
    - 每次扩容，都会选择下一个阈值点或者该集合存储数据的数量的最大值
    - Math.max(ArrayList.nextInt,ArrayList.capticy)
    
我们给出一个简单例子；
    - 当无参构造：addAll（1，2，3）这时阈值更新为下一个阈值10
    - 当无参构造：addAll（1，2，3，4，5，6，7，8，9，10，11），这时阈值更新到添加后集合的最大值11
    
    - 有参构造：目前已有10个元素，addAll(1,2,3)，更新到下一个阈值15
    - 有参构造：目前已有10个元素，addAll(1,2,3,4,5,6)，更新到添加后最大阈值16
    
/*ArrayList扩容具体步骤*/
    
ArrayList扩容步骤：
	1.首先新创一个新数组，数组大小就是扩容大小
    2.采用Arrays类的CopyOf()方法，将原数据移动到新数组中，再进行新的add或addAll方法

/*ArrayList特点*/

1.基于数组，需要连续空间
2.随机访问快（根据下标访问）
3.尾部插入，删除性能快，其他部分插入删除会移动数据，性能慢
4.可以利用CPU的空间局部性原理，加快速率
    
这里提出一点：ArrayList继承了RandomAccess类，该类只是一个标识类，但当其继承该类后表示可以采用下标进行数据查询
    
/*LinkedList特点*/
    
1.基于双向链表，无需连续空间
2.随机访问慢，需要遍历链表
3.头尾插入速率快
4.占用内存较多

/*HashMap组成*/

首先由一个数组h[]组成
    
每个数组上都是一个链表，链表具有e[],next[]两个数组组成，分别代表当前值，下一个值
    
HashMap的默认长度首先为16，当出现特定情况时就会进行扩容
    
当链表过长时，就会转化为红黑树来优化

/*HashMap操作*/
    
put插入操作：
    1.通过hashCode()获得一次hash
    2.通过hash()获得二次hash
    3.将二次hash & (桶Size - 1) ；其实就是mod然后得到余数
    4.将数据放入即可
    
查找操作：
    1.通过hashCode()获得一次hash
    2.通过hash()获得二次hash
    3.将二次hash & (桶Size - 1) ；其实就是mod然后得到余数
    4.在指定位置进行查询，通过链表查询，通常复杂度O(1)

/*HashMap组成结构*/

1.7： 数组 + 链表
    
1.8： 数组 + （链表/红黑树）
    
/*简单问题*/
    
// HashMap扩容条件
    1.当插入数据大于桶Size的0.75时
    2.当链表长度大于8，且桶Size长度小于64时，采用HashMap扩容希望减小链表长度
    
// 红黑树出现条件
	1.当链表长度大于8时，为了减少链表长度进行操作
    2.但是当桶Size < 64,会优先进行HashMap扩容来优化链表长度；当桶Size >= 64时，才会进行红黑树转换
    3.注意：当链表长度为8，再添加时，只会执行上述的一种，倘若桶Size扩充后链表并未分散开，也不会有其他操作
    
// 红黑树退化为链表条件
    1.当进行扩容时，如果拆分树后，该树的节点小于等于6，就会退化
    1.在删除操作前，做判断：该树root，root.left,root.right,root.left.left 任意一个 == null，就转化为链表
    2.注意是操作前：假如我们本次操作删除了root.left.left,并不会导致退化，而是在下次remove操作时才会进行退化
    
/*链表和红黑树问题*/
    
// 为什么要采用红黑树？
	红黑树一般用于避免Dos攻击，防止链表过长性能下降，出现数化为偶然状况
    
// 为什么最开始使用链表，后续才使用红黑树？
	当链表长度较短时，链表查询复杂度为O（1），红黑树查询复杂度为O（log2 n）
	红黑树所占用的内存空间相对而言比较大，耗费过多
    
// 红黑树出现阈值为什么为8？
	因为当hash值较为随机时，hash表按破损分布，当负载因子为0.75时，长度超过8的概率仅有亿分之六，这里是为了让树化几率足够小
    
/*hashCode问题*/
    
// 索引如何计算
    首先我们都需要采用hashCode（）获得一次hash，然后采用hash（）获得二次hash
    
    1.在我们的视角里：hash值 % 桶Size
    2.在计算机视角里：hash值 & （桶Size - 1）
    
// 采用hashCode（）获得后，为什么还需要hash（）方法二次计算
    hash方法可以帮助我们综合高位数据，让哈希分布更加均匀
    
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

// 数组容量为什么是2的n次幂
	计算索引时，我们可以采用位运算来代替正常mod，来增加速率
    扩容时，我们会根据扩容2倍，这时我们可以根据当前值的hash & oldCap == 0来判断是否需要移动
    若为0不需要移动，若不为0，移动至 旧位置 + oldCap
        
    其次其实前面的hash，hashcode等操作都是为了配合容量为2的n次幂的优化手段
        
/*PUT方法流程版本*/
        
// PUT方法统一流程
	1.HashMap是懒惰创建数组，只有首次使用才会创建数组
    2.计算索引（桶下标）
    3.如果桶下标还没有人占用，创建Node占位返回
    4.如果桶下标已有人占用
        - 已经是TreeNode，走红黑树的添加或更新逻辑
        - 是普通Node，走链表的添加或更新逻辑，若超过树化阈值，走树化逻辑
    5.返回前检查容量是否查过阈值，一旦超过进行扩容（注意：这里是先将数据添加到数组中，然后再进行扩容处理）
        
// 版本不同流程
    1.链表插入节点时：1.7为头插法，1.8为尾插法
    2.对于扩容调价：1.7当大于等于阈值且当前添加点已经存在链表值才会扩容，1.8当大于阈值直接扩容
    3.1.8再扩容计算Node索引时存在优化：就是hash & oldCap == 0来判断是否需要移动
        
/*加载因子问题*/
        
// 加载因子为什么是0.75？
	1.在空间占用与查询时间之间取得较好的平衡
    2.大于这个数，空间节省了，但链表长度就会比较长从而影响性能
    3.小于这个数，效率加快了，但扩容更加频繁，空间占用较多
        
/*多线程下问题*/
        
// 数据缺失问题（1.7，1.8均出现）
    1.当线程1，线程2同时进行putval方法时，可能出现数据缺失
    2.进行putval需要先判断当前节点是否为null，若为空，采用Node占位，然后放入数据
    3.当线程1，检测该节点为null后，转换线程2，线程2也判断该节点为null，然后放入数据
    4.这时线程1重新取得权限，但是已经判断过为null了，然后它也往节点输入数据，就会导致线程2的数据被覆盖
        
// 并发死链问题（1.7头插法导致）
    1.线程1，线程2同时进行扩容操作时
    2.假设原HashMap存在a->b，注意扩容时，仅仅是将数据对象的next数据改变，数据本身不会新创也不会改变
    3.线程1首先获得a，然后切换到线程2执行，线程2进行操作，使其变化为b->a
    4.线程1重新获得操作，然后它会将a继续加入到链表中，变为a->b->a，但其实这时就出现了一个a，b之间的死循环
        
/*key相关问题*/
        
// key是否可以为null？
    HashMap的key可以为null，其他的Map不一定
        
// 作为key，具有什么要求？
    1.必须实现hashCode和equals方法
    2.必须是不可变类型，其内容不能修改，否则可能查询失败导致错误
        
/*hashCode方法问题*/
        
// hashCode为什么每次都乘31？
    1.目的是为了达到较为均匀的散列效果，每个字符串的hashCode足够独特
    2.字符串中的每个字符都可以表现为一个数字，称为Si，其中i的范围是0~n-1
    3.散列公式为：S0 * 31^n-1 + S1 * 31^n-2 + ...... + Sn-1 * 31^0
    4.31带入公式具有较好的散列特性，并且31*h可以优化为：
        32 * h - h
        2^5 * h - h
        h << 5 - h