首页  思维导图  详情

集合

2020-06-22 10:30:06   0  举报





AI智能生成

JAVA集合以常见及面试

java

软件开发

学习笔记

学习总结

作者其他创作

大纲/内容

Collection（单例集合）

子类

List

ArrayList

介绍

java.util.ArrayList <E> 所在位置

java.util.ArrayList是大小可变的数组的实现，存储在集合内的数据称为元素。
此类提供一些方法来操作内部存储的元素。ArrayList 中可不断添加元素，其大小也自动增长。

特有方法

构造方法

public ArrayList ( )：构造一个内容为空的集合。
例如： ArrayList<String> list = new ArrayList<String>();

成员方法

public boolean add(E e)：将指定的元素添加到此集合的尾部

public E remove(int index) ：移除此集合中指定位置上的元素。返回被删除的元素

public E get(int index) ：返回此集合中指定位置上的元素。返回获取的元素

public int size() ：返回此集合中的元素数。遍历集合时，可以控制索引范围，防止越界

特点

具有List集合的所有特性与方法

有序集合

可以存储重复的元素

底层是数组，可以根据索引遍历所有元素

ArrayList集合线程不安全，效率高，查询快，增删慢

LinkedListed

方法<特有方法>

public E getFirst() 返回此列表的第一个元素

public void addLast(E e) 将指定元素添加到此列表的结尾

public E getLast() 返回此列表的最后一个元素

public void addFirst(E e) 将指定元素插入此列表的开头

public E removeFirst() 移除并返回此列表的第一个元素

public E removeLast() 移除并返回此列表的最后一个元素

public E pop() 删除并返回此列表的第一个元素。此方法相当于removeFirst()

特点

也可以存储null元素

它的底层使用的链表结构

LinkedList集合底层也是线程不安全，效率高

有头有尾，其中的方法都是围绕头和尾设计的

LinkedList是List的子类，List中的方法LinkedList都是可以使用

LinkedList集合可以根据头尾进行各种操作，但它的增删效率高，查询效率低；

Vector

特点

底层数据结构是数组，查询快，增删慢，线程安全，效率低

Set

HashSet 类（Set子类）

LinkedHashSet（HashSet 子类）

特点

存取有序（底层有一个链接表）链表记录着存储数据的顺序

保证元素的唯一（哈希表）哈希表是真正存储数据的地方

线程不安全，效率高

LinkedHashSet集合没有自己的特有函数，所有的功能全部继承父类

步骤

使用new关键字创建LinkedHashSet类的对象set，对象set的类型是LinkedHashSet

使用对象set调用add()函数给集合LinkedHashSet添加字符串常量

使用迭代器类Iterator进行迭代并输出集合中的数据

HashSet类的介绍和特点

介绍

要给HashSet集合中保存对象，需要调用对象的hashCode函数

底层使用哈希表结构

不保证集合中的迭代顺序（不保证元素存取一致），允许存储null元素

实现了Set接口，具备了Set集合的特性

特点

HashSet集合不能存储重复的元素

HashSet集合存储元素的顺序不固定

底层数据结构：哈希表

定义

在JDK1.8之前，哈希表底层采用数组+链表实现，数组是哈希表的主体，链表则是主要为了解决哈希冲突(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)**而存在的（“拉链法”解决冲突).

JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于等于64时，此时此索引位置上的所有数据改为使用红黑树存储。

特点

如果哈希值不同,说明两个对象一定不同，如果哈希值相同,两个对象不一定相同

补充

将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于等于64时，链表才转换为红黑树

步骤

使用new关键字创建HashSet集合类的对象set，类型是HashSet类型

使用集合对象set调用集合中的add()函数向HashSet集合中添加字符串数据

使用对象set调用iterator()函数获取迭代器对象it

使用for循环遍历，通过迭代器对象调用hasNext()和next()函数，并输出获取的数据

总结

HashSet集合的底层使用的哈希表结构。那么就要求存放的对象必须备hashCode功能。
由于任何一个类的父类都是Object类，而hashCode函数定义在了Object类中，
因此所有的对象都具备hashCode功能

如果我们要把一个对象可以正确的存放在HashSet集合中，
这个对象所属的类一般都需要复写hashCode函数。
建立本类自己的计算哈希值的方式

如果在HashSet集合中要保证对象唯一，
不能仅仅依靠hashCode函数，还要依赖于对象的equals函数，
当hashCode函数计算出来的哈希值相同的时候，
还要调用equals方法比较2个对象是否相同

要求在向HashSet集合中存储自己定义一个类对象的时候，
那么必须在这个自定义类中复写Object类中的hashCode和equals函数。

注意当向HashSet集合中存储数据的时候，对象一定会调hashCode函数计算下标，
但是不一定一定会调用equals函数，只有当计算的下标相同时才会调用equals函数，
否则不会调用equals函数

面试题

哈希碰撞

对象的hashCode方法计算的值相等产生哈希碰撞

如何解决哈希碰撞

使用链表(8之前)，使用链表+红黑树(8之后)

为什么引入红黑树

目的是为了提高查找效率

何时链表变为红黑树

链表节点大于大于8并且数组长度大于等于64

为什么红黑树设置的节点是8

满足泊松分布，统计学

什么是加载因子

加载因子也称为负载因子，默认是0.75.他是根据数组长度计算出边界值，何时扩容的。
数组长度默认是16，边界值：16*0.75===》12

为什么加载因子设置为0.75呢

因为0.75是最佳方案

创建集合对象时，如果知道存储多少个数据，那么不建议使用空参的

initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子（即 loader factor）默认
为 0.75，如果暂时无法确定初始值大小，请设置为 16（即默认值）。
反例：HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素不断增加，容量 7 次被
迫扩大，resize 需要重建 hash 表，严重影响性能

HashSet(int initialCapacity) 7--->变为8 10--->16
底层会根据你指定的值变为比你指定的值大的最小的2的n次幂

哈希表保证元素唯一

依赖两个方法：hashCode和equals。
哈希表底层其实基于数组，元素在存储的时候，会先通过hashCode算法结合数组长度得到一个索引。然后判断该索引位置是否有元素：
1）如果没有，不用调用equals函数，直接存储；【情况1】
2）如果有数据，先判断两个对象的哈希码值是否相等;
a:不相等：直接存储。【情况2】
b:相等：此时使用对象调用重写之后的equals方法比较内容是否相等：(哈希值相等发生哈希碰撞)
1）不相等：直接存储。【情况3】
2）相等：将后添加的元素覆盖之前的元素.【情况4】

TreeSet 类（Set子类）

特有方法

Object first()；返回集合中的第一个元素；

Object last()；返回集合中的最后一个元素；

Object lower(Object o)；返回集合中位于指定元素之前的元素（即小于指定元素的最大元素，参考元素不需要是TreeSet集合里的元素）

Object higher(Object o) 返回集合中位于指定元素之后的元素（即大于指定元素的最小元素，参考元素不需要是TreeSet集合里的元素）

SortedSet subSet(Object fromElement,Object toElement) 返回此Set的子集合，返回从fromElement,Object （包含到）toElement(不包含）

SortedSet headSet(Object toElement)；返回此Set的子集，由小于toElement的元素组成

SortedSet tailSet(Object fromElement)；返回此Set的子集，由大于或等于fromElement的元素组成

TreeSet排序方式

自然排序(Comparable)

TreeSet类的add()方法中会把存入的对象强转成Comparable类型
调用对象的compareTo()方法和集合中的对象比较
根据compareTo()方法返回的结果进行存储

比较器排序(Comparator)

创建TreeSet的时候可以制定一个Comparator
如果传入了Comparator，那么TreeSet就不会按照自然顺序排序了
add()方法内部会自动调用Comparator接口中compare()方法排序

相关

Comparator 比较器（用在排序中<自定义> 使用比较灵活）

Comparable 比较器（用在排序中<自然排序>）

常用方法

public int size() 返回集合中元素的个数

public void clear() 清空集合中所有的元素

public boolean add(E e) 把给定的对象添加到当前集合中

public boolean isEmpty() 判断当前集合是否为空

public boolean remove(E e) 把给定的对象在当前集合中删除

public boolean contains(E e) 判断当前集合中是否包含给定的对象

public Object[] toArray() 把集合中的元素,存储到数组中,可以间接对集合进行遍历

public Iterator iterator() 获取集合对应的迭代器，用来遍历集合中的元素的

Map（集合）双列集合

Map集合相关

Map 集合的特点

Map集合可以一次性存储两个对象

在Map集合中保存的key和value这样的具备一定对应关系的一组（一对）数据，Map集合中存储的是两个对象的对应关系(映射关系)。
[ key-value映射关系 ]

Map集合中的key必须保证唯一（存储的key元素不能重复,value可以重复，但是一个key只能对应一个value）

Map集合中的key和value属于一一对应关系（一个key只能对应一个value）

Map接口中的常用方法

创建 public V put (K key, V value): 把指定的键与指定的值添加到Map集合中

获取集合中的元素,public V get(Object key) 根据指定的键，在Map集合中获取对应的值。

删除元素 public V remove(Object key)
把指定的键所对应的键值对元素在Map集合中删除，返回被删除元素的值

public Set<K> keySet(): 获取Map集合中所有的键，存储到Set集合中
publicSet<Map.Entry<K,V>> entrySet() 返回此映射所包含的映射关系的 Set 视图，建议使用键值对

int size()获取Map集合中存储的key-value对应关系的个数。获取集合长度

Map集合的遍历

public Set<K> keySet(): 获取Map集合中所有的键，存储到Set集合中，遍历2次，效率低，不建议使用

entrySet()：Map中的key和value关系对象存储到Set集合中，阿里建议使用此种方式

子类

HashMap

特点

HashMap底层是哈希表

键唯一，要保证键唯一，所以底层的哈希表主要作用在key上。存在HashMap的键位置的对象所属类必须复写hashCode和equals函数，而存在value位置的对象所属的类可以不复写hashCode和equals函数；

存取无序

线程不安全，所以效率高

HashMap集合中的所有方法全部来自于Map接口，对Map接口中的方法做了全部的实现

键值对可以为空

当值为null时，此时的key的哈希值为0，源码对key为null做了判断：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

LinkedHashMap（子类）

存取有序：链表

元素唯一：哈希表

补充

执行put添加数据的时候，如果新添加的键不存在，那么此时直接添加，并返回null

源码：
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;

执行put添加数据的时候，如果新添加的键存在，那么新添加的value覆盖之前旧的value，并返回旧的value

源码：
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}

Hashtable

特点

线程不安全，效率高

键和值不可以是null

当value为null时，使用put方法判断value是否为null，如果是，抛出NPE异常
key调用hashCode方法时，为null，也会抛出NPE异常，
源码：if (value == null) {throw new NullPointerException();}
int hash = key.hashCode();

存取无序

元素不能重复