首页  思维导图  详情

单双例集合知识框架学习笔记

2022-10-31 11:02:39   0  举报





AI智能生成

为你推荐

查看更多



双11

单双例集合知识框架学习笔记

单双例集合

双例集合

集合

作者其他创作

大纲/内容

java.util.ArrayList amp;lt;Eamp;gt; 所在位置

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

介绍amp;lt;bramp;gt;

public ArrayList ( )：构造一个内容为空的集合。amp;lt;bramp;gt;例如： ArrayListamp;lt;Stringamp;gt; list = new ArrayListamp;lt;Stringamp;gt;();amp;lt;bramp;gt;

构造方法

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

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

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

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

成员方法

特有方法

具有List集合的所有特性与方法amp;lt;bramp;gt;

有序集合amp;lt;bramp;gt;

可以存储重复的元素amp;lt;bramp;gt;

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

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

特点amp;lt;bramp;gt;

ArrayList

public E getFirst() 返回此列表的第一个元素amp;lt;bramp;gt;

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

public E getLast() 返回此列表的最后一个元素amp;lt;bramp;gt;

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

public E removeFirst() 移除并返回此列表的第一个元素amp;lt;bramp;gt;

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

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

方法amp;lt;特有方法amp;gt;

也可以存储null元素amp;lt;bramp;gt;

它的底层使用的链表结构amp;lt;bramp;gt;

LinkedList集合底层也是线程不安全，效率高amp;lt;bramp;gt;

有头有尾，其中的方法都是围绕头和尾设计的amp;lt;bramp;gt;

LinkedList是List的子类，List中的方法LinkedList都是可以使用amp;lt;bramp;gt;

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

特点

LinkedListed

底层数据结构是数组，查询快，增删慢，线程安全，效率低amp;nbsp;amp;lt;bramp;gt;

Vector

List

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

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

线程不安全，效率高

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

使用new关键字创建LinkedHashSet类的对象set，对象set的类型是LinkedHashSetamp;lt;bramp;gt;

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

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

步骤amp;lt;bramp;gt;

LinkedHashSet（HashSet 子类）

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

底层使用哈希表结构amp;lt;bramp;gt;

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

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

介绍

HashSet集合不能存储重复的元素amp;lt;bramp;gt;

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

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

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

定义

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

补充

底层数据结构：哈希表

使用new关键字创建HashSet集合类的对象set，类型是HashSet类型amp;lt;bramp;gt;

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

使用对象set调用iterator()函数获取迭代器对象itamp;lt;bramp;gt;

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

步骤

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

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

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

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

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

总结

对象的hashCode方法计算的值相等产生哈希碰撞amp;lt;bramp;gt;

哈希碰撞

使用链表(8之前)，使用链表+红黑树(8之后)amp;lt;bramp;gt;

如何解决哈希碰撞amp;lt;bramp;gt;

目的是为了提高查找效率amp;lt;bramp;gt;

为什么引入红黑树amp;lt;bramp;gt;

链表节点大于大于8并且数组长度大于等于64amp;lt;bramp;gt;

何时链表变为红黑树

满足泊松分布，统计学amp;lt;bramp;gt;

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

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

什么是加载因子

因为0.75是最佳方案amp;lt;bramp;gt;

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

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

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

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

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

哈希表保证元素唯一

面试题

HashSet类的介绍和特点

HashSet 类（Set子类）amp;lt;bramp;gt;

Object first()；返回集合中的第一个元素；amp;lt;bramp;gt;

Object last()；返回集合中的最后一个元素；amp;lt;bramp;gt;

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

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

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

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

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

自然排序(Comparable)amp;lt;bramp;gt;

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

比较器排序(Comparator)amp;lt;bramp;gt;

TreeSet排序方式amp;lt;bramp;gt;

TreeSet 类（Set子类）amp;lt;bramp;gt;

Set

Collections工具类，主要就是操作集合的。amp;lt;bramp;gt;如果当操作集合的时候，发现集合的方法不够用了，amp;lt;bramp;gt;这时一定要先到Collections工具类中找有没有适合我们需求的功能。

public static void shuffle(Listamp;lt;?amp;gt; list) 打乱顺序:打乱集合顺序amp;lt;bramp;gt;

public static amp;lt;Tamp;gt; void sort(Listamp;lt;Tamp;gt; list):将集合中元素按照默认规则排序amp;lt;bramp;gt;

public static amp;lt;Tamp;gt; void sort(Listamp;lt;Tamp;gt; list，Comparatoramp;lt;? super Tamp;gt; ):将集合中元素按照指定规则排序

常用方法amp;lt;bramp;gt;

Comparator 比较器（用在排序中amp;lt;自定义amp;gt; 使用比较灵活）amp;lt;bramp;gt;

Comparable 比较器（用在排序中amp;lt;自然排序amp;gt;）

相关

子类

Collection（单例集合）

Map集合可以一次性存储两个对象amp;lt;bramp;gt;

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

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

Map 集合的特点amp;lt;bramp;gt;

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

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

Map接口中的常用方法

public Setamp;lt;Kamp;gt; keySet(): 获取Map集合中所有的键，存储到Set集合中，遍历2次，效率低，不建议使用amp;lt;bramp;gt;

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

Map集合的遍历

Map集合相关amp;lt;bramp;gt;

HashMap底层是哈希表amp;lt;bramp;gt;

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

存取无序amp;lt;bramp;gt;

线程不安全，所以效率高

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

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

键值对可以为空

存取有序：链表amp;lt;bramp;gt;

元素唯一：哈希表

LinkedHashMap（子类）

源码：amp;lt;bramp;gt;++modCount;amp;lt;bramp;gt; if (++size amp;gt; threshold)amp;lt;bramp;gt; resize();amp;lt;bramp;gt; afterNodeInsertion(evict);amp;lt;bramp;gt; return null;

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

源码：amp;nbsp;amp;lt;bramp;gt;if (e != null) { // existing mapping for keyamp;lt;bramp;gt; V oldValue = e.value;amp;lt;bramp;gt; if (!onlyIfAbsent || oldValue == null)amp;lt;bramp;gt; e.value = value;amp;lt;bramp;gt; afterNodeAccess(e);amp;lt;bramp;gt; return oldValue;amp;lt;bramp;gt; }

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

HashMapamp;lt;bramp;gt;

线程不安全，效率高amp;lt;bramp;gt;

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

键和值不可以是null

存取无序

元素不能重复

Hashtable

Map（集合）双列集合

单双例集合知识框架学习笔记