| 注册
请输入搜索内容

热门搜索

Java Linux MySQL PHP JavaScript Hibernate jQuery Nginx
xyyujnnaruz
8年前发布

Java容器深入研究

   <h2><strong>基本功能</strong></h2>    <h2>Arrays & Collections</h2>    <h2><strong>常用的方法</strong></h2>    <pre>  <code class="language-java">//Arrays.java  public static <T> List<T> asList(T... a) {     return new ArrayList<>(a);  }</code></pre>    <p>注意这里返回的ArrayList不同于我们平时使用的ArrayList,根据该 ArrayLsit 的源码</p>    <pre>  <code class="language-java">private static class ArrayList<E> extends AbstractList<E></code></pre>    <p>知道其继承至 AbstractList ,但是没有实现它的 add() 和 delete() 方法,因此若调用会抛出 UnsupportedOperationException 的提示,这是由于该 List 的底层就是一个数组,而且不会扩容,所以不支持添加等操作,在使用的时候要特别注意。</p>    <pre>  <code class="language-java">List list = ...;  List lists1 = new ArrayList(list);  List lists2 = Collections.addAll(list);</code></pre>    <p>上面代码,相比 lists1 , lists2 更为高效。</p>    <h2><strong>集合类基本介绍</strong></h2>    <ul>     <li>List 以特定顺序保存的一组元素</li>     <li>Set 以特定顺序保存的不重复的一组元素</li>     <li>Queue 同数据结构队列</li>     <li>Map 使用KV保存两组值</li>    </ul>    <h2><strong>具体介绍</strong></h2>    <p><img src="https://simg.open-open.com/show/e3bd7e027fec2ec9068294f844f4e6f0.png"></p>    <p>集合类图</p>    <h2><strong>List</strong></h2>    <p>相比 Collection ,多 了一些方法,如 listIterator() 等.</p>    <h2><strong>ArrayList</strong></h2>    <p><img src="https://simg.open-open.com/show/1e33df41ac486660ba70e610ea3766a9.png"></p>    <p style="text-align:center">ArrayList包含函数</p>    <h2><strong>概述</strong></h2>    <p>根据类图可以知道 ArrayList 的继承结构, RandomAccess 是一个说明性接口,没有任何的方法实现. ArrayList 的底层实现任然是数组,当容量达到一定时,会新建一个数组,再把原来的数据拷贝过去,所以性能并不是太好.下面详细的看看.</p>    <h2><strong>准备</strong></h2>    <p>由于 ArrayList 的底层是由数组实现的,并且 ArrayList 是动态大小,因此修改扩容,这里用到 Arrays.copyOf(...) 方法</p>    <pre>  <code class="language-java">public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {      @SuppressWarnings("unchecked")      T[] copy = ((Object)newType == (Object)Object[].class)            ? (T[]) new Object[newLength]            : (T[]) Array.newInstance(newType.getComponentType(), newLength);      System.arraycopy(original, 0, copy, 0,                     Math.min(original.length, newLength));  //native      return copy;  }</code></pre>    <h2><strong>源码阅读</strong></h2>    <pre>  <code class="language-java">transient Object[] elementData; // 为什么是Object而不是泛型E?  private int size; //实际大小 size()函数就是返回该值</code></pre>    <p>它的三个构造函数的作用都是初始化上面两个参数的值.都是非常的简单,不多说,下面看看最常用的 add() 函数.</p>    <pre>  <code class="language-java">public boolean add(E e) {     ensureCapacityInternal(size + 1);  // 判断数组容量是否够,不够就扩容     elementData[size++] = e;     return true;  }    public void add(int index, E element) {      rangeCheckForAdd(index); //index > size || index < 0抛异常      ensureCapacityInternal(size + 1);  // Increments modCount!!      System.arraycopy(elementData, index, elementData, index + 1,                       size - index);//index后的往后移一位      elementData[index] = element;      size++;  }    public boolean addAll(Collection<? extends E> c) {      Object[] a = c.toArray();      int numNew = a.length;      ensureCapacityInternal(size + numNew);  // Increments modCount      System.arraycopy(a, 0, elementData, size, numNew);      size += numNew;      return numNew != 0;  }    public boolean addAll(int index, Collection<? extends E> c) {      rangeCheckForAdd(index);      Object[] a = c.toArray();      int numNew = a.length;      ensureCapacityInternal(size + numNew);  // Increments modCount      int numMoved = size - index;      if (numMoved > 0)         System.arraycopy(elementData, index, elementData, index + numNew,                           numMoved);      System.arraycopy(a, 0, elementData, index, numNew);      size += numNew;      return numNew != 0;  }</code></pre>    <p>本身这段代码是非常容易理解的,下面看看它扩容的实现.</p>    <pre>  <code class="language-java">private void ensureCapacityInternal(int minCapacity) {        if (elementData == EMPTY_ELEMENTDATA) { //还没有数据时            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);        }        ensureExplicitCapacity(minCapacity);  }    private void ensureExplicitCapacity(int minCapacity) {       modCount++;       // overflow-conscious code       //注意elementData.length只是表示现有的容量,不是size       if (minCapacity - elementData.length > 0)           grow(minCapacity);  }    private void grow(int minCapacity) {      // overflow-conscious code      int oldCapacity = elementData.length;      int newCapacity = oldCapacity + (oldCapacity >> 1);//增加1.5倍容量,位操作效率远远高于做除法      if (newCapacity - minCapacity < 0) //容量还没有达到申请的量          newCapacity = minCapacity;      if (newCapacity - MAX_ARRAY_SIZE > 0) //Integer.MAX_VALUE - 8          newCapacity = hugeCapacity(minCapacity);      // minCapacity is usually close to size, so this is a win:      elementData = Arrays.copyOf(elementData, newCapacity);//把原来的数据移动到新数组中      private static int hugeCapacity(int minCapacity) {      if (minCapacity < 0) // int 溢出变为负数了          throw new OutOfMemoryError();      return (minCapacity > MAX_ARRAY_SIZE) ?           Integer.MAX_VALUE :           MAX_ARRAY_SIZE;  }</code></pre>    <p>通过上面的代码,可以看到 ArrayList 的最大容量为 Integer.MAX_VALUE ,即 65535 .接下来就看看同等常用的 get() 函数.</p>    <pre>  <code class="language-java">public E get(int index) {       rangeCheck(index);  //检查index是否在[0,size)范围内,具体实现就这一个条件判断       return elementData(index); //取得元素elementData[index]  }</code></pre>    <p>根据他的名称我们很容易的了解他的功能,并且对于数组的随机存取,这个实现太简单了,就不必多说.下面看看 set() 方法.</p>    <pre>  <code class="language-java">public E set(int index, E element) {      rangeCheck(index);      E oldValue = elementData(index);      elementData[index] = element;      return oldValue;  }</code></pre>    <p>卧槽,我都不想多说什么了,就是简单的判断 index 的范围,然后就是对数组操作.函数 indexOf()/contains() 和 lastIndexOf() 都是简单的对数组的遍历过程,也跳过.下面看看 remove() 相关的方法.</p>    <pre>  <code class="language-java">public E remove(int index) {      rangeCheck(index);      modCount++;      E oldValue = elementData(index);      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      return oldValue;  }    /**   * 先遍历查找到index,在移除   */  public boolean remove(Object o) {      if (o == null) {          for (int index = 0; index < size; index++)              if (elementData[index] == null) {                  fastRemove(index);                  return true;              }      } else {          for (int index = 0; index < size; index++)              if (o.equals(elementData[index])) {                  fastRemove(index);                  return true;              }      }      return false;  }    private void fastRemove(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  }</code></pre>    <p>下面看看 retainAll() 和 removeAll() 的实现函数 batchRemove() .</p>    <pre>  <code class="language-java">private boolean batchRemove(Collection<?> c, boolean complement) {      final Object[] elementData = this.elementData;      int r = 0, w = 0;      boolean modified = false;      try {          for (; r < size; r++)             if (c.contains(elementData[r]) == complement)                  elementData[w++] = elementData[r]; //保留相等/或者不等的部分      } finally {         // Preserve behavioral compatibility with AbstractCollection,         // even if c.contains() throws.         if (r != size) {             System.arraycopy(elementData, r,                              elementData, w,                               size - r);              w += size - r;          }          if (w != size) {              // clear to let GC do its work              for (int i = w; i < size; i++)                  elementData[i] = null;              modCount += size - w;              size = w;              modified = true;          }      }       return modified;  }</code></pre>    <p>下面看看排序函数 sort()</p>    <pre>  <code class="language-java">public void sort(Comparator<? super E> c) {      final int expectedModCount = modCount;      Arrays.sort((E[]) elementData, 0, size, c);      if (modCount != expectedModCount) {          throw new ConcurrentModificationException();      }      modCount++;  }</code></pre>    <p>由上面的代码可以看出 sort() 在排序过程重中是不允许执行修改/添加等等操作的. subList() 返回一个 List ,但是这个 List 是依附在原本的 ArrayList 的,也就是说 subList() 得到的 List 其实是 ArrayList 的镜像,当 ArrayList 修改后,取得的 subList 也会显示出修改后的状态.这里可以看看它的一部分实现</p>    <pre>  <code class="language-java">//构造函数  SubList(AbstractList<E> parent,          int offset, int fromIndex, int toIndex) {     this.parent = parent;     this.parentOffset = fromIndex;     this.offset = offset + fromIndex;     this.size = toIndex - fromIndex;     this.modCount = ArrayList.this.modCount;  }    public E get(int index) {     rangeCheck(index);     checkForComodification();     //从这里可以看出,它的数据是外部类ArrayList的.     return ArrayList.this.elementData(offset + index);  }</code></pre>    <p>最后看看函数 listIterator() 和函数 iterator() ,他们分别返回一个双向迭代器和单向迭代器.本质他们的遍历过程还是数组的遍历,想要了解详情可以去看看具体的源码,这里就不介绍了.</p>    <h2>LinkedList</h2>    <p><img src="https://simg.open-open.com/show/d6f6fae0a25fae7816fb399e928ad194.png"></p>    <p style="text-align:center">LinkedList包含函数</p>    <h2><strong>概述</strong></h2>    <p>inkedList 实现了 List 、 Deque 、 Cloneable 以及 Serializable 接口。其中 Deque 是双端队列接口,所以 LinkedList 可以当作是栈、队列或者双端队队列。在使用它的时候,通常可以把它向上转型为 List , Queue 已达到缩小她的接口的功能(限制了不需要的方法).</p>    <h2><strong>源码阅读</strong></h2>    <p>由于是由链表实现,首先需要查看的就是结点了.</p>    <pre>  <code class="language-java">private static class Node<E> {          E item;          Node<E> next;          Node<E> prev;            Node(Node<E> prev, E element, Node<E> next) {              this.item = element;              this.next = next;              this.prev = prev;          }  }</code></pre>    <p>在 LinkedList 的内部,保存着 first 和 last 结点的引用,这样就方便了两端的插入删除等操作.</p>    <pre>  <code class="language-java">transient int size = 0;      transient Node<E> first;      transient Node<E> last;</code></pre>    <p>下面看看它的关键实现函数,添加结点相关函数.</p>    <pre>  <code class="language-java">//尾部添加  void linkLast(E e) {          final Node<E> l = last;          final Node<E> newNode = new Node<>(l, e, null); //注意构造函数已经绑定的前结点          last = newNode;          if (l == null)              first = newNode;          else              l.next = newNode;          size++;          modCount++;  }    //头部添加  private void linkFirst(E e) {          final Node<E> f = first;          final Node<E> newNode = new Node<>(null, e, f);          first = newNode;          if (f == null)              last = newNode;          else              f.prev = newNode;          size++;          modCount++;  }    //在某个结点前添加  void linkBefore(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 = newNode;          else              pred.next = newNode;          size++;          modCount++;  }</code></pre>    <p>删除结点相关函数.</p>    <pre>  <code class="language-java">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) {              first = next;          } else {              prev.next = next;              x.prev = null;          }            if (next == null) {              last = prev;          } else {              next.prev = prev;              x.next = null;          }            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 = 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 = prev;          if (prev == null)              first = null;          else              prev.next = null;          size--;          modCount++;          return element;  }</code></pre>    <p>以上两组函数实现都是非常的简单,和数据结构书中讲的都几乎一样,想必大家也可以看懂,就不多废话了,而该类的其他方法多依赖于以上方法的实现.还有一个其他函数的依赖函数是 node()</p>    <pre>  <code class="language-java">//获取第index个结点  Node<E> node(int index) {          // assert isElementIndex(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;          }  }</code></pre>    <p>可以看出他是遍历链表的操作,只是因为有 first 和 last 的存在,可以稍微优化一下.</p>    <h2><strong>Stack</strong></h2>    <p>根据上面 LinkedList 的实现,其实使用 LinkedList 实现一个 Stack 是非常的容易的,可以看看实现方式.</p>    <pre>  <code class="language-java">public class Stack<T> {      private LinkedList<T> storage = new LinkedList<T>();         /** 入栈 */      public void push(T v) {         storage.addFirst(v);      }         /** 出栈,但不删除 */      public T peek() {         return storage.getFirst();      }         /** 出栈 */      public T pop() {         return storage.removeFirst();      }         /** 栈是否为空 */      public boolean empty() {         return storage.isEmpty();      }         /** 打印栈元素 */      public String toString() {         return storage.toString();      }  }</code></pre>    <p>但是 Java 中任然提供了 Stack 类,而且实现方式与上面的完全不同,它的内部存储结构是数组,基本的实现其实还是和 ArrayList 差不多,而且在 <<Think In Java>> 中并不建议使用它,因此这里不讲了.</p>    <h2><strong>Map</strong></h2>    <h2><strong>HashMap</strong></h2>    <p><img src="https://simg.open-open.com/show/b40a403085f6862400c7e83af6a97ece.png"></p>    <p>HasgMap包含函数</p>    <p>本文的代码均来至于JDK1.8, HashMap 与前面版本的变化比较大,Android SDK V23中的是旧版本的</p>    <h2><strong>源码阅读</strong></h2>    <pre>  <code class="language-java">transient Node<K,V>[] table;      transient Set<Map.Entry<K,V>> entrySet;      // HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子)         int threshold;      final float loadFactor; //加载因子,注意Android SDK写死的0.75</code></pre>    <p>在这里可以看看构造函数的参数</p>    <pre>  <code class="language-java">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;          //tableSizeFor(n) Returns the smallest power of two >= its argument          this.threshold = tableSizeFor(initialCapacity);  }</code></pre>    <p>可以看出 threshold 在没到达最大值之前是$2^n$.下面再看看常用的方法.</p>    <pre>  <code class="language-java">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; int n, i;          //还没有初始化数组          if ((tab = table) == null || (n = tab.length) == 0)              n = (tab = resize()).length;          //找到要添加的位置          if ((p = tab[i = (n - 1) & hash]) == null)              //如果还没有元素,就放入              tab[i] = newNode(hash, key, value, null);          else {              Node<K,V> e; K k;              if (p.hash == hash &&                  ((k = p.key) == key || (key != null && key.equals(k))))                  //已经存在了一个相同KEY的元素                  e = p;                  //红黑树,JDK1.8的优化点,当链表的长度大于8时,不再使用链表,转为红黑树              else if (p instanceof TreeNode)                  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);                          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                              treeifyBin(tab, hash); //链表长度为8了,转红黑树                          break;                      }                      //在链表中找到了同KEY值得元素                      if (e.hash == hash &&                          ((k = e.key) == key || (key != null && key.equals(k))))                          break;                      p = e;                  }              }              if (e != null) { // existing mapping for key ,已经存在的KEY,修改原本的值                  V oldValue = e.value;                  if (!onlyIfAbsent || oldValue == null)                      e.value = value;                  afterNodeAccess(e);                  return oldValue;              }          }          ++modCount;          if (++size > threshold)              resize();          afterNodeInsertion(evict); //空操作          return null;  }     final void treeifyBin(Node<K,V>[] tab, int hash) {          int n, index; Node<K,V> e;          if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)              resize();          else if ((e = tab[index = (n - 1) & hash]) != null) {              TreeNode<K,V> hd = null, tl = null;              do {                  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); //形成从该节点连接的节点的树。实现有点复杂          }  }</code></pre>    <p>关于红黑树的操作本身是非常复杂的,可以参考 <a href="/misc/goto?guid=4959713472457608076" rel="nofollow,noindex">Wiki</a> ,接下来看看 get() 操作.</p>    <pre>  <code class="language-java">public V get(Object key) {          Node<K,V> e;          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;          if ((tab = table) != null && (n = tab.length) > 0 &&              (first = tab[(n - 1) & hash]) != null) {              //Fiest为链表的首节点或红黑树的根节点              if (first.hash == hash && // always check first node                  ((k = first.key) == key || (key != null && key.equals(k))))                  return first;              if ((e = first.next) != null) {                  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;  }</code></pre>    <p>之理也只是大体说明一下 HashMap 的结构,核心的东西就是红黑树,它的其他方法也是大体一致,都是对链表和红黑树的操作. entrySet() 和 keySet() 也是和 List 中的 iterator 一样,内部的操作都是由 HashMap 本身来完成.</p>    <pre>  <code class="language-java">public boolean containsValue(Object value) {          Node<K,V>[] tab; V v;          if ((tab = table) != null && size > 0) {              for (int i = 0; i < tab.length; ++i) {                  for (Node<K,V> e = tab[i]; e != null; e = e.next) {                      if ((v = e.value) == value ||                          (value != null && value.equals(v)))                          return true;                  }              }          }          return false;  }</code></pre>    <p>这个函数大家可能也会有一点困惑,为什么这里就只讨论了链表的情况,并根据 next() 遍历整个链表?其实 TreeNode 是继承至 Node ,并且在生成红黑树的时候并没有修改 next 的指向,所以通过 next() 遍历就没问题了.</p>    <h2><strong>TreeMap</strong></h2>    <p><img src="https://simg.open-open.com/show/b8148fb2007668d925597bd5c88ace54.png"></p>    <p>TreeMap包含函数</p>    <p>TreeMap 的底层实现也是基于红黑树的.</p>    <h2><strong>源码阅读</strong></h2>    <p>还是老规矩,先看最常用的方法 put() .</p>    <pre>  <code class="language-java">public V put(K key, V value) {          Entry<K,V> t = root;          //红黑树为空,直接添加一个结点接OK          if (t == null) {              compare(key, key); // type (and possibly null) check              root = new Entry<>(key, value, null);              size = 1;              modCount++;              return null;          }          int cmp;          Entry<K,V> parent;          // split comparator and comparable paths          Comparator<? super K> cpr = comparator;          //优先使用主动提供的比较器,          //在使用该类(KEY)自带的比较器(继承Comparable)          if (cpr != null) {              do {                  parent = t;                  cmp = cpr.compare(key, t.key);                  if (cmp < 0)                      t = t.left;                  else if (cmp > 0)                      t = t.right;                  else                      //找到key值相同的结点,覆盖该值即可                      return t.setValue(value);              } while (t != null);          }          else {              //key不允许为NULL              if (key == null)                  throw new NullPointerException();              @SuppressWarnings("unchecked")                  Comparable<? super K> k = (Comparable<? super K>) key;              do {                  parent = t;                  cmp = k.compareTo(t.key);                  if (cmp < 0)                      t = t.left;                  else if (cmp > 0)                      t = t.right;                  else                      return t.setValue(value);              } while (t != null);          }          //到此找到了要插入到结点parent的子结点          Entry<K,V> e = new Entry<>(key, value, parent);          if (cmp < 0)              parent.left = e;          else              parent.right = e;          //插入完成,此时的红黑树结构可能已经被破坏,需要重新构建          //过程和HasmMap的其实是一样的.了解更多可以看文章后面的参考          fixAfterInsertion(e);          size++;          modCount++;          return null;  }  `</code></pre>    <p>接下来看看 get() 函数.</p>    <pre>  <code class="language-java">public V get(Object key) {          Entry<K,V> p = getEntry(key);          return (p==null ? null : p.value);  }    final Entry<K,V> getEntry(Object key) {          // Offload comparator-based version for sake of performance          if (comparator != null)              //自定义比较器的时候              return getEntryUsingComparator(key);          if (key == null)              throw new NullPointerException();          @SuppressWarnings("unchecked")              Comparable<? super K> k = (Comparable<? super K>) key;          Entry<K,V> p = root;          //实现就是查找二叉树查找问题          while (p != null) {              int cmp = k.compareTo(p.key);              if (cmp < 0)                  p = p.left;              else if (cmp > 0)                  p = p.right;              else                  return p;          }  }  //这个函数的实现  final Entry<K,V> getEntryUsingComparator(Object key) {          @SuppressWarnings("unchecked")              K k = (K) key;          Comparator<? super K> cpr = comparator;          if (cpr != null) {              Entry<K,V> p = root;              while (p != null) {                  int cmp = cpr.compare(k, p.key);                  if (cmp < 0)                      p = p.left;                  else if (cmp > 0)                      p = p.right;                  else                      return p;              }          }          return null;  }</code></pre>    <p>遍历的时候调用了一个函数</p>    <pre>  <code class="language-java">final Entry<K,V> nextEntry() {              Entry<K,V> e = next;              if (e == null)                  throw new NoSuchElementException();              if (modCount != expectedModCount)                  throw new ConcurrentModificationException();              next = successor(e);  //中序遍历的E的后一节点              lastReturned = e;              return e;  }</code></pre>    <p>这样输入的数据就是按照红黑树中序遍历的数据,也就是有序数据.</p>    <h2><strong>LinkedHashMap</strong></h2>    <p><img src="https://simg.open-open.com/show/91332aea0c153369fb5739986f6a9e4c.png"></p>    <p>LinkedHashMap函数列表</p>    <p>根据最上面的继承关系图我们知道 LinkedHashMap 继承至 HashMap ,所以重复型的东西我就不说了, LinkedHashMap 的核心功能就是维持了原有的输入顺序或者指定为访问顺序 (LRU) .下面也是主要看看这个功能的实现.</p>    <h2><strong>源码阅读</strong></h2>    <p>LinkedHashMap 中的字段</p>    <pre>  <code class="language-java">// 头部放旧结点(最久没使用或最久放入)      transient LinkedHashMap.Entry<K,V> head;      // 尾部放新节点      transient LinkedHashMap.Entry<K,V> tail;</code></pre>    <p>通过上面的分析,我们知道 HashMap 的 put() 时调用了函数 newNode() ,而 LinkedHashMap 就重写了这个方法.</p>    <pre>  <code class="language-java">//结点,相比HashMap多了before和after  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);          }  }    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {          //创建一个结点          LinkedHashMap.Entry<K,V> p =              new LinkedHashMap.Entry<K,V>(hash, key, value, e);          linkNodeLast(p);          return p;  }  //内部保存了一个链表  private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {          LinkedHashMap.Entry<K,V> last = tail;          tail = p;          if (last == null)              head = p;          else {              p.before = last;              last.after = p;          }  }</code></pre>    <p>这样就要求在以后的插入删除的工作中需要额外的维护这个链表.另外,如果开启了按访问顺序排序的话,在每次 get() 或者 put() 了重复数据是都会要求把访问的结点放到链表尾部.</p>    <pre>  <code class="language-java">//把E移动到双向链表的尾部  void afterNodeAccess(Node<K,V> e) { // move node to last          LinkedHashMap.Entry<K,V> last;          if (accessOrder && (last = tail) != e) {              LinkedHashMap.Entry<K,V> p =                  (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;              p.after = null;              if (b == null) //P本身为首节点                  head = a;              else                  b.after = a;              if (a != null)                  a.before = b;              else         //P本身为尾接点                  last = b;              //到此P被移除了                  if (last == null) //原本链表只有一个元素,移除光了                  head = p;              else {                 //P放在最后                  p.before = last;                  last.after = p;              }              //修改指向末尾结点的指针              tail = p;              ++modCount;          }  }</code></pre>    <p>接下来就看看 LinkedHashMap 的遍历. entrySet() 返回的是一个 LinkedEntrySet 的实例,而 LinkedEntrySet 的迭代器是 LinkedEntryIterator , LinkedEntryIterator 的 next() 方法调用 nextNode() 函数.</p>    <pre>  <code class="language-java">//构造函数  LinkedHashIterator() {              next = head;              expectedModCount = modCount;              current = null;  }    final LinkedHashMap.Entry<K,V> nextNode() {              LinkedHashMap.Entry<K,V> e = next;              if (modCount != expectedModCount)                  throw new ConcurrentModificationException();              if (e == null)                  throw new NoSuchElementException();              current = e;              next = e.after;              return e;   }</code></pre>    <p>可以很明显的看到,它的实现完全依赖于构建的链表,不像 HashMap 对组数和链表(红黑树)的遍历.相比 HashMap 其实就是多了一个双向链表而已.</p>    <h2><strong>Set</strong></h2>    <p>Set 是一个不包含重复元素的 Collection 。更确切地讲, Set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2 ,并且最多包含一个 null 元素.</p>    <h2><strong>HashSet</strong></h2>    <p><img src="https://simg.open-open.com/show/6f5f72c7fee03e99e06796f3d73bfc14.png"></p>    <p>HashSet函数列表</p>    <p>HashSet 的底部是使用一个 HashMap ,把值存在 HashMap 的 KEY , HashMap 的 VALUE 字段为固定的值,根据 HashMap 的 KEY 的唯一性,可以保证 HashSet 的值得唯一性.额外,有一个构造器使用的是 LinkedHashMap ,只有包权限,是后面要讲的 LinkedHashSet 的实现.</p>    <pre>  <code class="language-java">//dummy 参数只是使用来区别构造函数  HashSet(int initialCapacity, float loadFactor, boolean dummy) {          map = new LinkedHashMap<>(initialCapacity, loadFactor);  }</code></pre>    <h2><strong>源码阅读</strong></h2>    <p>其实 HashSet 的源码并没有什么东西,都是调用 HashMap 的基本操作.下面随便看两个函数.</p>    <pre>  <code class="language-java">private transient HashMap<E,Object> map;    public boolean add(E e) {          return map.put(e, PRESENT)==null;  }    public Iterator<E> iterator() {          return map.keySet().iterator();  }    public boolean contains(Object o) {          return map.containsKey(o);  }</code></pre>    <p>由于这些方法前面都已经说过了,这里就不说了.</p>    <h2><strong>TreeSet</strong></h2>    <p><img src="https://simg.open-open.com/show/2a3394da408e29d1b2bbd964e68ebefc.png"></p>    <h2><strong>TreeSet函数列表</strong></h2>    <p>有了上面 HashSet 的介绍,可能你已经猜到 TreeSet 的实现方式是基于 TreeMap 了.将值存放在 TreeMap 的 KEY 中,保证了不会重复并且有序,最后只需要遍历 TreeSet 的 KEY 就行了.具体的操作可以看看 TreeMap .</p>    <h2><strong>LinkedHashSet</strong></h2>    <p>它的实现是最简单的,继承至 HashSet ,调用前面说的特殊构造器,相当于把 HashSet 的 HashMap 换成了 LinkedHashMap ,并且按照插入顺序排序.</p>    <h2><strong>Queue</strong></h2>    <h2><strong>LinkedList</strong></h2>    <p>这个上面已经分析过了,这里跳过。</p>    <h2><strong>PriorityQueue</strong></h2>    <p><img src="https://simg.open-open.com/show/2813ad2ea8142928f8ff17cac1f97c1e.png"></p>    <p style="text-align:center">PriorityQueue函数</p>    <h2><strong>准备</strong></h2>    <p>在数据结构的课程中,我们都学过用数组表示完全二叉树,这里有一些固定的公式</p>    <pre>  <code class="language-java">Index(parent) = (Index(Child)-1) >> 1   //索引0开始</code></pre>    <p>而优先级队列 Priority 就是使用了数组表示最小堆,每次插入删除都会重新排列内部数据。</p>    <p>最小堆,是一种经过排序的完全二叉树</p>    <h2><strong>源码阅读</strong></h2>    <p>有用的字段</p>    <pre>  <code class="language-java">priavte transient Object[] queue; //内部表示最小堆的数组  private int size = 0; //实际大小</code></pre>    <p>常用方法 add() 的实现</p>    <pre>  <code class="language-java">public boolean add(E e) {      return offer(e); // add方法内部调用offer方法  }    public boolean offer(E e) {      if (e == null) // 元素为空的话,抛出NullPointerException异常          throw new NullPointerException();      modCount++;      int i = size;      if (i >= queue.length) // 如果当前用堆表示的数组已经满了,调用grow方法扩容          grow(i + 1); // 扩容      size = i + 1; // 元素个数+1      if (i == 0) // 堆还没有元素的情况          queue[0] = e; // 直接给堆顶赋值元素      else // 堆中已有元素的情况          siftUp(i, e); // 重新调整堆,从下往上调整,因为新增元素是加到最后一个叶子节点      return true;  }    private void siftUp(int k, E x) {      if (comparator != null)  // 比较器存在的情况下          siftUpUsingComparator(k, x); // 使用比较器调整      else // 比较器不存在的情况下          siftUpComparable(k, x); // 使用元素自身的比较器调整  }    private void siftUpUsingComparator(int k, E x) {      while (k > 0) { // 一直循环直到父节点还存在          int parent = (k - 1) >>> 1; // 找到父节点索引,依赖完全二叉树性质          Object e = queue[parent]; // 赋值父节点元素          if (comparator.compare(x, (E) e) >= 0) // 新元素与父元素进行比较,如果满足比较器结果,直接跳出,否则进行调整              break;          queue[k] = e; // 进行调整,新位置的元素变成了父元素          k = parent; // 新位置索引变成父元素索引,进行递归操作      }      queue[k] = x; // 新添加的元素添加到堆中  }  private void siftUpComparable(int k, E x) {   ...//同上面类似  }</code></pre>    <p>下面看看函数 remove() 的实现</p>    <pre>  <code class="language-java">public boolean remove(Object o) {          int i = indexOf(o); //按数组索引遍历          if (i == -1)              return false;          else {              removeAt(i);              return true;          }  }    private E removeAt(int i) {          // assert i >= 0 && i < size;          modCount++;          int s = --size;          if (s == i) // removed last element,移除最后的元素,该数组依旧是最小堆              queue[i] = null;          else {              E moved = (E) queue[s];              queue[s] = null; //数组最后一个位置置空              siftDown(i, moved);               if (queue[i] == moved) {                  siftUp(i, moved);                  if (queue[i] != moved)                      return moved;              }          }          return null;  }      private void siftDown(int k, E x) {          if (comparator != null)              siftDownUsingComparator(k, x);          else              siftDownComparable(k, x);  }    @SuppressWarnings("unchecked")  private void siftDownComparable(int k, E x) {          Comparable<? super E> key = (Comparable<? super E>)x;          int half = size >>> 1;        // loop while a non-leaf          //为什么是一半??          //因为大于half的元素必然是没有叶子节点的,这是只需要用末节点X替换要删除的节点index(K),然后重新排序。          //而对于小于half的节点,由于存在(左)/(右)节点,用较小的节点替换要删除的节点,这样带删除节点的Index = (左)/(右)的索引,然后继续递归执行,直到大于half,在用末节点替换她。          while (k < half) {              int child = (k << 1) + 1; // assume left child is least              Object c = queue[child];              int right = child + 1;              if (right < size &&                  ((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;  }</code></pre>    <p>函数 poll() 和 remove() 的实现基本一致。</p>    <pre>  <code class="language-java">public E poll() {          if (size == 0)              return null;          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;  }</code></pre>    <p>其他的比如扩容函数和 ArrayList 的原理都是一样的,这里就不说了。到此,基本的集合类的源码大体上都说完了。</p>    <h2><strong>其他技术点</strong></h2>    <h2><strong>Java 8 default关键字</strong></h2>    <pre>  <code class="language-java">interface A {       void doSomeThing();  }  static class B implements A {       @Override       public void doSomeThing() {          System.out.println("B");       }   }   static class C implements A {       @Override       public void doSomeThing() {           System.out.println("C");       }   }</code></pre>    <p>以上代码如果想在 A 中添加一个函数,必然需要修改 B 和 C 的实现,但是在 <em>Java 8</em> 支持为接口添加一个默认的实现,这样和抽象类就很相似了。</p>    <pre>  <code class="language-java">interface A {       void doSomeThing();       default void doAction() {           System.out.println("Default");       }  }  static class B implements A {       @Override       public void doSomeThing() {          System.out.println("B");       }   }   static class C implements A {       @Override       public void doSomeThing() {           System.out.println("C");       }   }</code></pre>    <p>就向上面就OK了。</p>    <h2><strong>Integer比较问题</strong></h2>    <pre>  <code class="language-java">System.out.println(Integer.valueOf(127)==Integer.valueOf(127));  System.out.println(Integer.valueOf(128)==Integer.valueOf(128));  System.out.println(Integer.parseInt("128")==Integer.valueOf("128"));</code></pre>    <p>输出</p>    <p>true</p>    <p>false</p>    <p>true</p>    <p>为什么会有这问题?通过源代码</p>    <pre>  <code class="language-java">public static Integer valueOf(int i) {     if (i >= IntegerCache.low && i <= IntegerCache.high)          return IntegerCache.cache[i + (-IntegerCache.low)];      return new Integer(i);  }</code></pre>    <p>代码中的 IntegerCache.low 为固定值 -128 , IntegerCache.high 根据VM系统参数不同会有区别,默认127,因此在[-128,127]范围内,实例化的时候是返回的同一个对象,必然相等。当 Integer 修改的时候,由于他是 <em>不可变对象(参考String,每次修改都是重新生成对象)</em> ,也不会出现问题。对于第三个例子, parseInt() 的返回是 int ,这时和 Integer 比较, Integer 会拆包为 int ,当然也就相等。</p>    <p>另外补充一点,当我们调用</p>    <pre>  <code class="language-java">Integer i = 1;</code></pre>    <p>其实也是执行</p>    <pre>  <code class="language-java">Integer i = Integer.valueOf(1);</code></pre>    <p>可以从反编译中看出</p>    <pre>  <code class="language-java">//源码  public static void main(String[] args){    Integer i = 1;    int r = i + 1;  }  //反编译结果  public static void main(java.lang.String[]);    Code:       0: iconst_1             1: invokestatic  #2                  // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;       4: astore_1             5: aload_1              6: invokevirtual #3                  // Method java/lang/Integer.intValue:()I       9: iconst_1            10: iadd                11: istore_2            12: return</code></pre>    <p>自动拆箱调用 intValue() ,自动装箱调用 valueOf() 。</p>    <h2><strong>List&Set&Map在遍历过程中删除添加元素错误</strong></h2>    <pre>  <code class="language-java">for(int i:list){    if(i == 2){        list.remove(Integer.valueOf(2));     }  }</code></pre>    <p>以上这段代码会抛出 java.util.ConcurrentModificationException 异常。这是因为foreach本质还是调 list.iterator() ,这里用 ArrayList 说明。</p>    <pre>  <code class="language-java">public Iterator<E> iterator() {       return new Itr();  }</code></pre>    <p>这里返回一个迭代器,其内部参数包括</p>    <pre>  <code class="language-java">private class Itr implements Iterator<E> {      int cursor;       // index of next element to return      int lastRet = -1; // index of last element returned; -1 if no such      int expectedModCount = modCount; //修改次数,注意int为值传递  }</code></pre>    <p>也就是说保存了修改的次数,在迭代器的 next() 中有检测这个值是否被篡改(可以修改的地方包括 ArrayList 的 add(...) 和 remove() )。</p>    <pre>  <code class="language-java">final void checkForComodification() {     if (modCount != expectedModCount)        throw new ConcurrentModificationException();  }</code></pre>    <p>解决方案是使用迭代器的 remove(...)</p>    <pre>  <code class="language-java">Iterator iterator = list.iterator();  while (iterator.hasNext()){     Integer i = (Integer) iterator.next();     if(i == 2){        iterator.remove();     }  }</code></pre>    <h2><strong>instanceof 关键字</strong></h2>    <pre>  <code class="language-java">Object obj = null;  if(obj instanceof Object){     System.out.println("会输出吗?还是崩溃");  }</code></pre>    <p>上面的例子不会输出,也不会崩溃, instanceof 会检测左边对象是否为 null ,若是,返回 false .</p>    <h2><strong>HashMap的容量为什么为$2^n$</strong></h2>    <p>在 put() 函数中,选取数组索引的方式为</p>    <pre>  <code class="language-java">tab[i = (n - 1) & hash]</code></pre>    <p>重点关注 (n - 1) & hash ,这里的 n 是容量,若 n= $2^n$, n-1 的二进制形式为 11...11 ,做 & 运算后只有 hash 的后几位相关,保证足够散列,而若其他情况,下 n-1 为 01..01 ,运算后只有 hash 的后几位中的某几位相关,缩小了散列范围,如 n-1 最末尾为 0 ,这样 & 之后始终是一个偶数,导致分布过于集中.</p>    <h2>参考</h2>    <ul>     <li><a href="/misc/goto?guid=4959713472562056200" rel="nofollow,noindex">Why do == comparisons with Integer.valueOf(String) give different results for 127 and 128?</a></li>     <li><a href="/misc/goto?guid=4959713472683064060" rel="nofollow,noindex">要裝箱還是拆封</a></li>     <li><a href="/misc/goto?guid=4959713472790840696" rel="nofollow,noindex">Java LinkedList源码分析</a></li>     <li><a href="/misc/goto?guid=4959713472910550623" rel="nofollow,noindex">基于LinkedList实现栈和队列</a></li>     <li><a href="/misc/goto?guid=4959713473024804032" rel="nofollow,noindex">HashMap源码剖析</a></li>     <li><a href="/misc/goto?guid=4959713473122625973" rel="nofollow,noindex">Java类集框架之HashMap(JDK1.8)源码剖析</a></li>     <li><a href="/misc/goto?guid=4959713473227177225" rel="nofollow,noindex">紅黑樹</a></li>     <li><a href="/misc/goto?guid=4959713473318410931" rel="nofollow,noindex">jdk PriorityQueue优先队列工作原理分析</a></li>     <li><a href="/misc/goto?guid=4959713473420421360" rel="nofollow,noindex">Java集合框架——PriorityQueue</a></li>    </ul>    <p> </p>    <p>来自:http://www.jianshu.com/p/8d14b55fa1fb</p>    <p> </p>    
 本文由用户 xyyujnnaruz 自行上传分享,仅供网友学习交流。所有权归原作者,若您的权利被侵害,请联系管理员。
 转载本站原创文章,请注明出处,并保留原始链接、图片水印。
 本站是一个以用户分享为主的开源技术平台,欢迎各类分享!
 本文地址:https://www.open-open.com/lib/view/open1472717096502.html
Java 链表 红黑树 Java开发