www.日韩一二三,九九精品免费在线观看,久久中文熟妇视频

開(kāi)始

這篇文章主要記錄下平常開(kāi)發(fā)中常用的數(shù)據(jù)結(jié)構(gòu)，會(huì)簡(jiǎn)單說(shuō)明每種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)、缺點(diǎn)、特點(diǎn)等等。

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

image

List

image

ArrayList

基于動(dòng)態(tài)數(shù)組集合，可以動(dòng)態(tài)的增加、刪除元素，動(dòng)態(tài)擴(kuò)容等，默認(rèn)初始容量10，超出上限會(huì)擴(kuò)容至：
int newCapacity = oldCapacity + (oldCapacity >> 1); 也就是原來(lái)容量的1.5倍。

優(yōu)點(diǎn)：按下標(biāo)索引速度快(O(1))。缺點(diǎn)：插入刪除會(huì)慢(O(n))。

一個(gè)容量10的ArrayList。

image

擴(kuò)容1.5倍后的樣子

image

ArrayList 擴(kuò)容源碼

/**
 * 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
- 基于鏈表的集合，是一個(gè)雙向鏈表，沒(méi)有初始化大小，也沒(méi)有擴(kuò)容的機(jī)制，會(huì)一直在前面或者后面新增Node。
- 優(yōu)點(diǎn)：便于存取，只要改變頭尾節(jié)點(diǎn)指向 (O(1))。缺點(diǎn)：索引慢，極端情況會(huì)出現(xiàn)從頭結(jié)點(diǎn)遍歷到最后一個(gè)節(jié)點(diǎn)的情況 (O(n))。
- 單向鏈表：每個(gè)節(jié)點(diǎn)只會(huì)指向下一個(gè)節(jié)點(diǎn)
  
  image
- 雙向鏈表：每個(gè)節(jié)點(diǎn)會(huì)保存上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)
  
  image
Vector
- 也是基于數(shù)組的一個(gè)集合，對(duì)一些操作數(shù)據(jù)的方法加了synchronized，可以看做是ArrayList一個(gè)同步、線程安全的版本
- 優(yōu)點(diǎn)：線程安全的。缺點(diǎn)：同步必然會(huì)導(dǎo)致效率慢。
小結(jié)
- 上面幾種集合都屬于線性數(shù)據(jù)結(jié)構(gòu)，也是有序，元素之間都有關(guān)聯(lián)關(guān)系。
- 基于數(shù)組的：在分配內(nèi)存時(shí)是一塊規(guī)整的內(nèi)存，所有數(shù)據(jù)都緊鄰著。(也有說(shuō)數(shù)組不屬于線性結(jié)構(gòu)的，希望大佬指正)
- 基于鏈表的：雖然在內(nèi)存里都是不連續(xù)的，但是每個(gè)節(jié)點(diǎn)都會(huì)保留下一個(gè)節(jié)點(diǎn)的引用。

Map

Map 是一種把鍵對(duì)象和值對(duì)象映射的集合，它的每一個(gè)元素都包含一對(duì)鍵對(duì)象和值對(duì)象。 Map沒(méi)有繼承于Collection接口。

image

HashMap

HashMap 底層是數(shù)組+鏈表(jdk1.8是數(shù)組+鏈表/紅黑樹(shù))，HashMap可能也是應(yīng)用最多的數(shù)據(jù)結(jié)構(gòu)了。

初始容量

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

負(fù)載因子：據(jù)說(shuō)0.75是在時(shí)間和空間上一個(gè)較為合適的數(shù)，過(guò)高容易哈希碰撞，過(guò)低容易浪費(fèi)空間

/**
 * 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;

擴(kuò)容機(jī)制：

當(dāng)size > (capacity * load factor)時(shí)會(huì)觸發(fā)擴(kuò)容(newCap = oldCap << 1)。源碼resize() 方法有點(diǎn)長(zhǎng)，這里就不貼了。

何時(shí)轉(zhuǎn)換紅黑樹(shù)：

      //條件1：當(dāng)鏈表長(zhǎng)度>=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ù)擴(kuò)容
          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);
          }
      }

何時(shí)退化成鏈表：

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

HashMap 鏈表紅黑樹(shù)轉(zhuǎn)換過(guò)程

image

HashTable

其實(shí)就是HashMap的一個(gè)線程安全版本，像Vector和ArrayList的關(guān)系一樣，對(duì)內(nèi)部的方法都加了synchronized關(guān)鍵字修飾。
```
 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);
         }
     }
```
- 缺點(diǎn)：因?yàn)椴捎?code>synchronized保證同步，每次都會(huì)鎖住整個(gè)map，所以高并發(fā)線程在爭(zhēng)奪同一把鎖的時(shí)候性能急劇下降。

TreeMap

平常開(kāi)發(fā)中用的不多，是一個(gè)紅黑樹(shù)版本的map，實(shí)現(xiàn)了NavigableMap<K,V>并且NavigableMap又繼承了SortedMap<K,V>類(lèi)，SortedMap接口有一個(gè)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> { //紅黑樹(shù)結(jié)構(gòu)
          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的結(jié)構(gòu)

image

特點(diǎn)：采用紅黑樹(shù)實(shí)現(xiàn)，是一個(gè)有序的map。

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

image
- 分段鎖思想：
  
  都知道HashTable效率低下的原因是因?yàn)檎麄€(gè)容器只有一把鎖，多線程爭(zhēng)搶同一把鎖導(dǎo)致。
  ConcurrentHashMap分段鎖指得是將數(shù)據(jù)分成一個(gè)個(gè)的Segment<K,V>，每個(gè)Segment又繼承ReentrantLock，這樣一個(gè)map容器就會(huì)有多個(gè)Lock，每個(gè)Lock鎖不同的數(shù)據(jù)段，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)的時(shí)候，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)。
```
      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. 因?yàn)榈讓邮荋ashMap，so 1.8之后也變成了數(shù)組+鏈表/紅黑樹(shù)。
  
  2. 1.8之后放棄了分段鎖，采用了synchronized+CAS來(lái)保證并發(fā)。
- 1.8為何放棄分段鎖：
  
  1. 我認(rèn)為主要是1.8對(duì)synchronized進(jìn)行了優(yōu)化(偏向鎖、輕量級(jí)鎖、自旋鎖、自適宜自旋)
  2. 加入多個(gè)分段鎖浪費(fèi)內(nèi)存空間。
  3. 生產(chǎn)環(huán)境中， map在放入時(shí)競(jìng)爭(zhēng)同一個(gè)鎖的概率非常小，分段鎖反而會(huì)造成更新等操作的長(zhǎng)時(shí)間等待。
  
  image

Set

HashSet

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

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

    private transient HashMap<E,Object> map; // 底層就是一個(gè)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)一用一個(gè)static final修飾的Object對(duì)象
    public boolean add(E e) {
       return map.put(e, PRESENT)==null;
   }
}

LinkedHashSet

LinkedHashSet 基于LinkedHashMap實(shí)現(xiàn)，繼承自HashSet，可以看出是一個(gè)有序的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

總結(jié)

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

JAVA常用數(shù)據(jù)結(jié)構(gòu)

JAVA常用數(shù)據(jù)結(jié)構(gòu)

開(kāi)始

List

Map

Set

Stack

Queue

總結(jié)

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

JAVA常用數(shù)據(jù)結(jié)構(gòu)

開(kāi)始

List

Map

Set

Stack

Queue

總結(jié)

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av