一、继承关系

1. Collection

下载.svg

2. Map

下载 (1).svg

二、List集合

  • 集合中允许有重复的元素并且有先后放入次序
  • 该集合的主要实现类有：ArrayList、LinkedList、Stack、Vector

1.ArrayList类

  • 底层是采用动态数组 Object[] 进行数据管理的，支持下标访问，增删元素不方便
  • 调用add方法添加元素时，集合的默认长度是10
  • 当集合数据数量等于集合长度时就会扩容至原来的1.5倍

2.LinkedList类

  • 底层是采用双向链表进行数据管理的，访问不方便，增删元素方便
  • 记录第一个和最后一个的 Node 来进行链表数据的访问

3.Stack类Vector类

  • Stack类的底层是采用 动态数组实现栈 进行数据管理
  • Vector类的底层是采用 动态数组 进行数据管理，与ArrayList类相比属于线程安全的类，效率比较低

三、Set集合

  • 该集合中元素没有先后放入次序，且不允许重复
  • 该集合的主要实现类是：HashSet 和 TreeSet 以及 LinkedHashSet

1. HashSet

  • HashSet 类的底层是采用哈希表进行数据管理的
  • 使用元素调用 hashCode 方法获取对应的哈希码值，再由某种哈希算法计算出该元素在数组中的索引位置
  • 同一个哈希算法生成的索引位置相同，只需要与该索引位置已有元素比较即可，从而提高效率并避免重复元素的出现
  • 其中 LinkedHashSet 类与 HashSet 类的不同之处在于内部维护了一个双向链表，链表中记录了元素的迭代顺序，也就是元素插入集合中的先后顺序，因此便于迭代

2. TreeSet

  • TreeSet 的底层是采用红黑树进行数据管理
  • 由于 TreeSet 集合的底层采用红黑树进行数据的管理，当有新元素插入到TreeSet集合时，需要使用新元素与集合中已有的元素依次比较来确定新元素的合理位置

四、Map集合

  • 集合中存取元素的基本单位是 (Key,Value) ，并且key是不允许重复的，而且一个key只能对应一个value
  • 集合的主要实现类有：HashMap、TreeMap、LinkedHashMap、Hashtable、 Properties

1. HashMap

  • 其中HashMap类的底层是采用哈希表进行数据管理的
  • 使用元素的key调用hashCode方法获取对应的哈希码值，再由某种哈希算法计算在数组中的索引 位置
  • 若该位置没有元素，则将该键值对直接放入即可。
  • 若该位置有元素，则使用key与已有元素依次比较哈希值，若哈希值不相同，则将该元素直接放 入
  • 若key与已有元素的哈希值相同，则使用key调用equals方法与已有元素依次比较。
  • 若相等则将对应的value修改，否则将键值对直接放入即可

2.相关常量

  • DEFAULT_INITIAL_CAPACITY：HashMap的默认容量是16
  • DEFAULT_LOAD_FACTOR：HashMap的默认加载因子是0.75
  • threshold：扩容的临界值，该数值为:容量*填充因子，也就是12
  • TREEIFY_THRESHOLD：若Bucket中链表长度大于该默认值则转化为红黑树存储，该数值是8。
  • MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量，该数值是64。

HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使HashMap 具有线程安全的能力，或者使ConcurrentHashMap。我们用下面这张图来介绍HashMap 的结构。

image.png

大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

  1. capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
  2. loadFactor：负载因子，默认为 0.75。
  3. threshold：扩容的阈值，等于 capacity * loadFactor

（2）. JAVA8 实现
Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。
根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

image.png

2. TreeMap

  • TreeMap类的底层是采用红黑树进行数据管理。

3. Hashtable

  • Hashtable 类是古老的Map实现类，与 HashMap 类相比属于线程安全的类
  • 不允许null作 为key或者value的数值

4. LinkedHashMap

  • LinkedHashMap 与 HashMap 的不同之处在于内部维护了一个双向链表，链表中记录了元素的迭代顺序，也就是元素插入集合中的先后顺序，因此便于迭代

5. Properties

  • Properties 是 Hashtable 的子类，该对象用于处理属性文件，key 和 value 都是 String 类型