JavaSE之集合及底层

基本

常用集合接口和实现类的UML图

关系图.png

特点

List接口实现类的特点：有序可重复。

Set接口特点：无序不可重复。

SortedSet实现类：无序不可重复，但是可以按照元素的大小自动排列。

ArrayList底层使用的是数组，所以他的特点和数组类似，查询比较快，但是增删效率比较低。

LinkedList底层使用的是双向链表，查询不方便，但是增删效率比较高。

Vector线程安全，但是不推荐使用，因为效率比较低。

TreeSet特点是无序不重复，但是取出来的元素是按大小排列出来的！

HashSet底层时候用的哈希表。

Collection常用方法

@Test
    public void demon(){
        /*
        boolean add(Object Element):向集合中添加元素
        void clear():清空集合
        boolean isEmpty():清空集合
        Object[] toArray():将集合转换为数组
         */

        List<Object> c = new ArrayList<Object>();
        c.add(1);//由于jdk5之后，可以进行自动装箱，将int类型转换为Integer类型
        c.add(new Integer(100));
        Object o = new Object();
        c.add(o);
        System.out.println("存储元素的个数"+c.size());
        System.out.println(c.isEmpty());
        Object[] arr  = c.toArray();
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        //c.clear();
        //System.out.println(c);
    }

迭代器

//面向接口
//迭代器，迭代器是集合类的父类，所以任何集合类都可以使用迭代器
Iterator it = c.iterator();
while (it.hasNext()){//hasNext方法返回的布尔值
    Object element = it.next();//指向下一个地址，并且取出这个元素
    System.out.print(element+"    ");
}

关于HashSet底层

java中的HashSet底层就是HashMap，而HashMap的底层是一个哈希表/散列表，而在java中，哈希表由数组和单向链表组成。下图可以表示哈希表。

我们看一下底层的源码。

我们在HashMap中可以发现单向链表的一个节点，我们发现这个节点有四部分组成，k-v值，hash值还有指向下一个节点。

单向链表的一个节点.png

实际上，这个哈希表就可以画成底下这个结构！

hashmap总的标示图.png

注意这个hash值，它是有key通过哈希算法得出来的，如果我们传入k所得出来的hash值都是相同的，那么就放在同一个单向链表中，注意，在放之前首先使用equals方法去对比放入的值的key与已存在的key是否相同，如果相同就不进行存放，这就是为什么HashMao不重复的原因，还有就是如果传入的k所得出来的hash不存在这个数组中，那么就在这个数组中往后排，继续创建一个。Hash表之所以查询增删的效率快，就是因为数组相当于做了一个索引，先去查找这个hash值，找到hash值之后再在这个对应的单向链表中进行查找数据。增删是因为单向链表的增删效率本来就很快！

我们继续看一下源码：

初始容量和加载因子.png

什么是初试容量，什么又是加载因子？

我们可以知道Hash表底层是一个数组，数组的长度在定义好之后是不可变的，这个16就是HashMap默认的初试容量，默认加载因子就是当这个数组填满百分之75的时候，就需要对这个数组进行一个扩容处理！

总结

HashSet底层实际上是一个HashMap，HashMap底层是一个哈希表。
哈希表又称为散列表，哈希表底层是一个数组，数组中存储的是一个单向链表。每一个单向链表都一个独一无二的hash值，代表数组下标。在一个单向链表上的Hash值是相同的，hash值实际上是由key调用hashCode方法，再通过“hash Function”转换成的值。
如何向Hash表中添加元素：先调用key的HashCode方法，计算出该数据的Hash值，如果在这个Hash表中不存在该Hash值，就直接添加元素。如果该Hash值已经存在，继续调用key之间的equals方法，如果equals返回false，则代表没有相同的key就可以添加元素，如果返回true就代表已经存在了，不能进行添加！
HashSet其实就是HashMap中的Key，HashSet有什么特点，HashMap中应该具有相同的特点。
HashMap和HashSet初试容量都是16，默认的加载因子是0.75。

补充：在jdk1.8之后，当单向链表的长度大于8之后，总数量大于64之后，会将单向链表改变为一个红黑树。