public E remove(int index){ // 保证index合法 rangeCheck(index);
modCount++; // 返回旧值 E oldValue = elementData(index);
int numMoved = size - index - 1; if (numMoved > 0) // 将index后面元素前移一个单元 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 最后一个空间置空 elementData[--size] = null; // clear to let GC do its work
return oldValue; }
// 遍历，调用fastRemove方法 publicbooleanremove(Object o){ if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); returntrue; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); returntrue; } } returnfalse; }
// 相比remove空参方法，省去了index检查，返回值， privatevoidfastRemove(int index){ modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }
// 这种处理方法我们见过很多次了，针对o是否为空，分别处理 publicintindexOf(Object o){ if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } // 参考indexOf，区别在于遍历是倒序的，适用于知道o是在后面的位置 publicintlastIndexOf(Object o){ if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
public <T> T[] toArray(T[] a) { // a的空间不够，新拷贝一个数组返回 if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); // a的空间足够，将elementData复制给a，返回a System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }
// 将e构成新节点，添加到succ节点前面 voidlinkBefore(E e, Node<E> succ){ // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; // 链接前面的链表 if (pred == null) // 如果前面没有节点，first指向新节点 first = newNode; else // 否则，前一个节点的next指向新节点 pred.next = newNode; size++; modCount++; }
// 将e构成新节点，添加到链表头 privatevoidlinkFirst(E e){ final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; // 链接后面的链表 if (f == null) // 如果后面为空，将last指向新节点 last = newNode; else // 否则，后面节点的prev指向新节点 f.prev = newNode; size++; modCount++; }
// 将e构成新节点，添加到链表末尾 voidlinkLast(E e){ final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; // 链接前面的链表 if (l == null) // 如果前面没有节点，first指向新节点 first = newNode; else // 否则，前一个节点的next指向新节点 l.next = newNode; size++; modCount++; }
// x节点脱离链表（删除x节点，返回x节点的元素值） E unlink(Node<E> x){ // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; // 修改前一个节点的指向 if (prev == null) { // 如果x是第一个节点 first = next; } else { prev.next = next; x.prev = null; } // 修改后一个节点的指向 if (next == null) { // 如果x是最后一个节点 last = prev; } else { next.prev = prev; x.next = null; } // 置空，方便GC x.item = null; size--; modCount++; return element; }
// 头节点脱离链表（删除头节点，返回头节点的元素值） private E unlinkFirst(Node<E> f){ // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC // 修改first指向 first = next; // 修改下一个节点指向 if (next == null) // 如果下一个节点为空 last = null; else next.prev = null; size--; modCount++; return element; }
// 尾节点脱离链表（删除尾节点，返回头尾节点的元素值） private E unlinkLast(Node<E> l){ // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC // 修改last指向 last = prev; // 修改上一个节点指向 if (prev == null) // 如果上一个节点为空 first = null; else prev.next = null; size--; modCount++; return elemen; }
// 查找第index个元素 Node<E> node(int index){ // assert isElementIndex(index); // 如果index在前一半，从前往后找，在后一半，从后往前找。 // 使用位运算，提高效率 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
// 判断index合法性，查找、修改使用，不能等于size privatebooleanisElementIndex(int index){ return index >= 0 && index < size; }
// 判断index合法性，添加使用，可以等于size privatebooleanisPositionIndex(int index){ return index >= 0 && index <= size; }
publicbooleanaddAll(int index, Collection<? extends E> c){ // 判断index合法性 checkPositionIndex(index); // 转化为数组，返回副本，防止外部对c进行更改，从而影响链表 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) returnfalse;
// pred是插入位置的前一个节点，succ是插入位置节点 Node<E> pred, succ; if (index == size) { // 插入到最后 succ = null; pred = last; } else { // 插入到index位置 succ = node(index); pred = succ.prev; } for (Object o : a) { // 遍历要插入的元素，将每一个都添加到链表中 @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } // 执行完后pred指向添加的最后一个元素 // 将后面链表接上 if (succ == null) { // 插入到最后，对应index == size情况，直接修改last指向 last = pred; } else { // 将后面的链表接上 pred.next = succ; succ.prev = pred; }
size += numNew; modCount++; returntrue; }
6.6.2 删除方法
// 清空所有元素 publicvoidclear(){ // 清除所有链接，方便GC（引用都指向null） for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
// 删除第index个节点 public E remove(int index){ checkElementIndex(index); //node(index)这是返回第index个节点 return unlink(node(index)); }
// 删除第一个出现的o对象，没有找到返回false publicbooleanremove(Object o){ if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); returntrue; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); returntrue; } } } returnfalse; }
6.6.3 修改方法
public E set(int index, E element){ checkElementIndex(index); // 首先找到目标节点 Node<E> x = node(index); E oldVal = x.item; // 修改值 x.item = element; return oldVal; }
// 获取第index节点的元素值 public E get(int index){ checkElementIndex(index); return node(index).item; }
// 从头开始找，元素值为o的索引，没找到返回-1 publicintindexOf(Object o){ int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
// 从尾开始找，元素值为o的索引，没找到返回-1 publicintlastIndexOf(Object o){ int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
// 返回数组副本 public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }
public <T> T[] toArray(T[] a) { // 判断a的大小，不满足则利用反射创建新数组 if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item;
// 如果a数组没有用完，最后一个元素置null if (a.length > size) a[size] = null;
// 出队 public E poll(){ final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } // 队头出队 public E pollFirst(){ final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } // 对尾出队 public E pollLast(){ final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }
// 出栈 public E pop(){ return removeFirst(); }
// 删除链表头节点 public E remove(){ return removeFirst(); }
public E removeFirst(){ final Node<E> f = first; if (f == null) thrownew NoSuchElementException(); return unlinkFirst(f); }
// 删除链表尾节点 public E removeLast(){ final Node<E> l = last; if (l == null) thrownew NoSuchElementException(); return unlinkLast(l); }
// 删除最后一个等于o的节点 publicbooleanremoveLastOccurrence(Object o){ if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); returntrue; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); returntrue; } } } returnfalse; }
6.7.3 查找方法
// 获取第一个元素 public E element(){ return getFirst(); }
public E getFirst(){ final Node<E> f = first; if (f == null) thrownew NoSuchElementException(); return f.item; }
// 获取最后一个元素 public E getLast(){ final Node<E> l = last; if (l == null) thrownew NoSuchElementException(); return l.item; }
// 返回但不删除第一个元素 public E peek(){ final Node<E> f = first; return (f == null) ? null : f.item; }
public E peekFirst(){ final Node<E> f = first; return (f == null) ? null : f.item; }
// 返回但不删除最后一个元素 public E peekLast(){ final Node<E> l = last; return (l == null) ? null : l.item; }
publicPriorityQueue(Comparator<? super E> comparator){ this(DEFAULT_INITIAL_CAPACITY, comparator); }
publicPriorityQueue(int initialCapacity, Comparator<? super E> comparator){ // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) thrownew IllegalArgumentException(); // 初始化数组 this.queue = new Object[initialCapacity]; // 设置comparator this.comparator = comparator; }
// 在整个树中建立堆不变式(如上所述)，不考虑调用之前元素的顺序。 privatevoidheapify(){ // 从第一个父元素开始，自下而上进行下沉 for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); }
7.3 重要方法
对于堆来说，下沉和上浮是保证堆规则的重要方法，下面我们看一下下沉和上浮的方法。
// 下沉操作，分为有比较器和没有比较器两种情况 // 将x插入到k的位置，通过反复将x降到树的下层，直到它小于或等于它的子元素，或者是叶子，从而保持堆不变。 privatevoidsiftDown(int k, E x){ if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); }
// 有比较器 privatevoidsiftDownUsingComparator(int k, E x){ int half = size >>> 1; while (k < half) { // 左孩子下标 int child = (k << 1) + 1; Object c = queue[child]; // 右孩子下标 int right = child + 1; if (right < size && // compare方法注释有着这样的描述： // 比较它的两个order参数。当第一个参数小于、等于或大于第二个参数时，返回一个负整数、零或正整数。 // 下面代码>0表示左孩子大于右孩子 comparator.compare((E) c, (E) queue[right]) > 0) // 将右孩子下标以及右孩子保存到child和c中 c = queue[child = right]; // 执行到这里，c保存的是k的左右孩子中元素值较小的那个，child保存的是他的下标 // 再和x进行比较，如果x更小，则跳出循环，否则说明还有下沉的可能，继续循环 if (comparator.compare(x, (E) c) <= 0) break; // 进行下沉操作 // 将较小的值放到k的位置 queue[k] = c; // 更新k到下一层 k = child; } // 执行到这里，k是当前坐标，并且当前元素的左右孩子都比x大 // 将x插入到k位置 queue[k] = x; }
// 没有比较器 privatevoidsiftDownComparable(int k, E x){ Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = queue[child]; int right = child + 1; if (right < size && // compareTo方法注释有着这样的描述：将此对象与指定的order对象进行比较。 // 返回一个负整数、零或正整数，因为该对象小于、等于或大于指定的对象。 // 和上面的方法基本相同，只是比较方法使用的是元素的compareTo方法 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key; }
// 查询优先队列中是否含有o元素 publicbooleancontains(Object o){ return indexOf(o) != -1; } // 移除o元素 publicbooleanremove(Object o){ int i = indexOf(o); if (i == -1) returnfalse; else { removeAt(i); returntrue; } }
public Object[] toArray() { return Arrays.copyOf(queue, size); }
public <T> T[] toArray(T[] a) { finalint size = this.size; if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(queue, size, a.getClass()); System.arraycopy(queue, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } // 返回size publicintsize(){ return size; }
7.6 队列方法
// 添加元素 publicbooleanadd(E e){ return offer(e); }
// 清空所有元素 publicvoidclear(){ modCount++; for (int i = 0; i < size; i++) queue[i] = null; size = 0; }
// 入队 publicbooleanoffer(E e){ if (e == null) thrownew NullPointerException(); modCount++; // 扩容 int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) // 堆为空 queue[0] = e; else // 从最后一个位置向上浮 siftUp(i, e); returntrue; }
// 查看队头元素 public E peek(){ return (size == 0) ? null : (E) queue[0]; }
// 出队 public E poll(){ if (size == 0) returnnull; int s = --size; modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; // 将最后一个元素从顶向下沉 if (s != 0) siftDown(0, x); return result; }
publicbooleancontainsValue(Object value){ // 获取迭代器 Iterator<Entry<K,V>> i = entrySet().iterator(); if (value==null) { // 查找null的情况 while (i.hasNext()) { Entry<K,V> e = i.next(); if (e.getValue()==null) returntrue; } } else { // 查找value非空的情况 while (i.hasNext()) { Entry<K,V> e = i.next(); if (value.equals(e.getValue())) returntrue; } } returnfalse; }
// 和上面的方法类似 publicbooleancontainsKey(Object key){ Iterator<Map.Entry<K,V>> i = entrySet().iterator(); if (key==null) { while (i.hasNext()) { Entry<K,V> e = i.next(); if (e.getKey()==null) returntrue; } } else { while (i.hasNext()) { Entry<K,V> e = i.next(); if (key.equals(e.getKey())) returntrue; } } returnfalse; }
// 同样通过迭代器查找 public V get(Object key){ Iterator<Entry<K,V>> i = entrySet().iterator(); if (key==null) { while (i.hasNext()) { Entry<K,V> e = i.next(); if (e.getKey()==null) return e.getValue(); } } else { while (i.hasNext()) { Entry<K,V> e = i.next(); if (key.equals(e.getKey())) return e.getValue(); } } returnnull; }
// Modification Operations
// 不支持put方法 public V put(K key, V value){ thrownew UnsupportedOperationException(); }
public V remove(Object key){ // 首先通过迭代器找目标entry，找到或遍历结束退出循环 Iterator<Entry<K,V>> i = entrySet().iterator(); Entry<K,V> correctEntry = null; if (key==null) { while (correctEntry==null && i.hasNext()) { Entry<K,V> e = i.next(); if (e.getKey()==null) correctEntry = e; } } else { while (correctEntry==null && i.hasNext()) { Entry<K,V> e = i.next(); if (key.equals(e.getKey())) correctEntry = e; } } // 如果找到目标entry，调用迭代器remove方法移除 V oldValue = null; if (correctEntry !=null) { oldValue = correctEntry.getValue(); i.remove(); } // 返回删除entry的value return oldValue; }
publicbooleanequals(Object o){ if (o == this) returntrue;
if (!(o instanceof Map)) returnfalse; Map<?,?> m = (Map<?,?>) o; if (m.size() != size()) returnfalse;
try { // 使用迭代器遍历entrySet，判断对于相同的key，二者的value是否相等 Iterator<Entry<K,V>> i = entrySet().iterator(); while (i.hasNext()) { Entry<K,V> e = i.next(); K key = e.getKey(); V value = e.getValue(); if (value == null) { if (!(m.get(key)==null && m.containsKey(key))) returnfalse; } else { if (!value.equals(m.get(key))) returnfalse; } } } catch (ClassCastException unused) { returnfalse; } catch (NullPointerException unused) { returnfalse; }
returntrue; }
// 所有entry的hashCode和 publicinthashCode(){ int h = 0; Iterator<Entry<K,V>> i = entrySet().iterator(); while (i.hasNext()) h += i.next().hashCode(); return h; }
public String toString(){ Iterator<Entry<K,V>> i = entrySet().iterator(); if (! i.hasNext()) return"{}";
StringBuilder sb = new StringBuilder(); sb.append('{'); for (;;) { Entry<K,V> e = i.next(); K key = e.getKey(); V value = e.getValue(); sb.append(key == this ? "(this Map)" : key); sb.append('='); sb.append(value == this ? "(this Map)" : value); if (! i.hasNext()) return sb.append('}').toString(); sb.append(',').append(' '); } }
// hash key的哈希值 // onlyIfAbsent 如果为true，不改变现有值 // evict 如果为false，处于创建模式 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict){ Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) // 如果还没有初始化table，调用resize方法，这个方法后面再说 n = (tab = resize()).length; // 到这里，tab == table n == tab.length // (n - 1) & hash 散列（与n-1进行与运算进行取余操作，散列到位置） if ((p = tab[i = (n - 1) & hash]) == null) // 如果桶是空的，将当前键值对添加进去 tab[i] = newNode(hash, key, value, null); // 到这里，p指向当前hash桶的第一个Node else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // hash值相等，并且key相等，说明要执行更改操作，保存p节点 e = p; elseif (p instanceof TreeNode) // 如果p是TreeNode，当前为红黑树结构，调用TreeNode的putTreeVal方法 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 链表结构、遍历当前桶中的链表 for (int binCount = 0; ; ++binCount) { // 找到最后一个节点 if ((e = p.next) == null) { // 添加到链表最后 p.next = newNode(hash, key, value, null); // 如果链表长度大于TREEIFY_THRESHOLD，调用treeifyBin方法转化为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果发现hash值相等，并且key相等，说明要执行更改操作 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key // 说明要执行修改操作，e为要修改的Node V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 返回旧值 return oldValue; } } // 到这里，说明执行的是添加操作 ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); returnnull; }
finalvoidputMapEntries(Map<? extends K, ? extends V> m, boolean evict){ int s = m.size(); if (s > 0) { if (table == null) { // pre-size // 如果table还没有初始化 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } elseif (s > threshold) // 扩容table为2倍 resize(); // 遍历m，添加 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }
总结一下putVal方法：
if 还没有初始化table 调用resize方法初始化table else if 当前桶是空的 将当前键值对添加进去 else if 要执行修改操作 保存要修改的节点 else if 当前桶中已经是红黑树 执行TreeNode的putTreeVal方法 else for if 到链表末尾 将当前节点添加到链表末尾 如果链表长度超过TREEIFY_THRESHOLD，转化为红黑树 要执行修改操作 保存要修改的节点 如果保存了要修改的节点 修改操作，返回旧值，end
staticfinalinttableSizeFor(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; }
