关于对Java集合类的一些总结（二）

叁歲伎倆 2022-11-29 03:05 128阅读 0赞

## 上一节对List接口下的ArrayList和LinkedList实现类的底层数据结构、扩容机制、线程安全简要做了一个分析，这一节我们来看一下Set接口下的实现类 ##

### 一、Set接口下主要有两个实现类，分别是HashSet和TreeSet ###

1、HashSet的底层是HashMap

private transient HashMap<E,Object> map;
    
        // Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();
    
        /** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */
        public HashSet() { 
            map = new HashMap<>();
        }

HashSet添加元素的方法

public boolean add(E e) { 
            return map.put(e, PRESENT)==null;
        }

通过源码我们可以很清晰的看出，在HashSet中添加元素依然是使用了HashMap中的put方法，HashSet的key就是要添加的元素e,value是一个常量空对象`PRESENT`，key可以为null，但只能存一个null值。

**HashSet是如何添加元素的？**  
HashSet添加元素时，会先计算出对象的hashcode，判断插入的位置，同时也会与其他已插入元素的hashcode作比较，如果值不相等，插入成功；如果相等，调用equals()方法，如果两个对象不相同，插入成功，如果两个对象相同，插入失败。

判断HashSet中是否包含某元素:

public boolean contains(Object o) { 
            return map.containsKey(o);
        }

由于HashSet具有无序、不可重复的性质，所以也常常用HashSet做某些算法的去重工作。

HashSet的删除方法：

public boolean remove(Object o) { 
            return map.remove(o)==PRESENT;
        }

HashSet具有以下特点：  
（1）唯一、无序（这里的无序指存入元素的顺序和输出时的顺序不一致）  
（2）判断两个元素是否相等调用了equals方法  
（3）是HashMap的皮包类，线程不安全

LinkedHashSet继承自HashSet，底层数据结构是双向链表，有序

2、TreeSet是基于TreeMap实现的，它的底层是红黑树(自排序的平衡二叉树)，是Set接口下SortedSet下NavigableSet的实现类  
TreeSet默认构造器：调用了TreeMap的构造器

public TreeSet() { 
            this(new TreeMap<E,Object>());
        }
    ...
    public TreeMap() { 
            comparator = null;
        }

TreeSet对添加的元素(类型须一致)会以`红黑树`的形式排序存储，有两种排序方式：自然排序和定制排序，自然排序要求添加的元素实现`Comparable`接口，实现compareTo()方法，obj1.compareTo(obj2)方法返回0表明两个元素大小相等，返回整数表明obj1大于obj2，返回负数表明obj1小于obj2；

//String类实现的compareTo方法，用于比较两个字符串的大小
    public int compareTo(String anotherString) { 
            int len1 = value.length;
            int len2 = anotherString.value.length;
            int lim = Math.min(len1, len2);
            char v1[] = value;
            char v2[] = anotherString.value;
    
            int k = 0;
            while (k < lim) { 
                char c1 = v1[k];
                char c2 = v2[k];
                if (c1 != c2) { 
                    return c1 - c2;
                }
                k++;
            }
            return len1 - len2;
        }

定制排序需要在TreeSet构造方法中声明一个`comparator`，实现Comparator接口下的compare()方法

//TreeSet构造器
    public TreeSet(Comparator<? super E> comparator) { 
            this(new TreeMap<>(comparator));
        }
    ...
    int compare(T o1, T o2);

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java集合：关于Vector类

文章目录一、Vector概念二、Vector的使用 2.1Vector的构造方法 2.2常用方法 2.3代码演示

清疚/ 2024年03月31日 12:33/ 0 赞/ 93 阅读

相关 Java集合：关于LinkedList类

文章目录一、LinkedList概念二、体系结构三、LinkedList的使用 3.1构造函数 3.2添加节点

亦凉/ 2024年03月17日 15:07/ 0 赞/ 142 阅读

相关 java集合类总结

java集合类主要负责保存、盛装其他数据，因此集合类也称容器类。java集合类分为：set、list、map、queue四大体系。其中set代表无序、不可重复的集合；list代

刺骨的言语ヽ痛彻心扉/ 2023年10月10日 13:46/ 0 赞/ 39 阅读

相关关于对Java集合类的一些总结（三）

Map接口下的实现类主要有HashMap、HashTable、ConcurrentHashMap、TreeMap 一、HashMap 底层数据结构是数组+链表/红黑

傷城~/ 2022年11月29日 05:56/ 0 赞/ 124 阅读

相关关于对Java集合类的一些总结（二）

上一节对List接口下的ArrayList和LinkedList实现类的底层数据结构、扩容机制、线程安全简要做了一个分析，这一节我们来看一下Set接口下的实现类一、S

叁歲伎倆/ 2022年11月29日 03:05/ 0 赞/ 129 阅读

相关关于对Java集合类的一些总结（一）

Java集合类主要分为Collection和Map两大接口，下面将对每个实现类做简要概述 ![集合类][watermark_type_ZmFuZ3poZW5naGVpdG

小咪咪/ 2022年11月28日 15:13/ 0 赞/ 102 阅读

相关关于一些常识的总结

这些天上网，查到了不少新的知识，在此处总结一下。 //8.24号 h5相当于h4的洗一个版本，增添和删除了某些标签，同时更改了一些功能图片格式的转换在于编码方式的

缺乏、安全感/ 2022年07月18日 01:24/ 0 赞/ 339 阅读

相关 Java集合类总结

一、为什么出现集合类？面向对象语言对事物的体现都是以对象的形式，所以为了方便对多个对象的操作，就对对象进行存储，集合就是存储对象最常用的一

绝地灬酷狼/ 2022年06月03日 04:28/ 0 赞/ 215 阅读

相关关于java内部类的一些总结

> 1. 成员内部类 > 2. 局部内部类 > 3. 静态内部类 > 4. 内部类的继承成员内部类 > 成员内部类的语法如下： > > public c

拼搏现实的明天。/ 2022年03月18日 14:30/ 0 赞/ 353 阅读

相关关于numa的一些总结

1.不同的操作系统对numa的支持不一样. 1.1 solaris提供了locality group api. 可以使用它方便地进行 locality操作.api可以参考[h

柔情只为你懂/ 2022年01月14日 03:29/ 0 赞/ 469 阅读