Collections集合篇-Map

HashMap

最常用的Map结构，使用的是拉链法

数据结构

HashMap采用Entry数组来存储key-value,Entry有四个属性，Key，value，哈希值和下一个的指针

这里是1.8的版本，Node是Entry的一种实现

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

表的数据结构就是一个个的Entry

transient Node<K,V>[] table;

属性

/**
 * 初始的大小
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 为什么这里是2^31呢，因为hashCode是int类型的值，
 * 对于数组下标而言不能有负数，整数的范围就是0-2^31-1
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 阈值的计算参数，太多了可能会造成链表变长而降低查找效率
 * 太低了可能频繁扩容也会影响效率
 * 这个值是通过泊松分布计算出来的
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 意味着如果链表的长度大于8就要转化为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 相反的，如果当前树节点小于6个就要将其转化为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 链表的长度大于8且数组长度大于64转化为红黑树
 */
static final int MIN_TREEIFY_CAPACITY = 64;

hashCode()和equals()方法

首先看Object的hashCode方法：

作用：返回对象的哈希码值，用于在哈希表等数据结构中快速定位对象，提高哈希表的性能。

默认实现：Object类中的hashCode()方法默认返回对象的内存地址的哈希码值。

这个默认的方法是根据地址计算出来的，
如果两个对象的hashCode()返回值相同，不一定表示这两个对象相等(一般情况下是可以说明两个对象相等)，因为可能存在哈希冲突。

哈希值不能等价于地址，因为Java是在JVM中执行的，并不是真正的地址。

public class Hashcode {
    public static void main(String[] args) {
        A a = new A();
        A a1 = new A();
        A a2 = a1;
        System.out.println(a.hashCode());//460141958
        System.out.println(a1.hashCode());//1163157884
        System.out.println(a2.hashCode());//1163157884
    }
}
 
class A{
}

我们再看HashMap重写的hashCode

这里选择高十六位和第十六位进行异或运算，是为了尽量提取全部位的特征参与哈希计算，使得其更加分散

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

1. int h;：定义一个整型变量 h，用于存储计算出的哈希值。
2. (key == null) ? 0 : (h = key.hashCode())：这是一个三元运算符，用于判断给定的键是否为 null。如果键为 null，则将哈希值 h 设为 0；否则，调用键的 hashCode() 方法获取其哈希码，并将结果赋给变量 h。
3. (h >>> 16)：这是一个无符号右移运算，将变量 h 的二进制表示向右移动 16 位。这么做的目的是为了增加哈希值的随机性，使得哈希值的高位和低位都参与了哈希码的计算。
4. (h = key.hashCode()) ^ (h >>> 16)：这是一个按位异或运算，将哈希值 h 和右移后的哈希值进行异或运算。按位异或运算是一种常用的混合哈希函数，用于将高位的信息与低位的信息混合在一起，增加哈希值的随机性。
5. return：将计算出的哈希值返回。

在put操作里面是这样判断hashcode和equals的

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

• 首先判断两个的哈希是否相等，如果哈希不相等那么肯定不存在冲突
• 如果哈希相等，可能是哈希碰撞，也可能是真的就是一样的元素，需要对具体的k进行判断
• p.key == key判断的是引用是否相等，也就是指针，有的时候两个类的指针指向的是同一块空间，那么这个时候就肯定是相等的
• key.equals(k)判断的是内容是否相等，有的时候两个指针指得确实是不一样的，但是他们包含的内容是一样的，那么肯定也不能放进哈希表，new Student(“yyf”)和new Student(“xxy”)指针肯定是不同的，因为指向不同的内存空间，但是内容不一样。这个检测就需要equal来检测了

看源码这一段判断，书里的长篇大论都可以不看了：

hashcode一致，内容不一样的两个肯定是能进哈希表的，这就是哈希碰撞

hashcode一致，equals返回true那肯定是不能进的，这里逻辑是或，就是内容或者引用满足一个相等就不能放了

重写了hashcode，但是equals返回true是可以放进去的，因为逻辑是与

put操作

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里主要有几点注意：

• (n - 1) & hash是怎么来的，其实这就是一个取余的操作，因为n为2的整数倍，那么n-1肯定是末尾全为1前面全为0的，用位运算会比%快
• p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))在前面已经讲过了

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断数组是否未初始化,这里table已经赋值给tab了，n也同理
    if ((tab = table) == null || (n = tab.length) == 0)
        //如果未初始化，调用resize方法 进行初始化
        n = (tab = resize()).length;
    //通过 & 运算求出该数据（key）的数组下标并判断该下标位置是否有数据
    /**
     * 这里是取余操作，位运算更快
     * 由于n必然是2的倍数，那么-1就是除了最高位其他都为1，这个时候就相当于掩码，与hash进行与运算
     * 就可以得到余数，非常神奇
     */
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果没有，直接将数据放在该下标位置
        tab[i] = newNode(hash, key, value, null);
    //该数组下标有数据的情况
    else {
        Node<K,V> e; K k;
        //判断该位置数据的key和新来的数据是否一样
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            //如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到
            e = p;
        //判断是不是红黑树
        else if (p instanceof TreeNode)
            //如果是红黑树的话，进行红黑树的操作
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //新数据和当前数组既不相同，也不是红黑树节点，证明是链表
        else {
            //遍历链表
            for (int binCount = 0; ; ++binCount) {
                //判断next节点，如果为空的话，证明遍历到链表尾部了
                if ((e = p.next) == null) {
                    //把新值放入链表尾部
                    p.next = newNode(hash, key, value, null);
                    //因为新插入了一条数据，所以判断链表长度是不是大于等于8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //如果是，进行转换红黑树操作
                        treeifyBin(tab, hash);
                    break;
                }
                //判断链表当中有数据相同的值，如果一样，证明为修改操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //把下一个节点赋值为当前节点
                p = e;
            }
        }
        //判断e是否为空（e值为修改操作存放原数据的变量）
        if (e != null) { // existing mapping for key
            //不为空的话证明是修改操作，取出老值
            V oldValue = e.value;
            //一定会执行  onlyIfAbsent传进来的是false
            if (!onlyIfAbsent || oldValue == null)
                //将新值赋值当前节点
                e.value = value;
            afterNodeAccess(e);
            //返回老值
            return oldValue;
        }
    }
    //计数器，计算当前节点的修改次数
    ++modCount;
    //当前数组中的数据数量如果大于扩容阈值
    if (++size > threshold)
        //进行扩容操作
        resize();
    //空方法
    afterNodeInsertion(evict);
    //添加操作时 返回空值
    return null;
}

put的逻辑是：

• 首先判断是不是没有进行初始化，如果是第一次加入，那么resize，这里的默认长度是16，阈值为16*0.75
• 如果初始化了，看tab[(n - 1) & hash]是否有数据，如果没有，就直接放这里；如果有那么就进行后面的逻辑
• 判断p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))看跟当前的这个是不是一样的，如果是一样的那就进行修改，如果不是，那就要进行链表或者红黑树的添加了
• 如果是红黑树，那么就走红黑树的添加逻辑
• 如果是链表，就遍历链表，每一个都进行判断p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))，如果是那就修改，如果遍历到最后了，那就添加到末尾
• 边走边判断是不是要超过8个了，如果遍历到的节点到第七个了，那就要树化了
• 最后遍历完了看是否超过扩容阈值了，如果要扩容还要扩

  关于这里链表的尾插法，后续还有相关知识点

HashMap的扩容

//扩容、初始化数组
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
    	//如果当前数组为null的时候，把oldCap老数组容量设置为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //老的扩容阈值
    	int oldThr = threshold;
        int newCap, newThr = 0;
        //判断数组容量是否大于0，大于0说明数组已经初始化
    	if (oldCap > 0) {
            //判断当前数组长度是否大于最大数组长度
            if (oldCap >= MAXIMUM_CAPACITY) {
                //如果是，将扩容阈值直接设置为int类型的最大数值并直接返回
                /**
                 * 如果都已经到最大限制了不能再多了，那么阈值就要变得最大以免还要进行扩容操作
                 */
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果在最大长度范围内，则需要扩容  OldCap << 1等价于oldCap*2
            //运算过后判断是不是最大值并且oldCap需要大于16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold  等价于oldThr*2
        }
    	//如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在，       			如果是首次初始化，它的临界值则为0
        /**
         * // 为什么这里的oldThr在未初始化数组的时候就有值呢？
         // 这是因为HashMap有两个带参构造器，可以指定初始容量，
         // 若你调用了这两个可以指定初始容量的构造器，
         // 这两个构造器就会将阈值记录为第一个大于等于你指定容量，且满足2^n的数（可以看看这两个构造器）
         */
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //数组未初始化的情况，将阈值和扩容因子都设置为默认值
        //初始化走这个
    	else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    	//初始化容量小于16的时候，扩容阈值是没有赋值的
        if (newThr == 0) {
            //创建阈值
            float ft = (float)newCap * loadFactor;
            //判断新容量和新阈值是否大于最大容量
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
    	//计算出来的阈值赋值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //根据上边计算得出的容量 创建新的数组       
    	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    	//赋值
    	table = newTab;
    	//扩容操作，判断不为空证明不是初始化数组
        if (oldTab != null) {
            //遍历数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //判断当前下标为j的数组如果不为空的话赋值个e，进行下一步操作
                if ((e = oldTab[j]) != null) {
                    //将数组位置置空
                    oldTab[j] = null;
                    //判断是否有下个节点
                    if (e.next == null)
                        //如果没有，就重新计算在新数组中的下标并放进去
                        newTab[e.hash & (newCap - 1)] = e;
                   	//有下个节点的情况，并且判断是否已经树化
                    else if (e instanceof TreeNode)
                        //进行红黑树的操作
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //有下个节点的情况，并且没有树化（链表形式）
                    else {
                        //比如老数组容量是16，那下标就为0-15
                        //扩容操作*2，容量就变为32，下标为0-31
                        //低位：0-15，高位16-31
                        //定义了四个变量
                        //        低位头          低位尾
                        Node<K,V> loHead = null, loTail = null;
                        //        高位头		   高位尾
                        Node<K,V> hiHead = null, hiTail = null;
                        //下个节点
                        Node<K,V> next;
                        //循环遍历
                        do {
                            //取出next节点
                            next = e.next;
                            //通过 与操作 计算得出结果为0
                            if ((e.hash & oldCap) == 0) {
                                //如果低位尾为null，证明当前数组位置为空，没有任何数据
                                if (loTail == null)
                                    //将e值放入低位头
                                    loHead = e;
                                //低位尾不为null，证明已经有数据了
                                else
                                    //将数据放入next节点
                                    loTail.next = e;
                                //记录低位尾数据
                                loTail = e;
                            }
                            //通过 与操作 计算得出结果不为0
                            else {
                                 //如果高位尾为null，证明当前数组位置为空，没有任何数据
                                if (hiTail == null)
                                    //将e值放入高位头
                                    hiHead = e;
                                //高位尾不为null，证明已经有数据了
                                else
                                    //将数据放入next节点
                                    hiTail.next = e;
                               //记录高位尾数据
                               	hiTail = e;
                            }
                            
                        } 
                        //如果e不为空，证明没有到链表尾部，继续执行循环
                        while ((e = next) != null);
                        //低位尾如果记录的有数据，是链表
                        if (loTail != null) {
                            //将下一个元素置空
                            loTail.next = null;
                            //将低位头放入新数组的原下标位置
                            newTab[j] = loHead;
                        }
                        //高位尾如果记录的有数据，是链表
                        if (hiTail != null) {
                            //将下一个元素置空
                            hiTail.next = null;
                            //将高位头放入新数组的(原下标+原数组容量)位置
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
    	//返回新的数组对象
        return newTab;
    }

resize()的逻辑是：

• 首先判断oldCap是否大于0，如果是大于0那么说明已经初始化了，如果是等于0但是有阈值，说明可能是通过remove光了，也可能是初始化的时候使用有参构造方法，最后是等于0但是也没有阈值，对应的是无参构造方法，这个时候还没有真正给hashmap空间
• 大于0，那么就是扩展hashmap长度为原来两倍（这里是左移一位，也就是2），那么阈值也跟着扩展，如果等于0但是有阈值，那么新的阈值也是原来的，如果是无参的初始化，那么就是默认的16，阈值160，75
• 完成了新数组长度和新阈值的计算，接着就是移动数组了，新建一个新长度的数组
• 在旧的数组里面遍历，如果不为空，说明要移动了，如果后续没有，那么直接进新数组，如果还有后续，先判断是否是红黑树的TreeNode节点，是的话就走红黑树的逻辑，如果不是那就说明是链表了
• 链表的添加有两种，首先新建两个链表，一个是需要原封不动放在新链表对应节点的，另一组是放在$newTab[j + oldCap] = hiHead$中
• 如何判断移动呢？进行$e.hash & oldCap$的判断，这个计算的结果是oldcap最高位的值，我们放在table数组里面的哈希碰撞都是通过取余操作，这个计算的是oldcap的最高位后面的位数，最高位被忽视了，比如101010 & 001111和111010 & 001111结果都是1010，放在10的位置，对于这个链表来说最高位10和11的效果是一样的，因此为了缩短链表，把这一部分进行分开是很有必要的，这样就可以有效缩短链表。
• 然后通过判断遍历这个链表，按照上面的条件分别进入两个待移动链表。
• 最后移动链表，完成扩容

引申：为什么HashMap的数组是2的次幂

回答这个问题可以看两个判断条件

1. (n - 1) & hash，n为数组长度
2. e.hash & oldCap，oldCap为数组长度
   参考回答：

• 对于取余操作：计算索引的效率更高，如果是2的n次幂可以用位运算代替取模运算
• 对于计算新索引，e.hash & oldCap可以计算高位，判断是否转移到新表下。

Java1.7的HashMap死循环问题

jdk7的的数据结构是：数组+链表

在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

• 变量e指向的是需要迁移的对象
• 变量next指向的是下一个需要迁移的对象
• Jdk1.7中的链表采用的头插法
• 在数据迁移的过程中并没有新的对象产生，只是改变了对象的引用

产生死循环的过程：

线程1和线程2的变量e和next都引用了这个两个节点

线程2扩容后，由于头插法，链表顺序颠倒，但是线程1的临时变量e和next还引用了这两个节点

第一次循环

由于线程2迁移的时候，已经把B的next执行了A

第二次循环

第三次循环

参考回答：

在jdk1.7的hashmap中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

比如说，现在有两个线程

线程一：读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入

线程二：也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。

线程一：继续执行的时候就会出现死循环的问题。

线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，

所以B->A->B,形成循环。

当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），尾插法，就避免了jdk7中死循环的问题。

LinkedHashMap

LinkedHashMap继承自HashMap，实现了Map接口，HashMap是不记录顺序的，有的时候我们需要记住插入的顺序，LinkedHashMap通过维护一个链表来记录顺序，可以想象成每插入一个到HashMap，链表也要插入一个保留顺序。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

数据结构

在1.8维护了一个双向链表，定义头指针和尾指针，每一个Entry都会有前驱和后继

这是新的 Entry的数据结构，继承自HashMap的Node，多了前驱和后继

/**
 * LinkedHashMap中的node直接继承自HashMap中的Node。并且增加了双向的指针
 */
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);
    }
}

LinkedHashMap定义了头尾指针，accessOrder是一个重要变量，设置为真的话，get也会使元素移动到链表末尾，可以用这个变量实现LRU

/**
   * 头指针，指向第一个node
   */
  transient LinkedHashMap.Entry<K,V> head;

  /**
   * 尾指针，指向最后一个node
   */
  transient LinkedHashMap.Entry<K,V> tail;

  /**
   * 一个条件变量，它控制了是否在get操作后需要将新的get的节点重新放到链表的尾部
   * LinkedHashMap可以维持了插入的顺序，但是这个顺序不是不变的，可以被get操作打乱。
   *
   * @serial
   */
  final boolean accessOrder;

构造函数

/**
   * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
   * with the specified initial capacity and load factor.
   *
   * @param  initialCapacity the initial capacity
   * @param  loadFactor      the load factor
   * @throws IllegalArgumentException if the initial capacity is negative
   *         or the load factor is nonpositive
   */
  public LinkedHashMap(int initialCapacity, float loadFactor) {
      super(initialCapacity, loadFactor);
      accessOrder = false;
  }

  /**
   * 构造一个空的，按插入序（accessOrder = false）的LinkedHashMap，使用默认初始大小和负载因子0.75
   */
  public LinkedHashMap(int initialCapacity) {
      super(initialCapacity);
      accessOrder = false;
  }

  /**
   * 默认的无参构造函数继承自HashMap的无参构造，那么也是刚开始懒加载
   * 直到第一个元素进来才会有分配空间resize一次
   * 默认也是accessOrder为假，也就是说不能get改变顺序
   */
  public LinkedHashMap() {
      super();
      accessOrder = false;
  }
  
  public LinkedHashMap(Map<? extends K, ? extends V> m) {
      super();
      accessOrder = false;
      putMapEntries(m, false);
  }

  /**
   * 这个构造方法指定了accessOrder
   * 注意细节，要配置accessOrder只能用容量和负载因子的有参构造方法
   */
  public LinkedHashMap(int initialCapacity,
                       float loadFactor,
                       boolean accessOrder) {
      super(initialCapacity, loadFactor);
      this.accessOrder = accessOrder;
  }

Java1.7和1.8LinkedHashMap的区别

• 1.7版本的是用的双向循环链表，相比于HashMap多了两个变量，一个是头节点，因为是双向循环链表，head既可以是头也可以是尾。还有个顺序的变量，true是顺序，false是逆序，对于链表来说就是头插法和尾插法的区别，头插法就是逆序，尾插法就是顺序
• 1.8用的是双向链表，接下来重点介绍

1.8维护链表的操作

对于数组的插入和扩容继承自HashMap，不在赘述。主要研究双向链表如何维护。

afterNodeRemoval

顾名思义，在节点移除之后要做的事情

//在节点删除后，维护链表，传入删除的节点
void afterNodeRemoval(Node<K,V> e) { // unlink
    //p指向待删除元素，b执行前驱，a执行后驱
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //这里执行双向链表删除p节点操作，很简单。
    p.before = p.after = null;
    //如果没有前面的节点，那这个就是第一个，这个时候全局的head指针要给当前节点的下一个作为头节点
    if (b == null)
        head = a;
    //如果不是第一个节点，那就前面节点的后继为当前节点的后继
    else
        b.after = a;
    //如果没有后继的节点，那么前面的节点就要接替成为尾节点
    if (a == null)
        tail = b;
    //同理
    else
        a.before = b;
}

afterNodeAccess

根据accessOrder判断是否要在get之后进行调整

  //在节点被访问后根据accessOrder判断是否需要调整链表顺序
//将节点放在最后面
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        //如果accessOrder为false或者只有一个节点了，什么都不做
        if (accessOrder && (last = tail) != e) {
            //p指向待删除元素，b执行前驱，a执行后驱
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            //这里执行双向链表删除操作
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            //这里执行将p放到尾部
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            //保证并发读安全。
            ++modCount;
        }
    }

afterNodeInsertion

这个方法是在添加之后的操作，可以想象成LRU，当容量超过阈值的时候可以重写removeEldestEntry方法返回true，就会删除最老的一个元素

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //removeEldestEntry(first)默认返回false，所以afterNodeInsertion这个方法其实并不会执行
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

get操作

/**
 * 调用hashmap的getNode方法获取到值之后，维护链表
 * @param key
 * @return
 */
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //根据这个accessOrder来看是否要更新队伍
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

put操作