Java集合框架【二容器[LinkedList容器类、Set接口]】

小灰灰 2024-03-31 10:21 21阅读 0赞

#### 文章目录 ####

*  一 LinkedList容器类
 *   *  1.1 LinkedList的使用(List接口)
     *  1.2 Linked的使用(非List标准)
     *  1.4 LinkedList源码分析
 *  二 Set接口
 *   *  2.1 Set接口特点
     *  2.2 HashSet容器类
     *   *  2.2.1 Hash算法原理
         *  2.2.2 HashSet的例子
         *  2.2.3 HashSet存储特征分析
     *  2.3 TreeSet容器类
     *  2.4 通过元素自身实现比较规则
     *  2.5 通过比较器实现比较规则
 *  三 单例集合使用例子
 *   *  List实现
     *  Set实现

## 一 LinkedList容器类 ##

*  LinkedList底层用双向链表实现的存储。
 *  ***特点：查询效率低，增删效率高***，线程不安全双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。  
    ![在这里插入图片描述][4a9ff86de3b945779c07a341e5008c71.png]

class Node<E> {
        
    	E item;
    	Node<E> next;
    	Node<E> prev;
    }

### 1.1 LinkedList的使用(List接口) ###

*  Linked实现了List接口，所以LinkedList是具备List的存储特征的【有序、可重复】

public class LInkedListTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> list = new LinkedList<>();
            list.add("a");
            list.add("b");
            list.add("c");
            list.add("a");
            for(String s :list) {
        
                System.out.println(s);
            }
        }
    }

![在这里插入图片描述][f854498ef3b3461faffc09a817adb940.png]

### 1.2 Linked的使用(非List标准) ###

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>void addFirst(E e）</td> 
   <td>将指定元素插入到开头</td> 
  </tr> 
  <tr> 
   <td>void add Last(E e）</td> 
   <td>将指定元素插入到结尾</td> 
  </tr> 
  <tr> 
   <td>getFirst(）</td> 
   <td>返回此列表的第一个元素</td> 
  </tr> 
  <tr> 
   <td>getLast(）</td> 
   <td>返回此列表的最后一个元素</td> 
  </tr> 
  <tr> 
   <td>removeFirst()</td> 
   <td>移除此列表中的第一个元素，并返回这个元素</td> 
  </tr> 
  <tr> 
   <td>removeLast(）</td> 
   <td>移除此列表中的最后一个元素，并返回这个元素</td> 
  </tr> 
  <tr> 
   <td>E pop(）</td> 
   <td>从此列表所表示的堆栈处弹出一个元素，等效于removeFirst</td> 
  </tr> 
  <tr> 
   <td>voidpush(E e）</td> 
   <td>将元素推入此列表所表示的堆栈这个等效于addFisrt(E e）</td> 
  </tr> 
  <tr> 
   <td>booleanisEmpty(）</td> 
   <td>判断列表是否包含元素，如果不包含元素则返回true</td> 
  </tr> 
 </tbody> 
</table>

### 1.4 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;
            }
        }

## 二 Set接口 ##

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

### 2.1 Set接口特点 ###

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

### 2.2 HashSet容器类 ###

*  ***Hashset是一个没有重复元素的集合，不保证元素的顺序。而且HashSet允许有null元素。HashSet是采用哈希算法实现，底层实际是用HashMap实现的（HashSet本质就是一个简化版的HashMap），因此，查询效率和增删效率都比较高。***

#### 2.2.1 Hash算法原理 ####

*  Hash算法也称之为散列算法  
    ![在这里插入图片描述][31e5bb645e45468683169434b35ce1ed.png]

#### 2.2.2 HashSet的例子 ####

/**
     * @author 缘友一世
     * date 2022/11/23-9:03
     */
    public class HashSetTest {
        
        public static void main(String[] args) {
        
            Set<String> set = new HashSet<>();
            set.add("a");
            set.add("d");
            set.add("b");
            set.add("a");
            //获取元素,在set容器中没有索引，没有对应的get方法。
            for(String s:set) {
        
                System.out.println(s);
            }
            boolean flag = set.remove("d");
            System.out.println(flag);
            for(String s:set) {
        
                System.out.println(s);
            }
            System.out.println(set.size());
        }
    }

![在这里插入图片描述][e17b0bd822fd45ec95d73226b5f6479e.png]

#### 2.2.3 HashSet存储特征分析 ####

*  Hashset是一个***不保证元素的顺序且没有重复元素的集合***，是***线程不安全***的。Hashset***允许有null元素***
    
    1.  无序：
        
         *  在HashSet中底层是使用HashMap存储元素的。
         *  HashMap底层使用的是数组与链表实现元素的存储。
         *  元素在数组中存放时，并不是有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定元素在数组中的位置。
    2.  不重复：
        
         *  当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会调用元素的equals()方法判断两个元素是否相同。如果元素相同则不会添加该元素，如果不相同则会使用单向链表保存该元素。

/**
     * @author 缘友一世
     * date 2022/11/23-9:11
     */
    public class Users {
        
        private String userName;
        private int userAge;
    
        public Users() {
        
        }
    
        public Users(String userName, int userAge) {
        
            this.userName = userName;
            this.userAge = userAge;
        }
    
        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 int hashCode() {
        
            int result=userName !=null ? userName.hashCode():0;
            result=31*result+userAge;
            return result;
        }
    
        @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):false;
        }
    
        @Override
        public String toString() {
        
            return "Users{" +
                    "userName='" + userName + '\'' +
                    ", userAge=" + userAge +
                    '}';
        }
    }
    
    class Test {
        
        public static void main(String[] args) {
        
            HashSet<Users> set1 = new HashSet<>();
            Users aaa = new Users("aaa", 19);
            Users bbb = new Users("aaa", 19);
            set1.add(aaa);
            set1.add(bbb);
            for(Users user:set1) {
        
                System.out.println(user);
            }
    
        }
    }

![在这里插入图片描述][caa78525644647e395bc412b8ad1c1ed.png]

### 2.3 TreeSet容器类 ###

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

/**
     * @author 缘友一世
     * date 2022/11/23-9:30
     */
    public class TreeSetTest {
        
        public static void main(String[] args) {
        
            TreeSet<String> set = new TreeSet<>();
            set.add("c");
            set.add("a");
            set.add("b");
            set.add("1");
            for(String str:set) {
        
                System.out.println(str);
            }
        }
    }

![在这里插入图片描述][ad748a827e78440e9d1f0f78da6f43f0.png]  
![在这里插入图片描述][a3ee3e51f4df4405aa2a390a75c04301.png]

### 2.4 通过元素自身实现比较规则 ###

*  在元素自身实现比较规则时，需要实现Comparable接口中的compareTo方法，该方法中用素定义比较规则。TreeSet通过调用该方法来完成对元素的排序处理。

/**
     * @author 缘友一世
     * date 2022/11/23-12:53
     */
    public class SortTest {
        
        public static void main(String[] args) {
        
            TreeSet<Users2> set1 = new TreeSet<>();
            Users2 aaa = new Users2("aaa", 19);
            Users2 ccc = new Users2("ccc", 17);
            Users2 bbb = new Users2("bbb", 19);
            set1.add(aaa);
            set1.add(bbb);
            set1.add(ccc);
            for(Users2 user:set1) {
        
                System.out.println(user);
            }
        }
    }
    class Users2 implements Comparable<Users2> {
        
    
        private String userName;
        private int userAge;
    
        public Users2() {
        
        }
    
        public Users2(String userName, int userAge) {
        
            this.userName = userName;
            this.userAge = userAge;
        }
    
        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 int hashCode() {
        
            int result=userName !=null ? userName.hashCode():0;
            result=31*result+userAge;
            return result;
        }
    
    
    
        @Override
        public boolean equals(Object o) {
        
            if(this==o) return true;
            if(o==null || getClass()!=o.getClass()) return false;
            Users2 users = (Users2) o;
            if(userAge!=users.userAge) return false;
            return userName!=null ? userName.equals(users.userName):false;
        }
    
        @Override
        public String toString() {
        
            return "Users{" +
                    "userName='" + userName + '\'' +
                    ", userAge=" + userAge +
                    '}';
        }
    
        @Override
        public int compareTo(Users2 o) {
        
            if(this.userAge>o.getUserAge()) {
        
                return 1;
            }
            if(this.userAge==o.getUserAge()) {
        
                return this.userName.compareTo(o.getUserName());
            }
            return -1;
        }
    }

![在这里插入图片描述][dffd09c7ed5d46bdaba6c12188268531.png]

### 2.5 通过比较器实现比较规则 ###

*  通过比较器定义比较规则时，我们需要单独创建一个比较器，比较器需要实现Comparator接口中的compare方法来定义比较规则。
 *  在实例化TreeSet时将比较器对象交给TreeSet来完成元素的排序处理。此时元素自身就不需要实现比较规则了。

/**
     * @author 缘友一世
     * date 2022/11/23-13:24
     */
    class Test {
        
        public static void main(String[]args){
        
            TreeSet<student> set = new TreeSet<>(new ComparatorTest());
            student ooo = new student("ooo", 18);
            student aaa = new student("aaa", 22);
            student sss = new student("sss", 22);
            set.add(ooo);
            set.add(aaa);
            set.add(sss);
            for(student x:set) {
        
                System.out.println(x);
            }
        }
    }
    public class ComparatorTest implements Comparator<student> {
        
        //定义比较规则
    
        @Override
        public int compare(student o1, student o2) {
        
            if(o1.getAge()>o2.getAge()) {
        //升序
                return 1;
            }else if(o1.getAge()==o2.getAge()) {
        
                return o1.getName().compareTo(o2.getName());
            }
            return -1;
        }
    }
    class student {
        
        private  String name;
        private int age;
    
        public student() {
        
        }
    
        public student(String name, int age) {
        
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
        
            return name;
        }
    
        public void setName(String name) {
        
            this.name = name;
        }
    
        public int getAge() {
        
            return age;
        }
    
        public void setAge(int age) {
        
            this.age = age;
        }
    
        @Override
        public boolean equals(Object o) {
        
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            student student = (student) o;
            return age == student.age && Objects.equals(name, student.name);
        }
    
        @Override
        public int hashCode() {
        
            return Objects.hash(name, age);
        }
    
        @Override
        public String toString() {
        
            return "student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }

![在这里插入图片描述][398ac571b0bf4a0f9406cba1b49e774e.png]

## 三 单例集合使用例子 ##

*  生成1-10之间的随机数(1-10),将不重复的10个随机数放到容器中

### List实现 ###

/**
     * @author 缘友一世
     * date 2022/11/23-13:36
     */
    public class SetDemo {
        
      public static void main(String[] args) {
        
      ArrayList<Integer> list = new ArrayList<>();
            while(true) {
        
                int num=(int)(Math.random()*10+1);
                if(!list.contains(num)) {
        
                    list.add(num);
                }
                if(list.size()==10) {
        
                    break;
                }
            }
            for(Integer x:list) {
        
                System.out.println(x);
            }
        }
    }

![在这里插入图片描述][ca58db9564494c60a6c0a45dba545b38.png]

### Set实现 ###

/**
     * @author 缘友一世
     * date 2022/11/23-13:36
     */
    public class SetDemo {
        
        public static void main(String[] args) {
        
            HashSet<Integer> set = new HashSet<>();
            while(true) {
        
                //set容器是不允许有重复元素的，所以不需要
                int num=(int)(Math.random()*10+1);
                set.add(num);
                if(set.size()==10) {
        
                    break;
                }
            }
            for(Integer i:set) {
        
                System.out.println(i);
            }
        }
    }

![在这里插入图片描述][3c0685a3dfa74e29b917168aa1508ce0.png]

[4a9ff86de3b945779c07a341e5008c71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4e1f72fe1c424796868ffc3f4eb01964.png
[f854498ef3b3461faffc09a817adb940.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/80fdd8c3618e476b8743490b354beb4b.png
[31e5bb645e45468683169434b35ce1ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/29659112452249b5908321112cf316d5.png
[e17b0bd822fd45ec95d73226b5f6479e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f7086f8da7804e89817cd3188f396223.png
[caa78525644647e395bc412b8ad1c1ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c4166a99ad514bc2a556a2be0d14178b.png
[ad748a827e78440e9d1f0f78da6f43f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d2af891040ce4db2a65364d71722bcad.png
[a3ee3e51f4df4405aa2a390a75c04301.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3288b90b42374a47b4df4b0f1920fa18.png
[dffd09c7ed5d46bdaba6c12188268531.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b56384964c6d429a89ab5ad9887db40b.png
[398ac571b0bf4a0f9406cba1b49e774e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ae9c8e2ff85d4afd96b38940056510ad.png
[ca58db9564494c60a6c0a45dba545b38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d339321403014e47920e298de23cf389.png
[3c0685a3dfa74e29b917168aa1508ce0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/335636f54b3a44988a332ba3989fec51.png