集合
集合
1 概念
1.1 集合是一个容器
- 是一个用来装对象的容器
1.2 数据结构
-
1、物理结构
-
数组也是一个容器
-
缺点
- (1)长度固定
- (2)无法直接获取有效元素的个数
-
在实际开发中，基本数据类型一般用数组，引用数据类型一般用集合
-
数组是依据“数组名+下标”来确定某个元素，数组名中存储的是数组的首地址
-
-
链表
- 不仅仅存储数据，还有存储前/后元素的引用
-
-
2、逻辑结构
-
动态数组
- 底层是数组，可以通过扩容的方式实现动态数组
-
链表
-
结合Node
-
双向链表
- class Node{ Node pre; Object data; Node next; }
-
单向链表
- class Node{ Object data; Node next; }
-
-
-
树
-
经典的代表
-
二叉树
- class Node{ Node left; Object data; Node right; }
-
-
-
栈
- 先进后出
- 添加的顺序
- 出栈的顺序
-
队列
- 先进先出
- 添加的顺序
- 出队列的顺序
-
堆
-
….
-
2 Collection
2.1 java.util.Collection是一个接口，是个根接口
2.2 Collection没有直接的实现类，它有两个子接口
-
java.util.List
请描述List的各种实现类的区别
ArrayList：动态数组(JDK1.2)，每次扩容为原来的1.5倍，支持Iterator和foreach迭代，线程不安全的
Vector：旧版的动态数组(JDK1.0)，默认每次扩容为原来的2倍，支持旧版Enumeration，还支持Iterator和foreach迭代，线程安全的
LinkedList：双向链表，在添加和删除时 效率比较高，不需要移动大量的元素，只需要修改前后元素引用关系
Stack：Stack是Vector的子类，具有后进先出的特点
-
有序的(添加顺序)，可重复的
-
java.util.Vector动态数组
-
JDK1.0就有，最早
-
支持Enumeration迭代方式
- 当然也支持Iterator，foreach
-
线程安全的
-
扩容算法
-
如果没有指定扩容参数，那么默认扩大为原来的2倍
- 默认初始容量是10
-
如果指定了扩容参数，那么就按照指定参数值进行扩容
-
-
-
java.util.ArrayList动态数组
-
相对Vector来说新一点
-
只支持Iterator，foreach
-
线程不安全的
-
扩容算法
- 扩大为原来的1.5倍
-
-
java.util.LinkedList双向链表
-
相对于动态数组来说的优势
- 在插入和删除操作比较频繁时，链表的方式效率更高
-
相对于动态数组来说的劣势
- 如果根据索引信息来查找的话，每次都要现统计
-
-
java.util.Stack
-
是Vector的子类
-
特征的方法
-
peek()
- 查看栈顶的元素，但不移除
-
pop()
- 获取栈顶的元素，并移除
-
push()
- 压入栈，添加的位置在栈顶
-
search(Object)
- 返回位置，以 1 为基数
-
-
逻辑结构
-
底层
- 数组
- 每次添加到后面，栈顶是数组的后面[size-1]号元素，栈底是数组的[0]元素
-
-
-
列表，序列
-
补充Collection的方法
-
和index相关的方法
-
(1)添加
- add(int index, E element)
- addAll(int index, Collection<? extends E> c)
-
(2)删除
- remove(int index)
-
(3)查找
- indexOf(Object o)
- lastIndexOf(Object o)
- get(int index)
-
(4)替换
- set(int index, E element)
-
(5)截取
- subList(int fromIndex, int toIndex)
-
-
-
-
java.util.Set
5、请描述Set的各种实现类的区别
HashSet：无序的，不可重复的，依据元素的hashCode()和equals方法
HashSet底层实现是HashMap，它的value是一个Object的常量对象TreeSet：不保证添加顺序，但是会按照元素的“大小”顺序进行排列，不可重复，
依据元素的自然排序Comparable(compareTo())或定制排序Comparator(compare())规则进行排序 TreeSet底层实现是TreeMap，它的value是一个Object的常量对象LinkedHashSet：是HashSet的子类，除了有HashSet的特点，它还要在HashSet基础上维护元素的添加的顺序，所以在添加和删除时比HashSet慢一点
LinkedHashSet的底层实现是LinkedHashMap，它的value是一个Object的常量对象-
无序的(添加顺序)，不可重复的
-
java.util.HashSet
-
无序，不可重复
-
依赖于元素的hashCode和equals方法
-
equals和hashCode
- hash值不同，这两个对象一定不同，可以不调用equals
- equals如果相同，hashCode一定相同
- hash值相同，这两个对象不一定相等，所以一定要调用equals方法进行确认
-
-
java.util.TreeSet
-
不按添加顺序，但是按照元素“大小”顺序存储，不可重复
-
不可重复，依据元素是否“大小相等”
- 调用元素的compareTo或定制比较器的compare
-
添加到TreeSet的元素一定要支持可比较大小，可排序
-
自然排序
- 要求元素类型本身要实现java.lang.Comparable接口，并重写int compareTo(Object)方法
-
定制排序
-
要为TreeSet指定一个定制比较器对象
- TreeSet set = new TreeSet(定制比较器对象);
-
-
-
-
java.util.LinkedHashSet
- 比较HashSet多了一个顺序维护，所以在添加和删除时，比HashSet效率低，遍历查找时效率高
- 继承HashSet
-
-
底层实现
-
HashSet
- HashMap
-
TreeSet
- TreeMap
-
LinkedHashSet
- LinkedHashMap
-
-
Set的元素其实也是一对，只不过它的value是共享同一个常量对象Object对象
-
2.3 遍历
-
(1)直接foreach
-
语法结构
- for(集合的元素类型 element : 集合名){ }
-
在遍历时，效率高，但是不适用于遍历的同时对集合进行修改，特别是影响集合元素个数的操作
-
-
(2)Iterator迭代器
-
语法结构
- Iterator iter = 集合对象.iterator();
- while(iter.hasNext()){ Object element = iter.next(); //可以使用iter.remove()进行移除 }
-
Iterator是一个接口
- 在每一类集合中，都有自己的实现类，通过内部类的形式来实现Iterator接口
-
2.4 继承关系图
2.5 Collection的常用方法
-
(1)添加
-
(1)add(Object obj)
- 添加一个元素到集合中
-
(2)addAll(Collection other)
- 把other集合中的元素一一添加到当前集合中，一次添加多个
-
-
(2)删除
-
remove(Object obj)
- 删除一个元素
-
removeAll(Collection other)
-
从当前集合中删除它俩的交集
- this - this ∩ other
-
-
-
(3)查找
-
contains(Object obj)
- 在当前集合中查找一个元素
-
containsAll(Collection c)
- 判断c是否是当前集合的子集
-
-
(4)其他
-
size()
- 获取有效元素的个数
-
retainsAll(Collection other)
-
把this ∩ other赋值给当前集合
- this = this ∩ other
-
-
-
(5)遍历
- Iterator iterator()
- Object[] toArray()
3 Map
3.1 Map的特点
- Map的元素，即存储的映射关系(key,value)，其类型是Entry类型，它是Map的内部子接口，在各种Map的实现类中，都用内部类的方式来实现Entry接口
- Map的key不可重复，而且一旦添加到map中，key不建议修改，特别是参与hashCode和equals方法的属性，或参与compareTo或compare方法比较的属性
3.2 Map的常用方法
-
常用的方法
-
1、添加
- put(key,value)
- putAll(Map)
-
2、有效键值对数
- size
-
3、根据key获取value
- get(key)
-
4、是否包含某个key/value
- containsKey()
- containsValue()
-
5、删除
- remove(key)
-
6、和迭代相关
-
遍历所有的key
- Set keySet()
-
遍历所有的value
- Collection values()
-
遍历所有的映射关系
- Set entrySet()
- Set的元素是Entry类型
-
-
3.3 Map的常见实现类
-
Hashtable
- JDK1.0就有的，属于旧版HashMap，线程安全的
-
HashMap
- 它的key不可重复的，依据key的hashCode()和equals()方法，线程不安全的 JDK1.7时底层实现是数组+链表 JDK1.8时底层实现是数组+链表+红黑树
-
TreeMap
- 它的key不可重复的，按照key的“大小”顺序进行排列, 依据key的自然排序Comparable(compareTo())或定制排序Comparator(compare())规则进行排序
-
LinkedHashMap
- 它是HashMap的子类，在HashMap的基础上同时要维护添加的顺序
-
Properties
- Properties是Hashtable的子类，它的key和value的类型都是String类型
3.4 高频面试题：HashMap的底层实现过程
-
JDK1.7时底层实现是数组+链表
-
(1)先取出key，算出它的hash值 (2)如果数组是空的，会先建立一个长度为16的数组table (3)如果数组不为空，这个时候要判断数组的长度是否达到临界点(数组长度*0.75)，如果已经达到临界点，应该先对数组进行扩容，扩大为2倍 一旦扩容，要重头开始(以前元素要重新排序位置，对新添加的映射关系也要重写计算key的hash值，和index) (4)会根据key的hash值与table数组的长度做一个“按位与&”的运算，计算出要存储的下标index (5)先判断table[index]是否为空，如果为空，直接放进去，放进去之前会构建一个Entry类型对象 (6)如果table[index]不是空的，那么调用key的equals方法与table[index]的key做比较，如果table[index]下面还有链表， 可能需要与table[index]下面的链表的元素一一比较，直到遇到了equals为true或都不相同 (7)如果有一个equals返回true，那么就把value给替换 (8)如果equals都不相等，那么把当前映射关系构建的Entry对象，放在此链表的表头，把原来的对象作为我的next当我们要添加一个新的映射关系时，
-
-
JDK1.8时底层实现是数组+链表+红黑树
-
(1)先取出key，算出它的hash值 (2)如果数组是空的，会先建立一个长度为16的数组table (3)如果数组不为空，这个时候要判断数组的长度是否达到临界点(数组长度*0.75)，如果已经达到临界点，应该先对数组进行扩容，扩大为2倍 一旦扩容，要重头开始(以前元素要重新排序位置，对新添加的映射关系也要重写计算key的hash值，和index) (4)会根据key的hash值与table数组的长度做一个“按位与&”的运算，计算出要存储的下标index (5)先判断table[index]是否为空，如果为空，直接放进去，放进去之前会构建一个Entry类型对象 (6)如果table[index]不是空的，那么调用key的equals方法与table[index]的key做比较，如果table[index]下面有树或者链表， 可能需要与table[index]下面的链表或树的元素一一比较，直到遇到了equals为true或都不相同 (7)如果有一个equals返回true，那么就把value给替换 (8)如果都不相等，如果现在已经是树，就直接添加到该树的叶子节点上。 (9)如果都不相等，如果现在不是树，而是链表，看当前链表的长度是否达到8个，如果没有达到8个，直接添加到链表的尾部 (10)如果已经达到8个，此时要检查数组table的长度是否达到64，如果没有达到64，先扩容，一旦扩容，一切从头开始 (11)如果达到64，把该链表变成一颗红黑树当我们要添加一个新的映射关系时， -
每次进行resize()，会检查树的叶子节点的总数是否<6个，如果<6个，会把这个红黑树变回链表什么时候树会变回链表？
-
4 集合框架图
5 集合工具类
5.1 java.util.Collections
-
操作集合的各种静态方法
-
1、Collections.addAll(Collection, T… elements)
-
2、binarySearch(List, T target)
- 对List的元素类型有要求，必须支持可比较大小
-
3、max/min(Collection)
- 对Collection的元素类型有要求，必须支持可比较大小
-
4、sort(List)
- 元素必须实现Comparable
-
5、sort(List,Comparator)
- 按照指定比较器进行排序
-
6、如果想要获得线程安全的集合对象
- synchronizedXXX(集合)
-
7、。。。。
-