集合-LinkedHashMap源码详解(特有方法解析)以及HashMap与LinkedHashMap的不同

特点:

底层数据结构:数组加链表用来存储数据; header双向链表用来实现数据插入有序或者访问有序;

集合-LinkedHashMap源码详解(特有方法解析)以及HashMap与LinkedHashMap的不同

继承关系:
public class LinkedHashMap<K,V>
    extends HashMap<K,V> //继承了HashMap
    implements Map<K,V>//实现了Map接口
{
默认值:
  • 默认数组大小:11 ==>继承父类
  • loadFactor(默认加载因子):0.75 ==>继承父类
基本属性:下面为LinkedHashMap特有,别的属性全部继承HashMap;
     
     private transient Entry<K,V> header; //头结点
     
     private final boolean accessOrder;//顺序性; true(访问有序); false(插入有序)
  • header如何初始化:header初始化需要调用重写后的 init()方法,创建一个不存储数据的entry实体,而init方法是在父类的构造函数中被调用,子类的初始化都会调用父类的构造函数,从而实现了header的初始化;
//子类重写方法;
@Override
    void init() {
        header = new Entry<>(-1, null, null, null); //hash值为-1;
        header.before = header.after = header;
    }
   //父类构造函数:
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init(); //在LinkedHashMap起作用,用来初始化header;
    }

构造函数:均是调用父类对应的构造函数
 public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);//调用父类的构造函数
        accessOrder = false; 
    }

     //只指定数组大小
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity); 
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

     //指定数组大小。加载因子,以及确定使用何种顺序
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
增长方式:继承父类,2*table.length;
CRUD(增删改查):
  • put: 调用的是父类的put方法,但是对put方法中一些相关函数进行重写;
// (父类HashMap实现)
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {//如果table为空,创建默认数组
        inflateTable(threshold);
    }
    if (key == null)//对key进行特殊处理,key为null总在0号角标链表中
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length); //通过hash找到对应角标
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    //遍历该角标俩表,找到对应key值
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        //找到key值将value值进行更新,并返回旧的value值
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);//现有集合中没找到key,那么创建一个新的entry实体
    return null;
}
//(当前类LinkedHashMap实现)
void addEntry(int hash, K key, V value, int bucketIndex) {
//目前此函数并没有看出与父类的区别
    super.addEntry(hash, key, value, bucketIndex);//调用父类创建entry实体

    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {//总返回false;这句等于无效代码,留作后用;
        removeEntryForKey(eldest.key);
    }
}
//(父类HashMap实现)
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
    //如果集合中元素个数已经大于阈值,那么进行扩容;
        resize(2 * table.length);//二倍扩容
        hash = (null != key) ? hash(key) : 0; 
        bucketIndex = indexFor(hash, table.length); 找到新的key对应的数组角标
    }

    createEntry(hash, key, value, bucketIndex);//创建entry实体,子类重写
}

//(当前类LinkedHashMap实现)
void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);//头插法
    table[bucketIndex] = e;
    e.addBefore(header);//实现第二功能,使数据实现插入有序;
    size++;
}
//(当前类LinkedHashMap实现) ,addBefore为子类Entry内部类中的方法,
//Entry多了两个属性,before(前驱),after(后驱)
private void addBefore(Entry<K,V> existingEntry) {
//使header实现插入有序,header所处链表实质上为一个循环的双向链表;
//将header.after理解为头结点的下一个结点,将header.before理解为尾结点;新结点插入位置为尾插
    after  = existingEntry;//新的尾结点链接头结点
    before = existingEntry.before;//新的尾结点的前驱链接旧的尾结点
    before.after = this;//旧的尾结点的下一结点链接新的尾结点
    after.before = this;//新的尾结点的下一结点的前驱链接新的尾结点
    //当然这句代码可以改为existingEntry.before=this;//头结点的前驱链接新的尾结点
}

HashMap与LinkedHashMap的不同的点:

上一篇:03


下一篇:关于ubntu 下Root 环境与用户环境