面向对象
封装 – 隐藏对象的属性和实现细节，仅对外公开接口；
继承 – 子类继承父类的特征和行为；
多态 – 同一个行为具有多个不同表现形式或形态的能力，在继承的基础上。
重载：一个类中多个方法，方法名一样，参数不一样，返回值也可以不一样；
重写：子类对父类的方法的重新实现，在父类中重写扩展子类的方法。
具体的事物用抽象（汽车），行为操作用接口（驾驶）。
开闭原则（Open Close Principle）- 面向扩展开放，面向修改关闭。
单一职责原则(Single Responsibility Principle) – 每一个类应该专注于做一件事情。
里氏替换原则(Liskov Substitution Principle) – 派生类（子类）对象能够替换其基类（超类）对象被使用。
依赖倒置原则(Dependence Inversion Principle) – 实现类尽量依赖抽象类。
接口隔离原则(Interface Segregation Principle) – 尽量拆分庞大臃肿的接口。
String
= – 引用传递，指向内存中的同一个对象。
== – 比较地址（可以为父子类关系）是否相同。
equals – Object 中的 equals 方法是==，String 类重写了 equals 方法，判断的是字符内容是否相同。
clone()-为浅拷贝，仅复制所考虑的对象，而不复制它所引用的对象，所有的对象引用仍然指向原来的对象。
hashcode – 对象根据哈希算法得出的哈希值，它并不是完全唯一的，通常hash集合会先对比 code 值，如果相等在调用 equals 对比，减少equals调用次数，提升效率。
StringBuffer – 线程安全，，内部使用 char 数组来存储数据，内部方法都添加了 synchronized 同步；
StringBuilder – 非同步，但效率高，内部使用 char 数组来存储数据。
Java集合
常见集合分 两大类；
继承 Collection接口，底层都由数组实现的 List，Set，Queue；
以及继承 Map接口的 HashMap，HashTable 等。
一种基本类型，必须声明其长度，顺序容器，无法动态调整大小，获取简单，查询一般，增（向后移动）删（向前移动）复杂。
对于数组结构，存储不够时会重新分配内存，把原来数据拷贝过去，在释放原内存（会容易导致程序性能下降，GC 消耗），所以初始化最好估算指定大小。离散存储结构，不需要申明长度，不是连续的，可动态调整大小，获取复杂，查询复杂，增删简单（只需要改变前后指针指向）；
每个元素都分为数据域和指针域，数据域存储实际数据，指针域指向下一个元素的地址。
单向链表：每个结点的指针（next）指向下一个结点，最后一个结点指向为 null，获取数据时需要从第一个指针域开始一个个查找到第N个。
双向链表：结点两个指针，单向链表前提下，第一个结点的pre和最后一个结点的 next 指向为 null；
获取数据会判断下标靠前还是靠后，以此决定从前后链表开始查找。
单向循环链表：在单向链表的基础上，最后一个结点 next 指向 head 结点，形成环。
双向循环链表：在双向链表的基础上，第一个结点的 pre 指向最后一个结点，最后一个结点的 next 指向第一个结点，形成环。
List（有序列表）
存取顺序一致。
数组结构，插入数据顺序，类型为 Object，实现快速查询，非线程安全，中间位置插入或者删除元素时，需要对数组前后数据进行移动（复制），代价比较高；
add 长度不够常情况下正常扩容（gorw()方法）1.5倍，如果扩展数组大小达到最大值，则取最大值。数组结构，类似 ArrayList，线程安全（只允许一个线程写），java1.0的产物；
add 长度不够常情况下正常扩容（gorw()方法）2倍。继承自 Vector， 先进后出，添加数据时，存放数组末尾。
双向链表结构的 List，插入顺序排序，因为是链表结构，所以增删效率高，继承 AbstractSequentialList，同时实现了 List 和 Deque 接口，非线程安全；
可以看作一个顺序容器也可以看作一个队列（Queue），同时又可以看作一个栈（Stack），使用上对比 ArrayList 多了一些 push 等方法。
Queue（队列）
先进先出，只允许在一端进行插入操作，另一端进行删除操作的线性表。
数组结构，非线程安全，支持同时从两端添加或移除元素，因此又被称为双端队列，官方也推荐可用来替代 Stack；
数据不能为 null，add 长度不够常情况下正常扩容（doubleCapacity()方法）2倍。
Map（映射）
数组+单向链表结构， 无序的，非线程安全，常用来做统计。
数组下标
根据 key 计算得出 hashcode 值，在重新进行哈希运算（为了避免重复计算，hash 值会缓存在结点的变量上），经过计算（跟数组长度做位与运算）可以得到数组下标。
查找数据：得到数组下标，获取 value。
添加数据
存入数据为 null 会单独处理，存放在数组下标为 0 的位置，如果 key 值不是 null，通过计算到的下标，存入对应下标结点 value 字段中；
如果发生碰撞，添加到同级链表中（本身是链表）。
hash冲突
哈希 冲突的产生是由于不同对象计算出来的 hashCode 可能相同，code 相同意味着计算得到的下标也相同，接下来会判断 key 值是否相同，如果相同，此时冲突产生。
没有 hash 冲突的 map 查询效率比较高，如果发生冲突就会导致这个结点结构形成链，当查询时就需要挨个匹配，影响效率。
树化
在 java8 之前，如果 hash（散列）冲突，首先会使用 链地址法解决，就是链表，把冲突的数据，添加到同一个 hash 值的元素后面，行成一个链；
在 java8 之后，采用红黑树存储，因为红黑树更加适合修改密集型任务。
HashMap 的大小只能是2的N次方，默认大小为16，假设你指定20，会自动转换成32。
LRU：新数据插入到链表头部，每当缓存命中则将数据移到链表头部，当缓存满了，将链表尾部的数据移除。
不能为空，数组+单向链表结构， 无序的，线程安全，实现跟 HashMap 大致一样，官方已经推荐使用 ConcurrentHashMap 替换。
数组+单向链表结构，线程安全，之前使用 分段锁（如果一个线程占用一段，别的线程可以操作别的部分），每个 segment 继承 ReentrantLock；
java1.8 之后改成了 CAS + synchronized 保证并发更新，一把锁只锁住一个链表或者一棵树，并发效率更加提升。数组+单向链表结构， 自然顺序，非线程安全，相比 HashMap 来说，TreeMap 多继承了 NavigableMap 接口，这个接口决定了 TreeMap 与 HashMap 的不同；
HashMap 的 key 是无序的，TreeMap 的 key 是有序的，也就是自动排序好。
Set（无序列表）
通过 hashCode() 和 equals() 来保证元素的唯一性，首先通过 hashCode 判断可以避免多次 equals，提高效率。
存储的结构是哈希表，基于 HashMap 来存储，非线程安全，数据存入 Key 中，value 使用同一个 Object 对象，节省内存开销，利用 HashMap 的 hash 判断达到去重的效果。
继承自 HashSet，保证了元素存取的顺序，区别在于多了双向链表，内部使用 LinkedHashMap 来存储数据。
基于 TreeMap 来存储， 自然顺序，区别是存储单个对象，不能重复。
Collections.synchronizedMap()：内部方法把传入的 map对象用 synchronized 进行上锁。
Original: https://www.cnblogs.com/LiuZhen/p/15918125.html
Author: 翻滚的咸鱼
Title: Java集合，队列，链表总结
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/580328/
转载文章受原作者版权保护。转载请注明原作者出处！