java集合框架是分层设计的数据结构体系：arraylist基于动态数组，随机访问o(1)但中间增删o(n)；linkedlist基于双向链表，头尾操作o(1)但查找o(n)；hashmap采用哈希表+链表/红黑树，平均查找o(1)；hashset、treeset分别依托hashmap和treemap实现无序去重与有序存储。
Java 集合框架不是一堆“黑盒工具”，而是由明确数据结构支撑、有清晰性能边界的一套分层设计。选对集合，关键不在背API，而在理解底层怎么存、怎么查、怎么变。
ArrayList：靠数组撑起的随机访问快车道
它本质是带自动扩容的Object[]数组。首次add时才分配默认10个槽位；当size == capacity，就新建一个1.5倍长度的数组，把老元素全拷过去——这个复制过程就是增删慢的根源。
- get(index) 是纯指针偏移，O(1)，适合下标遍历、频繁读取
- add(E) 在尾部是O(1)，但在中间或开头插入需移动后续所有元素，O(n)
- remove(int index) 同样要搬动数据，删除越靠前，代价越高
- 不支持null作为元素？错——ArrayList允许null，只是泛型约束可能限制实际使用
LinkedList：用双向链表换来的灵活增删
每个节点含prev、next和item引用，无连续内存要求。没有“容量”概念，增删只改指针，不挪数据。
- addFirst() / addLast() / removeFirst() 都是O(1)，适合做栈、队列或高频头尾操作
- get(index) 必须从头或尾出发逐个跳节点，平均O(n/2)，比ArrayList慢一个数量级
- 它实现了Deque接口，可直接当双端队列用，不必额外包装
- 注意：new LinkedList() 构造开销略大于ArrayList，空集合也有两个哨兵节点
HashMap：数组+链表/红黑树的混合寻址引擎
核心是“哈希定位 + 拉链/树化解决冲突”。先算key.hashCode()，再与table.length-1做&运算得桶索引；同桶内元素用链表（≤8）或红黑树（≥8且table≥64）组织。
- put(K,V) 和 get(K) 平均O(1)，但最坏情况（全哈希碰撞）退化为O(n)或O(log n)
- 初始容量16，负载因子0.75，达到12个元素就扩容——扩容触发rehash，是性能敏感点
- key必须正确重写hashCode()和equals()，否则put进去了也get不出来
- 允许一个null key（放在table[0]），多个null value
HashSet与TreeSet：Set背后的两种秩序
HashSet是HashMap的“value隐身版”——内部只用HashMap的key存元素，value固定为PRESENT对象；TreeSet则基于TreeMap，用红黑树保证自然序或自定义序。
- HashSet增删查都是O(1)均摊，无序，依赖hashCode分布质量
- TreeSet所有操作O(log n)，能天然排序，但插入成本高、不允许null（因比较时会NPE）
- LinkedHashSet是HashSet加双向链表，维持插入顺序，性能介于两者之间
- 去重逻辑统一走equals()判断，不是==，这点和数组完全不同
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
