前置知识
==和equals的区别
对于基本类型变量来说，只能使用 == ，因为基本类型的变量没有方法。使用==比较是值比较
对于引用类型的变量来说，==比较的两个引用对象的地址是否相等。所有类都是继承objcet类，而object类是equals方法比较的也是对象的地址是否相等，如果类没有重写equals方法，使用 == 和equals方法效果是一样的
为什么要重写equals和HashCode
HashCode方法：底层采用C语言编写，根据对象地址转换为整数类型
如果两个对象的HashCode相等，对象的内容至不一定相等；hash碰撞的问题
如果使用equals方法比较两个对象内容值相等的情况下，那么hashcode的值也相等
因为equals默认情况下Object类采用==比较对象，那么比较的是内存地址是否相等，当数据类型只要不是基本类型，那么比较永远不会相等。
set集合存储的就是不重复的对象，底层就是hashmap，依据equals和hashcode进行判断
时间复杂度
时间复杂度为O(n) 从头查询到尾部，查询多次
时间复杂度为O(1) 查询一次 比如根据数组下标查询
时间复杂度为O(logn) 平方查询 比如红黑树，
效率：O(1)>O(logn)>O(n)
(不带符号右移) >>>
无符号右移就是右移之后，无论该数为正还是为负，右移之后左边都是补上0
无符号右移运算符和右移运算符的主要区别在于负数的计算，因为无符号右移是高位补0，移多少位补多少个0
15>>>2=0000 1111 右移两位=0000 0011=3
^异或运算
相同为0，不同为1
2^3= 0010^0011=0001=1
&（与运算）
00得0 11得1 01得0
2&3=0010&0011=0010=2
位移操作：1<<2=4，1左移两位为什么等于4
这里的1是十进制，而计算机交流是用二进制，所以先要将1用二进制表示出来。
每一个符号（英文、数字或符号等）都会占用1Bytes的记录，每一个中文占2Byte
而一个1Bytes占8个bit，也就是8个二进制位
8位二进制数：28种不同状态 0000 0000 ~1111 1111=0~255=28=256
1的二进制表示0000 0001，然后进行位移操作。
位移操作向左边位移，后面空出来的补上0，越往左边越大，把0000 0001向左位移2位，变成了0000 0100，二进制0000 0100转化十进制所以为4，也可以说每左移一位是乘以2
8>>2?
0000 1000右移2位0000 0010，转化为10进制等于2
10>>2?
0000 1010右移2位0000 0010，转化为10进制等于2
1<<30?
0000 0001左移30位01000000 00000000 00000000 00000000，转化为10进制等于1073741824，也就是230
HashMap集合特点及源码分析（JDK1.8）
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
HashMap继承了AbstractMap类，实现了Cloneable克隆接口、Serializable序列化接口、Map接口
特点：数组+链表+红黑树构成
HashMap重要的五大点
1.集合初始化
HashMap成员变量
//默认初始化hashmap容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //2的4次幂 16 //hashmap最大容量1073741824 static final int MAXIMUM_CAPACITY = 1 << 30;//2的30次幂 //扩容因子 16*0.75=12 达到12就会进行扩容 static final float DEFAULT_LOAD_FACTOR = 0.75f; //链表中存储元素的数量 > 8 时，会自动转换为红黑树 static final int TREEIFY_THRESHOLD = 8; //删除元素时，如果一个红黑树中中存储元素数量 < 6 后，会自动转换为链表 static final int UNTREEIFY_THRESHOLD = 6; //数组容量>64&链表长度>8 转为红黑树 static final int MIN_TREEIFY_CAPACITY = 64; //阙值，用于判断是否扩容，threshold=容量*扩容因子=16*0.75=12 int threshold; //扩容因子实际大小 final float loadFactor; //HashMap中元素的数量 transient表示不能被序列化 transient int size; //集合修改次数 防止多线程篡改数据 transient int modCount; //存储元素的数组 单向链表 transient Node<K,V>[] table;
HashMap内部数据结构
链表
//单向链表 实现了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; } //基本方法 public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } //比较两个Node是否相等 public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
红黑树
//红黑树结构概览 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left;//左子树 TreeNode<K,V> right;//右子树 TreeNode<K,V> prev; // boolean red;//是否红色 TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } //返回当前节点 final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } }
HashMap构造方法
指定初始容量
构造一个具有默认初始容量 (16) 和默认负载因子 (0.75)的空HashMap
static final float DEFAULT_LOAD_FACTOR = 0.75f; public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; //扩容因子0.75 }
指定填充比
构造一个具有指定初始容量和默认扩容因子 (0.75)的空HashMap
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);//初始容量 扩容因子默认0.75 } 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;//负载因子 this.threshold = tableSizeFor(initialCapacity); } //获得的是大于cap的最小的2的幂，例如10，10的最小的2的幂=16 static final int tableSizeFor(int cap) { int n = cap - 1;//n=9 0000 1001 n |= n >>> 1;//|= 代表异或运算 先向右位移1位=0000 0100，0000 1001和0000 0100异或运算得到0000 1101 n |= n >>> 2;//....以此类推 n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; //n<0返回1，否则n大于MAXIMUM_CAPACITY的话返回最大值，小于最大值返回n + 1，全1的情况+1一定变成1后面跟一堆0的情况，这样就确定了最终的值，当HashMap的size到达threshold这个阈值时会扩容 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
用来初始化的Map
使用与指定Map相同的映射构造一个新的HashMap
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR;//默认负载因子0.75 putMapEntries(m, false); } //将集合元素put到HashMap中 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //获取元素大小 int s = m.size(); if (s > 0) { //如果存储元素的数组为空 说明这是刚构造的HashMap 那么就要为它指定最大容量 if (table == null) { //根据阈值和Map大小 推算出最大容量，向上取整为了取整数 float ft = ((float)s / loadFactor) + 1.0F; //判断容量是否超过最大容量 不超过就直接赋值 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //如果容量大于阈值 if (t > threshold) //重新计算阈值 threshold = tableSizeFor(t); } //数组已经初始化了 else if (s > threshold) resize(); //先扩容 // 循环put for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); //可能会触发resize putVal(hash(key), key, value, false, evict); } } }
2.数据寻址Get
根据key获取元素
public V get(Object key) { Node<K,V> e; //key的hash值 return (e = getNode(hash(key), key)) == null ? null : e.value; }
详细方法
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //如果table不等于null 数组不等于null first=赋值计算当前节点的hash值所在的数组下标位置 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { //如果比较当前节点的和第一个节点 if (first.hash == hash &&((k = first.key) == key || (key != null && key.equals(k)))) //返回第一个结点 return first; //如果第一个节点的下一个节点不为null if ((e = first.next) != null) { //判断是否为红黑树 if (first instanceof TreeNode) //处理getTreeNode()方法搜索key return ((TreeNode<K,V>)first).getTreeNode(hash, key); //是链表 do { //遍历比较直到找到节点或者节点为null退出循环 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
3.数据存储Put
将元素添加进HashMap
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
详细方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; //n表示table数组的长度 i表示key存放在哪个数组下标 int n, i; //将全局table=tab判断是否为空 或者 tab长度为0情况下 对table进行扩容 if ((tab = table) == null || (n = tab.length) == 0) //扩容 n=16 n = (tab = resize()).length; //i = (n - 1) & hash 计算key对应的index值 tab[i]key在数组中是否存在 if ((p = tab[i = (n - 1) & hash]) == null) //如果key的index值没有发生冲突 tab[i] = newNode(hash, key, value, null); //key的index发生冲突了 else { Node<K,V> e; K k; //如果hash和equals比较都相同 直接覆盖 if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) 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); //如果链表长度binCount大于8 数组容量大于64 if (binCount >= TREEIFY_THRESHOLD - 1) //把链表转换为红黑树 treeifyBin(tab, hash); break; } //查询链表中是否存在该key，如果存在直接修改value值 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //真正给e赋值 将新的value覆盖为oldvalue if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //只有新增才会使modCount++ 修改不会 fastclass机制防止在做遍历的时候有集合修改类 ++modCount; //如果size>12 就会提前去扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
4.节点删除
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value; }
详细方法
//hash:key的hash值 key:要删除的键值对的key value:要删除的键值对的value //matchValue 如果为true，则当key对应的键值对的值equals(value)为true时才删除；否则不关心value的值 //movable 删除后是否移动节点，如果为false，则不移动 final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; //节点数组tab不为空、数组长度n大于0、根据hash定位到的节点对象p if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; //如果当前节点的键和key相等，那么当前节点就是要删除的节点，赋值给node if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) node = p; //获取当前节点的下一个节点 else if ((e = p.next) != null) { //如果是一个红黑树，那么调用getTreeNode方法从树结构中查找满足条件的节点 if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); //如果是链表 else { //从头到尾逐个节点比对 do { //e节点的键是否和key相等，e节点就是要删除的节点，赋值给node变量 if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) { node = e; break; } p = e;//p指向e，让p存储的永远下一次循环里e的父节点 } while ((e = e.next) != null); } } //node不为空 找到了删除的节点 如果不需要对比value值或者需要对比value值但是value值也相等 if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) { //如果是红黑树上的节点 if (node instanceof TreeNode) //删除 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //如果是链表 该node节点就是首节点 else if (node == p) //删除 把当前节点的下一个赋值给当前表索引 tab[index] = node.next; //不是首节点，p是node的父节点 else // 删除 父节点的下一个节点就是node的下一个节点 p.next = node.next; ++modCount;//HashMap的修改次数递增 --size;//HashMap的元素个数 afterNodeRemoval(node);//保留的重写方法 无效果 return node;//返回删除结果 } } return null; }
5.扩容原理
JDK1.7 HashMap中扩容机制resize()
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果旧容量已经达到了最大，将阈值设置为最大值，与1.8相同 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //创建新哈希表 Entry[] newTable = new Entry[newCapacity]; //将旧表的数据转移到新的哈希表 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; //更新阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //遍历原来数组中所有的链表 for (Entry<K,V> e : table) { //判断每个下标对应的链表存放是否为空 while(null != e) { //这里两个多线程环境下都拿到 e.next可能会有死循环问题 Entry<K,V> next = e.next; //是否需要重新计算hash值 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } //得到新表中的索引 int i = indexFor(e.hash, newCapacity); //将新节点作为头节点添加到桶中 e.next = newTable[i]; newTable[i] = e; e = next; } } }
多线程环境下扩容造成死循环的分析过程
for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } }
因为是采用头插法，会导致整个链表顺序颠倒，多线程环境下遍历table这就容易导致死循环，因为操纵的同一个e对象
在多线程同时扩容的情况下，线程一抢先获得CPU资源，而线程二被挂起，此时它们拿到的数据都是e=a；next=c；线程一率先执行把key计算好了并放入newTable了
这时候线程二又被唤醒，因为线程之间不是共享的，所以此时newTable也为空，需要重新给里面赋值，但是e变量是可以被共享的。
1、线程二第一次循环还是之前拿到的数据e=a；next=c，此时newTable还为空
// e=a e.next=c Entry<K,V> next = e.next; //1 int i = indexFor(e.hash, newCapacity); //e.next=null e.next = newTable[i]; //数组1位置第一个元素赋值为 a newTable[i] = e; //e=c e = next;
2、线程二第二次循环
第二次循环获取e的数据，因为e的之前被线程一修改过变为d->c->
// e=c e.next=a Entry<K,V> next = e.next; //1 int i = indexFor(e.hash, newCapacity); //e.next=null e.next = newTable[i]; //数组1位置赋值为 c newTable[i] = e; //e=a e = next;
因为e的之前被线程一修改过变为d->c->a，所以c.next等于线程一里面的值，c.next=a
3、线程二第三次循环
//e=a； e.next=a.next=null Entry<K,V> next = e.next; //1 int i = indexFor(e.hash, newCapacity); //此时newTable[i]=a->c e.next=a.next a.next=c->a 出现死循环 e.next = newTable[i]; //数组1位置赋值为 a newTable[i] = e; //e=null e = next;
此时进入环形引用，无限循环中导致CPU使用率飙升
解决办法
单线程下没有不会有问题，多线程下采用ConCurrentHashMap
JDK1.8 HashMap中扩容机制resize()
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //如果原来的table=null, 则为HashMap的初始化, 生成空table返回即可 int oldCap = (oldTab == null) ? 0 : oldTab.length; //hashmap下一次扩容的阈值 int oldThr = threshold; //记录新的容量和新的下一次扩容大小 int newCap, newThr = 0; //大于0说明之前HashMap的数组不是空的 if (oldCap > 0) { // 再对数组进行检测 如果大于最大容量2的30次幂 直接返回 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //否者进行扩容为之前的二倍基于右移 newCap是oldCap长度的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //下一次提前扩容的数量 newThr = oldThr << 1; } //阈值大于0 说明集合已存在 赋值给newCap else if (oldThr > 0) newCap = oldThr; //如果等于0 说明刚初始化 newCap=0.75 newThr=新扩容的阈值=0.75*默认容量大小 else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果下一次提前扩容的数量==0 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"}) //HashMap里面新的扩容容量 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; //判断每个数组里面是否有链表 有的话用一个链表e存起来 if ((e = oldTab[j]) != null) { //然后将原来的链表赋值为null 能避免死循环 oldTab[j] = null; //下一个节点为空 说明只包含一个元素 if (e.next == null) //计算e在新table中的位置,放入其中 newTab[e.hash & (newCap - 1)] = e; //判断当前node是否是红黑树 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //链表情况下 else { //hashmap扩容会把原来的链表拆分成 两个链表 //低位链表的头尾 Node<K,V> loHead = null, loTail = null; //高位链表的头尾 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; //循环把链表拆分 放到两个链表里面 do { next = e.next; //散列下标不变的情况 oldCap=16 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //散列下标变的情况 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //两个做法都是把链表放在新的位置 //放在新表原位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //放在新表j+oldCap位置 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
HashMap1.8将链表通过运算拆封成两个链表存放到新的table中
HashMap面试题
HashMap什么时候会转换为红黑树
数组容量大于64并且链表长度大于8时
HashMap为什么要引进红黑树，为了解决什么问题？
链表查询时间复杂度为O(n),查询效率太低了，引用红黑树查询效率可以变为O(logN)
HashMap的长度为什么必须是2的次幂？
这样长度一定是偶数，在计算index下标的时候(n-1)&hash，这样（n-1）就会是奇数，奇数&hash值才会减小冲突。n取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列
如何避免HashMap内存溢出问题
因为没有重写hashcode和equals和方法，底层默认用==比较内存地址，就会导致new出多个对象，重写之后每次比较都会是同一个对象，会做覆盖。
HashMap根据key查询的时间复杂度
如果key没有产生冲突，时间复杂度为O(1)，一次就能查到
如果key产生冲突链表存放为O(n)，红黑树存放为O(logn)
HashMapKey为null存放在什么位置
第0个位置
int index = k == null ? 0 : k.hashCode() % objects.length;
HashMap底层是采用单链表还是双链表
单向链表
HashMap底层是有序存放的吗
单向链表存放无序散列，会将所有链表和红黑树都遍历，效率非常低
LinkedHashMap 和 TreeMap底层如何实现有序的
原理：将每个index中的链表实现关联，效率比HashMap要低
缓存淘汰算法底层实现原理LinkedHashMap
Redis如果缓存满的情况下如何清理？
LUR算法:清理最近少用的key
方案1：对每个key记录使用次数，然后排序再删除 效率非常低
方案2：基于LinkedHashMap有序集合实现 访问key的时候就会将key存到链表最后的位置
插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序
执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
其中参数accessOrder就是用来指定是否按访问顺序，如果为true，就是访问顺序。
为什么HashMap不使用取模运算
k.hashcode()%entrys.length取模会导致key冲突概率非常大
就会导致变为链表O(n)或者红黑树O(logn),需要降低Hash冲突概率，均匀的放在数组的每个下标的位置
求下标i=(n-1)&hash,为什么（n-1）变成了奇数
扩容默认是偶数，2的n次幂。如果是偶数&（与运算）hash，index冲突概率非常大，会使数据分布不均
所以需要变成奇数
HashMap如何降低Hash冲突
hash函数计算i=(n-1)&hash,通过奇数余hash值能够降低hash值发生冲突的概率
加载因子为什么是0.75而不是1
如果加载因子越大（1），空间利用率比较高16个位置都填满了，这样index冲突概率比较大
如果加载因子越小（0.1），达到0.1就扩容那么空间利用率越小，能存放的位置更多，这样index冲突概率越小
空间和时间上的平衡点：0.75
统计学概率：泊松分布是统计学和概率学常见的离散概率分布
Hashap存放1W条数据怎么样效率最高
hashmap容量=（需要存储的元素个数/扩容因子）+1=（10000/0.75）+1=13334
目的是减少底层扩容的次数，如果没有设置初始容量大小，hashmap需要进行7次扩容，严重影响性能
Hashmap1.7和Hashmap1.8的区别
Hashmap1.7基于数组+链表实现头插法，写法简单 但是有多线程死循环问题
Hashmap1.8基于数组+链表+红黑树实现尾插法，解决了多线程死循环问题
能够降低key对应的index的冲突概率，提高查询率
原来的链表使用与运算hash&原来table长度，拆分成两个链表放到新数组中，能够将链表长度缩短，提高查询效率
