集合

List

• 集合有序

数组和链表

数组

• 物理位置连续；
• 可以随机访问；
• 查找快，增删慢；

链表

• 物理位置不连续；
• 不能随机访问，只能顺序访问；
• 增删快，查找慢；

常用的List

• ArrayList
  • 底层实现为数组；
  • 特性为数组的特性；
• LinkedList
  • 底层实现是链表；
  • 特性为链表的特性；

Map

• 一对一，键值对(entry)，key-value；
• 底层实现是通过数组+链表+哈希算法；
  • 哈希算法：哈希算法是一种散列算法，可以通过数据算出数据的特征值；
    • MD5，SHA1；
    • 计算key的hash值，value不计算，纯粹用来存放数据；
    • 通过哈希算法算出特征值之后，根据特征值计算存放的位置；
    • 位置不是固定的，会根据桶的大小确定；
  • 如果出现key重复，那么后面的map键值对会把前面的顶掉；
• 键值对对应，但是键值对之间的顺序不是固定的；
• 速度很快

常用的Map

HashMap

LinkedHashMap

• 键值对有序；
• 有序的原理是维护了一个额外数组，通过数组记住他们的相对位置；

Set

• 无序，元素不重复的集合
• Set底层是通过Map实现的，Set把Map的value隐藏起来了；

常用的Set

• HashSet