Java底层实现基于链表和二分搜索树的 Set 集合

vlambda
2020-03-08

Java底层实现基于链表和二分搜索树的 Set 集合

Set 集合

基于链表和二分搜索树

Java底层实现基于链表和二分搜索树的 Set 集合

什么是集合

数学上定义为由一个或多个确定的元素所构成的整体。但是在计算机领域，集合被定义为由一个或多个不同的元素所构成的整体。也就是说一个集合里面的元素都是不同的。

这是由于这种特性，比较经典的就是用在语言统计上。查看一篇文章当中用了多少个词汇，进而判断用户阅读难度系数。

集合类的实现

——基于链表

同栈和队列相同，我们都是基于一些其他的数据结构来封装我们的类。所以我们需要涉及集合的接口。由于我们之前已经封装好了链表底层，具体的函数方法可以查看这篇文章。

2.1

接口函数实现

具体的函数方法依然是增删改查四个操作。这里可以并没有改操作，由于我们并不涉及索引概念，所以就没有改操作。

接口函数实现：

public interface Set<E> { void add(E e); void remove(E e); boolean contains(E e); int getSize(); boolean isEmpty();}

2.2

基本操作函数

由于我们之前已经封装好了链表底层，具体的函数方法可以查看LinkedList链表这篇文章。

程序实现：

@Overridepublic int getSize() { return linkedList.getSize();}
@Overridepublic boolean isEmpty() { return linkedList.isEmpty();}

2.3

增加元素

程序实现：

@Overridepublic void add(E e) { if (!linkedList.contains(e)) //集合中没有该元素 linkedList.addFirst(e); //向链表头添加元素时间复杂度最低}

2.4

删除元素

程序实现：

@Overridepublic void remove(E e) { linkedList.removeElement(e);}

2.5

查询元素

程序实现：

@Overridepublic boolean contains(E e) { return linkedList.contains(e);}
@Overridepublic int getSize() { return linkedList.getSize();}
@Overridepublic boolean isEmpty() { return linkedList.isEmpty();}

集合类的实现

——基于二分搜索树

由于我们之前已经封装好了链表底层，具体的函数方法可以查看这篇文章。

3.1

基本操作函数

@Overridepublic int getSize() { return bst.getSize();}
@Overridepublic boolean isEmpty() { return bst.isEmpty();}

3.2

增加元素

程序实现：

@Overridepublic void add(E e) bst.add(e);}

3.3

删除元素

程序实现：

@Overridepublic void remove(E e) bst.remove(e);}

3.3

查询元素

程序实现：

@Overridepublic boolean contains(E e) { return bst.contains(e);}

时间复杂度分析

我们从上面可以看出来，我们这几个方法都非常简介，这也正是由于我们底层封装的好。

	增加元素	删除元素	查询元素
链表	O(N)	O(N)	O(N)
BST	O(log(N))	O(log(N))	O(log(N))

这里小伙伴可以会问，链表中添加元素在头部添加难道不应该是O(1)的复杂度吗，其实不是的，那是因为在集合这个数据结构当中，我们需要保证元素不重复，就要先对链表进行遍历一遍，所以复杂度也就是O(N)级别。

因此我们可以在表中看出来，底层是二分搜索树的性能远高于链表的实现。总的来说集合这种数据结构相对来说比较简单。

END

更多精彩内容，大家可以转到我的主页：曲怪曲怪的主页

或者扫描下方二维码进行关注。里面有惊喜等你哦。

点击“阅读原文”

vlambda博客
学习文章列表