JAVA常用數(shù)據(jù)結構

開始

這篇文章主要記錄下平常開發(fā)中常用的數(shù)據(jù)結構，會簡單說明每種數(shù)據(jù)結構的優(yōu)點、缺點、特點等等。

JDK提供了一組主要的數(shù)據(jù)結構實現(xiàn)，如List、Map、Set、Queue 等常用數(shù)據(jù)結構。這些數(shù)據(jù)都繼承自java.util.Collection接口，并位于java.util包內(nèi)。

image

List

image

  • ArrayList

    • 基于動態(tài)數(shù)組集合，可以動態(tài)的增加、刪除元素，動態(tài)擴容等，默認初始容量10，超出上限會擴容至：
      int newCapacity = oldCapacity + (oldCapacity >> 1); 也就是原來容量的1.5倍。
    • 優(yōu)點：按下標索引速度快(O(1))。缺點：插入刪除會慢(O(n))。

    • 一個容量10的ArrayList。


      image

    • 擴容1.5倍后的樣子


      image
    • ArrayList 擴容源碼
    /**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 舊的容量 + 舊的容量左移一位(也就是除以2)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

  • LinkedList

    • 基于鏈表的集合，是一個雙向鏈表，沒有初始化大小，也沒有擴容的機制，會一直在前面或者后面新增Node。
    • 優(yōu)點：便于存取，只要改變頭尾節(jié)點指向 (O(1))。缺點：索引慢，極端情況會出現(xiàn)從頭結點遍歷到最后一個節(jié)點的情況 (O(n))。

    • 單向鏈表：每個節(jié)點只會指向下一個節(jié)點


      image
    • 雙向鏈表：每個節(jié)點會保存上一個節(jié)點和下一個節(jié)點

      image

  • Vector

    • 也是基于數(shù)組的一個集合，對一些操作數(shù)據(jù)的方法加了synchronized，可以看做是ArrayList一個同步、線程安全的版本
    • 優(yōu)點：線程安全的。缺點：同步必然會導致效率慢。

  • 小結

    • 上面幾種集合都屬于線性數(shù)據(jù)結構，也是有序，元素之間都有關聯(lián)關系。
    • 基于數(shù)組的：在分配內(nèi)存時是一塊規(guī)整的內(nèi)存，所有數(shù)據(jù)都緊鄰著。(也有說數(shù)組不屬于線性結構的，希望大佬指正)
    • 基于鏈表的：雖然在內(nèi)存里都是不連續(xù)的，但是每個節(jié)點都會保留下一個節(jié)點的引用。

Map

Map 是一種把鍵對象和值對象映射的集合，它的每一個元素都包含一對鍵對象和值對象。 Map沒有繼承于Collection接口。

image

  • HashMap

    • HashMap 底層是數(shù)組+鏈表(jdk1.8是數(shù)組+鏈表/紅黑樹)，HashMap可能也是應用最多的數(shù)據(jù)結構了。
    • 初始容量
        /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    • 負載因子：據(jù)說0.75是在時間和空間上一個較為合適的數(shù)，過高容易哈希碰撞，過低容易浪費空間
    /**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
    • 閾值
        /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    int threshold;
    • 擴容機制：

      當size > (capacity * load factor)時會觸發(fā)擴容(newCap = oldCap << 1)。源碼resize() 方法有點長，這里就不貼了。
    • 何時轉換紅黑樹：
          //條件1：當鏈表長度>=8
      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
          treeifyBin(tab, hash);
      break;
      
      //條件2：并且桶數(shù)量>=64鏈表:
      final void treeifyBin(Node<K,V>[] tab, int hash) {
          int n, index; Node<K,V> e;
          //如果小于64將繼續(xù)擴容
          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);
          }
      }
    • 何時退化成鏈表：

      當長度小于6又會退化成鏈表（如果小于8又轉換成鏈表，可能會出現(xiàn)鏈表與紅黑樹反復轉換的情況）,在removeTreeNode()和split()方法都觸發(fā)判斷邏輯。

    • HashMap 鏈表紅黑樹轉換過程


      image

  • HashTable

    其實就是HashMap的一個線程安全版本，像Vector和ArrayList的關系一樣，對內(nèi)部的方法都加了synchronized關鍵字修飾。

     public class Hashtable<K,V>
     extends Dictionary<K,V>
     implements Map<K,V>, Cloneable, java.io.Serializable {
     
         public Hashtable(int initialCapacity) {
             this(initialCapacity, 0.75f);
         }
     }
    • 缺點：因為采用synchronized保證同步，每次都會鎖住整個map，所以高并發(fā)線程在爭奪同一把鎖的時候性能急劇下降。

  • TreeMap

    平常開發(fā)中用的不多，是一個紅黑樹版本的map，實現(xiàn)了NavigableMap<K,V>并且NavigableMap又繼承了SortedMap<K,V>類，SortedMap接口有一個Comparator<? super K> comparator();比較器，所以TreeMap是支持比較排序的。

      public class TreeMap<K,V>
      extends AbstractMap<K,V>
      implements NavigableMap<K,V>, Cloneable, java.io.Serializable
  {
      public TreeMap(Comparator<? super K> comparator) { //支持比較器
          this.comparator = comparator;
      }

      static final class Entry<K,V> implements Map.Entry<K,V> { //紅黑樹結構
          K key;
          V value;
          Entry<K,V> left;
          Entry<K,V> right;
          Entry<K,V> parent;
          boolean color = BLACK;
          
          /**
           * Make a new cell with given key, value, and parent, and with
           * {@code null} child links, and BLACK color.
           */
          Entry(K key, V value, Entry<K,V> parent) {
              this.key = key;
              this.value = value;
              this.parent = parent;
          }
      }
  }

    • TreeMap的結構


      image
    • 特點：采用紅黑樹實現(xiàn)，是一個有序的map。

  • ConcurrentHashMap

    底層也是HashMap，同時保證了線程安全，與HashTable不同的ConcurrentHashMap采用分段鎖思想，拋棄了使用synchronized修飾操作方法的同步方式。


    image
    • 分段鎖思想：

      都知道HashTable效率低下的原因是因為整個容器只有一把鎖，多線程爭搶同一把鎖導致。
      ConcurrentHashMap分段鎖指得是將數(shù)據(jù)分成一個個的Segment<K,V>，每個Segment又繼承ReentrantLock，這樣一個map容器就會有多個Lock，每個Lock鎖不同的數(shù)據(jù)段，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問。
          static class Segment<K,V> extends ReentrantLock implements Serializable {
          private static final long serialVersionUID = 2249069246763182397L;
          final float loadFactor;
          Segment(float lf) { this.loadFactor = lf; }
      }
    • 1.7與1.8的區(qū)別：

      1. 因為底層是HashMap，so 1.8之后也變成了數(shù)組+鏈表/紅黑樹。

      2. 1.8之后放棄了分段鎖，采用了synchronized+CAS來保證并發(fā)。
    • 1.8為何放棄分段鎖：

      1. 我認為主要是1.8對synchronized進行了優(yōu)化(偏向鎖、輕量級鎖、自旋鎖、自適宜自旋)
      2. 加入多個分段鎖浪費內(nèi)存空間。
      3. 生產(chǎn)環(huán)境中， map在放入時競爭同一個鎖的概率非常小，分段鎖反而會造成更新等操作的長時間等待。
      image

Set

  • HashSet

    HashSet 基于HashMap實現(xiàn)，利用Map的key不能重復來實現(xiàn)Set的元素唯一性 

    public class HashSet<E> extends AbstractSet<E>
  implements Set<E>, Cloneable, java.io.Serializable { 

    private transient HashMap<E,Object> map; // 底層就是一個HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object(); 

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
  
    // HashSet每次add()都是將值插入Key上，而Value統(tǒng)一用一個static final修飾的Object對象
    public boolean add(E e) {
       return map.put(e, PRESENT)==null;
   }
}

  • LinkedHashSet

    LinkedHashSet 基于LinkedHashMap實現(xiàn)，繼承自HashSet，可以看出是一個有序的Set（可以像LinkedHashMap自定義排序）
    ```
    public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    public LinkedHashSet() {
    super(16, .75f, true);
    }

          public LinkedHashSet(Collection<? extends E> c) {
          super(Math.max(2*c.size(), 11), .75f, true);
          addAll(c);
      }
  }

Stack

todo

Queue

todo

總結

整篇文章對各種數(shù)據(jù)結構介紹的比較簡單，但也將每種結構的特點優(yōu)勢指出了，文章里的圖片部分是網(wǎng)上搜的(杜絕重復造輪子)。

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容