JavaSE 进阶 (7) 集合

piliqiu piliqiu 收录于 JavaSE 进阶
 约 1000 字 预计阅读 5 分钟 

HashSet-基本使用

HashSet集合概述和特点

HashSet 集合特点

  • 底层数据结构是哈希表
  • 不能保证存储和取出的顺序完全一致
  • 没有带索引的方法，所以不能使用普通 for 循环遍历
  • 由于是 Set 集合，所以元素唯一

HashSet集合练习

存储字符串并遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void main(string[] args){
	HashSet<String> hs = new HashSet<>();
	
	hs.add("hello");
	hs.add("world");
	hs.add("java");
	hs.add("java");
	hs.add("java");
	hs.add("java");
	hs.add("java");
	hs.add("java");

	Iterator<String> it = hs.iterator();
	while(it.hasNext()){
		String s = it.next();
		System.out.println(s);
	}

	System.out.println("=============================");

	for(String s : hs){
		System.out.println(s);
	}
}
图1

HashSet-哈希值

哈希值(哈希码值): 是 JDK 根据对象的地址或者属性值，算出来的 int 类型的整数


Object 类中有一个方法可以获取对象的哈希值

  • public int hashCode(): 根据对象的地址值计算出来的哈希值

一个类没有继承关系的话，默认继承 Object 类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/**
 * 计算哈希值
*/
public class HashSetDemo2{
	public static void main(string[] args){
		Student s1 = new Student("xiaozhi", 23);
		Student s2 = new Student("xiaomei", 22);

		//因为在Object类中，是根据对象的地址值计算出来的哈希值。
		System.out.println(s1.hashcode()); //1060830840
		System.out.println(s1.hashcode()); //1060830840
		
		System.out.println(s2.hashCode()); //2137211482
	}
}

我们可以对 Object 类中的 hashCode 方法进行重写，重写之后，就是根据对象的属相值来计算哈希值的，此时，对象的哈希值就跟地址值没有任何关系了

1
2
3
4
5
6

@Override
public int hashCode() {
	int result = name != null ? name.hsahCode() : 0;
	result = 31 * result + age;
	return result;
}

对象的哈希值特点

如果没有重写 hashCode 方法，那么是根据对象的地址值计算出的哈希值

  • 同一个对象多次调用 hashCode() 方法，返回的哈希值是相同的
  • 不同对象的哈希值是不一样的

如果重写了 hashCode 方法，一般都是通过对象的属性值计算处哈希值

  • 如果不同的对象属性值是一样的，那么计算出来的哈希值也是一样的

HashSet-JDK7底层原理解析

常见数据结构之哈希表

哈希表

  • JDK8 之前，底层采用数组+链表实现 (不包含jdk8)
  • JDK8 以后，底层进行了优化，由数组+链表+红黑树实现 (包含jdk8)

HashSet1.7 版本原理解析

图2

HashSet<String> hs = new HashSet<>();

图3

加载因子决定了集合在什么时候扩容

HashSet-JDK8底层优化

HashSet1.8 底层原理解析

图4

为了防止在4索引处的链表过长，如:100-200个，新存入的元素需要和每个元素相比较，次数过多，影响性能

加入红黑树的目的是为了提高效率

图5

此时，如果有元素要存入4索引，他会按照红黑树规则，小的跟左边比，大的跟右边比，如果一样则不存


总结

  1. 底层结构：哈希表 (数组、链表、红黑树)
  2. 当挂在下面的元素过多时，不利于添加，也不利于查询，所以在 JDK8 以后，当链表长度超过 8 时，会自动转换为红黑树
  3. 存储流程不变

HashSet1.8 版本的存储流程

图6

HashSet-练习

案例：HashSet 集合存储学生对象并遍历

需求：创建一个 HashSet 集合，存储多个学生对象，并进行遍历

要求：学生对象的成员变量值相同，我们就认为是同一个对象

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class HashSetTest1{
	public static void main(String[] args){
		HashSet<Student> hs = new HashSet<>();
		Student s1 = new Student("xiaohei", 23);
		Student s2 = new Student("xiaohei", 23);
		Student s3 = new Student("xiaomei", 22);

		hs.add(s1);
		hs.add(s2);
		hs.add(s3);
		
		for (Student student : hs){
			System.out.println(student);
		}
	}
}
图7

HsahSet 存放的是不重复的值，但是此时 (xiaohei,23) 重复了，并且存储成功了，这是因为 Student 调用父类 Object 类中的 hsahCode 方法，通过对象的地址值计算出哈希值进行比较，此时哈希值是不同的

图8

要求是: 同姓名，同年龄，就认为是同一个不存

重写 hashCode 方法，根据属相值计算哈希值，哈希值相同，存入相同的位置，再重写 equals 方法，比较属相值，一样则不存

图9

结论: 如果 HashSet 集合要存储自定义对象，那么必须重写 hsahCode 和 equals 方法

HashSet-小结

Set集合小结

图10

HashSet：在存储自定义对象的时候，自定义的对象里必须重写 hashCode 方法和 equals 方法，如果存 String、Integer 等，java 底层已经写好了，直接存就好

TreeSet：排序规则分为自然排序、比较器排序，默认使用的是自然排序，若自然排序不能满足要求，就使用比较器排序


LinkedHashSet

  • 概述：LinkedHashSet 是 HashSet 的子类，所以也要求重写 hashCode 和 equals 方法
  • 特点：LinkedHashSet 是 Set 家族唯一一个”有序的集合”

Map-基本使用

Map集合概述和使用

单列集合：一次存一个元素 图11

双列集合：一次存两个元素 (一对数据) 图12 图13 图14


Map 集合概述

  • Interface Map<K, V> K: 键的数据类型 ; V: 值的数据类型
  • 键不能重复，值可以重复
  • 键和值是一一对应的，每一个键只能找到自己对应的值
  • (键 + 值) 这个整体我们称之为 “键值对” 或者 “键值对对象” ，在 Java 中叫做 “Entry对象”

举例: 学生的学号和姓名

学号 姓名
1001 小智
1002 小美
1003 大胖

创建 Map 集合的对象

  • 多态的方式
  • 具体的实现类 HashMap
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

/**
 * map的基本使用 
*/
public class MyMap1{
	public static void main(String[] args){
		Map<String,String> map = new HashMap<>();

		map.put("001", "小智");
		map.put("002", "小美");
		map.put("003", "大胖");
		
		System.out.println(map);
	}
}

Map-常用方法

Map集合的基本功能

方法名 说明
public v put (键 , 值) 添加(如果集合中没有指定的键，则是添加，如果集合中已经存在了指定的键，则是修改，同时返回修改之前的值)
public v remove(键) 根据键删除键值对元素 (返回被删除的键值对的值)
public void clear() 清空集合中的所有元素
public boolean containsKey(键) 判断集合中是否包含指定的键
public boolean containsValue(值) 判断集合中是否包含指定的值
public boolean isEmpty() 判断集合是否为空
public int size() 获取集合中 ”键值对” 的个数
public 值 get(键) 根据键获取值
public Set keyset() 获取所有的键
public Collection values() 获取所有的值
public Set<Map.Entry<K,V» entrySet() 获取所有的键值对 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class MyMap2{
	public static void main(String[] args){
		Map<String,String> map = new HashMap<>();
		// V put(K key, V value)  添加元素
		//如果要添加的键不存在，那么会把键值对都添加到集合中
		//如果要添加的键是存在的，那么会覆盖原先的值，把原先值当做返回值进行返回。
		map.put("001", "小智");
		map.put("002", "小美");
		map.put("003", "大胖");
		map.put("004", "小黑");
		map.put("005", "大师");

		String s = map.put("001","aaa");
		System.out.println(s);  //"小智"
		System.out.println(map);
	}
}

Map-第一种遍历方式

遍历Map集合

小故事：有一个房间，里面有 N 对夫妻，先找到所有的丈夫，询问每一个丈夫，让他们找到自己的妻子 图15 图16

Map集合的获取功能

方法名 说明
etkeySet() 获取所有键的集合
get(Object key) 根据键获取值 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class MyMap3{
	public static void main(String[] args){
		//创建集合并添加元素
		Map<String,String> map = new HashMap<>();
		map.put("1号丈夫","1号妻子");
		map.put("2号丈夫","2号妻子");
		map.put("3号丈夫","3号妻子");
		map.put("4号丈夫","4号妻子");
		map.put("5号丈夫","5号妻子");

		//获取到所有的键
		Set<string> keys = map.keyset();

		//遍历Set集合得到每一个键
		for(String key : keys){
			//通过每一个键key,来获取到对应的值
			string value = map.get(key);
			System.out.println(key + "---" + value);
		}
	}
}

Map-第二种遍历方式

图17
方法名 说明
Set<Map.Entry<K,V»entrySet() 获取所有键值对对象的集合
K getKey() 获得键
V getValue() 获得值 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class MyMap4{
	public static void main(String[] args){
		//创建集合并添加元素
		Map<String,String> map = new HashMap<>();
		map.put("1号丈夫","1号妻子");
		map.put("2号丈夫","2号妻子");
		map.put("3号丈夫","3号妻子");
		map.put("4号丈夫","4号妻子")
		map.put("5号丈夫","5号妻子");

		//首先要获取到所有的键值对对象。
		//Set集合中装的是键值对对象(Entry对象)
		//而Entry里面装的是键和值
		Set<Map.Entry<String,String>> entries = map.entryset();
		for(Map.Entry<string,string> entry : entries){
			//得到每一个键值对对象
			String key = entry.getkey();
			String value = entry.getvalue();
			System.out.println(key + "---" + value);
		}
	}
}

Set<Map.Entry<String,String» entries = map.entryset();: Set 集合中装的是 Entry 对象 (Entry 是 map 里的内部类)，所以 Set 的泛型是: Set<Map.Entry>，而 Entry 对象里面装的是键和值，所以 Map.Entry 的泛型 是Map.Entry<String, String>

Map-第三种遍历方式 

1
2
3
4
5
6
7

public static void main(String[] args) {
    HashMap<Student,String> hs = new HashMap<>();
    Set<Student> students = hs.keySet();
    hs.forEach((Student key, String val) -> {
        System.out.println(key + "---" + val);
    });
}
图18

HashMap-原理解析

HashMap的特点

  • HashMap 是 Map 里面的一个实现类
  • 没有额外需要学习的方法，直接使用 Map 里面的方法就可以了
  • HashMap 跟 HashSet 一样，底层是哈希表结构
  • 依赖 hashCode 方法和 equals 方法保证键的唯一
  • 如果键要存储的是自定义对象，需要重写 hashCode 和 equals 方法，如果是在值的位置存储自定义对象，是不用重写 hashCode 和 equals 方法，如果键的位置是字符串，也是不用重写的，因为 Java 已经帮我们写好了，我们直接用就好了

HashMap的添加规则

图19
  1. 将键和值放入到 Entry 对象中
  2. 通过 hashCode 方法，计算出键的哈希值 (跟键值对中的值是无关的)
  3. 算出在数组中存放的位置，如果这个位置为 null，则直接放进去，该位置不为 null，调用 equals 方法比较键的属相值，一样，覆盖原来的键值对对象，不一样，新的添加到数组中，老的元素挂在新元素的下面，形成一个链表

在 JDK8 时，为了提高性能，当链表的长度大于等于 8 的时候，会自动转为红黑树

图20

HashMap-练习

案例：HashMap 集合存储自定义对象并遍历

需求：创建一个 HashMap 集合，键是学生对像(Student)，值是籍贯(String)。存储三个键值对元素，并遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class MyMap5{
	public static void main(String[] args){
		HashMap<Student,String> hm = new HashMap<>();
		Student s1 = new Student("xiaohei", 23);
		Student s2 = new Student("dapang", 22);
		Student s3 = new Student("xiaomei", 22);
		
		hm.put(s1,"江苏");
		hm.put(s2,"北京");
		hm.put(s3,"天津");
		
		//第一种：先获取到所有的键，再通过每一个键来找对应的值
		Set<Student> keys = hm.keyset();
		for (Stndent key : keys){
			String value = hm.get(key);
			System.out.println(key + "----" + value);
		}
		
		//第二种：先获取到所有的键值对对象。再获取到里面的每一个键和每一个值
		Set<Map.Entry<Student,String> >entries = hm.entryset();
		for(Map.Entry<Student,string> entry : entries){
			Student key = entry.getkey();
			String value = entry.getvalue();
			System.out.println(key + "----" + value);
		}
		
		//第三种：通过foreach方法，给一个函数式接口biConsumer的匿名实现类
		hm.forEach(
			(Student key, String value)->{
				system.out.println(key + "----" + value);
			}
		);
		
	}
}

TreeMap-原理解析

TreeMap的特点

  • TreeMap 是 Map 里面的一个实现类
  • 没有额外需要学习的特有方法，直接使用 Map 里面的方法就可以了
  • TreeMap 跟 TreeSet 一样底层是红黑树结构
  • 依赖自然排序或者比较器排序，对键进行排序
  • 如果键存储的是自定义对象，需要实现 Comparable 接口或者在创建 TreeMap 对象的时候给出比较器规则

TreeMap原理

图21 图22 图23

违反红黑树规则：根节点必须是黑色的

图24

添加第二个节点: 根据自然排序规则或比较器排序规则

图25 图26 图27 图28

两个连续的红色节点，违反红黑规则

  • 将“父节点”设为“黑色
  • 将“祖父节点”设方红色”
  • 以祖父节点为支点进行旋转
图29

遍历：

  • 先获取左边
  • 再获取中间
  • 再获取右边

小结

HashMap < - > HashSet

TreeMap < - > TreeSet


HashMap:

  • HashMap 的键，本质上就是 HashSet
  • HashMap 的键要求不允许重复，也要重写 hashCode 和 equals 方法

TreeMap:

  • TreeMap 的键，本质就是 TreeSet
  • TreeMap 的键，不允许重复，需要让键实现 Comparable 接口，或者提供一个 Comparator 比较器对象
收录于 合集・JavaSE 进阶 7
更新于 2025-12-08 
CC BY-NC-SA 4.0
在编辑器中打开
返回 | 主页
0%