7-LinkedHashSet底层结构和源码分析

7-LinkedHashSet底层结构和源码分析

介绍汇总:

  1. LinkedHashSet全面说明
  2. LinkedHashSet底层机制说明

1-LinkedHashSet全面说明

  1. LinkedHashSet 底层是一个 LinkedHashMap ,底层维护了一个数组 + 双向链表 。由于 LinkedHashMap 是继承 HashMap 的所有特性的,其双向链表是在原本的数据结点上加上了 before 和 after 指针,并且也不破坏原来 HashMap 中链表和红黑树的结构,来完成实现双向链表的。
  2. LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,同时使用链表维护元素的次序,这就保证元素看起来是以插入顺序保存的。
  3. LinkedHashSet 不允许添加重复元素,这点与 HashSet 一致。

2-LinkedHashSet底层机制说明

  1. 在 LinkedHashSet 中维护了一个 hash 表和双向链表( LinkedHashSet (LinkedHashMap) 有 head 和 tail )
  2. 每一个数据结点在原本的基础上(通过继承 HashMap 的数据结点 Node ,拥有 Node 所有特性)有 before 和 after 属性,这样就可以形成双向链表(before 和 after 属性类型为 Entry ,这个类是继承 Node,这也是为啥 LinkedHashSet 中表的类型为 Node,却可以存放 Entry 类型数据结点)
  3. 在添加一个元素时,先求 hash 值,再求索引;确定该元素在 table 的位置,然后将添加的元素加入到双向链表(若已存在,不添加【原则和 HashSet 一样】)
// 添加示意代码
tail.next = newElement
newElement.pre = tail
tail = newElement
  1. 这样的话,遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致

  2. LinkedHashSet 继承了 HashSet 的所有特性,并且基本上都是调用其父类的方法进行。而其内部是维护了一个 LinkedHashMap,并且 LinkedHashMap 也继承了 HashMap 的所有特性,并且扩容流程也是和父类一致或者就是直接调用父类的扩容流程,只是其中有一些关键类和方法进行了重写。例如,数据结点 Entry (继承 HashMap 的内部类 Node )。还有创建新数据结点方法 newNode 方法进行了重写,创建 Entry 结点,并且增加了维护的双向链表的增加机制。还有一个就是 newTreeNode 方法,创建好后树结点,进行链表添加,并且该 TreeNode 结点是继承了 Entry 所有特性。

  3. 最主要就是 LinkedHashSet 与 HashSet 多维护了双向链表,可以按添加顺序进行遍历。

  4. 当前仅是介绍了添加元素的底层。

  5. 实践练习

    1. 测试链表树化
    package set.linkedhashset;
    
    import java.util.LinkedHashSet;
    
    public class LinkedHashSetSource {
    
        @SuppressWarnings({"all"})
        public static void main(String[] args) {
    
            // 测试链表树化
            // 与 HashMap 中的树化流程基本一致,满足两个条件才可树化
            // 只是多了双向链表
    
            LinkedHashSet linkedHashSet = new LinkedHashSet();
    
            for (int i = 1; i <= 12 ; i ++) {
                linkedHashSet.add(new Pet(i)) ;
            }
        }
    }
    
    class Pet {
    
        private int n ;
    
        public Pet(int n) {
            this.n = n;
        }
    
    
        @Override
        public int hashCode() {
            return 100;
        }
    }
    
    
    1. 相同元素
    package set.linkedhashset;
    
    import java.util.LinkedHashSet;
    import java.util.Objects;
    
    public class LinkedHashSetExercise {
    
        @SuppressWarnings({"all"})
        public static void main(String[] args) {
    
            /**
             * Car 类(属性:name,price),若 name 和 price 一样,则认为是相同元素,就不能添加
             * 解题思路
             * 按一般不同对象肯定不同,首先肯定不同,因为其引用中存放的地址值不同
             * 所以要想通过字段来确认为相同元素,需要重写 equals 和 hashCode 方法
             * 为啥还要在重写 hashCode ,是为了保证equals方法和hashCode方法之间的一致性合约,
             * 即如果两个对象通过equals方法比较是相等的,那么这两个对象的hashCode方法也必须返回相同的整数值。
             * 这是从对象本身的角度出发,前边的练习从 HashMap 的相同元素的条件角度进行
             */
    
            LinkedHashSet linkedHashSet = new LinkedHashSet();
    
            linkedHashSet.add(new Car("奥拓",1000)) ;
            linkedHashSet.add(new Car("奥迪",300000)) ;
            linkedHashSet.add(new Car("法拉利",10000000)) ;
            linkedHashSet.add(new Car("奥迪",300000)) ;
            linkedHashSet.add(new Car("保时捷",70000000)) ;
            linkedHashSet.add(new Car("奥迪",300000)) ;
    
            System.out.println("====集合中元素有" + linkedHashSet + "====");
        }
    }
    
    class Car {
    
        private String name ;
    
        private double price ;
    
        public Car(String name, double price) {
            this.name = name;
            this.price = price;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Car car = (Car) o;
            return Double.compare(price, car.price) == 0 && Objects.equals(name, car.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, price);
        }
    
        @Override
        public String toString() {
            return "Car{" +
                    "name='" + name + '\'' +
                    ", price=" + price +
                    '}';
        }
    }
    
    

热门相关:超级英雄   至尊医道   恐怖复苏   我的女友是丧尸   天帝龙魂