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。

相关文章

Python实现无痛修改第三方库源码的方法详解

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很
阅读更多...
Python容器类型之列表/字典/元组/集合方式

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》：本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表（List） - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典（D
阅读更多...
Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory
阅读更多...
Java的volatile和sychronized底层实现原理解析

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente
阅读更多...
MySQL中Next-Key Lock底层原理实现

MySQL中Next-Key Lock底层原理实现

《MySQL中Next-KeyLock底层原理实现》Next-KeyLock是MySQLInnoDB存储引擎中的一种锁机制,结合记录锁和间隙锁,用于高效并发控制并避免幻读,本文主要介绍了MySQL中... 目录一、Next-Key Lock 的定义与作用二、底层原理三、源代码解析四、总结Next-Key L
阅读更多...
Java集合中的List超详细讲解

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类（如ArrayList、LinkedList和V... 目录一，List的继承体系二，List的常用操作及代码示例1，创建List实例2，增加元素3，访问元
阅读更多...
C#比较两个List集合内容是否相同的几种方法

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法（顺序和内容都相等）2.
阅读更多...
MySQL中的MVCC底层原理解读

MySQL中的MVCC底层原理解读

《MySQL中的MVCC底层原理解读》本文详细介绍了MySQL中的多版本并发控制（MVCC）机制,包括版本链、ReadView以及在不同事务隔离级别下MVCC的工作原理,通过一个具体的示例演示了在可重... 目录简介ReadView版本链演示过程总结简介MVCC（Multi-Version Concurr
阅读更多...
Go中sync.Once源码的深度讲解

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语，用于确保某个操
阅读更多...
Java汇编源码如何查看环境搭建

Java汇编源码如何查看环境搭建

《Java汇编源码如何查看环境搭建》：本文主要介绍如何在IntelliJIDEA开发环境中搭建字节码和汇编环境,以便更好地进行代码调优和JVM学习,首先,介绍了如何配置IntelliJIDEA以方... 目录一、简介二、在IDEA开发环境中搭建汇编环境2.1 在IDEA中搭建字节码查看环境2.1.1 搭建步
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2