《恋上数据结构第1季》集合 ListSet、TreeSet、HashSet

简介: 《恋上数据结构第1季》集合 ListSet、TreeSet、HashSet
数据结构与算法笔记目录《恋上数据结构》 笔记目录

想加深 Java 基础推荐看这个Java 强化笔记目录

我的《恋上数据结构》源码(第1季 + 第2季):https://github.com/szluyu99/Data_Structure_Note

集合的特点:

  • 不存放重复的元素
  • 常用于去重
    存放新增 IP,统计新增 IP
    存放词汇,统计词汇量
    ...

思考:集合的内部实现能否直接利用以前学过的数据结构?

  • 动态数组
  • 链表
  • 二叉搜索树(AVL树、红黑树)

集合的接口定义

集合的接口文件(interface),所有实现的集合都需要实现该接口。

public interface Set<E> {
    int size();    //元素数量
    boolean isEmpty(); // 是否为空
    void claer(); // 清空集合
    boolean contains(E element); // 是否包含element元素
    void add(E element); // 添加element元素
    void remove(E element); // 删除element元素
    void traversal(Visitor<E> visitor); // 通过访问器遍历
    
    public static abstract class Visitor<E>{ // 访问器
        boolean stop;
        public abstract boolean visit(E element);
    }
}
AI 代码解读

双向链表 LinkedList 实现 ListSet

通过 双向链表 实现 ListSet。

/**
 * LinkedList实现的ListSet
 */
public class ListSet<E> implements Set<E>{
    private LinkedList<E> list = new LinkedList<>();

    public int size() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public void claer() {
        list.clear();
    }

    public boolean contains(E element) {
        return list.contains(element);
    }

    public void add(E element) {
        // if(list.contains(element)) return;
        
        int index = list.indexOf(element);
        if(index == List.ELEMENT_NOT_FOUND){ // 没有该元素
            list.add(element); // 没有就添加
        }else{
            list.set(index, element); // 已经有就替换
        }
    }

    public void remove(E element) {
        int index = list.indexOf(element);
        if(index != List.ELEMENT_NOT_FOUND){
            list.remove(index);
        }
    }

    public void traversal(Visitor<E> visitor) {
        int size = list.size();
        for(int i = 0; i < size; i++){
            visitor.visit(list.get(i));
        }
    }

}
AI 代码解读

红黑树 RBTree 实现 TreeSet

通过 红黑树 实现的 TreeSet。

/**
 * 红黑树实现集合
 */
public class TreeSet<E> implements Set<E>{
    private RBTree<E> tree = new RBTree<>();
    
    public int size() {
        return tree.size();
    }

    public boolean isEmpty() {
        return tree.isEmpty();
    }

    public void claer() {
        tree.clear();
    }

    public boolean contains(E element) {
        return tree.contains(element);
    }

    public void add(E element) {
        tree.add(element); // 红黑树自带去重
    }

    public void remove(E element) {
        tree.remove(element);
    }

    public void traversal(Visitor<E> visitor) {
        tree.inorder(new BinaryTree.Visitor<E>() {
            @Override
            public boolean visit(E element) {
                return visitor.visit(element);
            }
        });
    }

}
AI 代码解读

TreeMap 实现 TreeSet

通过 TreeMap 实现 TreeSet。

/**
 * 利用TreeMap实现TreeSet
 */
public class TreeSet<E> implements Set<E> {

    private Map<E, Object> map = new TreeMap<>();
    
    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }

    public void claer() {
        map.clear();
    }

    public boolean contains(E element) {
        return map.containsKey(element);
    }

    public void add(E element) {
        map.put(element, null);
    }

    public void remove(E element) {
        map.remove(element);
    }

    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }
}
AI 代码解读

HashMap 实现 HashSet

通过 HashMap 实现 TreeSet。

/**
 * 利用HashMap实现HashSet
 */
public class HashSet<E> implements Set<E> {
    private HashMap<E, Object> map = new HashMap<>();

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }
    
    public void clear() {
        map.clear();
    }

    public boolean contains(E element) {
        return map.containsKey(element);
    }

    public void add(E element) {
        map.put(element, null);
    }

    public void remove(E element) {
        map.remove(element);
    }

    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }

}
AI 代码解读
目录
打赏
0
0
0
0
3
分享
相关文章
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
113 3
Python数据结构:列表、元组、字典、集合
Python 中的列表、元组、字典和集合是常用数据结构。列表(List)是有序可变集合,支持增删改查操作;元组(Tuple)与列表类似但不可变,适合存储固定数据;字典(Dictionary)以键值对形式存储,无序可变,便于快速查找和修改;集合(Set)为无序不重复集合,支持高效集合运算如并集、交集等。根据需求选择合适的数据结构,可提升代码效率与可读性。
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
177 7
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
117 5
【数据结构】HashSet的底层数据结构
【数据结构】HashSet的底层数据结构
372 2
|
9月前
|
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
191 4
|
9月前
|
【用Java学习数据结构系列】探索Java集合框架的无尽秘密pro
【用Java学习数据结构系列】探索Java集合框架的无尽秘密pro
59 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问