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

    目录

    LinkedList容器介绍

    Set接口介绍

     HashSet容器的使用

     通过HashSet存储自定义对象

    TreeSet容器的使用

    LinkedList容器介绍

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

     LinkedList的存储结构图

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

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

    List实现类的选用规则

    如何选用ArrayList、LinkedList、Vector?

    1 需要线程安全时，用Vector。

    2 不存在线程安全问题时，并且查找较多用ArrayList（一般使用它）

    3 不存在线程安全问题时，增加或删除元素较多用LinkedList

    LinkedList容器的使用（List标准） 

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

    1. public class LinkedListTest {
    2.     public static void main(String[] args) {
    3.         //实例化LinkedList容器
    4.         List<String> list = new LinkedList<>();
    5.         //添加元素
    6.         boolean a = list.add("a");
    7.         boolean b = list.add("b");
    8.         boolean c = list.add("c");
    9.         list.add(3,"a");
    10.         System.out.println(a+"\t"+b+"\t"+c);
    11.         for(int i=0;i<list.size();i++){
    12.             System.out.println(list.get(i));
    13.        }
    14.    }
    15. }

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

    1. public class LinkedListTest2 {
    2.     public static void main(String[] args) {
    3.         System.out.println("-------LinkedList-------------");
    4.         //将指定元素插入到链表开头
    5.         LinkedList<String> linkedList1 = new LinkedList<>();
    6.         linkedList1.addFirst("a");
    7.         linkedList1.addFirst("b");
    8.         linkedList1.addFirst("c");
    9.         for (String str:linkedList1){
    10.             System.out.println(str);
    11.        }
    12.         System.out.println("----------------------");
    13.         //将指定元素插入到链表结尾
    14.         LinkedList<String> linkedList = new LinkedList<>();
    15.         linkedList.addLast("a");
    16.         linkedList.addLast("b");
    17.         linkedList.addLast("c");
    18.         for (String str:linkedList){
    19.             System.out.println(str);
    20.        }
    21.         System.out.println("---------------------------");
    22.         //返回此链表的第一个元素
    23.       
    24.         System.out.println(linkedList.getFirst());
    25.         //返回此链表的最后一个元素
    26.       
    27.         System.out.println(linkedList.getLast());
    28.         System.out.println("-----------------------");
    29.         //移除此链表中的第一个元素，并返回这个元素
    30.         linkedList.removeFirst();
    31.         //移除此链表中的最后一个元素，并返回这个元素
    32.         linkedList.removeLast();
    33.         for (String str:linkedList){
    34.             System.out.println(str);
    35.        }
    36.         System.out.println("-----------------------");
    37.         linkedList.addLast("c");
    38.         //从此链表所表示的堆栈处弹出一个元素,等效于removeFirst
    39.         linkedList.pop();
    40.         for (String str:linkedList){
    41.             System.out.println(str);
    42.        }
    43.         System.out.println("-------------------");
    44.         //将元素推入此链表所表示的堆栈 这个等效于addFisrt(E e)
    45.         linkedList.push("h");
    46.         for (String str:linkedList){
    47.             System.out.println(str);
    48.        }
    49.    }
    50. }

    LinkedList的源码分析

    添加元素

    1. private static class Node<E> {
    2.     E item;
    3.     Node<E> next;
    4.     Node<E> prev;
    5.     Node(Node<E> prev, E element, Node<E> next) {
    6.         this.item = element;
    7.         this.next = next;
    8.         this.prev = prev;
    9.    }
    10. }

    成员变量

    1. transient int size = 0;
    2.  
    3. /**
    4. * Pointer to first node.
    5. * Invariant: (first == null && last == null) ||
    6. *           (first.prev == null && first.item != null)
    7. */
    8.  
    9. transient Node<E> first;
    10.  
    11. /**
    12. * Pointer to last node.
    13. * Invariant: (first == null && last == null) ||
    14. *            (last.next == null && last.item != null)
    15. */
    16.  
    17. transient Node<E> last;

    添加元素

    1. /**
    2. * Appends the specified element to the end of this list.
    3. *
    4. * <p>This method is equivalent to {@link #addLast}.
    5. *
    6. * @param e element to be appended to this list
    7. * @return {@code true} (as specified by {@link Collection#add})
    8. */
    9.  
    10. public boolean add(E e) {
    11.     linkLast(e);
    12.     return true;
    13. }
    14.  
    15. /**
    16. * Links e as last element.
    17. */
    18. void linkLast(E e) {
    19.     final Node<E> l = last;
    20.     final Node<E> newNode = new Node<>(l, e, null);
    21.     last = newNode;
    22.     if (l == null)
    23.         first = newNode;
    24.     else
    25.         l.next = newNode;
    26.     size++;
    27.     modCount++;
    28. }

    头尾添加元素

    addFirst

    1. /**
    2. * Inserts the specified element at the beginning of this list.
    3. *
    4. * @param e the element to add
    5. */
    6.  
    7. public void addFirst(E e) {
    8.     linkFirst(e);
    9. }
    10.  
    11. /**
    12. * Links e as first element.
    13. */
    14. private void linkFirst(E e) {
    15.     final Node<E> f = first;
    16.     final Node<E> newNode = new Node<>(null, e, f);
    17.     first = newNode;
    18.     if (f == null)
    19.     last = newNode;
    20.     else
    21.         f.prev = newNode;
    22.     size++;
    23.     modCount++;
    24. }

    addLast

    1. /**
    2. * Appends the specified element to the end of this list.
    3. *
    4. * <p>This method is equivalent to {@link #add}.
    5. *
    6. * @param e the element to add
    7. */
    8.  
    9. public void addLast(E e) {
    10.     linkLast(e);
    11. }
    12.  
    13. /**
    14. * Links e as last element.
    15. */
    16. void linkLast(E e) {
    17.     final Node<E> l = last;
    18.     final Node<E> newNode = new Node<>(l, e, null);
    19.     last = newNode;
    20.     if (l == null)
    21.     first = newNode;
    22.     else
    23.         l.next = newNode;
    24.     size++;
    25.     modCount++;
    26. }

    获取元素

    1. /**
    2. * Returns the element at the specified position in this list.
    3. *
    4. * @param index index of the element to return
    5. * @return the element at the specified position in this list
    6. * @throws IndexOutOfBoundsException {@inheritDoc}
    7. */
    8.  
    9. public E get(int index) {
    10.     checkElementIndex(index);
    11.     return node(index).item;
    12. }
    1. private void checkElementIndex(int index) {
    2.     if (!isElementIndex(index))
    3.         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    4. }
    1. /**
    2. * Tells if the argument is the index of an existing element.
    3. */
    4.  
    5. private boolean isElementIndex(int index) {
    6.     return index >= 0 && index < size;
    7. }   
    1. /**
    2. * Returns the (non-null) Node at the specified element index.
    3. */
    4. Node<E> node(int index) {
    5.     // assert isElementIndex(index);
    6.     if (index < (size >> 1)) {
    7.         Node<E> x = first;
    8.         for (int i = 0; i < index; i++)
    9.             x = x.next;
    10.         return x;
    11.    } else {
    12.         Node<E> x = last;
    13.         for (int i = size - 1; i > index; i--)
    14.             x = x.prev;
    15.             return x;
    16.    }
    17. }

    Set接口介绍

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

     Set接口特点

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

     Set常用的实现类有：HashSet、TreeSet等，我们一般使用 HashSet。

     HashSet容器的使用

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

    1. public class HashSetTest {
    2.     public static void main(String[] args) {
    3.         //实例化HashSet
    4.         Set<String> set = new HashSet<>();
    5.         //添加元素
    6.         set.add("a");
    7.         set.add("b1");
    8.         set.add("c2");
    9.         set.add("d");
    10.         set.add("a");
    11.         //获取元素,在Set容器中没有索引，所以没有对应的get(int index)方法
    12.         for(String str: set){
    13.             System.out.println(str);
    14.        }
    15.         System.out.println("--------------------");
    16.         //删除元素
    17.         boolean flag = set.remove("c2");
    18.         System.out.println(flag);
    19.         for(String str: set){
    20.             System.out.println(str);
    21.        }
    22.         System.out.println("------------------------");
    23.         int size = set.size();
    24.         System.out.println(size);
    25.    }
    26. }

    HashSet存储特征分析

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

     无序：

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

     不重复：

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

     通过HashSet存储自定义对象

    创建Users对象

    1. public class Users {
    2.     private String username;
    3.     private int userage;
    4.     public Users(String username, int userage) {
    5.  
    6.     this.username = username;
    7.         this.userage = userage;
    8.    }
    9.     public Users() { }
    10.     @Override
    11.     public boolean equals(Object o) {
    12.         if (this == o) return true;
    13.         if (o == null || getClass() != o.getClass()) return false;
    14.         Users users = (Users) o;
    15.         if (userage != users.userage) return false;
    16.         return username != null ? username.equals(users.username) : users.username == null;
    17.    }
    18.  
    19.     @Override
    20.     public int hashCode() {
    21.         int result = username != null ? username.hashCode() : 0;
    22.         result = 31 * result + userage;
    23.         return result;
    24.        }
    25.     public String getUsername() {
    26.         return username;
    27.       }
    28.     public void setUsername(String username)
    29.       {
    30.         this.username = username;
    31.       }
    32.     public int getUserage() {
    33.         return userage;
    34.       }
    35.     public void setUserage(int userage) {
    36.         this.userage = userage;
    37.       }
    38.     @Override
    39.     public String toString() {
    40.         return "Users{" +
    41.                 "username='" + username + '\'' +
    42.                 ", userage=" + userage +
    43.                '}';
    44.    }
    45. }

     在HashSet中存储Users对象

    1. public class HashSetTest2 {
    2.     public static void main(String[] args) {
    3.         //实例化HashSet
    4.         Set<Users> set = new HashSet<>();
    5.         Users u = new Users("oldlu",18);
    6.         Users u1 = new Users("oldlu",18);
    7.         set.add(u);
    8.         set.add(u1);
    9.         System.out.println(u.hashCode());
    10.         System.out.println(u1.hashCode());
    11.         for(Users users:set){
    12.             System.out.println(users);
    13.        }
    14.    }
    15. }

    HashSet底层源码分析

    成员变量

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

    添加元素

    1. /**
    2. * Adds the specified element to this set if it is not already present.
    3. * More formally, adds the specified element <tt>e</tt> to this set if
    4. * this set contains no element <tt>e2</tt> such that
    5. * <tt>(e==null&nbsp;? &nbsp;e2==null&nbsp;:&nbsp;e.equals(e2)) </tt>.
    6. * If this set already contains the element, the call leaves the set
    7. * unchanged and returns <tt>false</tt>.
    8. *
    9. * @param e element to be added to this set
    10. * @return <tt>true</tt> if this set did not already contain the specified
    11. * element
    12. */
    13. public boolean add(E e) {
    14.     return map.put(e, PRESENT)==null;
    15. }

    TreeSet容器的使用

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

    排序规则实现方式：

    1、通过元素自身实现比较规则。

    2、通过比较器指定比较规则。

    1. public class TreeSetTest {
    2.     public static void main(String[] args) {
    3.         //实例化TreeSet
    4.         Set<String> set = new TreeSet<>();
    5.         //添加元素
    6.         set.add("c");
    7.         set.add("a");
    8.         set.add("d");
    9.         set.add("b");
    10.         set.add("a");
    11.         //获取元素
    12.         for(String str :set){
    13.             System.out.println(str);
    14.        }
    15.    }
    16. }
  • 相关阅读:
    关于跨域问题详解
    什么是跨域？及7种跨域解决方法
    【语音增强】多维谱自适应小波语音信号去噪【含Matlab源码 1972期】
    Redis源码学习：ziplist的数据结构和连锁更新问题
    CentOS7如何设置开机自启动程序、开机自启动脚本？
    第142篇 合约安全-重入锁
    Java - 由ReflectionFactory引发的对final关键字的思考
    关于分布式一致性
    pytest-bdd快速示例和问题解决
    【无标题】
  • 原文地址：https://blog.csdn.net/m0_58719994/article/details/131669937