多用多學之Java中的Set,List,Map詳解

很久以來一直在程式碼中使用的比較多的資料清單主要是List，而且都是ArrayList，感覺有這個玩意就夠了。 ArrayList是用來實作動態陣列的包裝工具類，這樣寫程式碼的時候就可以拉進拉出，迭代遍歷，蠻方便的。

也不知道從什麼時候開始慢慢的程式碼中就常常會出現HashMap和HashSet之類的工具類別。應該說HashMap比較多一些，而且還是面試經典題，平常也會多看看。開始用的時候簡單理解就是個鍵值對應表，使用鍵來找資料比較方便。隨後深入了解後發現

這玩意還有點小奧秘，特別是新版的JDK對HashMap的改成樹後，程式碼都有點小複雜咯。

Set開始用的較少，只是無意中在一個程式碼中發現一個TreeSet，發現這個類別可以自帶順利，感覺蠻有點意思，才慢慢的發現這也是個好工具啊。

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

好了，簡單的整理一下：

•List：即是列表，支援數組、鍊錶的功能，一般都是線性的
•Map：即是映射表，儲存的是鍵與值的對應關係
•Set：即集合的意思，主要用於排重資料及排序

先來看看List

List是用於存放線性資料的一種窗口，例如：用於數組的ArrayList和用於鍊錶的LinkedList。

ArrayList

這是一個數組列表，不過提供了自動擴容的功能，實現List接口，外部操作都是通過接口申明的方法訪問，這樣即安全又方便。

ArrayList的關鍵就是自動擴容，在物件初始化時可以設定初始容量，也可以依照預設的容量。如果對陣列大小沒有特別明確可以不指定初始大小，如果明確的話可以指定一個大小，這樣減少動態擴容時產生的卡頓。說到這就要說一下擴容是怎麼實現的了，看看下面的程式碼：

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在添加元素或一些容易檢查時會觸發的一個方法。主要過程：

1、得到數組的長度，並對其進行右移，這樣就相當於oldCapacity/2，得到新的長度

2、如果這個長度小於最小容量那麼直接就用最小容易

3 、如果大於了最大容易則取一個最大值，這裡會呼叫一個hugeCapacity方法，主要是比較minCapacity與MAX_ARRAY_SIZE的，如果minCapacity大於MAX_ARRAY_SIZE則取Integer.MAX_VALUE，否則就取MAX_ARRAY_SIZE，有趣的是MAX_ARRAYeger_VALUE，否則就取MAX_ARRAY_SIZE，有趣的是MAX_ARRAYeger_ZE_ARRAYeger_ZE_ARRAY .MAX_VALUE - 8;並不知道這樣做的意義是什麼

4、最後就是呼叫一個複製方法將現有數複製到一個新的陣列中。

因為有這個複製過程，如果陣列比較大，那麼老是觸發擴容當然就會出現卡頓的情況。所以如果一開始就知道最大值而且很容易成長到這個值，那麼開始初始化時就指定大小會有一定的作用。

LinkedList

這是針對鍊錶的工具類，鍊錶的優秀是添加刪除啥的比較快，但是查找會慢一些。

至於程式碼好像也沒什麼特別的，就是一串指針連結起來，當然Java中就用物件來代替，建立一個Node的對象，Node本身指向了前一個Node和後一個Node，這就是鍊錶的結構：

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

然後用兩個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;

看一個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.建立一個新的Node，將資料取到這個Node中，建立過程會將新Node的prev指向l，這樣就接上了鏈

3、然後將last指向這個新Node

4、然判斷l是否null，如果是null說明是空鍊錶，新node就是第一個元素，這樣first也要指向newNode

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

6、累加計數器

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

再來看看Map

Map是鍵與值做一個映射表的應用，主要的實現類別：HashMap,HashTable,TreeMap

HashMap和HashTable

使用hash演算法進行鍵值映射
HashMap和HashTable

使用hash演算法進行鍵值映射的就是HashMap， HashTable是帶有同步的執行緒安全性的類，它們兩主要的差別就是這個。原理也類似，都是透過桶子+鏈來組合實現。桶子是用來存Key的，而由於Hash碰撞的原因值需要用一個鍊錶來儲存。

•桶的意義在於高效，透過Hash計算可以一步定位

•鍊錶的意義在於訪問重複hash的數據

具體的原理以前寫過一篇《學習筆記：Hashtable和HashMap》🎜🎜只不過看JDK1.8的HashMap換了儲存結構，採用紅黑樹的結構，這樣可能是解決鍊錶查找效率問題吧？具體沒有細研究。 🎜🎜TreeMap🎜

看过TreeMap的代码后发现还是使用的树结构，红黑树。由于红黑树是有序的，所以自然带排序功能。当然也可通过comparator来指定比较方法来实现特定的排序。

因为采用了树结构存储那么添加和删除数据时会麻烦一些，看一下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、先是检查根节点是否存在，不存在说明是第一条数据，直接作为树的根

2、判断是否存在比较器，如果存在则使用比较器进行查找数据的存放位置，如果比较器返回结果小于0取左，大于0取右，否则直接替换当前节点的值

3、如果不存在比较器则key直接与节点的key比较，比较和前面方法一样

4、接下来就是在找到的parent上创建一个子节点，并放入左或者右子节点中

5、fixAfterInsertion是对节点进行着色

6、累加器处理

在remove操作时也会有点麻烦，除了删除数据外，还要重新平衡一下红黑树。

另外，TreeMap实现了NavigableMapb77a8d9c3c319e50d4b02a976b347910接口，所以也提供了对数据集合的一些返回操作。

最后看看Set

Set主要是两类应用：HashSet和TreeSet。

HashSet

字面意思很明确，使用了Hash的集合。这种集合的特点就是使用Hash算法存数据，所以数据不重复，存取都相对较快。怎么做到的呢？

public boolean add(E e) {
 
    return map.put(e, PRESENT)==null;
 
  }

原来是存在一个map对象中，再看map是个啥？

private transient HashMap<E,Object> map;

是个HashMap，了解HashMap的就明白，这样的数据是不会重复的。因为存入时是鼗对象本身作为Key来存的，所以在HashMap中只会存在一份。

了解了这点其他的东西就非常明白了。

TreeSet

这个集合是用于对集合进行排序的，也就是除了带有排重的能力外，还可以自带排序功能。只不过看了TreeSet的代码发现，其就是在TreeMap的基础实现的。更准确的说应该是NavigableMap的派生类。默认不指定map情况下TreeSet是以TreeMap为基础的。

public TreeSet() {
 
    this(new TreeMap<E,Object>());
 
  }

所以，这里可能更关注的是TreeSet是如何排重呢？看一下add的方法吧：

public boolean add(E e) {
 
    return m.put(e, PRESENT)==null;
 
  }

和HashSet有点类似，都是基于Map的特性来实现排重。确实简单而且有效。

以上就是小编为大家带来的多用多学之Java中的Set,List,Map详解全部内容了，希望大家多多支持PHP中文网~

更多多用多学之Java中的Set,List,Map详解相关文章请关注PHP中文网！