天天看點

Java集合類面試總結:

1、String、StringBuffer、StringBuilder 的差別是什麼?String為什麼是不可變的?

         ①String是字元串常量,StringBuffer和StringBuilder都是字元串變量。後兩者的字元内容可變,而因為在JDK中String類被聲明為一個final類,建立後内容不可變。②StringBuffer是線程安全的,而StringBuilder是非線程安全的。

         ps:線程安全會帶來額外的系統開銷,是以StringBuilder的效率比StringBuffer高。如果對系統中的線程是否安全很掌握,可用StringBuffer,線上程不安全處加上關鍵字Synchronize。

        String為什麼是不可變的:什麼是不可變的?一個對象在建立完成後,不能再改變它的狀态。(即不能改變對象内的成員變量)---String的屬性被final修飾、私有的并且沒有提供修改方法。 (主要字段是char數組,雖然被final修飾但數組是可變的,私有保證了不被修改但還是可以通過反射來改變String,但一般不這樣做)

       ---為什麼設計成不可變的?字元串常量池的需要,提升效率和減少記憶體配置設定;安全性考慮,防止被意外修改;作為hashmap、hashtable等hash類型的資料key的必要。

2.set接口:

         無序,不能重複。沒有get方法,想要擷取元素,需要使用疊代器來實作,常用實作類是HashSet。

        HashSet:實作Set接口,底層是一個hashmap,value存的是空的object;不能保證元素的排列順序,順序有可能發生變化,不是同步的,集合元素可以是null,但隻能放入一個null

         LinkedHashSet:繼承自HashSet,底層實作是LinkedHashMap。維護了一個雙連結清單來記錄插入的順序,使元素按照插入順序儲存。基本方法的複雜度為O(1)。

         TreeSet:是SortedSet接口的唯一實作類,可以確定集合元素處于排序狀态,底層實作是TreeMap。

3. HashSet與HashMap差別:

       HashSet底層是一個hashmap,value存的是空的object;

      HashMap實作了Map接口 ,HashSet實作了Set接口;

      HashMap儲存鍵值對 ,HashSet僅僅存儲對象;

      HashMap使用put()方法将元素放入map中 ,HashSet使用add()方法将元素放入set中;

      HashMap中使用鍵對象來計算hashcode值 ,HashSet使用成員對象來計算hashcode值;

      HashMap比較快,因為是使用唯一的鍵來擷取對象 ,HashSet較HashMap來說比較慢;

4、Vector,ArrayList, LinkedList的差別是什麼?

        List:有序的,可以重複的。

        ①Vector、ArrayList都是以類似數組的形式存儲在記憶體中,LinkedList則以連結清單的形式進行存儲。②List中的元素有序、允許有重複的元素,Set中的元素無序、不允許有重複元素。③Vector線程同步,ArrayList、LinkedList線程不同步。④LinkedList适合指定位置插入、删除操作,不适合查找;ArrayList、Vector适合查找,不适合指定位置的插入、删除操作。⑤ArrayList預設大小為10,在元素填滿容器時會按1.5倍擴容【因為位運算】(擴容後的大小= 原始大小+原始大小/2 + 1),LinkedList維護的是連結清單,沒有擴容機制,而Vector則是100%,是以ArrayList更節省空間。

/*ArrayLst的擴容操作*/
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);//預設的相當于1.5倍
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;//如果還是不夠,就把需要的值指派
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);//判斷newCapacity大容量情況,考慮minCapacity
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
           
//Vector擴容操作
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); //擴大1倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
           

        【LinkedList使用普通for循環周遊慢的原因,LinkedList在get任何一個位置的資料的時候,都會把前面的資料走一遍。周遊的時間複雜度為O(N2)】

        【Vector為什麼是線程安全的?--->Vector在一些必要的方法上都加了 synchronized關鍵字,Vector中有一個 elements()方法用來傳回一個 Enumeration,以匿名内部類的方式實作的:】

public Enumeration<E> elements() {
        return new Enumeration<E>() {
            int count = 0;
            public boolean hasMoreElements() {
                return count < elementCount;
            }
            public E nextElement() {
                synchronized (Vector.this) {
                    if (count < elementCount) {
                        return elementData(count++);
                    }
                }
                throw new NoSuchElementException("Vector Enumeration");
            }
        };
    }
           

       【ArrayList會自動擴容,但不會自動縮容,如何縮容? ArrayList裡面有一個方法可以縮小容積,trimToSize() 】

/**
     * Trims the capacity of this <tt>ArrayList</tt> instance to be the
     * list's current size.  An application can use this operation to minimize
     * the storage of an <tt>ArrayList</tt> instance.
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }
           

5.HashTable, HashMap,TreeMap差別?

        Map是Java.util包中的另一個接口,屬于集合類,鍵值對方式存儲,鍵唯一,值不唯一,對map集合周遊時先得到鍵的set集合,對set集合周遊,得到相應的值。常用實作類:HashMap、Hashtable、LinkedHashMap、TreeMap

        哈希表的實作,存儲方式:哈希表,也叫散清單, 是根據關鍵碼值(Key value)而直接進行通路的資料結構。具體通過把Key通過哈希函數轉換成一個整型數字,然後就将該數字對數組長度進行取餘,取餘結果就當作數組的下标,将value存儲在以該數字為下标的數組空間裡。

       哈希沖突:當關鍵字集合很大時,關鍵字值不同的元素可能會映像到哈希表的同一位址上。解決沖突的方法有鍊位址法(将所有哈希位址為i的元素構成一個同義詞的單連結清單,查找、插入、删除都在同義連結清單中進行)、再哈希法(同時構造多個不同的哈希函數)、開放定址法(再散列法,當管關鍵字key的哈希位址p出現沖突時,以此p為基礎,産生另一個哈希位址p1,如果仍然有沖突,則重複尋找直到找出一個不沖突的哈希位址)。

       HashTable、HashMap差別:①HashTable線程安全,HashMap非線程同步。②HashTable不允許<鍵,值>有空值,HashMap允許<鍵,值>有空值。③HashTable使用Enumeration,HashMap使用Iterator。④HashTable中hash數組預設大小是11,增加方式的old*2+1,HashMap中hash數組的預設大小是16,增長方式一定是2的指數倍。

     TreeMap:TreeMap是一個有序的key-value集合,基于紅黑樹實作,繼承于AbstractMap,實作了Cloneable、Serializable接口,可以被克隆,支援序列化;預設升序排列,可以通過重寫compare方法來改變,線程不安全。

      HashMap如何工作:HashMap基于哈希原理,通過put()和get()方法儲存和擷取對象。調用put()方法時,首先判斷key是否為空,如果為空,放入到table[0]的位置(周遊table[0]的連結清單的每個節點Entry,如果發現其中存在節點Entry的key為null,就替換新的value,然後傳回舊的value,如果沒發現key等于null的節點Entry,就增加新的節點),然後調用鍵對象的hashCode()方法來計算hashcode,然後找到bucket位置來儲存值對象。【根據hash值和數組長度算出索引值 h & (length-1);,確定算出來的索引是在數組大小範圍内,不會超出;比使用取模方式效率更高】,如果該位置key存在,替換新的value值,如果不存在,插入到頭結點中。這裡會涉及到擴容問題,容量擴大兩倍。使用LinkedList來解決碰撞問題,當發生碰撞了,對象将會儲存在LinkedList 的下一個節點中。 HashMap在每個LinkedList節點中儲存鍵值對對象。擷取對象時,調用get()方法,通過計算鍵對象的hash值,找到bucket位置,通過鍵對象的equals()方法找到正确的鍵值對,然後傳回值對象。

      HashMap,TreeMap差別:①TreeMap,SortMap接口,基于紅黑樹,HashMap基于哈希散清單實作;②TreeMap 預設按鍵的升序排序,HashMap随機存儲;③TreeMap鍵、值都不能為null,HashMap隻允許鍵、值均為null;④兩者都是線程不安全;5.HashMap效率要比TreeMap高。

      HashMap的實作機制:①維護一個每個元素是一個連結清單的數組,而且連結清單中的每個節點是一個Entry[]鍵值對的資料結構。②“連結清單散列”的資料結構,實作了數組+連結清單的特性,底層結構是數組,數組中的每一項是一條連結清單;查找快,插入删除也快。 ③對于每個key,他對應的數組索引下标是 int i = hash(key.hashcode)&(len-1); ④每個新加入的節點放在連結清單首,然後該新加入的節點指向原連結清單首。

      源碼分析,參考:https://www.cnblogs.com/ITtangtang/p/3948406.html#a6

      HashMap的内部結構是hash+連結清單,JDK1.8 以後當超過8 時轉化為紅黑樹,當小于6 時重新變為連結清單。當插入新元素時,對于紅黑樹的判斷如下:判斷table[i] 是否為treeNode,即table[i] 是否是紅黑樹,如果是紅黑樹,則直接在樹中插入鍵值對,否則轉向下面;周遊table[i],判斷連結清單長度是否大于8,大于8的話把連結清單轉換為紅黑樹,在紅黑樹中執行插入操作,否則進行連結清單的插入操作;周遊過程中若發現key已經存在直接覆寫value即可;

public V put(K key, V value) {
     // 若“key為null”,則将該鍵值對添加到table[0]中。
         if (key == null) 
            return putForNullKey(value);
     // 若“key不為null”,則計算該key的哈希值,然後将其添加到該哈希值對應的連結清單中。
         int hash = hash(key.hashCode());
     //搜尋指定hash值在對應table中的索引
         int i = indexFor(hash, table.length);
     // 循環周遊Entry數組,若“該key”對應的鍵值對已經存在,則用新的value取代舊的value。然後退出!
         for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
             Object k;
              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同則覆寫并傳回舊值
                  V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
              }
         }
     //修改次數+1
         modCount++;
     //将key-value添加到table[i]處
     addEntry(hash, key, value, i);
     return null;
}
           

  HashMap 包含如下幾個構造器:

   HashMap():建構一個初始容量為 16,負載因子為 0.75 的 HashMap。

   HashMap(int initialCapacity):建構一個初始容量為 initialCapacity,負載因子為 0.75 的 HashMap。

   HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的負載因子建立一個 HashMap。

   HashMap的基礎構造器HashMap(int initialCapacity, float loadFactor)帶有兩個參數,它們是初始容量initialCapacity和加載因子loadFactor。

   initialCapacity:HashMap的最大容量,即為底層數組的長度。

   loadFactor:負載因子loadFactor定義為:散清單的實際元素數目(n)/ 散清單的容量(m)。

   【hashmap 容量為什麼是2 的幂次? --->友善取模和擴容,這樣可以直接進行位操作計算。(首先,length為2的整數次幂的話,h&(length-1)就相當于對length取模,這樣便保證了散列的均勻,同時也提升了效率;其次,length為2的整數次幂的話,為偶數,這樣length-1為奇數,奇數的最後一位是1,這樣便保證了h&(length-1)的最後一位可能為0,也可能為1(這取決于h的值),即與後的結果可能為偶數,也可能為奇數,這樣便可以保證散列的均勻性,而如果length為奇數的話,很明顯length-1為偶數,它的最後一位是0,這樣h&(length-1)的最後一位肯定為0,即隻能為偶數,這樣任何hash值都隻會被散列到數組的偶數下标位置上,這便浪費了近一半的空間,是以,length取2的整數次幂,是為了使不同hash值發生碰撞的機率較小,這樣就能使元素在哈希表中均勻地散列。)】

      使用的是2次幂的擴充(指長度擴為原來2倍),是以,經過rehash之後,元素的位置要麼是在原位置,要麼是在原位置再移動2次幂的位置。1.8中不需要像JDK1.7的實作那樣重新計算hash,隻需要看看原來的hash值新增的那個bit是1還是0就好了,是0的話索引沒變,是1的話索引變成“原索引+oldCap”  ( JDK1.8)

Java集合類面試總結:

     【 當兩個不同的鍵對象的hashcode相同時會發生什麼?--->它們會儲存在同一個bucket位置的LinkedList中。鍵對象的equals()方法用來找到鍵值對。】

     【如果兩個鍵的hashcode相同,你如何擷取值對象?---> 調用get()方法,HashMap會使用鍵對象的hashcode找到bucket位置,然後調用keys.equals()方法去找到LinkedList中正确的節點,最終找到要找的值對象。】

     【如果HashMap的大小超過了負載因子定義的容量,怎麼辦?----->HashMap預設的初始容量是16,負荷系數是0.75(why?---如果負載因子越大,對空間的利用更充分,後果是查找效率的降低;如果負載因子太小,那麼散清單的資料将過于稀疏,對空間造成嚴重浪費),閥值是為負荷系數乘以容量,無論何時我們嘗試添加一個entry,如果map的大小比閥值大的時候,HashMap會對map的内容進行重新哈希,且使用更大的容量。容量總是2的幂。】

      【重新調整HashMap大小存在什麼問題?--->resize後的HashMap容量是容量的兩倍;當多線程的情況下,當兩個線程同時開始擴容時,有可能出現環形連結清單,陷入死循環。(HashMap在高并發下如果沒有處理線程安全會有陷入死循環這樣的安全隐患)】

void resize(int newCapacity) {
          Entry[] oldTable = table;
          int oldCapacity = oldTable.length;
          if (oldCapacity == MAXIMUM_CAPACITY) {
              threshold = Integer.MAX_VALUE;
              return;
         }
  
         Entry[] newTable = new Entry[newCapacity];
         transfer(newTable);//用來将原先table的元素全部移到newTable裡面
         table = newTable;  //再将newTable指派給table
         threshold = (int)(newCapacity * loadFactor);//重新計算臨界值
     }
           

    【可以使用自定義的對象作為鍵嗎?---可以使用任何對象作為鍵,隻要它遵守了equals()和hashCode()方法的定義規則,并且當對象插入到Map中之後将不會再改變了。如果這個自定義對象時不可變的,那麼它已經滿足了作為鍵的條件,因為當它建立之後就已經不能改變了。】

    【可以使用CocurrentHashMap代替HashTable嗎?----ConcurrentHashMap當然可以代替HashTable,但是HashTable提供更強的線程安全性】

     【ConcurrentHashMap多線程下比HashTable效率更高-- HashTable使用一把鎖處理并發問題,當有多個線程通路時會導緻阻塞;ConcurrentHashMap使用分段,每個部分配置設定一把鎖,這樣就可以支援多線程通路。】

    【一緻性hash算法--将整個哈希值空間組織成一個虛拟的圓環,解決了增減伺服器導緻的資料散列問題、分布式環境下負載均衡問題。】

      【為什麼重寫hashcode、equals方法?--Hashmap的key可以是任何類型的對象,例如User這種對象,為了保證兩個具有相同屬性的user的hashcode相同,我們就需要改寫hashcode方法,比方把hashcode值的計算與User對象的id關聯起來,那麼隻要user對象擁有相同id,那麼他們的hashcode也能保持一緻了,這樣就可以找到在hashmap數組中的位置了。如果這個位置上有多個元素,還需要用key的equals方法在對應位置的連結清單中找到需要的元素,是以隻改寫了hashcode方法是不夠的,equals方法也需要改寫。】

ConcurrentHashMap源碼分析:

     JDK1.7版本中Segment繼承ReentrantLock用來充當鎖的角色,每個 Segment 對象守護每個散列映射表的若幹個桶;HashEntry 用來封裝映射表的鍵 / 值對;底層采用 數組+連結清單 的存儲結構。

    JDK1.8版本中已經抛棄了Segment分段鎖機制,利用CAS+Synchronized來保證并發更新的安全, Node用來存儲鍵值對,底層采用 數組+連結清單+紅黑樹 的存儲結構。

4.fail-fast:

        java集合(Collection)中的一種錯誤機制。當多個線程對同一個集合的内容進行操作時,就可能會産生fail-fast事件。

        例如:當某一個線程A通過iterator去周遊某集合的過程中,若該集合的内容被其他線程所改變了;那麼線程A通路集合時,就會抛出ConcurrentModificationException異常,産生fail-fast事件。

        這一政策在源碼中的實作是通過modCount域,modCount顧名思義就是修改次數,對HashMap内容的修改都将增加這個值,那麼在疊代器初始化過程中會将這個值賦給疊代器的expectedModCount。

5.Arrays.sort()與Collections.sort():

       Arrays.sort() 算法是一個經過調優的快速排序,此算法在很多資料集上提供N*log(N)的性能,這導緻其他快速排序會降低二次型性能。

       Collections.sort()算法是一個經過修改的合并排序算法。此算法可提供保證的N*log(N)的性能,此實作将指定清單轉儲到一個數組中,然後再對數組進行排序,在重置數組中相應位置處每個元素的清單上進行疊代。這避免了由于試圖原地對連結清單進行排序而産生的n2 log(n)性能。

繼續閱讀