天天看點
傳回

Java 集合（一）

集合類介紹

  • ArrayList（非線程安全）

    • ArrayList底層采用數組存放資料
    • 建立時可以指定初始容量的大小，若不指定則預設是10.
    • ArrayList擴容是1.5倍的增長 
    int newCapacity = oldCapacity + (oldCapacity >> );
//将數組内容拷貝到新建立的數組中，并傳回新建立數組的引用
elementData = Arrays.copyOf(elementData, newCapacity);
    • arrayList不是線程安全的容器
    • 當數組元素已經達到數組容量時才會發生擴容

  • Vector（線程安全）

    • Vector與ArrayList實作基本相同，當時Vector是線程安全的，每個操作方法中加了synchronized關鍵字，屬于線程安全的容器
    • 建立Vector時可以指定初始容量，也可以指定發生擴容時擴容的大小。若沒指定初始容量大小預設是10；若沒有指定擴容的大小，預設是兩倍增長，否則 
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);

  • LinkedList（非線程安全）

    • LinkedList底層實作是通過連結清單，每個元素是一個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;
        }
    }
    • 定義兩個變量first、last分别指向連結清單的頭結點和尾結點
    • 實作了Queue 接口
      1. offer(E e) 操作調用add方法，将元素插入隊列的尾部
        Java 集合（一）
        添加元素e之後，last會緊接着指向新添加的元素e
        Java 集合（一）
      2. poll操作删除隊列頭元素，删除的是first結點
      3. element操作傳回隊列頭結點，即first結點，如果first==null 抛出異常
      4. peek操作傳回隊列頭結點，即first結點，如果first==null 則傳回null
    • 實作了Stack功能
      1. push添加元素，注意是在連結清單的頭結點處插入元素
        Java 集合（一）
      2. pop 操作是删除連結清單的頭結點
      3. peek 操作傳回連結清單的頭結點

  • HashMap（非線程安全）

    • HashMap底層由一個EntrySet數組構成，每個EntrySet都是一個連結清單 
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
         ……
    }
    Java 集合（一）
    • loadFactor，加載因子，預設值是0.75。當map中的元素個數size>=table.length*loadFactor時，hashMap 會進行擴容。如果loadFactor過小，則空間浪費比較嚴重；若loadFactor過大，則hashmap沖突的機率會加大，造成一些EntrySet連結清單過長。
    • 建立hashMap時可以指定初始容量和加載因子，預設初始容量為16，加載因子為0.75
    • 計算元素o 在table數組中的下标，其中h是根據o.key計算的hash值，length是指數組的長度 
    static int indexFor(int h, int length) {
        return h & (length-);
    }
    • hashMap中的key和value都可以為null，當key==null時，該元素會放在table下标為0的位置上。 
    if (key == null)
    return putForNullKey(value);
           
    private V putForNullKey(V value) {
    for (Entry<K,V> e = table[]; e != null; e = e.next) {
            //如果map中原來已經存在key值為null的元素，則更新value值
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        // hash值為0，key=null  value=value  在table中位置index=0
        addEntry(, null, value, );
        return null;
}
    • map中添加新元素時，是将元素添加在連結清單頭。 
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //threshold = table.length * loadFactor  判斷是否需要擴容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize( * table.length);
            hash = (null != key) ? hash(key) : ;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
           
    //建立一個新的結點，插傳入連結表頭。即建立新元素時是插傳入連結表頭的。
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        //table[bucketIndex]表示的是連結清單頭，連結清單頭指向了建立的結點，同時新節點的next指針指向          了原來的連結清單頭結點。
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
    • map擴容是原來table長度的2倍。擴容時，需要周遊原來的map，将每個元素重新計算hash值和在新table的中位置，再放入新的table中。 
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ?  : hash(e.key);
                }
                //計算元素在新table中的位置
                int i = indexFor(e.hash, newCapacity);
                //newTable[i]是其中一個連結清單的連結清單頭
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

集合類繼承關系圖 和常用API

Java 集合（一）

常用的API:

ArrayList：

//List尾部添加元素
boolean add(E e);
//在index位置添加元素
public void add(int index,E element);
//移除元素o
boolean remove(Object o);
//移除下标index的元素
public E remove(int index);
//清空清單
public void clear();
//添加集合中的全部元素
public boolean addAll(Collection<? extends E> c);
//傳回list的周遊
public Iterator<E> iterator();
//是否包含元素
public boolean contains(Object o);
//将下标為index元素替換
public E set(int index,E element)

Queue：

//添加元素
boolean add(E e);
//擷取并移除隊列頭,此隊列為空時将抛出一個異常。
E remove();
//擷取并移除此隊列的頭，如果此隊列為空，則傳回 null。
E poll();
//擷取，但是不移除此隊列的頭。此方法與 peek 唯一的不同在于：此隊列為空時将抛出一個異常。
E element();
//擷取但不移除此隊列的頭；如果此隊列為空，則傳回 null。
E peek();

Set:

//添加元素
boolean add(E e);
//移除元素
boolean remove(Object o);
//添加所有集合元素
boolean addAll(Collection<? extends E> c);
//清空集合
void clear();
//傳回set的疊代器
Iterator<E> iterator();

Stack: 繼承自vector，是線程安全的

//把項壓入堆棧頂部。
public E push(E item);
//移除棧頂元素
public E pop();
//傳回棧頂元素，但是不删除
public E peek();
//測試棧是否為空
public boolean empty();
//傳回元素在棧中的位置，以1為基數，-1表示不存在
public int search(Object o);

Map集合繼承關系圖：

Java 集合（一）
JAVA知識點 java 集合 hashmap arraylist
上一篇: 記憶體管理相關知識
下一篇: Tcp Flags for 3 way handshake

繼續閱讀