很長時(shí)間以來一直代碼中用的比較多的數(shù)據(jù)列表主要是List，而且都是ArrayList，感覺有這個(gè)玩意就夠了。ArrayList是用于實(shí)現(xiàn)動態(tài)數(shù)組的包裝工具類，這樣寫代碼的時(shí)候就可以拉進(jìn)拉出，迭代遍歷，蠻方便的。

也不知道從什么時(shí)候開始慢慢的代碼中就經(jīng)常會出現(xiàn)HashMap和HashSet之類的工具類。應(yīng)該說HashMap比較多一些，而且還是面試經(jīng)典題，平時(shí)也會多看看。開始用的時(shí)候簡單理解就是個(gè)鍵值對應(yīng)表，使用鍵來找數(shù)據(jù)比較方便。隨后深入了解后發(fā)現(xiàn)

這玩意還有點(diǎn)小奧秘，特別是新版本的JDK對HashMap的改成樹后，代碼都有點(diǎn)小復(fù)雜咯。

Set開始用的較少，只是無意中在一個(gè)代碼中發(fā)現(xiàn)一個(gè)TreeSet，發(fā)現(xiàn)這個(gè)類可以自帶順利，感覺蠻有點(diǎn)意思，才慢慢的發(fā)現(xiàn)這也是個(gè)好工具啊。

代碼寫的多了就感覺到基礎(chǔ)的重要性，所以在此寫一篇小文簡單的整理一下對集合的一些知識。

好了，簡單的整理一下：

•List：即是列表，支持?jǐn)?shù)組、鏈表的功能，一般都是線性的
•Map：即是映射表，存儲的是鍵與值的對應(yīng)關(guān)系
•Set：即是集合的意思，主要是用于排重?cái)?shù)據(jù)及排序

先來看看List

List是用于存放線性數(shù)據(jù)的一種窗口，比如：用于數(shù)組的ArrayList和用于鏈表的LinkedList。

ArrayList

這是一個(gè)數(shù)組列表，不過提供了自動擴(kuò)容的功能，實(shí)現(xiàn)List接口，外部操作都是通過接口申明的方法訪問，這樣即安全又方便。

ArrayList的關(guān)鍵就是自動擴(kuò)容，在對象初始化時(shí)可以設(shè)定初始容量，也可以按默認(rèn)的容量。如果對數(shù)組大小沒有特別明確可以不指定初始大小，如果明確的話可以指定一個(gè)大小，這樣減少動態(tài)擴(kuò)容時(shí)產(chǎn)生的卡頓。說到這就要說一下擴(kuò)容是怎么實(shí)現(xiàn)的了，看下面的代碼：

private void grow(int minCapacity) {

    // overflow-conscious code

    int oldCapacity = elementData.length;

    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);

  }

grow是在ArrayList在添加元素或者一些容易檢查時(shí)會觸發(fā)的一個(gè)方法。主要過程：

1、得到數(shù)組的長度，并對其進(jìn)行右移，這樣就相當(dāng)于oldCapacity/2，得到新的長度

2、如果這個(gè)長度小于最小容量那么直接就用最小容易

3、如果大于了最大容易則取一個(gè)最大值，這里會調(diào)用一個(gè)hugeCapacity方法，主要是比較minCapacity與MAX_ARRAY_SIZE的，如果minCapacity大于MAX_ARRAY_SIZE則取Integer.MAX_VALUE，否則就取MAX_ARRAY_SIZE，有意思的是MAX_ARRAY_SIZE取的是Integer.MAX_VALUE - 8;并不知道這樣做的意義是什么

4、最后就是調(diào)用一個(gè)復(fù)制方法將現(xiàn)有數(shù)復(fù)制到一個(gè)新的數(shù)組中。

因?yàn)橛羞@個(gè)復(fù)制過程，如果數(shù)組比較大，那么老是觸發(fā)擴(kuò)容當(dāng)然就會出現(xiàn)卡頓的情況。所以如果一開始就知道最大值而且很容易增長到這個(gè)值，那么開始初始化時(shí)就指定大小會有一定的作用。

LinkedList

這是針對鏈表的工具類，鏈表的優(yōu)秀是添加刪除啥的比較快，但是查找會慢一些。

至于代碼好像也沒什么特別的，就是一串指針鏈接起來，當(dāng)然Java中就使用對象來代替，建立一個(gè)Node的對象，Node本身指向了前一個(gè)Node和后一個(gè)Node，這就是鏈表的結(jié)構(gòu)：

 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;

    }

  }

然后用兩個(gè)Node指向頭和尾就完成了，下面的代碼：

/**

   * Pointer to first node.

   * Invariant: (first == null && last == null) ||

   *      (first.prev == null && first.item != null)

   */

  transient Node<E> first;

 

  /**

   * Pointer to last node.

   * Invariant: (first == null && last == null) ||

   *      (last.next == null && last.item != null)

   */

  transient Node<E> last;

看一個(gè)add操作：

/**

   * Links e as last element.

   */

  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++;

  }

過往就是：

1、獲取到最后的Node并放在l中

2、創(chuàng)建一個(gè)新的Node，將數(shù)據(jù)取到這個(gè)Node中，創(chuàng)建過程會將新Node的prev指向l，這樣就接上了鏈

3、然后將last指向這個(gè)新Node

4、然判斷l(xiāng)是否null，如果是null說明是空鏈表，新node就是第一個(gè)元素，這樣first也要指向newNode

5、如果不為空則將l的next指向newNode

6、累加計(jì)數(shù)器

刪除操作也是這種Node的前后Node指向移動操作。

再來看看Map

Map是鍵與值做一個(gè)映射表的應(yīng)用，主要的實(shí)現(xiàn)類：HashMap,HashTable,TreeMap

HashMap和HashTable

使用hash算法進(jìn)行鍵值映射的就是HashMap啦，HashTable是帶有同步的線程安全的類，它們兩主要的區(qū)別就是這個(gè)。原理也類似，都是通過桶+鏈來組合實(shí)現(xiàn)。桶是用來存Key的，而由于Hash碰撞的原因值需要用一個(gè)鏈表來存儲。

•桶的意義在于高效，通過Hash計(jì)算可以一步定位
•鏈表的意義在于存取重復(fù)hash的數(shù)據(jù)

具體的原理以前寫過一篇《學(xué)習(xí)筆記：Hashtable和HashMap》

只不過看JDK1.8的HashMap換了存儲結(jié)構(gòu)，采用紅黑樹的結(jié)構(gòu)，這樣可能是解決鏈表查找效率問題吧？具體沒有細(xì)研究。

TreeMap

看過TreeMap的代碼后發(fā)現(xiàn)還是使用的樹結(jié)構(gòu)，紅黑樹。由于紅黑樹是有序的，所以自然帶排序功能。當(dāng)然也可通過comparator來指定比較方法來實(shí)現(xiàn)特定的排序。

因?yàn)椴捎昧藰浣Y(jié)構(gòu)存儲那么添加和刪除數(shù)據(jù)時(shí)會麻煩一些，看一下put的代碼：

public V put(K key, V value) {

    Entry<K,V> t = root;

    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;

    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

          return t.setValue(value);

      } while (t != null);

    }

    else {

      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);

    }

    Entry<K,V> e = new Entry<>(key, value, parent);

    if (cmp < 0)

      parent.left = e;

    else

      parent.right = e;

    fixAfterInsertion(e);

    size++;

    modCount++;

    return null;

  }

1、先是檢查根節(jié)點(diǎn)是否存在，不存在說明是第一條數(shù)據(jù)，直接作為樹的根

2、判斷是否存在比較器，如果存在則使用比較器進(jìn)行查找數(shù)據(jù)的存放位置，如果比較器返回結(jié)果小于0取左，大于0取右，否則直接替換當(dāng)前節(jié)點(diǎn)的值

3、如果不存在比較器則key直接與節(jié)點(diǎn)的key比較，比較和前面方法一樣

4、接下來就是在找到的parent上創(chuàng)建一個(gè)子節(jié)點(diǎn)，并放入左或者右子節(jié)點(diǎn)中

5、fixAfterInsertion是對節(jié)點(diǎn)進(jìn)行著色

6、累加器處理

在remove操作時(shí)也會有點(diǎn)麻煩，除了刪除數(shù)據(jù)外，還要重新平衡一下紅黑樹。

另外，TreeMap實(shí)現(xiàn)了NavigableMap<K,V>接口，所以也提供了對數(shù)據(jù)集合的一些返回操作。

最后看看Set

Set主要是兩類應(yīng)用：HashSet和TreeSet。

HashSet

字面意思很明確，使用了Hash的集合。這種集合的特點(diǎn)就是使用Hash算法存數(shù)據(jù)，所以數(shù)據(jù)不重復(fù)，存取都相對較快。怎么做到的呢？

public boolean add(E e) {

    return map.put(e, PRESENT)==null;

  }

原來是存在一個(gè)map對象中，再看map是個(gè)啥？

private transient HashMap<E,Object> map;

是個(gè)HashMap，了解HashMap的就明白，這樣的數(shù)據(jù)是不會重復(fù)的。因?yàn)榇嫒霑r(shí)是鼗對象本身作為Key來存的，所以在HashMap中只會存在一份。

了解了這點(diǎn)其他的東西就非常明白了。

TreeSet

這個(gè)集合是用于對集合進(jìn)行排序的，也就是除了帶有排重的能力外，還可以自帶排序功能。只不過看了TreeSet的代碼發(fā)現(xiàn)，其就是在TreeMap的基礎(chǔ)實(shí)現(xiàn)的。更準(zhǔn)確的說應(yīng)該是NavigableMap的派生類。默認(rèn)不指定map情況下TreeSet是以TreeMap為基礎(chǔ)的。

public TreeSet() {

    this(new TreeMap<E,Object>());

  }

所以，這里可能更關(guān)注的是TreeSet是如何排重呢？看一下add的方法吧：

public boolean add(E e) {

    return m.put(e, PRESENT)==null;

  }

和HashSet有點(diǎn)類似，都是基于Map的特性來實(shí)現(xiàn)排重。確實(shí)簡單而且有效。

以上就是小編為大家?guī)淼亩嘤枚鄬W(xué)之Java中的Set,List,Map詳解全部內(nèi)容了，希望大家多多支持腳本之家~

最新評論