List有序可重复有索引 ArrayList、LinkedList、VectorSet无序不可重复无索引 HashSet、LinkedHashSet、TreeSetMap键值对K,V键唯一值可重复 HashMap、LinkedHashMap、TreeMap ConcurrentHashMap、Hashtable一、List 系列有序、可重复、带下标1. ArrayList底层Object [] 动态数组默认容量 10扩容原容量 1.5 倍old old1特点查询快下标随机访问 O (1)、增删末尾快、中间插入删除慢数组移位线程不安全多线程并发添加会数组越界、数据丢失允许 null 元素适用大量查询、少量增删2. LinkedList底层双向链表 Node无扩容按需创建节点特点随机查询慢 O (n)、首尾增删快 O (1)中间增删慢实现 Deque可做队列、栈线程不安全适用频繁头尾增删3. Vector淘汰底层数组扩容 2 倍所有方法加 synchronized线程安全效率极低基本不用。List 通用考点Arrays.asList()返回固定长度集合不能 add/remove遍历for 下标遍历、增强 for、Iterator遍历中用集合 add/remove 会并发修改异常ConcurrentModificationException要用迭代器自身 remove排序Collections.sort()自定义对象重写 Comparable 或传 Comparator二、Set 系列不可重复无索引1. HashSet底层 HashMap元素作为 keyvalue 是静态 Object 占位去重规则hashCode()→equals()hash 不同直接存hash 相同equals 不同→链表 / 红黑树equals 相同→重复丢弃无序、只允许一个 null、线程不安全自定义实体存入必须重写hashCodeequals否则无法去重坑存入后修改对象属性→hash 变remove 删不掉数据遗留2. LinkedHashSet继承 HashSet底层 LinkedHashMap插入有序 去重链表维护插入顺序性能略低于 HashSet3. TreeSet底层 TreeMap红黑树自动排序 去重不能存 null不靠 hashCode/equals靠比较器自然排序元素实现Comparable构造传入Comparator定制排序优先级更高compare 返回 0 判定元素重复增删查 O (logn)Set 选型只去重无序HashSet去重 插入有序LinkedHashSet去重 自动排序TreeSet三、Map 系列键 K 唯一值 V 可重复键值对存储1. HashMap重中之重 JDK7 vs JDK8JDK1.7数组 单向链表默认容量 16负载因子 0.75扩容 2 倍头插法扩容并发扩容链表死循环线程不安全JDK1.8数组 链表 红黑树链表长度8 转红黑树树节点6 退回链表尾插法解决死链问题hash(key.hashCode() ^ (hash16)) (len-1)扰动算法减少哈希碰撞key 可为 nullnull 固定存在下标 0value 任意 null负载因子 0.75平衡空间与查询效率常用方法put()、get()、remove()、containsKey()、putIfAbsent()遍历三种keySet、entrySet、values2. LinkedHashMapHashMap 双向链表插入有序可开启 LRU 最近最少淘汰重写 removeEldestEntry3. TreeMap红黑树key 自动排序key 必须实现 Comparable 或构造传 Comparatorkey 不能 null4. Hashtable过时方法全synchronized锁整张表效率差key、value 都不能 null5. ConcurrentHashMap线程安全 MapJDK7Segment 分段锁Segment 数组 (默认 16 段)每段继承 ReentrantLock分段上锁并发度 16JDK8CAS synchronized 锁桶头空桶 CAS 插入已有数据锁住当前桶首 Node锁桶不锁整张表get 无锁依靠 volatile 保证可见性sizeCtl 控制初始化、扩容多线程协助扩容 transferputIfAbsent/computeIfAbsent原子方法替代 ifput 非原子代码Map 选型单线程无序HashMap单线程插入有序LinkedHashMap需要 key 排序TreeMap多线程安全ConcurrentHashMap四、List/Set/Map 对比总结集合重复性有序性底层线程安全List可重复索引有序数组 / 链表不安全 (除 Vector)HashSet不可重复无序HashMap不安全LinkedHashSet不可重复插入有序LinkedHashMap不安全TreeSet不可重复排序有序TreeMap不安全HashMapK 唯一 V 随意无序数组 链表 红黑树不安全ConcurrentHashMapK 唯一 V 随意无序数组 链表 红黑树安全
List、Set、Map 集合知识点
List有序可重复有索引 ArrayList、LinkedList、VectorSet无序不可重复无索引 HashSet、LinkedHashSet、TreeSetMap键值对K,V键唯一值可重复 HashMap、LinkedHashMap、TreeMap ConcurrentHashMap、Hashtable一、List 系列有序、可重复、带下标1. ArrayList底层Object [] 动态数组默认容量 10扩容原容量 1.5 倍old old1特点查询快下标随机访问 O (1)、增删末尾快、中间插入删除慢数组移位线程不安全多线程并发添加会数组越界、数据丢失允许 null 元素适用大量查询、少量增删2. LinkedList底层双向链表 Node无扩容按需创建节点特点随机查询慢 O (n)、首尾增删快 O (1)中间增删慢实现 Deque可做队列、栈线程不安全适用频繁头尾增删3. Vector淘汰底层数组扩容 2 倍所有方法加 synchronized线程安全效率极低基本不用。List 通用考点Arrays.asList()返回固定长度集合不能 add/remove遍历for 下标遍历、增强 for、Iterator遍历中用集合 add/remove 会并发修改异常ConcurrentModificationException要用迭代器自身 remove排序Collections.sort()自定义对象重写 Comparable 或传 Comparator二、Set 系列不可重复无索引1. HashSet底层 HashMap元素作为 keyvalue 是静态 Object 占位去重规则hashCode()→equals()hash 不同直接存hash 相同equals 不同→链表 / 红黑树equals 相同→重复丢弃无序、只允许一个 null、线程不安全自定义实体存入必须重写hashCodeequals否则无法去重坑存入后修改对象属性→hash 变remove 删不掉数据遗留2. LinkedHashSet继承 HashSet底层 LinkedHashMap插入有序 去重链表维护插入顺序性能略低于 HashSet3. TreeSet底层 TreeMap红黑树自动排序 去重不能存 null不靠 hashCode/equals靠比较器自然排序元素实现Comparable构造传入Comparator定制排序优先级更高compare 返回 0 判定元素重复增删查 O (logn)Set 选型只去重无序HashSet去重 插入有序LinkedHashSet去重 自动排序TreeSet三、Map 系列键 K 唯一值 V 可重复键值对存储1. HashMap重中之重 JDK7 vs JDK8JDK1.7数组 单向链表默认容量 16负载因子 0.75扩容 2 倍头插法扩容并发扩容链表死循环线程不安全JDK1.8数组 链表 红黑树链表长度8 转红黑树树节点6 退回链表尾插法解决死链问题hash(key.hashCode() ^ (hash16)) (len-1)扰动算法减少哈希碰撞key 可为 nullnull 固定存在下标 0value 任意 null负载因子 0.75平衡空间与查询效率常用方法put()、get()、remove()、containsKey()、putIfAbsent()遍历三种keySet、entrySet、values2. LinkedHashMapHashMap 双向链表插入有序可开启 LRU 最近最少淘汰重写 removeEldestEntry3. TreeMap红黑树key 自动排序key 必须实现 Comparable 或构造传 Comparatorkey 不能 null4. Hashtable过时方法全synchronized锁整张表效率差key、value 都不能 null5. ConcurrentHashMap线程安全 MapJDK7Segment 分段锁Segment 数组 (默认 16 段)每段继承 ReentrantLock分段上锁并发度 16JDK8CAS synchronized 锁桶头空桶 CAS 插入已有数据锁住当前桶首 Node锁桶不锁整张表get 无锁依靠 volatile 保证可见性sizeCtl 控制初始化、扩容多线程协助扩容 transferputIfAbsent/computeIfAbsent原子方法替代 ifput 非原子代码Map 选型单线程无序HashMap单线程插入有序LinkedHashMap需要 key 排序TreeMap多线程安全ConcurrentHashMap四、List/Set/Map 对比总结集合重复性有序性底层线程安全List可重复索引有序数组 / 链表不安全 (除 Vector)HashSet不可重复无序HashMap不安全LinkedHashSet不可重复插入有序LinkedHashMap不安全TreeSet不可重复排序有序TreeMap不安全HashMapK 唯一 V 随意无序数组 链表 红黑树不安全ConcurrentHashMapK 唯一 V 随意无序数组 链表 红黑树安全
![3分钟掌握VideoDownloadHelper：简单高效的网页视频下载插件终极指南 [特殊字符]](images/news3.jpg)
