国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

 1      /** 2      * Implements Map.put and related methods 3      * 實(shí)現(xiàn)Map的put和相關(guān)操作 4      * @param hash hash for key  計(jì)算出來(lái)的key的hash值 5      * @param key the key    鍵 6      * @param value the value to put  值 7      * @param onlyIfAbsent if true, don't change existing value 為true則不覆蓋已存在值 8      * @param evict if false, the table is in creation mode. 9      * @return previous value, or null if none10      */11     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,12                    boolean evict) {13         //tab數(shù)組節(jié)點(diǎn)    p當(dāng)前需要插入的節(jié)點(diǎn)                        14         Node<K,V>[] tab; Node<K,V> p; int n, i;15         //如果當(dāng)前map中無(wú)數(shù)據(jù)，執(zhí)行resize方法。并且返回n16         if ((tab = table) == null || (n = tab.length) == 0)17             n = (tab = resize()).length;18         //如果要插入的鍵值對(duì)在tab上剛好沒(méi)有元素，那么把他封裝成Node對(duì)象，放在這個(gè)位置上結(jié)束。19         if ((p = tab[i = (n - 1) & hash]) == null)20             tab[i] = newNode(hash, key, value, null);21         //有元素，在table的i位置發(fā)生碰撞22         else {23             Node<K,V> e; K k;24             //1.hash值一樣，key一樣，替換25             if (p.hash == hash &&26                 ((k = p.key) == key || (key != null && key.equals(k))))27                 e = p;28             //2.如果當(dāng)前節(jié)點(diǎn)是TreeNode類型的數(shù)據(jù)，插入紅黑樹(shù)29             else if (p instanceof TreeNode)30                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);31             //3.不是TreeNode，遍歷這條鏈子上的節(jié)點(diǎn)，跟jdk7一樣32             else {33                 for (int binCount = 0; ; ++binCount) {34                     if ((e = p.next) == null) {35                         p.next = newNode(hash, key, value, null);36                         //如果大于等于7，即準(zhǔn)備插入第8個(gè)，將鏈表轉(zhuǎn)換成紅黑樹(shù)（有條件，具體看下圖）。37                         if (binCount >= TREEIFY_THRESHOLD - 1) 38                             treeifyBin(tab, hash);39                         break;40                     }41                     if (e.hash == hash &&42                         ((k = e.key) == key || (key != null && key.equals(k))))43                         break;44                     p = e;45                 }46             }47             if (e != null) { // existing mapping for key48                 V oldValue = e.value;49                 if (!onlyIfAbsent || oldValue == null)50                     e.value = value;51                 afterNodeAccess(e);52                 return oldValue;53             }54         }55         ++modCount;56         //判斷閾值，決定是否擴(kuò)容57         if (++size > threshold)58             resize();59         afterNodeInsertion(evict);60         return null;61     }

 1     final void treeifyBin(Node<K,V>[] tab, int hash) { 2         int n, index; Node<K,V> e; 3         //當(dāng)tab為null或tab.length<64需要進(jìn)行擴(kuò)容 4         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 5             resize(); 6         else if ((e = tab[index = (n - 1) & hash]) != null) { 7             TreeNode<K,V> hd = null, tl = null; 8             do { 9                 TreeNode<K,V> p = replacementTreeNode(e, null);10                 if (tl == null)11                     hd = p;12                 else {13                     p.prev = tl;14                     tl.next = p;15                 }16                 tl = p;17             } while ((e = e.next) != null);18             if ((tab[index] = hd) != null)19                 //存儲(chǔ)在紅黑樹(shù)20                 hd.treeify(tab);21         }22     }

 1     /** 2      * The bin count threshold for using a tree rather than list for a 3      * bin.  Bins are converted to trees when adding an element to a 4      * bin with at least this many nodes. The value must be greater 5      * than 2 and should be at least 8 to mesh with assumptions in 6      * tree removal about conversion back to plain bins upon 7      * shrinkage. 8      */ 9     static final int TREEIFY_THRESHOLD = 8;10 11     /**12      * The smallest table capacity for which bins may be treeified.13      * (Otherwise the table is resized if too many nodes in a bin.)14      * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts15      * between resizing and treeification thresholds.16      */17     static final int MIN_TREEIFY_CAPACITY = 64;

 1     public V get(Object key) { 2         Node<K,V> e; 3         return (e = getNode(hash(key), key)) == null ? null : e.value; 4     } 5  6     /** 7      * Implements Map.get and related methods 8      * 9      * @param hash hash for key10      * @param key the key11      * @return the node, or null if none12      */13     final Node<K,V> getNode(int hash, Object key) {14         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;15         if ((tab = table) != null && (n = tab.length) > 0 &&16             (first = tab[(n - 1) & hash]) != null) {17             if (first.hash == hash && // always check first node18                 ((k = first.key) == key || (key != null && key.equals(k))))19                 return first;20             if ((e = first.next) != null) {21                 if (first instanceof TreeNode)22                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);23                 do {24                     if (e.hash == hash &&25                         ((k = e.key) == key || (key != null && key.equals(k))))26                         return e;27                 } while ((e = e.next) != null);28             }29         }30         return null;31     }    

 1 /** 2      * Initializes or doubles table size.  If null, allocates in 3      * accord with initial capacity target held in field threshold. 4      * Otherwise, because we are using power-of-two expansion, the 5      * elements from each bin must either stay at same index, or move 6      * with a power of two offset in the new table. 7      * 8      * @return the table 9      */10     final Node<K,V>[] resize() {11         Node<K,V>[] oldTab = table;12         int oldCap = (oldTab == null) ? 0 : oldTab.length;13         int oldThr = threshold;14         int newCap, newThr = 0;15         if (oldCap > 0) {16             if (oldCap >= MAXIMUM_CAPACITY) {17                 threshold = Integer.MAX_VALUE;18                 return oldTab;19             }20             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&21                      oldCap >= DEFAULT_INITIAL_CAPACITY)22                 newThr = oldThr << 1; // double threshold23         }24         else if (oldThr > 0) // initial capacity was placed in threshold25             newCap = oldThr;26         else {               // zero initial threshold signifies using defaults27             newCap = DEFAULT_INITIAL_CAPACITY;28             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);29         }30         if (newThr == 0) {31             float ft = (float)newCap * loadFactor;32             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?33                       (int)ft : Integer.MAX_VALUE);34         }35         threshold = newThr;36         @SuppressWarnings({"rawtypes","unchecked"})37             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];38         table = newTab;39         if (oldTab != null) {40             for (int j = 0; j < oldCap; ++j) {41                 Node<K,V> e;42                 if ((e = oldTab[j]) != null) {43                     oldTab[j] = null;44                     if (e.next == null)45                         newTab[e.hash & (newCap - 1)] = e;46                     else if (e instanceof TreeNode)47                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);48                     else { // preserve order49                         Node<K,V> loHead = null, loTail = null;50                         Node<K,V> hiHead = null, hiTail = null;51                         Node<K,V> next;52                         do {53                             next = e.next;54                             if ((e.hash & oldCap) == 0) {55                                 if (loTail == null)56                                     loHead = e;57                                 else58                                     loTail.next = e;59                                 loTail = e;60                             }61                             else {62                                 if (hiTail == null)63                                     hiHead = e;64                                 else65                                     hiTail.next = e;66                                 hiTail = e;67                             }68                         } while ((e = next) != null);69                         if (loTail != null) {70                             loTail.next = null;71                             newTab[j] = loHead;72                         }73                         if (hiTail != null) {74                             hiTail.next = null;75                             //把節(jié)點(diǎn)移動(dòng)新的位置j+oldCap,這種情況不適用與鏈表的節(jié)點(diǎn)數(shù)大于8的情況76                             //鏈表節(jié)點(diǎn)大于8的情況會(huì)轉(zhuǎn)換為紅黑樹(shù)存儲(chǔ)77                             newTab[j + oldCap] = hiHead;78                         }79                     }80                 }81             }82         }83         return newTab;84     }

 1 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, 2                                                     TreeNode<K,V> x) { 3             //插入的節(jié)點(diǎn)必須是紅色的，除非是根節(jié)點(diǎn)                                             4             x.red = true; 5             //遍歷到x節(jié)點(diǎn)為黑色,整個(gè)過(guò)程是一個(gè)上濾的過(guò)程 6             //xp=x.parent;xpp=xp.parent;xppl=xpp.left;xppr=xpp.right; 7             for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 8                 if ((xp = x.parent) == null) { 9                     x.red = false;10                     return x;11                 }12                 //如果xp的黑色就直接完成，最簡(jiǎn)單的情況13                 else if (!xp.red || (xpp = xp.parent) == null)14                     return root;15                 //如果x的父節(jié)點(diǎn)是x父節(jié)點(diǎn)的左節(jié)點(diǎn)16                 if (xp == (xppl = xpp.left)) {17                     //x的父親節(jié)點(diǎn)的兄弟是紅色的（需要顏色翻轉(zhuǎn)）18                     if ((xppr = xpp.right) != null && xppr.red) {19                         //x父親節(jié)點(diǎn)的兄弟節(jié)點(diǎn)置成黑色20                         xppr.red = false;21                         //父幾點(diǎn)和其兄弟節(jié)點(diǎn)一樣是黑色22                         xp.red = false;23                         //祖父節(jié)點(diǎn)置成紅色24                         xpp.red = true;25                         //然后上濾（就是不斷的重復(fù)上面的操作）26                         x = xpp;27                     }28                     else {29                         //如果x是xp的右節(jié)點(diǎn)整個(gè)要進(jìn)行兩次旋轉(zhuǎn),先左旋轉(zhuǎn)再右旋轉(zhuǎn)30                         if (x == xp.right) {31                             root = rotateLeft(root, x = xp);32                             xpp = (xp = x.parent) == null ? null : xp.parent;33                         }34                         if (xp != null) {35                             xp.red = false;36                             if (xpp != null) {37                                 xpp.red = true;38                                 root = rotateRight(root, xpp);39                             }40                         }41                     }42                 }43                 //以左節(jié)點(diǎn)鏡像對(duì)稱就不做具體分析了 44                 else {45                     if (xppl != null && xppl.red) {46                         xppl.red = false;47                         xp.red = false;48                         xpp.red = true;49                         x = xpp;50                     }51                     else {52                         if (x == xp.left) {53                             root = rotateRight(root, x = xp);54                             xpp = (xp = x.parent) == null ? null : xp.parent;55                         }56                         if (xp != null) {57                             xp.red = false;58                             if (xpp != null) {59                                 xpp.red = true;60                                 root = rotateLeft(root, xpp);61                             }62                         }63                     }64                 }65             }66         }

============================