容器【容器介绍、Set接口介绍、 HashSet容器的使用、TreeSet容器的使用】(三)-全面详解（学习总结---从入门到深化）

绝地灬酷狼 2023-10-13 15:43 59阅读 0赞

## ![5014dccbf4f846d0abdf0640d9ebbd88.gif][] ##

![1cebff27674e42408ad529354a03c47f.png][]

**目录**

LinkedList容器介绍

Set接口介绍

HashSet容器的使用

通过HashSet存储自定义对象

TreeSet容器的使用

--------------------

## LinkedList容器介绍 ##

> LinkedList底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。 双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两 个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中 的任意一个节点开始，都可以很方便地找到所有节点。

**LinkedList的存储结构图**

![6b47d28c9b1b4dee8461055539fb7c21.png][]

每个节点都应该有3部分内容：

class  Node<E> {
        Node<E>  previous;   //前一个节点
        E  element;          //本节点保存的数据
        Node<E> next;        //后一个节点
    }

**List实现类的选用规则**

> 如何选用ArrayList、LinkedList、Vector?
> 
> 1 需要线程安全时，用Vector。
> 
> 2 不存在线程安全问题时，并且查找较多用ArrayList（一般使用它）
> 
> 3 不存在线程安全问题时，增加或删除元素较多用LinkedList

**LinkedList容器的使用（List标准）**

LinkedList实现了List接口，所以LinkedList是具备List的存储特征的 (有序，元素有重复)。

public class LinkedListTest {
        public static void main(String[] args) {
            //实例化LinkedList容器
            List<String> list = new LinkedList<>();
            //添加元素
            boolean a = list.add("a");
            boolean b = list.add("b");
            boolean c = list.add("c");
            list.add(3,"a");
            System.out.println(a+"\t"+b+"\t"+c);
            for(int i=0;i<list.size();i++){
                System.out.println(list.get(i));
           }
       }
    }

**LinkedList容器的使用（非List标准）**

![9a9ccf2fc25348e088d511b197b405b6.png][]

public class LinkedListTest2 {
        public static void main(String[] args) {
            System.out.println("-------LinkedList-------------");
            //将指定元素插入到链表开头
            LinkedList<String> linkedList1 = new LinkedList<>();
            linkedList1.addFirst("a");
            linkedList1.addFirst("b");
            linkedList1.addFirst("c");
            for (String str:linkedList1){
                System.out.println(str);
           }
            System.out.println("----------------------");
            //将指定元素插入到链表结尾
            LinkedList<String> linkedList = new LinkedList<>();
            linkedList.addLast("a");
            linkedList.addLast("b");
            linkedList.addLast("c");
            for (String str:linkedList){
                System.out.println(str);
           }
            System.out.println("---------------------------");
            //返回此链表的第一个元素
          
            System.out.println(linkedList.getFirst());
            //返回此链表的最后一个元素
          
            System.out.println(linkedList.getLast());
            System.out.println("-----------------------");
            //移除此链表中的第一个元素，并返回这个元素
            linkedList.removeFirst();
            //移除此链表中的最后一个元素，并返回这个元素
            linkedList.removeLast();
            for (String str:linkedList){
                System.out.println(str);
           }
            System.out.println("-----------------------");
            linkedList.addLast("c");
            //从此链表所表示的堆栈处弹出一个元素,等效于removeFirst
            linkedList.pop();
            for (String str:linkedList){
                System.out.println(str);
           }
            System.out.println("-------------------");
            //将元素推入此链表所表示的堆栈 这个等效于addFisrt(E e)
            linkedList.push("h");
            for (String str:linkedList){
                System.out.println(str);
           }
       }
    }

**LinkedList的源码分析**

**添加元素**

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
       }
    }

**成员变量**

transient int size = 0;
    
    /**
    * Pointer to first node.
    * Invariant: (first == null && last == null) ||
    *           (first.prev == null && first.item != null)
    */
    
    transient Node<E> first;
    
    /**
    * Pointer to last node.
    * Invariant: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
    
    transient Node<E> last;

**添加元素**

/**
    * Appends the specified element to the end of this list.
    *
    * <p>This method is equivalent to {@link #addLast}.
    *
    * @param e element to be appended to this list
    * @return {@code true} (as specified by {@link Collection#add})
    */
    
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    /**
    * Links e as last element.
    */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

**头尾添加元素**

**addFirst**

/**
    * Inserts the specified element at the beginning of this list.
    *
    * @param e the element to add
    */
    
    public void addFirst(E e) {
        linkFirst(e);
    }
    
    /**
    * Links e as first element.
    */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
        last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

**addLast**

/**
    * Appends the specified element to the end of this list.
    *
    * <p>This method is equivalent to {@link #add}.
    *
    * @param e the element to add
    */
    
    public void addLast(E e) {
        linkLast(e);
    }
    
    /**
    * Links e as last element.
    */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
        first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

**获取元素**

/**
    * Returns the element at the specified position in this list.
    *
    * @param index index of the element to return
    * @return the element at the specified position in this list
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
    
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

/**
    * Tells if the argument is the index of an existing element.
    */
    
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

/**
    * Returns the (non-null) Node at the specified element index.
    */
    Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
       } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
                return x;
       }
    }

## Set接口介绍 ##

![b6749c6153a047cf8b524069e2a1b132.png][]

> Set接口继承自Collection接口，Set接口中没有新增方法，它和 Collection接口保持完全一致。我们在前面学习List接口的使用方 式，在Set中仍然适用。因此，学习Set的使用将没有任何难度。

**Set接口特点**

> Set特点：无序、不可重复。无序指Set中的元素没有索引，我们只 能遍历查找；不可重复指不允许加入重复的元素。更确切地讲，新 元素如果和Set中某个元素通过equals()方法对比为true，则只能保 留一个。
> 
> Set常用的实现类有：HashSet、TreeSet等，我们一般使用 HashSet。

## HashSet容器的使用 ##

HashSet是Set接口的实现类。是Set存储特征的具体实现。

public class HashSetTest {
        public static void main(String[] args) {
            //实例化HashSet
            Set<String> set = new HashSet<>();
            //添加元素
            set.add("a");
            set.add("b1");
            set.add("c2");
            set.add("d");
            set.add("a");
            //获取元素,在Set容器中没有索引，所以没有对应的get(int index)方法
            for(String str: set){
                System.out.println(str);
           }
            System.out.println("--------------------");
            //删除元素
            boolean flag = set.remove("c2");
            System.out.println(flag);
            for(String str: set){
                System.out.println(str);
           }
            System.out.println("------------------------");
            int size = set.size();
            System.out.println(size);
       }
    }

**HashSet存储特征分析**

![c839fe841eb34c36afd16151f9109d33.png][]

> HashSet 是一个不保证元素的顺序且没有重复元素的集合，是线程 不安全的。HashSet允许有null 元素。

**无序：**

> 在HashSet中底层是使用HashMap存储元素的。HashMap底层使 用的是数组与链表实现元素的存储。元素在数组中存放时，并不是 有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定 元素在数组中的位置。

**不重复：**

> 当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会 调用元素的equals()方法判断两个元素是否相同。如果元素相同则 不会添加该元素，如果不相同则会使用单向链表保存该元素。

## 通过HashSet存储自定义对象 ##

**创建Users对象**

public class Users {
        private String username;
        private int userage;
        public Users(String username, int userage) {
    
        this.username = username;
            this.userage = userage;
       }
        public Users() { }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Users users = (Users) o;
            if (userage != users.userage) return false;
            return username != null ? username.equals(users.username) : users.username == null;
       }
    
        @Override
        public int hashCode() {
            int result = username != null ? username.hashCode() : 0;
            result = 31 * result + userage;
            return result;
           }
        public String getUsername() {
            return username;
          }
        public void setUsername(String username)
          {
            this.username = username;
          }
        public int getUserage() {
            return userage;
          }
        public void setUserage(int userage) {
            this.userage = userage;
          }
        @Override
        public String toString() {
            return "Users{" +
                    "username='" + username + '\'' +
                    ", userage=" + userage +
                   '}';
       }
    }

**在HashSet中存储Users对象**

public class HashSetTest2 {
        public static void main(String[] args) {
            //实例化HashSet
            Set<Users> set = new HashSet<>();
            Users u = new Users("oldlu",18);
            Users u1 = new Users("oldlu",18);
            set.add(u);
            set.add(u1);
            System.out.println(u.hashCode());
            System.out.println(u1.hashCode());
            for(Users users:set){
                System.out.println(users);
           }
       }
    }

**HashSet底层源码分析**

**成员变量**

private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

**添加元素**

/**
    * Adds the specified element to this set if it is not already present.
    * More formally, adds the specified element <tt>e</tt> to this set if
    * this set contains no element <tt>e2</tt> such that
    * <tt>(e==null ?  e2==null : e.equals(e2)) </tt>.
    * If this set already contains the element, the call leaves the set
    * unchanged and returns <tt>false</tt>.
    *
    * @param e element to be added to this set
    * @return <tt>true</tt> if this set did not already contain the specified
    * element
    */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

## TreeSet容器的使用 ##

![5a8f24ce7b2246dfbb1f39190febd5c5.png][]

> TreeSet实现了Set接口，它是一个可以对元素进行排序的容器。底 层实际是用TreeMap实现的，内部维持了一个简化版的TreeMap， 通过key来存储元素。 TreeSet内部需要对存储的元素进行排序，因 此，我们需要给定排序规则。
> 
> 排序规则实现方式：
> 
> 1、通过元素自身实现比较规则。
> 
> 2、通过比较器指定比较规则。

public class TreeSetTest {
        public static void main(String[] args) {
            //实例化TreeSet
            Set<String> set = new TreeSet<>();
            //添加元素
            set.add("c");
            set.add("a");
            set.add("d");
            set.add("b");
            set.add("a");
            //获取元素
            for(String str :set){
                System.out.println(str);
           }
       }
    }

[5014dccbf4f846d0abdf0640d9ebbd88.gif]: https://img-blog.csdnimg.cn/5014dccbf4f846d0abdf0640d9ebbd88.gif
[1cebff27674e42408ad529354a03c47f.png]: https://img-blog.csdnimg.cn/1cebff27674e42408ad529354a03c47f.png
[6b47d28c9b1b4dee8461055539fb7c21.png]: https://img-blog.csdnimg.cn/6b47d28c9b1b4dee8461055539fb7c21.png
[9a9ccf2fc25348e088d511b197b405b6.png]: https://img-blog.csdnimg.cn/9a9ccf2fc25348e088d511b197b405b6.png
[b6749c6153a047cf8b524069e2a1b132.png]: https://img-blog.csdnimg.cn/b6749c6153a047cf8b524069e2a1b132.png
[c839fe841eb34c36afd16151f9109d33.png]: https://img-blog.csdnimg.cn/c839fe841eb34c36afd16151f9109d33.png
[5a8f24ce7b2246dfbb1f39190febd5c5.png]: https://img-blog.csdnimg.cn/5a8f24ce7b2246dfbb1f39190febd5c5.png