[数据结构与算法]LinkedHashSet底层机制和源码解读

LinkedHashSet介绍

• LinkedHashSet是HashSet说明

  • LinkedHashSet是HashSet的子类

  • LinkedHashSet底层是一个LinkedHashMap,底层维护了一个 数组 + 双向链表

  • LinkedHashSet根据元素的hashcode值来决定元素的存储位置，同时使用链表维护元素的次序，使得元素看起来十一插入顺序保存到

  • LinkedHashSet不能许添加重复元素

• LinkedHashSet 底层机制

  • 在 LinkedHashSe t中维护了一个 hash 表和双向链表(LinkedHashSet 有 head 和 tail)

  • 每一个节点有 pro 和 next 属性，这样可以i形成双向链表

  • 在添加一个元素时，先求 hash 值，在求索引，确定该元素在hashtable的位置，燃火将添加的元素加入到双向链表(如果已经存在，不添加[原则和 hashset 一样])

    tail.next = newElement
    newElement.pre = tail
    tail = newElement

  • 这样的话，我们遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致

?

LinkedHashSet源码解读

import java.util.LinkedHashSet;
?
public class LinkedHashSetSource {
 ? ?public static void main(String[] args) {
?
 ? ? ? ?LinkedHashSet linkedHashSet = new LinkedHashSet();
?
 ? ? ? ?linkedHashSet.add(new String("AA"));
 ? ? ? ?linkedHashSet.add(456);
 ? ? ? ?linkedHashSet.add(456);
 ? ? ? ?linkedHashSet.add(new Customer("刘",1001));
 ? ? ? ?linkedHashSet.add(123);
 ? ? ? ?linkedHashSet.add("Jack");
?
 ? ? ? ?System.out.println(linkedHashSet);
 ? ? ? ?//LinkedHashSet底层维护的是LinkedHashMap
?
?
 ?  }
}
class ?Customer{
 ? ?private String name;
 ? ?private int id;
?
 ? ?public Customer(String name, int id) {
 ? ? ? ?this.name = name;
 ? ? ? ?this.id = id;
 ?  }
?
 ? ?public String getName() {
 ? ? ? ?return name;
 ?  }
?
 ? ?public void setName(String name) {
 ? ? ? ?this.name = name;
 ?  }
?
 ? ?public int getId() {
 ? ? ? ?return id;
 ?  }
?
 ? ?public void setId(int id) {
 ? ? ? ?this.id = id;
 ?  }
?
 ? ?@Override
 ? ?public String toString() {
 ? ? ? ?return "Customer{" +
 ? ? ? ? ? ? ? ?"name='" + name + '\'' +
 ? ? ? ? ? ? ? ?", id=" + id +
 ? ? ? ? ? ? ? ?'}';
 ?  }
}
/*
运行结果：
[AA, 456, Customer{name='刘', id=1001}, 123, Jack]
解读：
1.LinkedHashSet 取出和存储的顺序一致
2.LinkedHashSet 底层维护的是一个LinkenhashMap(是HashMap的子类)
3.LinkedHashSet 底层结构（数组 + 双向链表）
4.添加第一次时，直接将数组table扩容到16，存放的节点类型是 LinkedHashMap$Entry类
5.数组是HashMap$Node[]存放的元素/数据是LinkedHashMap$Entry类型
 ? ? ? //继承关系是在内部类完成
 ? ? ? static class Entry<K,V> extends HashMap.Node<K,V>{
 ? ? ? ? ? ?Entry<K,V> before, after;
 ? ? ? ? ? ?Entry(int hash,K key,V value, Node<K,V> next){
 ? ? ? ? ? ? ? ?super(hash, Key, value, next);
 ? ? ? ? ? ?}
 ? ? ? }
 */

LinkedHashSet课后练习题

import java.util.LinkedHashSet;
import java.util.Objects;
?
public class LinkedHashSetExercise {
 ? ?public static void main(String[] args) {
 ? ? ? ?/*题目：
 ? ? ? ?1.Car类(属性：name,price),如果name和price一样，则认为是相同的元素，不能添加
 ? ? ? ? */
 ? ? ? ?LinkedHashSet linkedHashSet = new LinkedHashSet();
 ? ? ? ?linkedHashSet.add(new Car("奔驰",300000));
 ? ? ? ?linkedHashSet.add(new Car("宝马",300000));
 ? ? ? ?linkedHashSet.add(new Car("保时捷",1000000));
 ? ? ? ?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;
 ?  }
?
 ? ?public String getName() {
 ? ? ? ?return name;
 ?  }
?
 ? ?public void setName(String name) {
 ? ? ? ?this.name = name;
 ?  }
?
 ? ?public double getPrice() {
 ? ? ? ?return price;
 ?  }
?
 ? ?public void setPrice(double price) {
 ? ? ? ?this.price = price;
 ?  }
?
 ? ?@Override
 ? ?public String toString() {
 ? ? ? ?return "\nCar{" +
 ? ? ? ? ? ? ? ?"name='" + name + '\'' +
 ? ? ? ? ? ? ? ?", price=" + price +
 ? ? ? ? ? ? ? ?'}';
 ?  }
?
 ? ?//重写equals方法和hashCode方法
 ? ?//当name 和 price 相同时，就返回相同的 hashCode 值，equals返回true
 ? ?@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(car.getPrice(), getPrice()) == 0 &&
 ? ? ? ? ? ? ? ?Objects.equals(getName(), car.getName());
 ?  }
?
 ? ?@Override
 ? ?public int hashCode() {
 ? ? ? ?return Objects.hash(getName(), getPrice());
 ?  }
}
/*
运行结果：
[
Car{name='奔驰', price=300000.0},
Car{name='宝马', price=300000.0},
Car{name='保时捷', price=1000000.0}]
?
解读：
1.使用重写equals方法和hashCode方法就可以使相同的元素无法添加
 */