Java集合类源码解析

Java集合类源码解析

Java集合分为Collection和Map两大类

• Collection接口

  • List

    • ArrayList：底层Object数组，查找快，增删慢，线程不安全。默认开辟长度是10，如果要扩容，规则是当前容量的50%

      

      

    • Vector：底层Object数组。查找快，增删慢，线程安全，内部方法都用synchronized。效率低（插入新元素会复制整个数组到新的数组再删除之前的），很少有人用了，每次扩容增加一倍

      

    • LinkedList：双向链表数据结构。查找数据只需要移动指针从前往后依次查找。不同步，线程不安全。插入的性能比ArrayList更好

  • Set

    • HashSet：无序排列，不允许重复。底层是HashMap，在添加元素时会使用map.put()方法进行添加。默认值是PRESENT。

      • 如何保证数据不重复：在添加元素时，会先去比较新增的这个元素的hashCode是否相等，再比较equals是否相等，如果相等，会覆盖掉旧的value

        

    • TreeSet：排列有序，不允许重复（和HashSet一样的原理）。底层是TreeMap。默认值也是PRESENT

  • Queue接口：继承自Collection，用作队列

• Map

  • HashMap：基于哈希表的Map接口的非同步实现，线程不安全的。当我们向map里面put元素时，会利用key的hashCode重新计算当前对象在元素中的下标。在存储时，如果有两个hash值相等，key相同的话，后者覆盖前者，不同的话，说明出现冲突，就将当前的key-value放在链表中。这种方式在jdk1.8对数据存储做了优化，当存储节点大于8个以后会将链表转成红黑树。

    允许key和value都为null。不是线程安全的

    jdk1.8之前：

    

    jdk1.8：

    

    不同之处：

    

  • TreeMap：内部自带了CompareTo方法，所以是自动排序的，底层是二叉树

    

  • LinkedHashMap：实现自HashMap，在遍历时，得到的值是最先插入的

  • HashTable：线程安全的，底层是哈希表结构，键不可以重复，值可以重复

  • ConcurrentHashMap：

    1.8之前，和HashMap差不多，但是支持并发操作。整个ConcurrentHashMap由一个个的Segment组成（一段），所以又称为分段锁。Segment通过继承ReentrantLock来上锁，所以只要每次锁住的是Segment，就实现了全局的线程安全。默认是16个Segment。

    在之后，放弃了Segment的操作，改用了Node+CAS+Synchronized来实现线程安全。只需要将Synchronized锁住当前链表和红黑树的首个节点，保证hash不冲突，就可以实现线程安全。