Java集合框架的理解

常用集合框架
└── Iterator接口
    ├── Collection接口
        ├── List接口
            ├── LinkedList类
            ├── ArrayList类
            └── Vector类
            	└── Stack类
        └──Set接口
            ├── HashSet类
            └── TreeSet类
    └── Map接口
        ├── TreeMap类
        ├── HashMap类 ──── ConcurrentMap类
    	└── HashTable类

Iterator

• Iterator提供iterator方法用于遍历集合元素，提供了对当前集合的三种操作：判断集合中是否有下一个元素，获取下一个元素以及移除当前元素
• fail-fast机制（快速失败机制）：在实现了Iterator接口的集合类中，都会实现一种fail-fast机制，其目的是让集合在并发操作时，如果一个线程对集合类实例进行了结构性修改（remove，add，clear等操作），另一个线程在迭代时出现错误能够立即抛出异常。其实现原理是通过定义一个modCount变量记录当前集合被操作的次数，然后在每次使用itr对集合进行操作的时候调用checkForComodification方法比较expectedModCount和modCount的值是否相等，不相等的话就代表出现了脏数据，这个时候就会抛出ConcurrentModificationException错误

Collection

• Collection接口继承了Iterator接口，在此基础上添加了一些方法，如返回集合大小，判断集合是否为空，在集合中添加元素等等

Vector

• Vector类是可以动态增长和收缩的存储对象。Vector类继承了AbstractList类并且实现了List接口，支持随机访问，可以被克隆和序列化
  • 底层数据结构为数组，支持随机访问，可以动态扩展
  • 查询复杂度O(1)，添加和删除的复杂度O(n)
  • 默认容量大小为10，默认扩容大小为原来的2倍
  • 线程安全，使用synchronized关键字来实现

Stack

• Stack类继承了Vector类，但是对元素的访问和插入做了一定限制，只能在数组尾部添加或删除元素，这体现了一个后进先出（LIFO）的特性

ArrayList

• ArrayList类和Vector类的构造和功能相似
  • 底层数据结构为数组，支持随机访问，可以动态扩展
  • 查询复杂度O(1)，添加和删除的复杂度O(n)
  • 默认容量大小为10，默认扩容大小为原来的1.5倍
  • 线程不安全
• ArrayList和Vector的异同
  • 底层数据结构相同
  • 默认容量相同
  • 扩容机制不同
  • 前者线程不安全，后者线程安全

LinkedList

• LinkedList是继承了AbstractSequentialList的双向链表并且实现了Deque接口，可以被当作堆栈、队列或双向队列进行处理，可以被克隆和序列化
  • 底层数据结构为双向链表，不支持高效的随机访问，可以动态扩展
  • 查询复杂度O(n^2)，查找时分两半查找，添加和删除的复杂度O(1)
  • 默认容量为0
  • 线程不安全

Hashtable

• Hashtable类是一个key-value映射的哈希表，实现Map接口，继承Directionary类，可被克隆和序列化
  • 底层数据结构为单链表数组（Entry[]数组），每个数组元素中的单链表存放的是键值对（Entry对象）
  • 查找，添加和删除复杂度O(1)（理想状态下）
  • 默认容量大小为11，默认负载因子为0.75（到达负载因子对应的容量时进行扩容），默认扩容大小为原来的2倍加1
  • 使用拉链法解决哈希冲突（即在两个元素的哈希值相等的情况下将两个元素放在同一个位置的链表中）
  • 不能接受null键值和值
  • 线程安全

HashMap

• 与Hashtable相似是一个key-value映射的散列表，继承AbstractMap类，实现了Map接口，可被克隆和序列化
  • 底层数据结构为单链表数组或红黑树数组
  • 查找，添加和删除复杂度O(1)（理想状态下）
  • 默认容量大小为16，默认负载因子为0.75，默认扩容大小为原来的2倍
    • 为什么要扩容为原来的2倍？因为HashMap关注中hash的计算效率问题，在取模计算时，如果模数是2的幂，那么可以直接使用位运算来得到结果，效率要高于除法。不过这会导致哈希分布不均匀的问题
  • 当单个桶（单链表数组中每一个数组位置称为一个桶）大小大于8并且当前集合中键值对总数量大于64的时候，就会将数组位置中的单链表转换成红黑树（特点是查询时间缩短为O(logn)）
    • 单链表是如何转换成红黑树的？使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序进行插入
  • 查询或者是插入的过程是先对比hashCode方法得出的hash值（根据键值对计算出来的哈希值）是否相等，相等的情况下再调用equals方法（直接对比两个对象中的值）进行对比，两者都相等的时候才说明这两个对象相等
  • 线程不安全
    • 多线程下出现的问题？在多线程情况下重新调整HashMap中个元素的值的时候会存在条件竞争的问题，会出现死循环。所以多线程环境下不建议使用HashMap，可以转而使用ConcurrentHashMap
  • 常使用String，Integer等包装类作为键
    • 为什么包装类适合作为键？因为放入Map中的对象要保证遵守equals和hashCode方法的定义规则，并且要保证对象存取过程中hash值不会变；而String等包装类是不可变的，使用final修饰，其内存地址始终指向于同一块地址
• 在JDK1.8后对HashMap的改进有以下几处：
  • 使用红黑树进行扩展
  • hashCode值的扰动函数减少运算次数
  • 扩容为之从重新调用hash函数计算新的位置变为通过(e.hash&oldCapicity)==0来确定节点新位置是位于扩容前的角标还是之前的2倍角标位置

HashMap和Hashtable的区别

• 继承的父类不同：HashMap继承AbstractMap类，而Hashtable继承Dictionary类
• 对null键值支持不同，HashMap支持null键和null值，Hashtable不支持
• HashMap线程不安全，Hashtable线程安全
• 初始容量大小和每次扩容大小不同，HashMap默认大小是16，每次扩容容量变为16或是链表转化为红黑树；Hashtable默认大小是11，每次扩容，容量变为原来的2n+1
• 计算hash值的方法不同，Hashtable直接使用对象的hashCode，hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值，然后再使用除留余数法来获取最终位置；因为HashMap扩容使用2倍会导致哈希分布不均匀的问题，所以HashMap会使用使用一些简单的位处理减少哈希冲突

ConcurrentHashMap

• 由一个个Segment组成，Segment也被称为分段锁。所以ConcurrentHashMap实际上是一个Segment数组，Segment通过继承ReentrantLock来进行加锁，保证了每个Segment是线程安全的，从而实现全局的线程安全。ConcurrentHashMap中有一个concurrencyLevel变量，默认为16，就是说ConcurrentHashMap默认有16个Segment，而每一个Segment中有类似HashMap结构的单链表数组，只不过在这基础上实现了线程安全

TreeMap

• TreeMap的内部基于红黑树实现的，线程不安全

Set

• Set类整体依赖于Map类，即HashSet使用一个HashMap的实例实现，而TreeSet使用一个TreeMap实例实现
• HashSet和HashMap的区别
  • 实现的接口不同，HashSet实现Set接口，HashMap实现Map接口
  • HashSet仅存储值，HashMap存储键值对
  • 增加元素使用的方法名不同，HashSet使用add方法，HashMap使用put方法
  • 计算hashcode的对象不同，HashSet使用成员对象，HashMap使用键对象
• TreeSet是一个有序集合，它的作用是提供有序的Set集合。继承AbstractSet类，实现了NavagableSet接口，可以被克隆和序列化，支持一系列的导航方法（查找与指定目标最匹配值等）
  • TreeSet支持两种排序方式：自然排序和Comparator排序
    • 自然排序（元素具备比较性）：让元素所属的类实现Comparable接口
    • 比较器排序（集合具备比较性）：让集合接受一个Comparator的实现类对象

---