面试题（3）

题目来源于牛客网

介绍下集合

        Java集合框架是Java中用来存储，操作，管理对象的一种架构，分为单列集合和双列集合，其中单列集合中只能存放单个对象，顶层接口是Collenction，它有三个子接口，分别是list,set,queue.双列集合是按照键值对进行存储对象的，key必须是唯一的，但是value可以不唯一，顶级接口为Map，他没有子接口，只有一些实现类。对于单列集合子接口list来说，他有三个实现类，其中ArrayList是基于动态数组进行实现，由于可以进行下标进行访问，因此访问速度比较快，但是对于插入和删除，对于尾部来讲的话，O(1)的时间复杂度，因为不需要进行元素的移动，对于其他位置来说，是O(N)的时间复杂度，因为涉及到了元素的移动。ListedList是基于链表进行实现的，插入和删除需要找到节点的前驱或者后继，然后进行插入或者删除操作。由于查找的话是从链表的头节点开始进行遍历，因此随机访问比较慢。Vector它与ArrayList类似，但是是线程安全的，访问效率较低。对于子接口set来说，它是无序，不可重复的，有HashSet，它是基于哈希表进行实现，查找比较快，LinkedHashSet，它是基于哈希表和链表进行实现的，TreeSet是根据红黑树进行实现的，如果需要自动排序，那么需要实现Comparable或者提供Compaeator.Queue接口有LinkedList和PriorityQueue两大实现类，其中PriorityQueue是基于堆结构，按照优先级进行排序的。双列集合map的特点是存储键值对，它的key不能重复，可以为null，但是value可以重复,并且多个value可以为null。

HashMap原理

        hashmap的底层通过一个数组存储所有的元素，数组的初始大小16，数组中的每一个元素称之为hash桶，当存放一个数据是，首先是通过hashcode进行一个哈希运算得到一个非常大的数值，为了能够存放到数组中，可以通过（n-1）&hash来判断当前元素的存放位置。底层存放一个对象，jdk1.7中是entry，jdk1.8是node对象，以jdk1.8为例，存放一个对象时会new node(),里面存放得到的hash值，key，value,以及当前这个元素指向下一个元素的指针，当发生hash冲突时，就会使用到这个指针了。当hash冲突比较大的时候，如果查询的元素比较深，那么会影响查询效率，因此可以通过数组扩容进行解决（扩充两倍），再重新进行元素的分配，在jdk1.7中，索引的计算公式是，newIndex = (hash&(newCapacity-1)),在jdk1.8中索引计算公司是newIndex=(oldIndex<oldCap)?oldIndex:oldIndex+oldCap，根据hash值的高位是否为0/1，决定是否向后移动，当数组长度达到64且链表长度达到8时，发生hash冲突，此时的链表会转化为红黑树为了更好的查询（jdk1.8）。

ConcurrentHashMap原理

ConcurrentHashMap在jdk1.8中由数组，单项链表，红黑树构成，当初始一个ConcurrentHashMap实例时，默认初始化一个16长度的数组，核心为哈希表，会存在哈希冲突的问题，所以ConcurrentHashMap使用链式寻址的方式解决哈希冲突，因为当哈希冲突比较多的时候，会导致链表的长度比较长，查询数组元素的时间会增加，为了解决这个问题，在jdk1.8时引入了红黑树，链表大于超过阈值（默认为0），数组长度大于64，转为红黑树，而且随着链表扩容，链表长度小于6时，会将红黑树转化为链表。ConcurrentHashMap的基本功能和hashmap类似，但是它提供了一个并发安全的实现，主要是通过对node进行加锁保证数据更新的安全性。在jdk1.8中,ConcurrentHashMap锁的粒度是链表的头节点，jdk1.7采用的时分段锁（segment），锁粒度大，影响并发性能。在数组扩容是，jdk1.8采用的是多线程并发扩容，就是多个线程对原始数组进行分片，分片之后，每个线程负责对一个分片的数据迁移，从而提升整体的效率。ConcurrentHashMap中有个size()方法进行总元素个数的获取，当线程竞争不激烈的时候，采用CAS的方式实现原始个数原子的递增，线程激烈的情况下，使用数组维护元素的个数，要增加元素个数时，直接从里面选择一个，再通过CAS的方法进行原子递增，核心时引入了数组来进行并发的一个负载

gc算法

1. 引用计数，每个对象维护一个计数器，一个对象引用它的时候+1，当引用失效的时候-1，当计数器对象为0，就可以立即回收，这个方法可以实时回收，但是每次引用或者解除是都要操作计数器，影响性能，而且无法处理循环引用
2. 标记清除，从 根对象 出发，通过引用链遍历所有可达对象，标记为“存活”，回收未被标记的对象，但是这样子清除后内存不连续，可能导致后续分配大对象失败，而且效率较低
3. 标记复制，内存分为两块相同的区域，为From和To,分配阶段只分配到From,回收阶段标记存活对象，将存活对象赋值到To中，清理From,最后进行交换，这样子避免了内存碎片，但是会导致内存利用率低，存活对象高是效率较低
4. 标记整理，标记存活对象，将他们移向另一端，清理边界内存，最后得到的结果是存活的对象在内存一侧，释放另一侧的所有空间
5. 分代回收，将存活时间长的放在老年代，使用标记整理算法，存活时间短的放在新生代，使用标记复制算法。新生代经历多次GC，晋升到老年代，新生代内存不足，直接晋升到老年代

什么时候对象会从ender到survier区，为什么是这些时候

当 Eden区空间不足 时，需要创建新对象但无法分配内存，此时会触发 Minor GC（针对新生代的垃圾回收）。因为新生代的设计目标是快速回收短期存活对象。Eden区的内存有限，当其被填满时，必须通过 GC 清理存活对象，并将它们转移到 Survivor 区，从而释放 Eden 空间供新对象使用。

三大范式及其例子

第一范式：每个字段的值必须是不可再分的原子值，不能是重复或者嵌套的结构，每一列的值在表中有相同的含义，并且每一行每个字段有明确的值。

CREATE TABLE student (
  id INT PRIMARY KEY,
  name VARCHAR(50),
  address VARCHAR(100)  -- "广东省广州市天河区"（地址可拆分为省、市、区）
);

CREATE TABLE student (
  id INT PRIMARY KEY,
  name VARCHAR(50),
  province VARCHAR(50),
  city VARCHAR(50),
  district VARCHAR(50)
);

第二范式：在1NF基础上，所有非主键字段必须完全依赖主键，不能仅依赖主键的一部分，若主键是多个字段的组合（复合主键），则非主键字段必须依赖整个主键，而非其中一部分。

CREATE TABLE order_detail (
  order_id INT,
  product_id INT,
  product_name VARCHAR(100),  -- 仅依赖 product_id
  price DECIMAL(10,2),       -- 仅依赖 product_id
  quantity INT,
  PRIMARY KEY (order_id, product_id)
);

-- 拆分为两个表：
CREATE TABLE product (
  product_id INT PRIMARY KEY,
  product_name VARCHAR(100),
  price DECIMAL(10,2)
);

CREATE TABLE order_detail (
  order_id INT,
  product_id INT,
  quantity INT,
  PRIMARY KEY (order_id, product_id),
  FOREIGN KEY (product_id) REFERENCES product(product_id)
);

第三范式：在2NF基础上，所有非主键字段不能依赖其他非主键字段

CREATE TABLE student (
  student_id INT PRIMARY KEY,
  name VARCHAR(50),
  department_id INT,          -- 部门ID
  department_phone VARCHAR(20) -- 部门电话（依赖 department_id，而非 student_id）
);

-- 拆分为两个表：
CREATE TABLE student (
  student_id INT PRIMARY KEY,
  name VARCHAR(50),
  department_id INT,
  FOREIGN KEY (department_id) REFERENCES department(department_id)
);

CREATE TABLE department (
  department_id INT PRIMARY KEY,
  department_name VARCHAR(50),
  department_phone VARCHAR(20)
);

反范式及其例子

增加冗余列

-- 用户表
CREATE TABLE user (
  user_id INT PRIMARY KEY,
  name VARCHAR(50),
  address VARCHAR(100)
);

-- 订单表（范式化）
CREATE TABLE order (
  order_id INT PRIMARY KEY,
  user_id INT,
  order_time DATETIME,
  -- 其他字段
  FOREIGN KEY (user_id) REFERENCES user(user_id)
);

-- 订单表（反范式化）
CREATE TABLE order (
  order_id INT PRIMARY KEY,
  user_id INT,
  user_name VARCHAR(50),    -- 冗余字段
  user_address VARCHAR(100),-- 冗余字段
  order_time DATETIME,
  -- 其他字段
  FOREIGN KEY (user_id) REFERENCES user(user_id)
);

减少 用户表 和 订单表 的关联操作，提升查询效率 

增加派生列

-- 订单明细表（范式化）
CREATE TABLE order_detail (
  detail_id INT PRIMARY KEY,
  order_id INT,
  product_id INT,
  price DECIMAL(10,2),
  quantity INT,
  -- 总价不存储，需计算
  FOREIGN KEY (order_id) REFERENCES order(order_id)
);

-- 订单表（反范式化）
CREATE TABLE order (
  order_id INT PRIMARY KEY,
  total_price DECIMAL(10,2), -- 派生列
  -- 其他字段
);

减少计算开销，提升查询性能. 

重新组表

-- 用户表、订单表、订单明细表（范式化）
SELECT u.name, o.order_id, od.product_id, od.quantity 
FROM user u 
JOIN order o ON u.user_id = o.user_id 
JOIN order_detail od ON o.order_id = od.order_id;

-- 合并表（反范式化）
CREATE TABLE order_summary (
  user_name VARCHAR(50),
  order_id INT,
  product_id INT,
  quantity INT,
  -- 其他字段
  PRIMARY KEY (order_id, product_id)
);

直接查询合并表，避免多表关联，提升复杂查询效率 

水平分割

CREATE TABLE orders (
  order_id INT PRIMARY KEY,
  order_time DATETIME,
  -- 其他字段
);


-- 水平分割后的表
CREATE TABLE current_orders (
  order_id INT PRIMARY KEY,
  order_time DATETIME,
  -- 其他常用字段
);

CREATE TABLE historical_orders (
  order_id INT PRIMARY KEY,
  order_time DATETIME,
  -- 所有字段
);

常用查询（如最近订单）仅访问 current_orders，减少数据量 

垂直分割

CREATE TABLE user (
  user_id INT PRIMARY KEY,
  name VARCHAR(50),
  address VARCHAR(100),
  phone VARCHAR(20),
  login_log TEXT,          -- 不常用字段
  -- 其他数十个字段
);

-- 垂直分割后的表
CREATE TABLE user_base (
  user_id INT PRIMARY KEY,
  name VARCHAR(50),
  address VARCHAR(100),
  phone VARCHAR(20)
);

CREATE TABLE user_details (
  user_id INT PRIMARY KEY,
  login_log TEXT,
  -- 其他不常用字段
);

常用查询仅访问 user_base，减少 I/O 开销