数据结构-集合

1. 内容大纲

本章节代码：https://github.com/wicksonZhang/data-structure/tree/main/9-Set

---

2. 基础知识

2.1. 集合是什么

集合（Set）：是一种抽象的数据结构，用于存储无序且唯一的元素。它是由一组不同元素构成的，其中每个元素都是独一无二的，没有重复。

2.2. 集合的优缺点

优点

1. 唯一性：在某种情况下来说，集合中的元素唯一可以确保数据的一致性和准确性。
2. 无序性：在集合不需要考虑顺序的情况下，简化了对数据的处理。

缺点

1. 无序性可能不适用某些场景： 在某些情况下，需要按照特定的顺序处理元素，此时集合的无序性可能成为一个缺点。
2. 不适合频繁的插入和删除操作： 一些集合实现对于频繁的插入和删除操作可能不够高效，例如，对于数组实现的集合，插入和删除可能需要移动大量元素。

2.3. 集合的应用场景

1. 元素去重：这个应该是使用比较多的。例如，一般使用 Set 集合可以对集合进行去重。
2. 新增统计在线用户数：如果说要确保在线用户数，我们可以获取对应的 ip 进行统计。

---

3. 接口设计

链表实现

红黑树实现

• Set.java

/**
 * Set 集合接口
 */
public interface Set<E> {

    // 元素数量
    int size();

    // 是否为空
    boolean isEmpty();

    // 清除所有元素
    void clear();

    // 是否包含某个元素
    boolean contains(E element);

    // 添加元素
    void add(E element);

    // 删除元素
    void remove(E element);

    // 遍历集合
    void traversal(Visitor<E> visitor);

}

• Visitor.java

public static abstract class Visitor<E> {
    boolean stop;

    public abstract boolean visit(E element);
}

---

4. 链表-代码实现

4.1. 初始化

• 由于是基于链表实现，我们选择通过双向链表进行实现

/**
 * 通过双向链表实现集合
 *
 * @param <E>
 */
public class ListSet<E> implements Set<E> {

    private final List<E> list = new LinkedList<E>();
    
}

4.2. 元素数量

/**
 * 元素数量
 *
 * @return int
 */
@Override
public int size() {
    return list.size();
}

4.3. 集合是否为空

/**
 * 集合是否为空
 *
 * @return boolean
 */
@Override
public boolean isEmpty() {
    return list.isEmpty();
}

4.4. 清空元素

/**
 * 清空元素
 */
@Override
public void clear() {
    list.clear();
}

4.5. 集合是否包含某个元素

/**
 * 集合是否包含某个元素
 *
 * @param element 元素
 * @return boolean
 */
@Override
public boolean contains(E element) {
    return list.contains(element);
}

4.6. 添加元素

• 添加的思路是：如果存在将新值覆盖掉旧值，如果不存在就将元素添加到集合中。

/**
 * 添加元素
 *
 * @param element 元素
 */
@Override
public void add(E element) {
    if (element == null) {
        throw new IllegalArgumentException("element must not be null");
    }
    int index = list.indexOf(element);
    if (index != -1) {
        list.set(index, element);
    } else {
        list.add(element);
    }
}

4.7. 删除元素

/**
 * 删除元素
 *
 * @param element 元素
 */
@Override
public void remove(E element) {
    if (element == null) {
        throw new IllegalArgumentException("element must not be null");
    }
    int index = list.indexOf(element);
    if (index != -1) {
        list.remove(index);
    }
}

4.8. 遍历集合

/**
 * 遍历集合
 *
 * @param visitor
 */
@Override
public void traversal(Visitor<E> visitor) {
    if (visitor == null) {
        return;
    }
    for (int i = 0; i < list.size(); i++) {
        if (visitor.visit(list.get(i))) {
            return;
        }
    }
}

4.9. 单元测试

public class ListSetTest {

    private ListSet<Integer> set;

    @BeforeEach
    public void setUp() {
        set = new ListSet<>();
    }

    @Test
    public void testSize() {
        Assertions.assertEquals(0, set.size());

        set.add(1);
        Assertions.assertEquals(1, set.size());

        set.add(2);
        set.add(3);
        Assertions.assertEquals(3, set.size());

        set.remove(2);
        Assertions.assertEquals(2, set.size());

        set.clear();
        Assertions.assertEquals(0, set.size());
    }

    @Test
    public void testIsEmpty() {
        Assertions.assertTrue(set.isEmpty());

        set.add(1);
        Assertions.assertFalse(set.isEmpty());

        set.remove(1);
        Assertions.assertTrue(set.isEmpty());
    }

    @Test
    public void testClear() {
        set.add(1);
        set.add(2);
        set.add(3);

        Assertions.assertFalse(set.isEmpty());

        set.clear();

        Assertions.assertTrue(set.isEmpty());
        Assertions.assertEquals(0, set.size());
    }

    @Test
    public void testContains() {
        set.add(1);
        set.add(2);

        Assertions.assertTrue(set.contains(1));
        Assertions.assertTrue(set.contains(2));
        Assertions.assertFalse(set.contains(3));
    }

    @Test
    public void testAdd() {
        set.add(1);
        set.add(2);

        Assertions.assertEquals(2, set.size());
        Assertions.assertTrue(set.contains(1));
        Assertions.assertTrue(set.contains(2));
    }

    @Test
    public void testRemove() {
        set.add(1);
        set.add(2);
        set.remove(1);
        Assertions.assertEquals(1, set.size());
        Assertions.assertFalse(set.contains(1));
        Assertions.assertTrue(set.contains(2));
    }

    @Test
    public void testTraversal() {
        set.add(1);
        set.add(2);
        set.add(3);

        StringBuilder result = new StringBuilder();
        Visitor<Integer> visitor = new Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                result.append(element).append(" ");
                return false;
            }
        };
        set.traversal(visitor);
        Assertions.assertEquals("1 2 3 ", result.toString());
    }

}

---

5. 红黑树-代码实现

5.1. 初始化

• 由于是基于红黑树实现，我们选择通过红黑树进行实现集合

/**
 * 红黑树实现集合
 */
public class TreeSet<E> implements Set<E> {

    private final RedBlackTree<E> tree = new RedBlackTree<E>();
    
}

5.2. 元素数量

/**
 * 元素数量
 *
 * @return int
 */
@Override
public int size() {
    return tree.size();
}

5.3. 集合是否为空

/**
 * 集合是否为空
 *
 * @return boolean
 */
@Override
public boolean isEmpty() {
    return tree.isEmpty();
}

5.4. 清空元素

/**
 * 清空元素
 */
@Override
public void clear() {
    tree.clear();
}

5.5. 集合是否包含某个元素

/**
 * 集合是否包含某个元素
 *
 * @param element 元素
 * @return boolean
 */
@Override
public boolean contains(E element) {
    return tree.contains(element);
}

5.6. 添加元素

• 添加的思路是：如果存在将新值覆盖掉旧值，如果不存在就将元素添加到集合中。

/**
 * 添加元素
 *
 * @param element 元素
 */
@Override
public void add(E element) {
    tree.add(element);
}

5.7. 删除元素

/**
 * 删除元素
 *
 * @param element 元素
 */
@Override
public void remove(E element) {
    tree.remove(element);
}

5.8. 遍历集合

/**
 * 遍历集合
 *
 * @param visitor
 */
@Override
public void traversal(Visitor<E> visitor) {
    tree.inorderTraversal(new Visitor<E>(){
        @Override
        public boolean visit(E element) {
            return visitor.visit(element);
        }
    });
}

5.9. 单元测试

public class ListSetTest {

    private TreeSet<Integer> set;

    @BeforeEach
    public void setUp() {
        set = new TreeSet<>();
    }

    @Test
    public void testSize() {
        Assertions.assertEquals(0, set.size());

        set.add(1);
        Assertions.assertEquals(1, set.size());

        set.add(2);
        set.add(3);
        Assertions.assertEquals(3, set.size());

        set.remove(2);
        Assertions.assertEquals(2, set.size());

        set.clear();
        Assertions.assertEquals(0, set.size());
    }

    @Test
    public void testIsEmpty() {
        Assertions.assertTrue(set.isEmpty());

        set.add(1);
        Assertions.assertFalse(set.isEmpty());

        set.remove(1);
        Assertions.assertTrue(set.isEmpty());
    }

    @Test
    public void testClear() {
        set.add(1);
        set.add(2);
        set.add(3);

        Assertions.assertFalse(set.isEmpty());

        set.clear();

        Assertions.assertTrue(set.isEmpty());
        Assertions.assertEquals(0, set.size());
    }

    @Test
    public void testContains() {
        set.add(1);
        set.add(2);

        Assertions.assertTrue(set.contains(1));
        Assertions.assertTrue(set.contains(2));
        Assertions.assertFalse(set.contains(3));
    }

    @Test
    public void testAdd() {
        set.add(1);
        set.add(2);

        Assertions.assertEquals(2, set.size());
        Assertions.assertTrue(set.contains(1));
        Assertions.assertTrue(set.contains(2));
    }

    @Test
    public void testRemove() {
        set.add(1);
        set.add(2);
        set.remove(1);
        Assertions.assertEquals(1, set.size());
        Assertions.assertFalse(set.contains(1));
        Assertions.assertTrue(set.contains(2));
    }

    @Test
    public void testTraversal() {
        set.add(1);
        set.add(2);
        set.add(3);

        StringBuilder result = new StringBuilder();
        Visitor<Integer> visitor = new Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                result.append(element).append(" ");
                return false;
            }
        };
        set.traversal(visitor);
        Assertions.assertEquals("1 2 3 ", result.toString());
    }

}

---

6. 性能对比

• 需求：我们通过测试读取文件，将文件中的内容进行去重，对比使用链表和红黑树操作集合 添加、查询、删除 所花费的时间

/**
 * 性能对比：红黑树和链表
 */
public class ComparisonTest {

    public String[] file() {
        FileInfo fileInfo = Files.read("C:\\Users\\wicks\\Desktop\\java-source\\java\\util\\concurrent", new String[]{"java"});

        System.out.println("文件数量：" + fileInfo.getFiles());
        System.out.println("代码行数：" + fileInfo.getLines());
        String[] words = fileInfo.words();
        System.out.println("单词数量：" + words.length);
        return words;
    }

    public void common(Set<String> set, String[] words) {
        // 添加
        for (String word : words) {
            set.add(word);
        }
        // 查询
        for (String word : words) {
            set.contains(word);
        }
        // 删除
        for (String word : words) {
            set.remove(word);
        }
    }

}

6.1. 链表

@Test
public void ListSetTest() {
    Times.test("ListSet", () -> common(new ListSet<>(), file()));
}

【ListSet】
开始：00:13:33.876
文件数量：88
代码行数：62399
单词数量：256149
结束：00:13:37.393
耗时：3.517秒

6.2. 红黑树

@Test
public void treeSetTest() {
    Times.test("TreeSet", () -> common(new TreeSet<>(), file()));
}

【TreeSet】
开始：00:14:36.354
文件数量：88
代码行数：62399
单词数量：256149
结束：00:14:36.693
耗时：0.338秒

---

7. 参考博文

• 恋上数据结构与算法(第一季)-MJ大神精选