宁晋网站建设多少钱,工业设计创意网站,wordpress完全卸载教程,抖音小程序怎么入驻1 Map集合
1.1 Map接口
1.1.1 Map接口概述
Map接口是一种双列集合。Map的每个元素都包含一个键对象Key和一个值对象Value #xff0c;键对象和值对象之间存在对应关系#xff0c;这种关系称为映射#xff08;Mapping#xff09;。
Map接口中的元素#xff0c;可以通过…1 Map集合
1.1 Map接口
1.1.1 Map接口概述
Map接口是一种双列集合。Map的每个元素都包含一个键对象Key和一个值对象Value 键对象和值对象之间存在对应关系这种关系称为映射Mapping。
Map接口中的元素可以通过 key 找到 value因此
一个键只能映射一个值但允许多个不同的键映射到同一个值上键对象Key必须是唯一的不允许重复值对象Value允许重复
如下图所示 1.1.2 Map接口的实现类
Map接口常用的实现类包括HashMap、TreeMap和LinkedHashMap 1.1.3 Map接口的常用方法
Map是实现映射集合的根接口。Map接口定义了关于映射集合的相关的操作方法常用方法如下所示 1.1.4 【案例】Map常用方法示例
编写代码测试Map的常用方法。代码示意如下
import java.util.*;
public class MapDemo1 {public static void main(String[] args) {MapInteger,String map new HashMap();// 存放元素以键值对形式map.put(1, Tom);map.put(3, Jerry);map.put(5, Lucy);// 获取元素通过key获取valueString value map.get(1);System.out.println(value: value); // TomString value2 map.get(2); // 尝试通过不存在的key获取valueSystem.out.println(value2: value2); // 返回null// 存放已存在的key则替换value并返回被替换的valueString oldValue map.put(1, Tony);System.out.println(oldValue: oldValue); // TomSystem.out.println(value: map.get(1)); // Tony// 支持基于key删除键值对返回被删除的valuemap.remove(1);System.out.println(value: map.get(1)); // null// 查询map中是否包含了某个key 或 valueboolean flag1 map.containsKey(3);System.out.println(containsKey 3: flag1);boolean flag2 map.containsValue(Tom);System.out.println(containsValue Tom: flag2);// 返回包含了所有key的集合SetInteger keys map.keySet();System.out.println(keys: keys); // [3, 5]// 返回包含了所有value的集合CollectionString values map.values();System.out.println(values: values); // [Jerry, Lucy]}
}
1.2 哈希表
1.2.1 初识哈希表
哈希表Hash Table也称为散列表是一种常见的数据结构用于存储和检索键值对key-value pairs。它基于哈希函数将关键字key映射到数组索引下标以便快速访问和操作数据。
我们通过一个对比案例来介绍哈希表的作用及原理。在这个案例中我们需要按顺序添加5个键值对分别是(5, Lucy), (22, Tom), (131, Jerry), (666, Bob), (23, Alice)。
首先我们来看一下不使用哈希表的情况默认按照元素的添加顺序将键值对的键存放到数组中如下图所示。 这种方式的缺点在于使用key查询数据时最差的情况下需要遍历整个数组。
接下来我们来看一下使用哈希表的情况。想使用哈希表我们需要先定义一个哈希函数。简单的说哈希函数是计算一个key对应的数组索引的函数。
在本例中我们使用的哈希函数如下 此时计算得到的key与数组下标的关系如下 按照这一规则元素在数组中的存放位置如下 采用这样的方式使用key查询数据时可以使用相同的规则计算索引直接通过计算的结果获取数组该位置元素查询效率高。
在许多情况下哈希表比搜索树或任何其他表查找结构平均更有效。 因此哈希表被广泛用于多种计算机软件特别是关联数组、数据库索引、缓存和集合。
1.2.2 哈希算法
哈希函数也称Hash算法有多种实现方法比如“除留取余法”以及“直接定址法”、“数字分析法”、“分段叠加法”、“平均取中法”、“伪随机数法”等。
除留取余法如下图所示 1.2.3 哈希冲突
两个不同的输入值根据同一哈希函数计算出的索引相同的现象称为哈希冲突也称为哈希碰撞。
例如假设数组的长度为10使用除留取余法元素18和元素28对应的数组索引均为8即发生了哈希冲突。
衡量一个Hash算法的重要指标就是发生冲突的概率以及发生冲突的解决方案。任何Hash函数基本都无法彻底避免冲突常见的解决冲突的方法有以下几种
1、开放地址法一旦发生了冲突就去寻找下一个空的哈希地址只要哈希表足够大总能找到空的哈希地址并将元素存入。
2、再Hash法当Hash地址发生冲突时使用其他函数计算另一个Hash函数地址直到不再产生冲突为止。
3、建立公共溢出区将Hash表分为基本表和溢出表两部分发生冲突的元素都放入溢出表。
4、链地址法将Hash表的每个单元作为链表的头节点所有Hash地址为i的元素构成一个同义词链表即发生冲突时就把该元素链接在该单元为头节点的链表的尾部。 1.3 HashMap
1.3.1 HashMap概述
HashMap类是Map接口最常用的实现类之一内部基于哈希表存储键值对数据以提供高效的插入、删除和查找操作。HashMap在实际开发中广泛应用于缓存、索引、数据存储和快速查找等场景。
HashMap的内部使用了一个Node类来表示存储在哈希桶数组中的键值对。Node类是HashMap的内部私有静态类。 Node类包含了以下几个主要的字段
final int hash存储键的哈希码用于确定键值对在桶数组中的位置。final K key存储键的值。V value存储与键相关联的值。NodeK,V next用于处理哈希冲突存储下一个Node节点的引用形成链表或红黑树结构。
1.3.2 【案例】HashMap遍历示例
编写代码测试HashMap的遍历。代码示意如下
import java.util.*;
public class HashMapDemo1 {public static void main(String[] args) {MapInteger,String map new HashMap();// 存放元素以键值对形式map.put(5, Tom);map.put(3, Jerry);map.put(9, Lucy);// 通过keySet()方法遍历SetInteger keySet map.keySet();for(Integer key : keySet) {// 基于key查询value多了一步查询System.out.println(key: key value: map.get(key));}// 通过entrySet方法遍历推荐一次查询出全部键值对SetMap.EntryInteger,String entrySet map.entrySet();for(Map.EntryInteger,String entry:entrySet){System.out.println(key: entry.getKey() value: entry.getValue());}}
}
1.3.3 hashCode方法
在前面的案例中我们使用的key是整型可以直接参与取余运算。如果我们想要使用字符串或者自定义类型例如Student作为key是否还能使用哈希表呢答案是肯定的。
Java在Object类中设计了hashCode方法用于返回当前对象的哈希值。通过下面的源码可以看到该方法返回的是一个int类型的值。 通过这样的设计任意一个Java对象均可以作为哈希表的key。 1.3.4 put方法的执行流程
当使用HashMap对象的put方法存储一个键值对时一般会经过以下几步
1、计算Key的哈希值。
如果Key为null则哈希值为0如果Key不为null调用Key的hashCode方法计算Key的哈希值
2、如果内部数组没有被初始化会先初始化内部数组。
3、通过Key的哈希值计算Key在桶数组中的位置。
4、如果桶中目标位置没有元素则创建Node对象存储键值对数据并将Node对象保存到桶中目标位置。
5、如果桶中目标位置有元素注意可能有多个则将key与这些元素的key进行比较。
如果Key与某个元素的Key相等 或 equals则使用新存入的Value覆盖旧的Value如果Key与桶中该位置的所有元素都不相等则创建新的Node对象存储键值对数据并追加到链表中
1.3.5 【案例】put方法示例
编写代码测试HashMap的遍历。代码示意如下
import java.util.HashMap;
import java.util.Map;
public class HashMapDemo2 {public static void main(String[] args) {// 使用包裹类作为KeyMapInteger, String map1 new HashMap();map1.put(1, Tom);map1.put(1, Jerry);System.out.println(map1.get(1)); // Jerry// 使用自定义类作为KeyMapStudent, String map2 new HashMap();Student s1 new Student(Tom, 18);Student s2 new Student(Tom, 18);map2.put(s1, Tom);map2.put(s2, Jerry);System.out.println(map2.get(s1)); // TomSystem.out.println(map2.get(s2)); // Jerry// hashCode不同导致不会调用equals方法System.out.println(s1.hashCode:s1.hashCode()); // 990368553System.out.println(s1.hashCode:s2.hashCode()); // 1096979270}
}
class Student{String name;Integer age;public Student(String name, Integer age) {this.name name;this.age age;}Overridepublic boolean equals(Object obj) { // 案例中的equals并没有被调用System.out.println(equals方法被调用了: obj);return super.equals(obj);}Overridepublic String toString() {return Student{ name name \ , age age };}
}
1.3.6 重写hashCode方法
结合put方法的执行流程及上面案例的执行效果我们可以发现使用hashCode方法的默认实现逻辑可能导致HashMap无法正确识别两个逻辑相等的Key。 因此在使用自定义类型作为HashMap中的Key时需要重写该类的hashCode方法以满足以下要求。
1、多次调用同一个对象的hashCode方法应返回相同的哈希码。
2、如果两个对象被equals()方法判断为相等那么它们的hashCode()方法应该返回相同的哈希码。
3、如果两个对象被equals()方法判断为不相等不强制要求它们的hashCode()方法返回不同的哈希码但是开发者应该了解返回不同的哈希码有利于提高哈希表的性能。
集成式开发环境如IDEA和Eclipse均提供了重写hashCode和equals方法的支持开发者可直接使用提高开发效率。
1.3.7 【案例】HashMap应用示例
请基于HashMap重构前一天的ArrayList应用示例对比HashMap和ArrayList在使用上的差别。
1、将前一天的Subject、Exam和ArrayListDemo2三个类拷贝到今天的package中。
2、将ArrayListDemo2更名为HashMapDemo3。
3、分析并重构HashMapDemo3中的代码在适合使用HashMap的地方将ArrayList替换为HashMap。
import java.io.BufferedReader;
import java.io.FileReader;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.*;
public class HashMapDemo3 {public static void main(String[] args) {String subjectPath d:/data/subject.csv;String examPath d:/data/exam.csv;HashMapInteger, Subject subjects readSubjects(subjectPath);System.out.println(subjects); // 打印科目信息HashMapInteger, Exam exams readExams(examPath, subjects);System.out.println(exams); // 打印考试信息// 筛选出考试时间在10点之后的考试信息DateTimeFormatter formatter DateTimeFormatter.ofPattern(yyyy-MM-dd HH:mm:ss);for (Exam exam : exams.values()) {LocalDateTime ldt LocalDateTime.parse(exam.getStartTime(),formatter);if (ldt.getHour()9){System.out.println(exam);}}}/*** 读取文件中的数据每行生成一个考试对象存储到集合中* param path* param subjects* return*/public static HashMapInteger, Exam readExams(String path, MapInteger, Subject subjects) {ListString lines readLines(path);HashMapInteger, Exam exams new HashMap();for (String line : lines) {String[] arr line.split(,);Exam exam new Exam();exam.setId(Integer.parseInt(arr[0]));exam.setName(arr[1]);exam.setStartTime(arr[2]);exam.setDuration(Integer.parseInt(arr[3]));// 从map中查询科目对象exam.setSubject(subjects.get(Integer.parseInt(arr[4])));exams.put(exam.getId(), exam);}return exams;}/*** 读取文件中的数据每行生成一个科目对象存储到集合中* param path* return*/public static HashMapInteger, Subject readSubjects(String path){ListString lines readLines(path);HashMapInteger, Subject subjects new HashMap();for(String line : lines){String[] arr line.split(,);Subject subject new Subject();subject.setId(Integer.parseInt(arr[0]));subject.setName(arr[1]);subjects.put(subject.getId(), subject);}return subjects;}/*** 读取文件中的数据每行生成一个字符串存储到集合中* param path* return*/public static ArrayListString readLines(String path){ArrayListString lines new ArrayList();try(FileReader fr new FileReader(path);BufferedReader br new BufferedReader(fr);){String line br.readLine();line br.readLine(); // 跳过第一行while(line ! null){lines.add(line);line br.readLine();}}catch (Exception e){e.printStackTrace();}return lines;}
}
1.4 HashMap原理
1.4.1 HashMap的容量
HashMap中使用数组作为存储元素的桶对应的内部属性为table如下图所示。HashMap的内部数组不是在创建HashMap对象时初始化而是在首次存入元素时进行初始化以减少对内存的占用。 从源码注释中我们可以发现官方规定table的长度总是2的幂即2的N次方。这样设计的原因是为了保证HashMap的速度足够快。这是一个需要特别注意的面试高频考点。
我们知道不论存操作还是取操作HashMap都使用除留取余法通过key的哈希值计算key在桶中的索引。如果能优化这一计算的速度将会大幅优化HashMap存取操作的速度。
在数学中有这样一条公式X % 2^n X (2^n - 1) 。简单的说当X对Y取余时如果Y是2的幂则可以将取余运算转换为位运算以提高计算速度。
综上HashMap的容量始终是2的幂以保证内部高效的哈希运算。
1.4.2 HashMap的初始容量
与ArrayList相似HashMap的初始容量分为默认容量和手动指定两种情况。
当使用无参构造器创建HashMap对象时table的初始化长度为16由如下的静态常量指定。 因此默认情况下HashMap的默认容量为16。
HashMap支持使用带参构造器HashMap(int initialCapacity)来创建HashMap对象并指定内部数组的初始化长度。
此处需要注意HashMap并不会直接使用开发者指定的长度作为内部数组的长度而是会通过一个内部方法计算大于开发者指定长度的最小的2的幂作为内部数组的长度。 因此当开发者指定初始长度时HashMap的容量为大于该长度的最小的2的幂。
1.4.3 HashMap的扩容
HashMap中提供了桶的自动扩容机制在满足特定的条件时自动将桶的长度扩容到原来的两倍。
想要理解桶的扩容条件需要先分清楚4个概念
1、容量capacityHashSet内部数组的长度默认长度为162、大小sizeHashSet中实际存储的元素的个数默认为03、负载因子loadFactor用来衡量HashSet“满”的程度默认值为0.75f4、临界值threshold当size超过临界值时HashSet将会扩容threshold capacity * loadFactor
对于一个默认的HashSet来说临界值16 * 0.75 12即当存储了超过12个元素时HashSet会自动扩容将容量扩大到原来的2倍即32。
扩容后还会对所有的元素进行一次rehash操作相当于对所有的元素重新做一遍Hash运算是一项比较耗时的操作。
由于存在上述的设计因此开发者手动指定HashMap的初始容量时需要计算合适的容量而不是直接传入要存储元素的个数。具体可参考《阿里巴巴 Java开发手册》中的建议。 1.4.4 树化与退化
HashMap中使用链地址法处理Hash冲突当桶中某个位置的链表过长时会响查询效率的情况。 自Java 8开始HashMap在解决哈希冲突时引入了红黑树的应用以提高查找操作的效率。当链表长度大于等于阈值默认为8同时HashMap容量已达到64时链表会转换为红黑树从而减少查找操作的时间复杂度这个过程称为树化Treeify。
树化的2个阈值由HashMap内部的静态常量指定。 红黑树是一种自平衡的二叉搜索树它具有良好的平衡性能和较快的查找、插入和删除操作的时间复杂度。相比于链表红黑树在大型哈希桶中可以提供更快的查找速度。 同时当红黑树中的节点数量减少到一定程度默认为6时HashMap会将红黑树转换回链表。这个过程称为退化Untreeify。退化的阈值同样由HashMap内部的静态常量指定 1.5 LinkedHashMap
1.5.1 LinkedHashMap概述
HashMap虽然提供了高效的添加和查询功能但是无法保存元素的添加顺序。在一些特定的应用场景中可能需要保存键值对的添加顺序此时可以使用LinkedHashMap来实现。
例如项目既需要提供按用户名快速查询用户信息的功能也需要提供按用户签到顺序显示用户信息列表的功能。此时需要能够记载元素的添加顺序。
LinkedHashMap是在HashMap的基础上维护了一个Entry的双向链表以此记录元素之间的先后顺序。 1.5.2 【案例】LinkedHashMap示例
编写代码测试LinkedHashMap的遍历。代码示意如下
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class LinkedHashMapDemo {public static void main(String[] args) {LinkedHashMapInteger,String map new LinkedHashMap();// 存放元素以键值对形式map.put(5, Tom);map.put(3, Jerry);map.put(9, Lucy);// 通过entrySet方法遍历SetMap.EntryInteger,String entrySet map.entrySet();for(Map.EntryInteger,String entry:entrySet){System.out.println(key: entry.getKey() value: entry.getValue());}}
}
2 Set集合
2.1 Set接口
2.1.1 Set接口概述
Set接口继承自Collection接口所以与Collection接口中的方法基本一致并没有对Collection接口进行功能上的扩充只是比Collection接口更加严格。
Set集合的特点是无序且不可重复
无序不能保证按照添加元素的顺序来存放元素不可重复集合中不能存储两个用equals方法判断为相等的元素
可以利用Set集合不可重复的特点实现去重操作。
2.1.2 【案例】Set集合示例
编写代码测试Set集合的使用。代码示意如下
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class SetDemo1 {public static void main(String[] args) {ListInteger list Arrays.asList(7, 3, 1, 3, 5, 3, 1);// 创建Set集合对象并将list集合中的元素添加到Set中SetInteger set new HashSet(list);System.out.println(set); // 1, 3, 5, 7// 尝试添加重复元素boolean flag set.add(1);System.out.println(flag: flag); // falseSystem.out.println(set); // 1, 3, 5, 7}
}
2.1.3 集合运算
Set接口能利用相关方法实现数学上的集合运算如并、交、差等 常用的集合运算方法如下所示 2.1.4 【案例】集合运算示例
编写代码测试集合运算。代码示意如下
import java.util.*;
public class SetDemo2 {public static void main(String[] args) {ListInteger list1 Arrays.asList(1, 2, 3, 4);ListInteger list2 Arrays.asList(3, 4, 5, 6);SetInteger set1 new HashSet(list1);SetInteger set2 new HashSet(list2);System.out.println(set1: set1);System.out.println(set2: set2);// 求交集set1.retainAll(set2);System.out.println(set1 和 set2 交集set1);// 重置set1set1 new HashSet(list1);// 求并集set1.addAll(set2);System.out.println(set1 和 set2 并集set1);// 重置set1set1 new HashSet(list1);// 求补集set1.removeAll(set2);System.out.println(set1 和 set2 补集set1);}
}
2.2 HashSet
2.2.1 HashSet概述
HashSet是Java中实现了Set接口的集合类它使用哈希表作为底层数据结构用于存储唯一的元素。HashSet不保证元素的顺序且不允许重复元素。
HashSet底层实际上是使用HashMap对象来存储数据如下图所示。 以下是HashSet的一些特点
1、HashSet基于哈希表使用哈希函数将元素映射到对应的存储位置。
2、HashSet存储的元素是无序的即元素的插入顺序与遍历顺序不一致。
3、HashSet不允许重复元素每个元素只能出现一次。当尝试将重复元素添加到HashSet时操作将被忽略。
4、HashSet的元素可以是任何对象但需要正确实现hashCode()和equals()方法以确保元素的唯一性。
5、HashSet允许使用null作为元素但只能有一个null元素。
6、HashSet的插入、删除和查找操作具有常数时间复杂度平均情况下为O(1)提供了高效的性能。
2.2.2 【案例】HashSet示例
编写代码测试HashSet的使用。代码示意如下
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
public class HashSetDemo1 {public static void main(String[] args) {SetStudent1 set1 new HashSet();set1.add(new Student1(Tom,18));set1.add(new Student1(Tom,18));System.out.println(set1);SetStudent2 set2 new HashSet();set2.add(new Student2(Tom,18));set2.add(new Student2(Tom,18));System.out.println(set2);}
}
class Student1{String name;int age;public Student1(String name, int age) {this.name name;this.age age;}Overridepublic String toString() {return Student1{ name name \ , age age };}
}
class Student2{String name;int age;public Student2(String name, int age) {this.name name;this.age age;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student2 student2 (Student2) o;return age student2.age Objects.equals(name, student2.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}Overridepublic String toString() {return Student1{ name name \ , age age };}
}
