Day27 手撕各种集合底层源码（二）

2024-03-31 03:52
文章标签 源码 底层 集合 day27

本文主要是介绍Day27 手撕各种集合底层源码（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Day27 手撕各种集合底层源码（二）

文章目录

  • Day27 手撕各种集合底层源码（二）
    • 一、手撕TreeMap底层原理
    • 二、 手撕TreeSet底层源码
    • 三、手撕Vector底层源码
    • 四、手撕HashMap的底层源码

一、手撕TreeMap底层原理

1、概念： TreeMap是基于红黑树实现的有序映射表，它通过红黑树来维护键值对的有序性。红黑树是一种自平衡的二叉查找树，具有较快的查找、插入和删除操作的时间复杂度。

2、应用场景：

  • 需要对键值对按照键的顺序进行排序存储和查找的场景。
  • 需要在有序映射表中进行范围查找的场景。

3、主要原理：

  1. 红黑树：TreeMap内部使用红黑树来存储键值对，红黑树是一种自平衡的二叉查找树，通过对节点的颜色和旋转操作来保持树的平衡。
  2. 比较器：TreeMap可以使用自然顺序或者自定义比较器来对键进行排序，如果没有提供比较器，则键需要实现Comparable接口。
  3. 节点结构：每个节点包含键、值和指向左右子节点的指针，以及表示节点颜色的信息。

4、关键方法：

  1. 插入操作：通过比较器或键的自然顺序将键值对插入到红黑树中，并根据红黑树的性质进行调整，以保持树的平衡。
  2. 删除操作：删除指定键的节点，并根据红黑树的性质进行调整，以保持树的平衡。
  3. 查找操作：根据键的比较结果在红黑树中进行查找，以实现快速的查找操作。

5、举例：

import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;public class Test01 {/*** 知识点：手撕TreeMap底层原理 -- 内置比较器*/public static void main(String[] args) {TreeMap<Student,String> map = new TreeMap<>();map.put(new Student("小空", '女', 23, "2401", "002"),"看书");        map.put(new Student("小希", '女', 27, "2401", "001"),"运动");        map.put(new Student("小丽", '女', 21, "2401", "003"),"打游戏");  //有相同的key，就替换value值String put = map.put(new Student("小丽", '女', 21, "2401", "003"),"写代码");System.out.println(put);//打游戏Set<Entry<Student,String>> entrySet = map.entrySet();for (Entry<Student, String> entry : entrySet) {System.out.println(entry);}}
}
public class Student implements Comparable<Student>{private String name;private char sex;private int age;private String classId;private String id;public Student() {}public Student(String classId, String id) {this.classId = classId;this.id = id;}public Student(String name, char sex, int age, String classId, String id) {this.name = name;this.sex = sex;this.age = age;this.classId = classId;this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public char getSex() {return sex;}public void setSex(char sex) {this.sex = sex;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getClassId() {return classId;}public void setClassId(String classId) {this.classId = classId;}public String getId() {return id;}public void setId(String id) {this.id = id;}//判断两个学生是否相同//比较规则：班级号+学号@Overridepublic boolean equals(Object obj) {if(this == obj){return true;}if(obj instanceof Student){Student stu = (Student) obj;if(this.classId.equals(stu.classId) && this.id.equals(stu.id)){return true;}}return false;}@Overridepublic String toString() {return name + "\t" + sex + "\t" + age + "\t" + classId + "\t" + id;}//排序规则：按照年龄排序@Overridepublic int compareTo(Student o) {//this表示添加到TreeSet中的学生对象//o表示TreeSet中的学生对象return this.age - o.age;}
}

二、 手撕TreeSet底层源码

1、概念： TreeSet是基于TreeMap实现的有序集合，它通过红黑树来维护元素的有序性。红黑树是一种自平衡的二叉查找树，具有较快的查找、插入和删除操作的时间复杂度。

2、应用场景：

  • 需要对元素按照自然顺序或自定义顺序进行排序存储和查找的场景。
  • 需要在有序集合中进行范围查找的场景。

3、主要原理：

  1. 红黑树：TreeSet内部使用红黑树来存储元素，红黑树是一种自平衡的二叉查找树，通过对节点的颜色和旋转操作来保持树的平衡。
  2. 元素比较：TreeSet使用元素的自然顺序或者自定义比较器来对元素进行排序，从而构建有序的红黑树。

4、关键方法：

  1. 添加元素：通过比较器或元素的自然顺序将元素插入到红黑树中，并根据红黑树的性质进行调整，以保持树的平衡。
  2. 删除元素：删除指定元素的节点，并根据红黑树的性质进行调整，以保持树的平衡。
  3. 查找操作：根据元素的比较结果在红黑树中进行查找，以实现快速的查找操作。

5、举例：

import java.util.TreeMap;
import java.util.TreeSet;public class Test01 {/*** 知识点：手撕TreeSet底层源码 -- 内置比较器*/public static void main(String[] args) {TreeSet<Student> set = new TreeSet<>();set.add(new Student("椎名空", '女', 23, "2401", "002"));        set.add(new Student("麻生希", '女', 27, "2401", "001"));        set.add(new Student("水菜丽", '女', 21, "2401", "003"));        new TreeMap<>();}
}
public class Student implements Comparable<Student>{private String name;private char sex;private int age;private String classId;private String id;public Student() {}public Student(String classId, String id) {this.classId = classId;this.id = id;}public Student(String name, char sex, int age, String classId, String id) {this.name = name;this.sex = sex;this.age = age;this.classId = classId;this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public char getSex() {return sex;}public void setSex(char sex) {this.sex = sex;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getClassId() {return classId;}public void setClassId(String classId) {this.classId = classId;}public String getId() {return id;}public void setId(String id) {this.id = id;}//判断两个学生是否相同//比较规则：班级号+学号@Overridepublic boolean equals(Object obj) {if(this == obj){return true;}if(obj instanceof Student){Student stu = (Student) obj;if(this.classId.equals(stu.classId) && this.id.equals(stu.id)){return true;}}return false;}@Overridepublic String toString() {return name + "\t" + sex + "\t" + age + "\t" + classId + "\t" + id;}//排序规则：按照年龄排序@Overridepublic int compareTo(Student o) {//this表示添加到TreeSet中的学生对象//o表示TreeSet中的学生对象return this.age - o.age;}
}

三、手撕Vector底层源码

1、概念： Vector是一个基于动态数组实现的线程安全的集合类。

2、应用场景：

  • 需要对元素按照自然顺序或自定义顺序进行排序存储和查找的场景。
  • 需要在有序集合中进行范围查找的场景。

3、经验：

Vector 部分关键源码，展示了其基于数组的动态扩容结构和常用方法的实现。通过动态扩容，Vector能够灵活地管理元素的存储，并提供了高效的添加、删除和访问操作。

4、关键源码：

成员变量：

protected Object[] elementData; // 用于存储元素的数组
protected int elementCount; // Vector中元素的数量
protected int capacityIncrement; // 动态增长的容量增量

构造方法：

public Vector() {javathis(10, 0);
}public Vector(int initialCapacity, int capacityIncrement) {if (initialCapacity < 0) {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}this.elementData = new Object[initialCapacity]; // 初始化数组this.capacityIncrement = capacityIncrement;
}

添加元素方法（add）：

public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1); // 确保容量足够elementData[elementCount++] = e; // 将元素添加到数组末尾return true;
}private void ensureCapacityHelper(int minCapacity) {if (minCapacity - elementData.length > 0) {grow(minCapacity); // 扩容}
}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); // 计算新容量if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}if (newCapacity - MAX_ARRAY_SIZE > 0) {newCapacity = hugeCapacity(minCapacity);}elementData = Arrays.copyOf(elementData, newCapacity); // 数组扩容
}

扩容方法：

private int hugeCapacity(int minCapacity) {if (minCapacity < 0) { // 溢出检查throw new OutOfMemoryError();}return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

5、举例：

import java.util.Vector;public class Test01 {/*** 知识点：手撕Vector底层源码*/public static void main(String[] args) {//Vector<String> v = new Vector<>(10, 5);Vector<String> v = new Vector<>();v.add("aaa");v.add("bbb");v.add("ccc");v.add("ddd");System.out.println(Integer.MAX_VALUE);}
}

四、手撕HashMap的底层源码

1、概念·： HashMap是基于哈希表实现的键值对映射 。

2、经验： HashMap 基于哈希表的键值对映射结构和常用方法的实现。通过哈希表，HashMap能够高效地管理键值对，并提供了快速的添加、删除和查找操作。

3、关键源码：

主要成员变量：

transient Node<K,V>[] table; // 用于存储键值对的哈希桶数组
transient Set<Map.Entry<K,V>> entrySet; // 存储键值对的集合
transient int size; // HashMap中键值对的数量
int threshold; // 扩容阈值
final float loadFactor; // 负载因子

内部节点类定义：

static class Node<K,V> implements Map.Entry<K,V> {final int hash; // 键的哈希值final K key; // 键V value; // 值Node<K,V> next; // 指向下一个节点的指针
}

添加元素方法（put）：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0) {n = (tab = resize()).length;}if ((p = tab[i = (n - 1) & hash]) == null) {tab[i] = newNode(hash, key, value, null);} else {// 省略部分代码}if (++size > threshold) {resize();}return null;
}

获取元素方法（get）：

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k)))) {return first;}if ((e = first.next) != null) {// 省略部分代码}}return null;
}

4、举例：

import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;public class Test01 {/*** 知识点：手撕HashMap底层原理*/public static void main(String[] args) {//		Float float1 = new Float("0.0f");
//		Float float2 = new Float("0.0f");
//		Float result = float1/float2;
//		System.out.println(result);//NaN
//		System.out.println(Float.isNaN(result));
//		HashMap<Student, String> map = new HashMap<>(16,result);HashMap<Student, String> map = new HashMap<>();map.put(new Student("小浩", '男', 23, "2401", "001"), "拍电影");map.put(new Student("小威", '男', 20, "2401", "002"), "打篮球");map.put(new Student("小俊", '男', 21, "2401", "003"), "玩游戏");map.put(new Student("小俊", '男', 21, "2401", "003"), "写代码");map.put(null, "aaa");map.put(null, "bbb");Set<Entry<Student,String>> entrySet = map.entrySet();for (Entry<Student, String> entry : entrySet) {System.out.println(entry);}}
}
public class Student {private String name;private char sex;private int age;private String classId;private String id;public Student() {}public Student(String name, char sex, int age, String classId, String id) {this.name = name;this.sex = sex;this.age = age;this.classId = classId;this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public char getSex() {return sex;}public void setSex(char sex) {this.sex = sex;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getClassId() {return classId;}public void setClassId(String classId) {this.classId = classId;}public String getId() {return id;}public void setId(String id) {this.id = id;}@Overridepublic int hashCode() {return 20;}@Overridepublic boolean equals(Object obj) {if(this == obj){return true;}if(obj instanceof Student){Student stu = (Student) obj;if(this.classId.equals(stu.classId) && this.id.equals(stu.id)){return true;}}return false;}@Overridepublic String toString() {return name + "\t" + sex + "\t" + age + "\t" + classId + "\t" + id;}}

HashMap理解图：
在这里插入图片描述

这篇关于Day27 手撕各种集合底层源码（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/863333。

相关文章

JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
uva 11178 计算集合模板题

uva 11178 计算集合模板题

题意： 求三角形行三个角三等分点射线交出的内三角形坐标。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
如何在Visual Studio中调试.NET源码

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时，发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null，再判断Count。 看了一下Count的源码如下： 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

Java的垃圾收集（Garbage Collection，GC）机制是Java语言的一大特色，它负责自动管理内存的回收，释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍： 一、垃圾收集机制概述： 对象存活判断：垃圾收集器定期检查堆内存中的对象，判断哪些对象是“垃圾”，即不再被任何引用链直接或间接引用的对象。内存回收：将判断为垃圾的对象占用的内存进行回收，以便重新使用。
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
kubelet组件的启动流程源码分析

kubelet组件的启动流程源码分析

概述 摘要: 本文将总结kubelet的作用以及原理，在有一定基础认识的前提下，通过阅读kubelet源码，对kubelet组件的启动流程进行分析。 正文 kubelet的作用 这里对kubelet的作用做一个简单总结。 节点管理 节点的注册 节点状态更新 容器管理(pod生命周期管理) 监听apiserver的容器事件 容器的创建、删除(CRI) 容器的网络的创建与删除
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2