IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 高级部分:集合 -> 正文阅读

[数据结构与算法]高级部分:集合

集合

一、Java集合框架概述

1.1集合的含义

集合和数组都是对多个数据进行存储操作的结构
此时的存储,指内存层面的存储,不涉及持久化的存储

1.2数组存储的特点与弊端

数组初始化以后,长度就确定了。
数组声明的类型,就决定了进行元素初始化时的类型

数组初始化以后,长度就不可变了,不便于扩展。
数组中提供的属性和方法少,不便于进行添加、删除、插入等操作,且效率不高。
同时无法直接获取存储元素的个数。
数组存储的数据是有序的、可以重复的。---->存储数据的特点单一

1.3集合存储的优点

①数组初始化以后,长度可以改变,便于扩展。
②数组中提供的属性和方法多,便于进行添加、删除、插入等操作,且效率高。
③可以同时直接获取存储元素的个数。
④集合存储的数据是无序的、但不可重复。

1.4集合框架

java集合可分为Collection和Map体系:
1.Collection接口:单列集合,用来存储一个一个的对象,其两个子接口:
①List接口:元素有序、重复的集合---->ArrayList、LinkedList、Vector都是List接口的实现类
②Set接口:元素无序、不可重复的集合---->HashSet(LinkedHashSet)、SortedSet(TreeSet)都是Set接口的实现类
2.Map接口:双列数据,保存具有映射关系“key-value对”的集合

二、Collection接口方法

1.添加 coll.add(Object o);|coll.addall(Collection coll);
2.获取有效元素的个数: int size();
3.清空集合: void clear();
4.是否是空集合:boolean isEmpty();
5.是否包含某个元素:
boolean contains(Object obj);
是通过元素的equals方法来判断是否是同一个对象
boolean containsAll(Collection c);
也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较。
6.删除
boolean remove(Object obj) ;
通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素
boolean removeAll(Collection coll);
取当前集合的差集
7.取两个集合的交集
boolean retainAll(Collection c);
把交集的结果存在当前集合中,不影响c
8.集合是否相等: boolean equals(Object obj);
9.转成对象数组:Object[] toArray();
10.获取集合对象的哈希值:hashCode();
11.遍历:

		//第一种遍历
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //第二种遍历
        for(Object obj: coll){
            System.out.println(obj);
        }

三、Collection子接口一:List

1.主要分为:ArrayList、LinkedList、Vector

2.ArrayList和LinkedList的异同

二者都线程不安全,相对线程安全的Vector,执行效率高。
此外,ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove,LinkedList比较占优势,因为ArrayList要移动数据。

3.ArrayList和Vector的区别

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized),属于强同步类。因此开销就比ArrayList要大,访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间,而ArrayList是1.5倍。Vector还有一个子类Stack。

四、Collection子接口之二:Set接口

1.Set 接口概述

1.Set接口是Collection的子接口,set接口没有提供额外的方法。
2.Set 集合不允许包含相同的元素,如果试把两个相同的元素加入同一个Set 集合中,则添加操作失败。
3.Set 判断两个对象是否相同不是使用 == 运算符,而是根据 equals() 方法。
4.|----Collection接口:单列集合,用来存储一个一个的对象

  • |----Set接口:存储无序的、不可重复的数据 -->高中讲的“集合”
    • |----HashSet:作为Set接口的主要实现类;线程不安全的;可以存储null值
  • |----LinkedHashSet:遍历其内部数据时,可以按照添加的顺序遍历,LinkedHashSet作为HashSet的子类,在添加数据的同时,每个数据还维护了两个引用,记录此数据前一个数据和后一个数据。优点:对于频繁的遍历操作,LinkedHashSet效率高于HashSet。
  • |----TreeSet:可以按照添加对象的指定属性,进行排序。

5.Set:存储无序的、不可重复的数据。以HashSet为例说明:

  1. 无序性:不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加,而是根据数据的哈希值决定的。
  2. 不可重复性:保证添加的元素按照equals()判断时,不能返回true.即:相同的元素只能添加一个。

2.Set实现类之一:HashSet

2.1向HashSet中添加元素的过程:

我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(即为:索引位置),判断数组此位置上是否已经有元素:

  • 如果此位置上没有其他元素,则元素a添加成功。 —>情况1
  • 如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较元素a与元素b的hash值:
    • 如果hash值不相同,则元素a添加成功。—>情况2
    • 如果hash值相同,进而需要调用元素a所在类的equals()方法:
      • equals()返回true,元素a添加失败
      • equals()返回false,则元素a添加成功。—>情况3
        在这里插入图片描述
        对于添加成功的情况2和情况3而言:元素a 与已经存在指定索引位置上数据以链表的方式存储。
        jdk 7 :元素a放到数组中,指向原来的元素。
        jdk 8 :原来的元素在数组中,指向元素a
        总结:七上八下

2.2重写 hashCode() 方法的基本原则

  • 在程序运行时,同一个对象多次调用 hashCode() 方法应该返回相同的值。
  • 当两个对象的 equals() 方法比较返回 true 时,这两个对象的 hashCode() 方法的返回值也应相等。
  • 对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值。

2.3重写 equals() 方法的基本原则

  • 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候,总是要改写hashCode(),根据一个类的equals方法(改写后),两个截然不同的实例有可能在逻辑上是相等的,但是,根据Object.hashCode()方法,它们仅仅是两个对象。
  • 因此,违反了“相等的对象必须具有相等的散列码”。
  • 结论:复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

3.Set实现类之二:LinkedHashSet

LinkedHashSet:遍历其内部数据时,可以按照添加的顺序遍历,LinkedHashSet作为HashSet的子类,在添加数据的同时,每个数据还维护了两个引用,记录此数据前一个数据和后一个数据。优点:对于频繁的遍历操作,LinkedHashSet效率高于HashSet。在这里插入图片描述

4.Set实现类之三:TreeSet

4.1TreeSet 概述:

首先,如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现 Comparable 接口。
其次,排序方式分为自然排序和定制排序。默认情况下,TreeSet 采用自然排序。

4.2自然排序

  • 向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。
  • 因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。
  • 对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj) 方法比较返回值。
  • 当需要把一个对象放入 TreeSet 中,重写该对象对应的 equals() 方法时,应保证该方法与 compareTo(Object obj) 方法有一致的结果:如果两个对象通过equals() 方法比较返回 true,则通过 compareTo(Object obj) 方法比较应返回 0。

4.3定制排序

  • TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。定制排序,通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
  • 利用int compare(T o1,T o2)方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。
  • 要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
  • 此时,仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
  • 使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。

五、Map接口

1.Map接口概述

|----Map:双列数据,存储key-value对的数据 —类似于高中的函数:y = f(x)

  • |----HashMap:作为Map的主要实现类;线程不安全的,效率高;存储null的key和value
    • |----LinkedHashMap:保证在遍历map元素时,可以按照添加的顺序实现遍历。
      原因:在原有的HashMap底层结构基础上,添加了一对指针,指向前一个和后一个元素。对于频繁的遍历操作,此类执行效率高于HashMap。
  • |----TreeMap:保证按照添加的key-value对进行排序,实现排序遍历。此时考虑key的自然排序或定制排序,底层使用红黑树
  • |----Hashtable:作为古老的实现类;线程安全的,效率低;不能存储null的key和value
    • |----Properties:常用来处理配置文件。key和value都是String类型

2.Map结构的理解(完全等同于数学中的函数):

①Map中的key:无序的、不可重复的,使用Set存储所有的key —> key所在的类要重写equals()和hashCode() (以HashMap为例)
②Map中的value:无序的、可重复的,使用Collection存储所有的value —>value所在的类要重写equals()
③ 一个键值对:key-value构成了一个Entry对象
④Map中的entry:无序的、不可重复的,使用Set存储所有的entry

3.HashMap的底层实现原理(以jdk7为例说明):

 HashMap map = new HashMap();  
 map.put(key1,value1); 

在实例化以后,底层创建了长度是16的一维数组Entry[] table。
首先,调用key1所在类的hashCode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Entry数组中的存放位置。

  • 如果此位置上的数据为空,此时的key1-value1添加成功。 ----情况1
  • 如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值:
    • 如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。----情况2
    • 如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较:调用key1所在类的equals(key2)方法,比较:
      如果equals()返回false:此时key1-value1添加成功。----情况3
      如果equals()返回true:使用value1替换value2。

补充:关于情况2和情况3:此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时,扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。

★jdk8 相较于jdk7在底层实现方面的不同:

  1. new HashMap():底层没有创建一个长度为16的数组
  2. jdk 8底层的数组是:Node[],而非Entry[]
  3. 首次调用put()方法时,底层创建长度为16的数组
  4. jdk7底层结构只有:数组+链表。jdk8中底层结构:数组+链表+红黑树。
    4.1 形成链表时,七上八下(jdk7:新的元素指向旧的元素。jdk8:旧的元素指向新的元素)
    4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,此时此索引位置上的所数据改为使用红黑树存储。

4.Map中的常用方法

4.1 添加、删除、修改操作:

Object put(Object key,Object value):将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key):移除指定key的key-value对,并返回value
void clear():清空当前map中的所有数据

4.2元素查询的操作:

Object get(Object key):获取指定key对应的value
boolean containsKey(Object key):是否包含指定的key
boolean containsValue(Object value):是否包含指定的value
int size():返回map中key-value对的个数
boolean isEmpty():判断当前map是否为空
boolean equals(Object obj):判断当前map和参数对象obj是否相等

4.3 元视图操作的方法(遍历):

Set—> .keySet():返回所有key构成的Set集合
Collection—> .values():返回所有value构成的Collection集合
Set—> .entrySet():返回所有key-value对构成的Set集合

总结:常用方法:

  • 添加:put(Object key,Object value)
  • 删除:remove(Object key)
  • 修改:put(Object key,Object value)
  • 查询:get(Object key)
  • 长度:size()
  • 遍历:keySet() / values() / entrySet()

5.Properties类

  • 常用来处理配置文件。key和value都是String类型
  • Properties 类是 Hashtable 的子类,该对象用于处理属性文件
  • 由于属性文件里的 key、value 都是字符串类型,所以 Properties 里的 key 和 value 都是字符串类型
  • 存取数据时,建议使用setProperty(String key,String value)方法和getProperty(String key)方法
Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-24 11:44:57  更:2021-07-24 11:47:32 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 9:45:58-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码