java中的集合框架深入学习笔记

温馨提示:图片点击放大功能正在增加,目前您可以右击在新标签中打开图片哦

1. jdk中集合框架的拓扑关系图

1. 图一

查看原图

2. 图二

查看原图 3. 图三

查看原图

大致了解了集合框架的总体情况后下面我们来详细介绍其中的一些常用比较重要的集合框架

2.ArrayList

• 底层是通过数组实现的,数据保存在属性 Object[] elementData中,并且添加删除的操作都没有同步设置,所以ArrayList是线程不安全的,因为使用的是数组,所以随机查询访问的效率较高,但是在元素个数较多时,插入删除操作时效率较低,因为需要复制到新的数组.

• 下面从源码层面介绍一下几个操作

2.1 remove(int index) & remove(Object o)

源码如下

public E remove(int index) {
        rangeCheck(index);
        //修改次数加1
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
        //这里调用的是native方法,底层直接进行数组的覆盖,生成的新数组会多一个最后一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //所以在这里会使最后一位空
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }


public boolean remove(Object o) {
//会先遍历找到当前需要删除的o元素对象所在的index位置,然后还是按照index删除(数组的覆盖)
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    

下面是System.arraycopy方法的源码

我们来测试一下这个方法:

2.2 size属性

ArrayList中维护了一个size属性,这个属性在每次修改数组的时候都会被维护,这样当我们使用size()方法返回list集合中当前存储的所有元素的数量

ps:
size()方法获取的是元素的个数,list的实际大小其实是其内部的elementData这个数组的长度.那么要怎样获取呢?首先elementData是这样被修饰的

transient Object[] elementData; // non-private to simplify nested class access

上面是jdk源码,它没有使用权限修饰符,所以就是默认权限,是在private和protect之间的,可以被同一个包下的类访问(父类都不行,如果不在一个包下),我们还发现这里jdk设置了一个注释,翻译过来就是之所以设置为非私有,是为了让内部类可以调用,在ArrayList源码中有内部类需要使用到elementData,并且有一个内部类是static静态内部类.之所以要强调静态,是因为非静态内部类是可以直接访问到私有化的外部类的属性的,下面我做了一个小测试.

所以要想取出elementData的长度就要在外部访问到elementData,但是因为权限控制符的限制这里就只能使用反射了;

/**
 * @author CodeManZuo
 */
public class ArrayListTest {

    static ArrayList<Integer> list = new ArrayList(200);

    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        for (int i = 0; i < 6; i++) {
            list.add(i);
        }
        Field elementData = null;
        elementData = ArrayList.class.getDeclaredField("elementData");
        elementData.setAccessible(true);
        Object[] myElementData = (Object[]) elementData.get(list);
        System.out.println(myElementData.length);
    }
}

====================================================================
打印结果:
200

Process finished with exit code 0

使用上述的方法就可以访问私有属性了,包括默认的权限修饰

2.3 add添加元素方法

    public boolean add(E e) {
        //参数为当前元素个数+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //还是存储在数组索引为size节点上,之后size加1(因为索引比个数小1)
        elementData[size++] = e;
        return true;
    }
    
    
    //从上面到下面这步,之前省略一些小操作,为了方便理解这里可以认为minCapacity
    //参数就是size+1,
    private void ensureExplicitCapacity(int minCapacity) {
        //修改次数加1
        modCount++;
        // overflow-conscious code
        //所以在这里比较一下如果发现已经超出了当前存储数组的长度就扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //扩容是在原来基础上增加0.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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);
    }

2.4 关于modcount属性

这个属性是和一个异常相关联的,这个异常叫做java.util.ConcurrentModificationException,集合框架的实现类基本都是这样设计的.在每一次对集合进行修改(包括删除添加)的时候,都会修改modCount(ArrayList的一个属性)值.有些操作中会先将modCount赋值给expectModCount,然后进行其他操作后会比较一下expectModCount和ModCount值是不是一样的,如果不一样则报错;原因也就是如果赋值了expectModCount之后,期间修改了ModCount并且没有再次同步给expectModCount,就会导致两个值不一样.

下面来详细介绍一下关于这个异常,后期在介绍hashmap的时候就简单描述了

public class ArrayListTest {

    static ArrayList<Integer> list = new ArrayList();

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            list.add(i);
        }
        System.out.println(list);

//使用for循环遍历时使用ArrayList的删除不会报错,因为不会比较expectModCount和ModCount
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i) == 2)
            {
                list.remove(i);
            }
        }

        System.out.println(list);

        
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i) == 3)
            {
                list.remove(new Integer(3));
            }
        }

        System.out.println(list);

        Iterator<Integer> iterator = list.iterator();

        while (iterator.hasNext())
        {
            Integer next = iterator.next();
            if(next == 4)
            {
            //使用iterator遍历的时候只可以使用iterator的删除,删除当前的元素
            //它会内部同步modCount和expectModCount
                iterator.remove();
            }
        }

        System.out.println(list);

        Iterator<Integer> iterator1 = list.iterator();

        while (iterator1.hasNext())
        {
            Integer next = iterator1.next();
            if(next == 1)
            {
            //使用iterator遍历的时候不允许使用ArrayList的删除,它不会同步modCount和expectModCount
                list.remove(new Integer(1));
            }
        }

        System.out.println(list);
    }
}


========================================================================
结果打印:
[0, 1, 2, 3, 4]
[0, 1, 3, 4]
[0, 1, 4]
[0, 1]
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at com.analyzemybatis.test.ArrayListTest.main(ArrayListTest.java:55)

Process finished with exit code 1

而之所以在使用迭代器的时候使用expectModCount和ModCount来限制api的使用,是因为,自带的remove可以删除任意的元素(可以是非当前遍历的元素),那么这样就会容易出现因为随意删除到值迭代器迭代报错,比如删除了迭代器需要遍历的下一个元素;所以规定只允许使用迭代器自己的删除(删除当前遍历的元素)

3.HashMap

3.1 HashMap in JDK1.7

• 先来看一下hashmap1.7的整体构造,如下图:

可以发现hashmap底层其实是数组加单向链表组成的.说白了hashmap就是一个数组,这个数组存储的数据类型是Entry这个链表节点对象(这个对象中包含key,value,next属性).

• 介绍一下底层源码中几个重要的属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //最大容量(底层数组的大小,也就是散列表的大小)
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //加载因子,是用来生成阈值的
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //真正存储数据的数组,这个数组的类型是Entry链表
    static final Entry<?, ?>[] EMPTY_TABLE = {};

    //记录当前hashmap中的元素个数(这里需要注意,这不是数组长度,而是元素个数,元素个数可能会大于数组长度,因为可能发生了hash冲突)
    transient int size;

    //阈值(扩容时的判断条件)
    int threshold;

    //加载因子(计算扩容阈值需要的属性)
    final float loadFactor;

    //hashmap数据被修改的次数,和前一篇文章说的ArrayList源码一样的作用
    transient int modCount;

• HashMap中的构造方法

//带参数的
public HashMap(int initialCapacity, float loadFactor) {
        (代码省略......)
        //使用用户设置的初始化容量和加载因子
    }

public HashMap(int initialCapacity) {
        (代码省略......)
        //使用用户设置的初始化容量,加载因子使用默认值
    }
//无参构造的
public HashMap() {
        //使用默认的容量大小和加载因子
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

这里需要注意的是,按照构造方法可以创建出HashMap,但是这个HashMap的实际容量大小和指定的不一定一致,后面会说明

• 介绍一下其中的单向链表类型的节点元素对象Entry

直接放源码

//元素节点对象是实现了Map中的子接口Entry
static class Entry<K, V> implements Map.Entry<K, V> {
        //存储key
        final K key;
        //存储value
        V value;
        //因为是单向链表节点,所以肯定是需要存储下一个指向的节点
        Entry<K, V> next;
        //保存改元素节点的hash值,可以通过hashmap规定的hash函数计算出该节点的索引位置
        int hash;

        Entry(int h, K k, V v, Entry<K, V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    
    }

• put(K key,V value)方法添加元素操作

public V put(K key, V value) {
        //第一次添加元素的时候才会去初始化hashmap(其实就是初始化底层用来存储的数组).包括:1.生成容量大小 2.生成阈值
        if (table == EMPTY_TABLE) {
        /*
        这里我们来看一下
        [inflateTable方法]
        private void inflateTable(int toSize) {
        //找到一个最小的比toSize大的2的n次方数
        int capacity = roundUpToPowerOf2(toSize);
        //计算出阈值(容量乘以加载因子)
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //在这里初始化底层存储的数组
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }
        */
            inflateTable(threshold);
        }
        //如果key是null进入下面的方法,hashmap允许一个null key,多个非null key,null value
        if (key == null)
            //会先检查当前0号位置上是否已经存在null key了,如果已经存在则覆盖,否则直接添加到0号位置
            return putForNullKey(value);
        //按照key来计算hash值,通过这个hash值来作为参数计算出需要存在数组何位置上
        /*
        下面是这个hash()方法
        [hash方法]
        final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        //下面的进行一些列的异或移位操作其实是为了使hascode的所有位的值都参与到运算中来,使hash碰撞几率降低
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
        */
        int hash = hash(key);
        /*
        这是根据由该key计算出来的hash获取存放位置的函数
        [indexFor方法]
        static int indexFor(int h, int length) {
        //这里直接使用前面我们得到的那个hash值与我们的length-1也就是数组的容量(2的n次幂)进行&运算,这样会得到一个0-length-1范围内的一个整数,当让也就可以直接进行下标啦
        //这里为什么不使用取余%呢,因为&操作比%效率高
        //因为length是一个2的n次幂,所以减少1之后的二进制数字就是之后的位数全是1,那么进行&操作就是这样的:
        //0001 1111 (length-1)
        //&
        //0000 0101 (hash值)
        //=0000 0101  始终是在第一个0001 1111范围内
        return h & (length - 1);
    }
    
    所以可以认为int hash = hash(key);
                int i = indexFor(hash,table.length)
    这两行代码就是本节开头的图片上的哈希函数(获取到这个节点元素待存储到的位置)
        */
        int i = indexFor(hash, table.length);
        //下面这个for循环是遍历当前这个位置是否有key重复,如果有就覆盖value,且返回旧的value值,这个时候存在底层数组的位置已经确定了,所以判断是否重复就是直接遍历这个单向链表即可
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            /*
            这个if判断就是判断两个对象是否相同的标准模式,涉及到Object中的hashCode(),equals,
            以及==之间的关系,以及hashcode值的作用和意义
            可以参考我的这篇博客:
            http://blog.onsee.vip/article/151
            */
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //可以发现最终真正添加新元素的方法是这个addEntry
        addEntry(hash, key, value, i);
        return null;
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
        /*
        下面就是hashmap1.7的扩容逻辑
        - 扩容需要满足的条件
            1.当前元素个数已经达到了阈值
            2.当前即将插入的底层数组的位置已经有元素存在了(即发生hash冲突(或叫做hash碰撞))
        - 
        */
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        //到这里才是真正的将元素存进来
        createEntry(hash, key, value, bucketIndex);
    }
    
    
    //这个方法也就是jdk1.7中的hashmap的单向链表的头插法的实现了
    void createEntry(int hash, K key, V value, int bucketIndex) {
    //之所以需要按照下面这样的方式来进行头插法是因为只有在创建元素节点的时候指明next属性
        //先获取原来的head位置的元素
        Entry<K, V> e = table[bucketIndex];
        //使用待存的值组装为新的Entry对象,并且新的Entry对象的next属性就是上面获取的变量,最后再把这个Entry对象放入head位置,这样就实现了头插法
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        //最后size++,使size()方法效率更高,不需要使用的时候遍历整个存储结构
        size++;
    }

• 额外说明

其实这些集合框架的实现都是类似的思想.比如在ArrayList和这个HashMap中,这些实现类中都会自带相应的删除remove方法,并且还会提供一个内部类,基本上是用来遍历的工具类,ArrayList和HashMap都具有的是Iterator,这个内部类也是提供remove方法.HashMap中还多一个EntrySet内部类也是提供了remove方法.但是他们都是只有iterator才能在遍历的时候删除.否则都会报错ConcurrentModificationException,原因都是因为只有在iteator中的remove方法才会去做modCount和expectModCount的同步.而遍历的时候都需要使用iterator的next方法,这个方法里面就是需要判断是否同步的.

来看一下下面的测试代码

public class Main {
    public static void main(String[] args) {
        /*
        [报错]
        [原因]:foreach底层使用的是迭代器iterator实现的
        Exception in thread "main" java.util.ConcurrentModificationException
         */
        //m1();

        /*
        [执行成功]
         */
        //m2();

        /*
        [报错]
        [原因]:foreach底层使用的是迭代器iterator实现的
        Exception in thread "main" java.util.ConcurrentModificationException
         */
        //m3();

        /*
        [执行成功]
         */
        m4();

    }

    public static void m1()
    {
        HashMap<String,String> map1 = new HashMap<>();
        map1.put("1","11");
        map1.put("2","22");
        map1.put("3","33");
        map1.put("4","44");
        Set<Map.Entry<String, String>> entries = map1.entrySet();
        for (Map.Entry<String, String> entry : entries) {  //但会比较
            if(entry.getKey().equals("2"))
            {
                map1.remove(entry.getKey());  //不会同步
            }
        }
        System.out.println(map1);
    }

    public static void m2()
    {
        HashMap<String,String> map1 = new HashMap<>();
        map1.put("1","11");
        map1.put("2","22");
        map1.put("3","33");
        map1.put("4","44");
        Set<Map.Entry<String, String>> entries = map1.entrySet();
        Iterator<Map.Entry<String, String>> iterator = entries.iterator();
        while (iterator.hasNext())  //虽然会比较
        {
            String keyTemp = iterator.next().getKey();
            if(keyTemp.equals("2"))
            {
                iterator.remove();  //但是会同步
            }
        }
        System.out.println(map1);
    }

    public static void m3()
    {
        HashMap<String,String> map1 = new HashMap<>();
        map1.put("1","11");
        map1.put("2","22");
        map1.put("3","33");
        map1.put("4","44");
        Set<String> keySet = map1.keySet();
        for (String s : keySet) {  //内部使用的其实还是迭代器,所以会比较
            if(s.equals("2"))
            {
                map1.remove(s);   //但是集合框架实现类自带的remove不会同步
            }
        }
        System.out.println(map1);
    }

    public static void m4()
    {
        HashMap<String,String> map1 = new HashMap<>();
        map1.put("1","11");
        map1.put("2","22");
        map1.put("3","33");
        map1.put("4","44");
        Set<String> keySet = map1.keySet();
        Iterator<String> iterator = keySet.iterator();
        while (iterator.hasNext())
        {
            String keyTemp = iterator.next();
            if(keyTemp.equals("2"))
            {
                iterator.remove();
            }
        }
        System.out.println(map1);
    }
}

==也就是说,在迭代时(foreach底层也是迭代),要想修改map的结构只能使用迭代器自带的remove方法,使用其他方法都会抛出异常ConcurrentModificationException==

3.2 HashMap in JDK1.8

• HashMap1.8的底层实现和1.7版本有了较大的变化,先来看一下1.8版本的结构图

说明:
底层使用的任然是数组存储数据的,但是元素节点对象不再只是单向链表,在hash冲突的元素个数达到一定的阈值后就会从链表转为红黑树

    //默认的底层存储数组的容量大小(同样的也是2的n次方)
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //最大的底层数组的容量
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //默认的加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //默认的转树的出现hash冲突的元素的阈值
    static final int TREEIFY_THRESHOLD = 8;

    //默认的转链表的出现hash冲突的元素的阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    //转树需要达到的底层数组的最小大小(也就是说 在转变成树之前，出了上面的转树阈值,还会有一次判断，只有散列表容量大于 64 才会发生转换。这是为了避免在哈希表建立初期(表长度较小)，由于hash函数可能出现不合理,导致多个键值对恰好出现碰撞被放入了同一个链表中而导致不必要的转化。)
    static final int MIN_TREEIFY_CAPACITY = 64;

• 简单说明一下1.8与1.7的其他几个不同之处

1. 扩容条件,当元素存入的个数超过阈值就直接扩容,不需要再满足当前存入元素刚好发生hash冲突
2. 扩容时重新计算索引的方式也有改变,hashmap1.8变得更高效,非常巧妙的应用了二进制与操作的特点.详细了解请点我

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2020/07/01 21:17