什么是hash？
把任意长度的输入通过一个hash算法之后，映射成固定长度的输出。在这个过程中会产生一种情况，就是两个不同的值通过hash算法计算出的结果是相同的，这个就是造成了哈希冲突。hash冲突理论上是无法避免的，只能说尽量取避免它。比如说通过该hash算法计算出来的值区间为[m , n] 。 但是现在有（n- m）* 2 个值要用该hash算法计算，那总会造成冲突。
以String类来打个比方，String重写了Object类的hashCode() , 该方法返回的是一个int类型的值，也就是说他最多能表示一个整形范围的hash值。 但是不同的字符串远远不止这个范围。所以这种hash冲突是无法避免的。
hash值是不能通过计算的方式反推出原值的。一个好的hash算法要尽可能降低hash冲突。
首先Jdk1.8的HashMap底层数据结构： 数组 + 链表 + 红黑树。（每一个数据单元都是一个Node对象）
Node类中的成员与构造方法如下
static class Node<K,V> implements Map.Entry<K,V> {final int hash; //key的hashCode再经过计算之后的值（使哈希值更加散列）final K key; //保存key值V value; //保存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;}
}
HashMap中的一些默认常量：
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {private static final long serialVersionUID = 362498820763181265L;//默认table大小 --> 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //table的最大长度static final int MAXIMUM_CAPACITY = 1 << 30;//默认的负载因子大小0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认链表升级为红黑树的阈值 == 8（注意：这只是树化的条件之一）static final int TREEIFY_THRESHOLD = 8;//树降级为链表的阈值static final int UNTREEIFY_THRESHOLD = 6;//树化的另一个参数---当哈希表中所有元素个数超过64时才被允许树化static final int MIN_TREEIFY_CAPACITY = 64;
}
HashMap中的属性成员：
transient Node<K,V>[] table; //散列表transient Set<Map.Entry<K,V>> entrySet;transient int size; //记录当前哈希表的元素个数transient int modCount; //记录元素结构性修改次数int threshold; //扩容阈值（当哈希表中的元素超过阈值时触发扩容）final float loadFactor; //负载因子用于计算扩容阈值 threshold = capacity * loadFactor
HashMap的构造方法（列举其中三个）
//指定初始容量和负载因子
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;//获取初始的扩容阈值：手动指定initialCapacity为16及其以下得到值为16，传32及其以下得到32this.threshold = tableSizeFor(initialCapacity);
}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; //设置默认的负载因子0.75
}
双参构造方法需要指定初始容量与负载因子。当所指定的初识容量小于0时抛异常。且容量最大不能超过HashMap中规定的最大限度。负载因子不能为负数或者非法的值，因为负载因子要用于计算扩容阈值。接着得到初始的扩容阈值，利用tableSizeFor(int)方法。该方法的定义如下：
static final int tableSizeFor(int cap) {int n = cap - 1; n |= n >>> 1; n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
对该方法进行变量跟踪：
若cap == 10 则n 为9 (0000 1001)
n |= n >>> 1：0000 1001 | 0000 0100(4) ==>0000 1101(13)
n |= n >>> 2：0000 1101 | 0000 0011(3) ==>0000 1111(15)
n |= n >>> 4：0000 1111 | 0000 0000(0) ==>0000 1111(15)
n |= n >>> 8和n |= n >>> 16 的结果还是15
返回n最终结果为负数时取1，大于 MAXIMUM_CAPACITY时 取 MAXIMUM_CAPACITY 否则取16若cap == 16 则n为15 (0000 1111)
0000 1111 | 0000 0111 == 0000 1111（15） 最终返回n为16当没有int n = cap - 1;时n == 16(0001 0000)
0001 0000 | 0000 1000 ==> 0001 1000(24)
0001 1000 | 0000 0110 ==> 0001 1110(30)
0001 1110 | 0000 0001 ==> 0001 1111(31)
0001 1111 | 0000 0000 ==> 31 (返回32) 想要的结果16---得到的结果32综上发现规律：16及其以下： 最终得到补码：0000 1111(15) 2的4次方减一 16以上32及其以下： 最终得到补码0001 1111(31) 2的5次方减一 2的6次方减一 ...... 所以最终得到的初始扩容阈值总为2的次方数
特别的：指定初始容量为0时，得到的初始阈值为0
单参和无参构造方法是用的负载因子都是默认值。而且通过构造方法可以看出，在实例化对象时并没有为真正的散列表table开辟内存空间。
put方法的定义：
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
当我们调用put方法是其底层是调用了核心方法：putVal 而且在调用该方法时执行了一次hash(key)
hash方法定义如下：
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到在该方法中并没有直接使用对象的hashCode值，它是对该对象的hashCode值还进行了一次异或运算。这样可以使得hash值更加的散列。具体分析如下：
^运算符：相异为1，相同为0
>>>运算符：无符号右移 高位直接补0首先不同的key对象，如果hashCode相同，则(h = key.hashCode()) ^ (h >>> 16) 相同 ---> 哈希冲突h >>> 16 一定是 0000 0000 0000 0000 xxxx xxxx xxxx xxxx 对象A的hashCode ： 00010100 10110000 00001111 00000001
对象B的hashCode ： 01000100 01101001 00000111 00000001
如果没有此处的hash()方法， 直接使用对象的hashCode值，那么计算出的散列表中的桶位为：（桶位也就是table数组的下标位置，只不过采用数组加链表的方式，该下标位置的节点可能会形成一条链，就好像桶一样将各个节点装起来了一样，所以好多人给他起了个名字，叫桶位或者槽位。 计算公式tab[i = (n - 1) & hash]，这个公式也叫寻址算法）假如现在散列表容量为16 ==> 16 - 1 == 15(0000 1111)
对象A在散列表中的位置： table[1]
对象B在散列表中的位置： table[1]如果加上此处的hash()
对象A ： h >>> 16 ==> 00010100 10110000 那么异或运算后的值为：00010100 10110000 00011011 10110001
对象B： h >>> 16 ==> 01000100 01101001 那么异或运算后的值为：01000100 01101001 01000011 01101000对象A在散列表中的位置：table[1]
对象B在散列表中的位置：table[8]这种方案得到的hash值更加散列
得到hash值之后将其传入putVal方法中。
putVal：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; //散列表Node<K,V> p; //当前定位元素int n, i; //n(散列表的长度) i(寻址的结果)//若当前散列表为null(构造方法并没有初始化散列表)执行resize()，触发第一次扩容(懒汉式) if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; //此处是触发第一次扩容//如果该桶位没有任何元素（p在此处被赋值）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 = p;//如果是树结构else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//如果是链表结构else {//这里循环遍历链表for (int binCount = 0; ; ++binCount) {/*** 将当前节点的下一个节点引用保存在e中进行判断是否为null（也就是判断当前链表是不是遍历完了）* 此处是已经遍历完链表的情况。如果已经遍历完了没有重复的元素，那就创造一个Node对象保存数据。并且添加到末尾*/if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); /*** TREEIFY_THRESHOLD的值为8。binCount从0开始， 0 -- 7，也就是循环到第8次才进如到下面if中。* 到第8次的时候先进入上面if创造一个新的节点，在进入当前if中去。* 强烈注意：此处执行treeifyBin并不是说直接就升级为树。*/if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; //新数据保存完毕，跳出循环}//下面条件如果成立，那就是我们所说的“键重复”了if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))break;p = e; }}/***当创造出新节点时 p.next = newNode(hash, key, value, null); 并没有让e指向新节点。故e可能为null* 如果e != null 那就是“键重复”了，此处是将之前该节点的值（V）替换为新值。*/if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue; //结束put方法返回put进的新值}}/*** 能执行到这说明 e == null 也即put进了一个新的元素，散列表结构被改变了。* 键重复替换那不算 “结构性” 改变，只是某个“节点的值”改变了，所以结构性改变就是这个意思。* 该成员配合迭代器来检测并发修改异常。*/++modCount; //++size(先让散列表中元素的计数加1)再判断是否需要扩容了if (++size > threshold)resize();afterNodeInsertion(evict); //该方法是一个空方法，其主要目的是为了让子类重写该方法return null;
}
扩容方法resize()
首先扩容的是散列表(table数组)的长度。
为什么需要扩容：假如不扩容的情况下是否就不能完成任务，当然可以完成存取任务。因为散列表它本生是数组+链表+红黑树的方式实现，这一点就已经克服了数组的固定长度的短板。链表和树都是可以直接添加节点的。假如说现在没有扩容方法，那么在数据量非常庞大的情况下，可能会造成哈希冲突比较严重，也就是说它形成的树（JDK1.7的时候还没有引入红黑树，只是数组 + 链表的形式）或者链会很长。假如假如假如现在一个链现在有10000个节点，但是你要查找的元素恰好是最后一个节点，注意此处是单向链表。所以你只能从头开始往后一个一个找，这就会造成效率低下。如果能将一个长的链拆分成多个子链，或者说将一个很庞大的树拆分成多颗子树。那么查询效率就会好很多。所以扩容就是为了解决查询效率问题。当然扩容会增加内存占用量。所以这是一个空间换时间的思想。总的来说它是为了解决哈希冲突导致的链化影响查询效率的问题，扩容会缓解该问题。
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; //保存原table数组的引用int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap表示原容量，当第一次扩容时oldTab == nullint oldThr = threshold; //触发本次扩容的阈值int newCap, newThr = 0; //表示扩容之后的新容量 和 新的扩容阈值//原容量大于0，只有第一次扩容时原容量为0，这里就是为了区别是否为第一次扩容 if (oldCap > 0) {//容量都达到最大限度了那就别扩了if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//先将新容量指定为为原容量的2倍再进行检测，看是否超过最大限度 而且还需要旧容量 >= 默认初始容量才执行else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // 阈值变为原阈值的双倍}/*** oldCap == 0 且 oldThr > 0。* 就当前列举的三种构造方法而言：（首先需要oldCap == 0，即第一次扩容时才执行）* 双参构造方法手动指定阈值是会出现这种情况的（oldThr > 0）。 * 单参构造方法也会 默认传入初始阈值为16 * 无参则不会（第一次触发扩容时oldCap和oldThr都为0）*/else if (oldThr > 0) newCap = oldThr;//oldCap == 0 && oldThr == 0 无参构造触发第一次扩容时走这条路else { newCap = DEFAULT_INITIAL_CAPACITY; //16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // (int)(0.75f * 16) == 12}/*** newThr == 0的情况（即newThr这个局部变量并没有被重新赋值）：* oldCap > 0时 oldCap >= DEFAULT_INITIAL_CAPACITY不成立，也即手动指定的容量为16以下。* oldCap == 0 且 oldThr > 0时 （第一次扩容时 双参和单参构造方法都可能造成这种情况）*/if (newThr == 0) {float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);}//更新新的阈值threshold = newThr;/*------------------------------上面一大堆都是在计算newCap和newThr----------------------------------------------------------*/ @SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建一个新容量大小的散列表table = newTab;//第一次扩容时不进入下面一堆。直接返回table。 if (oldTab != null) {for (int j = 0; j < oldCap; ++j) { //遍历原散列表Node<K,V> e;if ((e = oldTab[j]) != null) { //将原桶位处头元素的引用临时保存在e中 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 { //不是树也不是单个节点 -----> 链表的情况Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next; //先获取当前节点的下一个节点/*** 下面是将一条链拆分为两个子链的过程,若现在是从16扩容到32* 假设现在遍历到下标为3的位置，之前存的时候是这样计算的：（e.hash & (cap - 1)）== 3* 也就是e.hash & 0000 1111 == 3* 那么之前在这条链上的元素的hash值就可能为 0010 0011 或者 0011 0011* * e.hash & oldCap：（注意此时j == 3）* 对于hash值为0010 0011 的元素： 0010 0011 & 0001 0000 == 0000 0000 判断成立 将其保存至低位链中。* 最后 loTail != null成立： 那么newTab[j](j == 3) ---> 这个元素在新数组中的位置还是下标为3* * 对于hash值为 0011 0011的元素： 0011 0011 & 0001 0000 == 0001 0000 == 16。进入else将其保存至高位链中。* 最后hiTail != null成立： 那么 newTab[j + oldCap] = hiHead; --->这个元素在新数组中的位置为 3 + 16 == 19。下标为19* * 若不扩容则是将一个hash值(二进制)的低4位拿出来做索引。* 扩容了他就相当于再拿出来一个位来用，用低5位。（利用一条链中那一个位的差别来重新分派桶位(如果均匀的话就是平分了链)）* 所以在查询的时候效率会大大提升。* 就这样将原数组中的一个链中的各个节点拆分重组成两条子链*/if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = 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;
}
在整个put的过程中还有一个方法treeifyBin
treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;/*** MIN_TREEIFY_CAPACITY == 64* 若表为null 或者 表长度 < 64* 从这里可以看出树化的两个条件：假如此时某一个桶位处的链表长度已经为8，但是此时散列表长度为16。它还是不会进行树化。只是会扩容一次* n在此处被赋值为表长度*/if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();// 链表长度为8，而且容量大于64的情况。找到该桶位处的索引。 此处将此索引赋值给index变量else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;//这个过程是将链表节点转化为树节点，然后重组成一条由树节点组成的双向链表。TreeNode间接继承与Node。所以它也有前驱和后继do {/*** 实例化一个TreeNode对象。一个二叉树节点，最基本要有三个引用父节点、左孩子、右孩子。 * 注意此时构造的树节点 其父节点 左孩子 右孩子 指向都为null*/TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null); //遍历整条连if ((tab[index] = hd) != null)hd.treeify(tab); //这才是真正地将链表结构转换为红黑树结构的方法}
}
一个红黑树节点的数据结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; //父节点TreeNode<K,V> left; //左孩子 TreeNode<K,V> right; //右孩子TreeNode<K,V> prev; // 删除后需要取消链接boolean red; //节点颜色//实例化TreeNode对象 注意此时red为false(黑) 而且parent left right prev都为nullTreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}
}
将链表结构转变为红黑树结构的方法
final void treeify(Node<K,V>[] tab) {TreeNode<K,V> root = null;//变量x在此处声明和赋值，这个循环是遍历链表。x表示当前索引处的元素 next表示下一个节点 for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next;x.left = x.right = null;//第一次循环只执行if中的语句，再次过程中树根被初次确定if (root == null) {x.parent = null; //树根没有父节点x.red = false; //树根默认为黑色root = x; //root变量在此处被赋值 }else {K k = x.key; //该节点的key值int h = x.hash; //该节点的key的hash值Class<?> kc = null; //首先让p == root，这个循环目的是将链表一步一步转换调整成红黑树for (TreeNode<K,V> p = root;;) { int dir, ph; //dir用来标记当前节点应该成为树的左孩子还是右孩子。 ph用来保存树节点的hash值K pk = p.key;if ((ph = p.hash) > h) dir = -1;else if (ph < h)dir = 1;//如果两个节点的key的hash值相等，下面判断条件是只是另一种比较方式else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0)dir = tieBreakOrder(k, pk);TreeNode<K,V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; //分情况处理 分配左孩子和右孩子 (如果父节点的hash值大于当前节点的hash的情况下是左孩子)if (dir <= 0) xp.left = x;else p.right = x;//传进root与x(当前节点)root = balanceInsertion(root, x); //旋转方法break; //注意 这里会跳出内层循环}}}}//旋转调整完之后树根可能发生改变，该方法让散列表中的头元素保存的永远是root树根moveRootToFront(tab, root);
}
balanceInsertion方法
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {x.red = true; //当前节点先设置为红色/*** xp == 当前节点的父节点* xpp ==......爷爷节点* xppl == 爷爷的左孩子* xppr == 爷爷的右孩子*/for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {//如果当前节点的父节点为 null 说明为树根if ((xp = x.parent) == null) { x.red = false; //树根染为黑色 return x;}//如果父节点是黑色 或者 不存在爷爷节点else if (!xp.red || (xpp = xp.parent) == null)return root;//如果存在父节点，而且父节点是爷爷节点的左孩子if (xp == (xppl = xpp.left)) {//如果爷爷节点的右孩子存在（也就是当前节点存在叔叔节点） 而且是红色 if ((xppr = xpp.right) != null && xppr.red) {xppr.red = false;xp.red = false;xpp.red = true;x = xpp;}//如果不存在叔叔节点 或者 叔叔节点为黑色else {//当前节点是父节点的右孩子的情况if (x == xp.right) {root = rotateLeft(root, x = xp); //以父节点为支点左旋（传入根节点和 ）父节点xpp = (xp = x.parent) == null ? null : xp.parent;}if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateRight(root, xpp); }}}}//如果父节点是爷爷节点的右孩子 或者 父节点是爷爷节点的右孩子但是为黑色else {//如果爷爷节点的左不为null 而且 是红色if (xppl != null && xppl.red) {xppl.red = false;xp.red = false;xpp.red = true;x = xpp;}else {//如果当前节点是父节点的左孩子if (x == xp.left) {root = rotateRight(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}//如果父节点不为nullif (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateLeft(root, xpp); //以xpp为支点左旋}}}}}
}
get方法：
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get方法底层也是调用的核心方法getNode
getNode方法：
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; //散列表Node<K,V> first, e; //first 桶位中的头元素 int n; K k;//如果当前散列表不为空 && 散列表长度大于0 && 该桶位处有值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;//判断是否含有下一个节点（即是否为一个链）if ((e = first.next) != null) {//树的情况(first为树根)if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//链的情况(循环遍历链)do {//找到了则直接返回if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}
如果是树的情况则执行getTreeNode方法遍历树：
final TreeNode<K,V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null); //先找到树根后调用find方法查找目标
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {TreeNode<K,V> p = this; //p表示当前定位的元素do {int ph, dir; K pk;TreeNode<K,V> pl = p.left, pr = p.right, q;if ((ph = p.hash) > h)p = pl; //如果当前定位元素的hash值 大于 目标元素的hash值 则只找定位元素的左子树 else if (ph < h)p = pr; //右子树//此处判断的前提是hash值相等else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p;/*--------------------------------------------------下面情况是hash值相同 key不相同--------------------------*/ else if (pl == null) //左子树为null 则让其往右子树方向p = pr;else if (pr == null) //右子树为null 则让其往左子树方向p = pl;//左右子树都不为null 而且 key不相同 按compare区分接下来应该往左还是往右找else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;else if ((q = pr.find(h, k, kc)) != null)return q;elsep = pl;} while (p != null);return null; //没找到则返回null
}