溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

03.Java數(shù)據(jù)結(jié)構(gòu)問題

發(fā)布時間:2020-07-19 11:51:11 來源:網(wǎng)絡 閱讀:215 作者:楊充 欄目:移動開發(fā)
目錄介紹
  • 3.0.0.1 在arrayList中System.arraycopy()和Arrays.copyOf()方法區(qū)別聯(lián)系?System.arraycopy()和Arrays.copyOf()代碼說明?
  • 3.0.0.2 SparseArray基本介紹,相比HashMap為什么性能會好?
  • 3.0.0.3 Arrays和Collections 對于sort的不同實現(xiàn)原理?說一說它們的區(qū)別……
  • 3.0.0.4 Java集合框架中有哪些類?都有什么特點?Java集合的快速失敗機制 “fail-fast”?
  • 3.0.0.5 ArrayList,Vector和LinkList的區(qū)別,底層分別是怎么實現(xiàn)的,存儲空間是如何擴容的?什么是加載因子?
  • 3.0.0.6 如何理解ArrayList的擴容消耗?Arrays.asList方法后的List可以擴容嗎?ArrayList如何序列化?
  • 3.0.0.7 如何理解list集合讀寫機制和讀寫效率?什么是CopyOnWriteArrayList,它與ArrayList有何不同?
  • 3.0.1.0 HashSet和TreeSet的區(qū)別?是如何保證唯一值的,底層怎么做到的?
  • 3.0.1.5 HashMap和Hashtable的區(qū)別?HashMap在put、get元素的過程?體現(xiàn)了什么數(shù)據(jù)結(jié)構(gòu)?
  • 3.0.1.6 如何保證HashMap線程安全?底層怎么實現(xiàn)的?HashMap是有序的嗎?如何實現(xiàn)有序?
  • 3.0.1.7 HashMap存儲兩個對象的hashcode相同會發(fā)生什么?如果兩個鍵的hashcode相同,你如何獲取值對象?
  • 3.0.1.8 HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標?
  • 3.0.1.9 為什么HashMap中String、Integer這樣的包裝類適合作為K?為啥不用其他作key值?
  • 3.0.2.0 HashMap是如何擴容的?如何理解HashMap的大小超過了負載因子定義的容量?重新調(diào)整HashMap大小存在什么問題嗎?

好消息

  • 博客筆記大匯總【15年10月到至今】,包括Java基礎(chǔ)及深入知識點,Android技術(shù)博客,Python學習筆記等等,還包括平時開發(fā)中遇到的bug匯總,當然也在工作之余收集了大量的面試題,長期更新維護并且修正,持續(xù)完善……開源的文件是markdown格式的!同時也開源了生活博客,從12年起,積累共計500篇[近100萬字],將會陸續(xù)發(fā)表到網(wǎng)上,轉(zhuǎn)載請注明出處,謝謝!
  • 鏈接地址:https://github.com/yangchong211/YCBlogs
  • 如果覺得好,可以star一下,謝謝!當然也歡迎提出建議,萬事起于忽微,量變引起質(zhì)變!所有博客將陸續(xù)開源到GitHub!
3.0.0.1 在arrayList中System.arraycopy()和Arrays.copyOf()方法區(qū)別聯(lián)系?System.arraycopy()和Arrays.copyOf()代碼說明?
  • System.arraycopy()和Arrays.copyOf()方法區(qū)別?
    • 比如下面<font color="red">add(int index, E element)</font>方法就很巧妙的用到了<font color="red">arraycopy()方法</font>讓數(shù)組自己復制自己實現(xiàn)讓index開始之后的所有成員后移一個位置:
      /**
       * 在此列表中的指定位置插入指定的元素。 
       * 先調(diào)用 rangeCheckForAdd 對index進行界限檢查;然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大;
       * 再將從index開始之后的所有成員后移一個位置;將element插入index位置;最后size加1。
       */
      public void add(int index, E element) {
          rangeCheckForAdd(index);
          ensureCapacityInternal(size + 1); 
          //arraycopy()方法實現(xiàn)數(shù)組自己復制自己
          //elementData:源數(shù)組;index:源數(shù)組中的起始位置;elementData:目標數(shù)組;index + 1:目標數(shù)組中的起始位置; size - index:要復制的數(shù)組元素的數(shù)量;
          System.arraycopy(elementData, index, elementData, index + 1, size - index);
          elementData[index] = element;
          size++;
      }
    • 如toArray()方法中用到了copyOf()方法
      /**
       *以正確的順序(從第一個到最后一個元素)返回一個包含此列表中所有元素的數(shù)組。 
       *返回的數(shù)組將是“安全的”,因為該列表不保留對它的引用。 (換句話說,這個方法必須分配一個新的數(shù)組)。
       *因此,調(diào)用者可以自由地修改返回的數(shù)組。 此方法充當基于陣列和基于集合的API之間的橋梁。
       */
      public Object[] toArray() {
      //elementData:要復制的數(shù)組;size:要復制的長度
          return Arrays.copyOf(elementData, size);
      }
    • 兩者聯(lián)系與區(qū)別
      • 看了上面的兩者源代碼可以發(fā)現(xiàn)copyOf()內(nèi)部調(diào)用了System.arraycopy()方法
      • 技術(shù)博客大總結(jié)
      • 區(qū)別:
        • 1.arraycopy()需要目標數(shù)組,將原數(shù)組拷貝到你自己定義的數(shù)組里,而且可以選擇拷貝的起點和長度以及放入新數(shù)組中的位置
        • 2.copyOf()是系統(tǒng)自動在內(nèi)部新建一個數(shù)組,并返回該數(shù)組。
  • System.arraycopy()和Arrays.copyOf()代碼說明?

    • 使用System.arraycopy()方法

      public static void main(String[] args) {
          // TODO Auto-generated method stub
          int[] a = new int[10];
          a[0] = 0;
          a[1] = 1;
          a[2] = 2;
          a[3] = 3;
          System.arraycopy(a, 2, a, 3, 3);
          a[2]=99;
          for (int i = 0; i < a.length; i++) {
              System.out.println(a[i]);
          }
      }
      
      //結(jié)果:
      //0 1 99 2 3 0 0 0 0 0 
    • 使用Arrays.copyOf()方法。技術(shù)博客大總結(jié)
      public static void main(String[] args) {
          int[] a = new int[3];
          a[0] = 0;
          a[1] = 1;
          a[2] = 2;
          int[] b = Arrays.copyOf(a, 10);
          System.out.println("b.length"+b.length);
          //結(jié)果:
          //10
      }
    • 得出結(jié)論
      • arraycopy() 需要目標數(shù)組,將原數(shù)組拷貝到你自己定義的數(shù)組里或者原數(shù)組,而且可以選擇拷貝的起點和長度以及放入新數(shù)組中的位置 copyOf() 是系統(tǒng)自動在內(nèi)部新建一個數(shù)組,并返回該數(shù)組。
3.0.0.2 SparseArray基本介紹,相比HashMap為什么性能會好?
  • 位于android.util,Android 中的數(shù)據(jù)結(jié)構(gòu),針對移動端做了優(yōu)化,在數(shù)據(jù)量比較少的情況下,性能會好過 HashMap,類似于 HashMap,key:int ,value:object 。
  • 1.key 和 value 采用數(shù)組進行存儲。存儲 key 的數(shù)組是 int 類型,不需要進行裝箱操作。提供了速度。
  • 2.采用二分查找法,在插入進行了排序,所以兩個數(shù)組是按照從小到大進行排序的。
  • 3.在查找的時候,進行二分查找,數(shù)據(jù)量少的情況下,速度比較快。
3.0.0.3 Arrays和Collections 對于sort的不同實現(xiàn)原理?說一說它們的區(qū)別……
  • 1、Arrays.sort()
    • 該算法是一個經(jīng)過調(diào)優(yōu)的快速排序,此算法在很多數(shù)據(jù)集上提供N*log(N)的性能,這導致其他快速排序會降低二次型性能。
  • 2、Collections.sort()
    • 該算法是一個經(jīng)過修改的合并排序算法(其中,如果低子列表中的最高元素效益高子列表中的最低元素,則忽略合并)。此算法可提供保證的N*log(N)的性能,此實現(xiàn)將指定列表轉(zhuǎn)儲到一個數(shù)組中,然后再對數(shù)組進行排序,在重置數(shù)組中相應位置處每個元素的列表上進行迭代。
  • 它們的區(qū)別
    • 技術(shù)博客大總結(jié)
3.0.0.4 Java集合框架中有哪些類?都有什么特點?Java集合的快速失敗機制 “fail-fast”?
  • 可將Java集合框架大致可分為Set、List、Queue 和Map四種體系
    • Set:代表無序、不可重復的集合,常見的類如HashSet、TreeSet
    • List:代表有序、可重復的集合,常見的類如動態(tài)數(shù)組ArrayList、雙向鏈表LinkedList、可變數(shù)組Vector
    • Map:代表具有映射關(guān)系的集合,常見的類如HashMap、LinkedHashMap、TreeMap
    • Queue:代表一種隊列集合
  • Java集合的快速失敗機制 “fail-fast”
    • 技術(shù)博客大總結(jié)
    • java集合的一種錯誤檢測機制,當多個線程對集合進行結(jié)構(gòu)上的改變的操作時,有可能會產(chǎn)生 fail-fast 機制。
      • 例如:假設(shè)存在兩個線程(線程1、線程2),線程1通過Iterator在遍歷集合A中的元素,在某個時候線程2修改了集合A的結(jié)構(gòu)(是結(jié)構(gòu)上面的修改,而不是簡單的修改集合元素的內(nèi)容),那么這個時候程序就會拋出 ConcurrentModificationException 異常,從而產(chǎn)生fail-fast機制。
    • 原因:
      • 迭代器在遍歷時直接訪問集合中的內(nèi)容,并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內(nèi)容發(fā)生變化,就會改變modCount的值。每當?shù)魇褂胔ashNext()/next()遍歷下一個元素之前,都會檢測modCount變量是否為expectedmodCount值,是的話就返回遍歷;否則拋出異常,終止遍歷。
    • 解決辦法:
      • 1.在遍歷過程中,所有涉及到改變modCount值得地方全部加上synchronized。
      • 2.使用CopyOnWriteArrayList來替換ArrayList
3.0.0.5 ArrayList,Vector和LinkList的區(qū)別,底層分別是怎么實現(xiàn)的?存儲空間是如何擴容的?什么是加載因子?
  • ArrayList
    • ArrayList的底層結(jié)構(gòu)是數(shù)組,可用索引實現(xiàn)快速查找;是動態(tài)數(shù)組,相比于數(shù)組容量可實現(xiàn)動態(tài)增長。
    • ArrayList非線程安全,建議在單線程中才使用ArrayList,而在多線程中可以選擇Vector或者CopyOnWriteArrayList;默認初始容量為10,每次擴容為原來的1.5倍
  • Vector
    • 和ArrayList幾乎是一樣的,Vector使用了synchronized關(guān)鍵字,是線程安全的,比ArrayList開銷更大,訪問更慢;默認初始容量為10,默認每次擴容為原來的2倍,可通過capacityIncrement屬性設(shè)置
  • LinkList
    • LinkedList底層結(jié)構(gòu)是鏈表,增刪速度快;是一個雙向循環(huán)鏈表,也可以被當作堆棧、隊列或雙端隊列
3.0.0.6 如何理解ArrayList的擴容消耗?Arrays.asList方法后的List可以擴容嗎?ArrayList如何序列化?
  • 如何理解ArrayList的擴容消耗
    • 由于ArrayList使用elementData = Arrays.copyOf(elementData, newCapacity);進行擴容,而每次都會重新創(chuàng)建一個newLength長度的數(shù)組,所以擴容的空間復雜度為O(n),時間復雜度為O(n)
      public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
      T[] copy = ((Object)newType == (Object)Object[].class)
          ? (T[]) new Object[newLength]
          : (T[]) Array.newInstance(newType.getComponentType(), newLength);
      System.arraycopy(original, 0, copy, 0,
                       Math.min(original.length, newLength));
      return copy;
      }
  • Arrays.asList方法后的List可以擴容嗎?
    • 不能,asList返回的List為只讀的。其原因為:asList方法返回的ArrayList是Arrays的一個內(nèi)部類,并且沒有實現(xiàn)add,remove等操作
  • List怎么實現(xiàn)排序?
    • 實現(xiàn)排序,可以使用自定義排序:list.sort(new Comparator(){...})
    • 或者使用Collections進行快速排序:Collections.sort(list)
  • ArrayList如何序列化?

    • ArrayList 基于數(shù)組實現(xiàn),并且具有動態(tài)擴容特性,因此保存元素的數(shù)組不一定都會被使用,那么就沒必要全部進行序列化。
    • 技術(shù)博客大總結(jié)
    • 保存元素的數(shù)組 elementData 使用 transient 修飾,該關(guān)鍵字聲明數(shù)組默認不會被序列化。
      transient Object[] elementData; // non-private to simplify nested class access
    • ArrayList 實現(xiàn)了 writeObject() 和 readObject() 來控制只序列化數(shù)組中有元素填充那部分內(nèi)容。
      
      private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
      elementData = EMPTY_ELEMENTDATA;
      s.defaultReadObject();
      s.readInt(); // ignored
      if (size > 0) {
          ensureCapacityInternal(size);
          Object[] a = elementData;
          for (int i=0; i<size; i++) {
              a[i] = s.readObject();
          }
      }
      }

    private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    int expectedModCount = modCount;
    s.defaultWriteObject();
    s.writeInt(size);
    for (int i=0; i<size; i++) {
    s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
    throw new ConcurrentModificationException();
    }
    }

    - 序列化時需要使用 ObjectOutputStream 的 writeObject() 將對象轉(zhuǎn)換為字節(jié)流并輸出。而 writeObject() 方法在傳入的對象存在 writeObject() 的時候會去反射調(diào)用該對象的 writeObject() 來實現(xiàn)序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法,原理類似。

    ArrayList list = new ArrayList();
    ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
    oos.writeObject(list);

3.0.0.7 如何理解list集合讀寫機制和讀寫效率?什么是CopyOnWriteArrayList,它與ArrayList有何不同?
  • 讀寫機制
    • ArrayList在執(zhí)行插入元素是超過當前數(shù)組預定義的最大值時,數(shù)組需要擴容,擴容過程需要調(diào)用底層System.arraycopy()方法進行大量的數(shù)組復制操作;在刪除元素時并不會減少數(shù)組的容量(如果需要縮小數(shù)組容量,可以調(diào)用trimToSize()方法);在查找元素時要遍歷數(shù)組,對于非null的元素采取equals的方式尋找。
    • LinkedList在插入元素時,須創(chuàng)建一個新的Entry對象,并更新相應元素的前后元素的引用;在查找元素時,需遍歷鏈表;在刪除元素時,要遍歷鏈表,找到要刪除的元素,然后從鏈表上將此元素刪除即可。
    • Vector與ArrayList僅在插入元素時容量擴充機制不一致。對于Vector,默認創(chuàng)建一個大小為10的Object數(shù)組,并將capacityIncrement設(shè)置為0;當插入元素數(shù)組大小不夠時,如果capacityIncrement大于0,則將Object數(shù)組的大小擴大為現(xiàn)有size+capacityIncrement;如果capacityIncrement<=0,則將Object數(shù)組的大小擴大為現(xiàn)有大小的2倍。
  • 讀寫效率
    • ArrayList對元素的增加和刪除都會引起數(shù)組的內(nèi)存分配空間動態(tài)發(fā)生變化。因此,對其進行插入和刪除速度較慢,但檢索速度很快。
    • LinkedList由于基于鏈表方式存放數(shù)據(jù),增加和刪除元素的速度較快,但是檢索速度較慢。
  • 什么是CopyOnWriteArrayList,它與ArrayList有何不同?
    • CopyOnWriteArrayList是ArrayList的一個線程安全的變體,其中所有可變操作(add、set等等)都是通過對底層數(shù)組進行一次新的復制來實現(xiàn)的。相比較于ArrayList它的寫操作要慢一些,因為它需要實例的快照。
    • CopyOnWriteArrayList中寫操作需要大面積復制數(shù)組,所以性能肯定很差,但是讀操作因為操作的對象和寫操作不是同一個對象,讀之間也不需要加鎖,讀和寫之間的同步處理只是在寫完后通過一個簡單的"="將引用指向新的數(shù)組對象上來,這個幾乎不需要時間,這樣讀操作就很快很安全,適合在多線程里使用,絕對不會發(fā)生ConcurrentModificationException ,因此CopyOnWriteArrayList適合使用在讀操作遠遠大于寫操作的場景里,比如緩存。
    • 技術(shù)博客大總結(jié)
3.0.1.0 HashSet和TreeSet的區(qū)別?是如何保證唯一值的,底層怎么做到的?
  • HashSet
    • 不能保證元素的排列順序;使用Hash算法來存儲集合中的元素,有良好的存取和查找性能;通過equal()判斷兩個元素是否相等,并兩個元素的hashCode()返回值也相等
  • TreeSet
    • 是SortedSet接口的實現(xiàn)類,根據(jù)元素實際值的大小進行排序;采用紅黑樹的數(shù)據(jù)結(jié)構(gòu)來存儲集合元素;支持兩種排序方法:自然排序(默認情況)和定制排序。前者通過實現(xiàn)Comparable接口中的compareTo()比較兩個元素之間大小關(guān)系,然后按升序排列;后者通過實現(xiàn)Comparator接口中的compare()比較兩個元素之間大小關(guān)系,實現(xiàn)定制排列
3.0.1.5 HashMap和Hashtable的區(qū)別?HashMap在put、get元素的過程?體現(xiàn)了什么數(shù)據(jù)結(jié)構(gòu)?
  • HashMap
    • 基于AbstractMap類,實現(xiàn)了Map、Cloneable(能被克隆)、Serializable(支持序列化)接口; 非線程安全;允許存在一個為null的key和任意個為null的value;采用鏈表散列的數(shù)據(jù)結(jié)構(gòu),即數(shù)組和鏈表的結(jié)合;初始容量為16,填充因子默認為0.75,擴容時是當前容量翻倍,即2capacity
  • Hashtable
    • 基于Map接口和Dictionary類;線程安全,開銷比HashMap大,如果多線程訪問一個Map對象,使用Hashtable更好;不允許使用null作為key和value;底層基于哈希表結(jié)構(gòu);初始容量為11,填充因子默認為0.75,擴容時是容量翻倍+1,即2capacity+1
    • HashTable里使用的是synchronized關(guān)鍵字,這其實是對對象加鎖,鎖住的都是對象整體,當Hashtable的大小增加到一定的時候,性能會急劇下降,因為迭代時需要被鎖定很長的時間。
  • HashMap在put、get元素的過程
    • 向Hashmap中put元素時,首先判斷key是否為空,為空則直接調(diào)用putForNullKey(),不為空則計算key的hash值得到該元素在數(shù)組中的下標值;如果數(shù)組在該位置處沒有元素,就直接保存;如果有,還要比較是否存在相同的key,存在的話就覆蓋原來key的value,否則將該元素保存在鏈頭,先保存的在鏈尾。
    • 從Hashmap中g(shù)et元素時,計算key的hash值找到在數(shù)組中的對應的下標值,返回該key對應的value即可,如果有沖突就遍歷該位置鏈表尋找key相同的元素并返回對應的value
  • 體現(xiàn)了什么數(shù)據(jù)結(jié)構(gòu)
    • HashMap采用鏈表散列的數(shù)據(jù)結(jié)構(gòu),即數(shù)組和鏈表的結(jié)合,在Java8后又結(jié)合了紅黑樹,當鏈表元素超過8個將鏈表轉(zhuǎn)換為紅黑樹
    • 技術(shù)博客大總結(jié)
3.0.1.6 如何保證HashMap線程安全?底層怎么實現(xiàn)的?HashMap是有序的嗎?如何實現(xiàn)有序?
  • 使用ConcurrentHashMap可保證線程安全
    • ConcurrentHashMap是線程安全的HashMap,它采取鎖分段技術(shù),將數(shù)據(jù)分成一段一段的存儲,然后給每一段數(shù)據(jù)配一把鎖,當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候,其他段的數(shù)據(jù)也能被其他線程訪問。在JDK1.8中對ConcurrentHashmap做了兩個改進:
      • 取消segments字段,直接采用transient volatile HashEntry<K,V>[] table保存數(shù)據(jù),將數(shù)組元素作為鎖,對每一行數(shù)據(jù)進行加鎖,可減少并發(fā)沖突的概率
      • 數(shù)據(jù)結(jié)構(gòu)由“數(shù)組+單向鏈表”變?yōu)椤皵?shù)組+單向鏈表+紅黑樹”,使得查詢的時間復雜度可以降低到O(logN),改進一定的性能。
    • 通俗一點解釋:ConcurrentHashMap引入了分割(Segment),可以理解為把一個大的Map拆分成N個小的HashTable,在put方法中,會根據(jù)hash(paramK.hashCode())來決定具體存放進哪個Segment,如果查看Segment的put操作,我們會發(fā)現(xiàn)內(nèi)部使用的同步機制是基于lock操作的,這樣就可以對Map的一部分(Segment)進行上鎖,這樣影響的只是將要放入同一個Segment的元素的put操作,保證同步的時候,鎖住的不是整個Map(HashTable就是這么做的),相對于HashTable提高了多線程環(huán)境下的性能,因此HashTable已經(jīng)被淘汰了。技術(shù)博客大總結(jié)
  • 使用LinkedHashMap可實現(xiàn)有序
    • HashMap是無序的,而LinkedHashMap是有序的HashMap,默認為插入順序,還可以是訪問順序,基本原理是其內(nèi)部通過Entry維護了一個雙向鏈表,負責維護Map的迭代順序
3.0.1.7 HashMap存儲兩個對象的hashcode相同會發(fā)生什么?如果兩個鍵的hashcode相同,你如何獲取值對象?
  • HashMap存儲兩個對象的hashcode相同會發(fā)生什么?
    • 錯誤回答:因為hashcode相同,所以兩個對象是相等的,HashMap將會拋出異常,或者不會存儲它們。
    • 正確回答:兩個對象就算hashcode相同,但是它們可能并不相等。如果不明白,可以先看看我的這篇博客:Hash和HashCode深入理解?;卮稹耙驗閔ashcode相同,所以它們的bucket位置相同,‘碰撞’會發(fā)生。因為HashMap使用鏈表存儲對象,這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中。
  • HashMap1.7和1.8的區(qū)別
    • 在JDK1.6,JDK1.7中,HashMap采用數(shù)組+鏈表實現(xiàn),即使用鏈表處理沖突,同一hash值的鏈表都存儲在一個鏈表里。但是當位于一個鏈表中的元素較多,即hash值相等的元素較多時,通過key值依次查找的效率較低。
    • JDK1.8中,HashMap采用位數(shù)組+鏈表+紅黑樹實現(xiàn),當鏈表長度超過閾值(8)時,將鏈表轉(zhuǎn)換為紅黑樹,這樣大大減少了查找時間。
  • 如果兩個鍵的hashcode相同,你如何獲取值對象?
    • 當調(diào)用get()方法,HashMap會使用鍵對象的hashcode找到bucket位置,然后獲取值對象。當然如果有兩個值對象儲存在同一個bucket,將會遍歷鏈表直到找到值對象。
    • 在沒有值對象去比較,如何確定確定找到值對象的?因為HashMap在鏈表中存儲的是鍵值對,找到bucket位置之后,會調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點,最終找到要找的值對象。
    • 技術(shù)博客大總結(jié)
3.0.1.8 HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標?
  • 不直接使用hashCode()處理后的哈希值
    • hashCode()方法返回的是int整數(shù)類型,其范圍為-(2^31)~(2^31-1),約有40億個映射空間,而HashMap的容量范圍是在16(初始化默認值)~2 ^ 30,HashMap通常情況下是取不到最大值的,并且設(shè)備上也難以提供這么多的存儲空間,從而導致通過hashCode()計算出的哈希值可能不在數(shù)組大小范圍內(nèi),進而無法匹配存儲位置;
  • HashMap是使用了哪些方法來有效解決哈希沖突的
    • 1.使用鏈地址法(使用散列表)來鏈接擁有相同hash值的數(shù)據(jù);
    • 2.使用2次擾動函數(shù)(hash函數(shù))來降低哈希沖突的概率,使得數(shù)據(jù)分布更平均;
    • 3.引入紅黑樹進一步降低遍歷的時間復雜度,使得遍歷更快;
  • 如何解決匹配存儲位置問題
    • HashMap自己實現(xiàn)了自己的hash()方法,通過兩次擾動使得它自己的哈希值高低位自行進行異或運算,降低哈希碰撞概率也使得數(shù)據(jù)分布更平均;
    • 在保證數(shù)組長度為2的冪次方的時候,使用hash()運算之后的值與運算(&)(數(shù)組長度 - 1)來獲取數(shù)組下標的方式進行存儲,這樣一來是比取余操作更加有效率,二來也是因為只有當數(shù)組長度為2的冪次方時,h&(length-1)才等價于h%length,三來解決了“哈希值與數(shù)組大小范圍不匹配”的問題;
  • 為什么數(shù)組長度要保證為2的冪次方呢?
    • 只有當數(shù)組長度為2的冪次方時,h&(length-1)才等價于h%length,即實現(xiàn)了key的定位,2的冪次方也可以減少沖突次數(shù),提高HashMap的查詢效率;
    • 技術(shù)博客大總結(jié)
    • 如果 length 為 2 的次冪 則 length-1 轉(zhuǎn)化為二進制必定是 11111……的形式,在于 h 的二進制與操作效率會非常的快,而且空間不浪費;如果 length 不是 2 的次冪,比如 length 為 15,則 length - 1 為 14,對應的二進制為 1110,在于 h 與操作,最后一位都為 0 ,而 0001,0011,0101,1001,1011,0111,1101 這幾個位置永遠都不能存放元素了,空間浪費相當大,更糟的是這種情況中,數(shù)組可以使用的位置比數(shù)組長度小了很多,這意味著進一步增加了碰撞的幾率,減慢了查詢的效率!這樣就會造成空間的浪費。
3.0.1.9 為什么HashMap中String、Integer這樣的包裝類適合作為K?為啥不用其他作key值?
  • 為什么HashMap中String、Integer這樣的包裝類適合作為K?
    • String、Integer等包裝類的特性能夠保證Hash值的不可更改性和計算準確性,能夠有效的減少Hash碰撞的幾率
      • 都是final類型,即不可變性,保證key的不可更改性,不會存在獲取hash值不同的情況
      • 內(nèi)部已重寫了equals()、hashCode()等方法,遵守了HashMap內(nèi)部的規(guī)范(不清楚可以去上面看看putValue的過程),不容易出現(xiàn)Hash值計算錯誤的情況;
  • 想要讓自己的Object作為K應該怎么辦呢?
    • 重寫hashCode()和equals()方法
      • 重寫hashCode()是因為需要計算存儲數(shù)據(jù)的存儲位置,需要注意不要試圖從散列碼計算中排除掉一個對象的關(guān)鍵部分來提高性能,這樣雖然能更快但可能會導致更多的Hash碰撞;
      • 重寫equals()方法,需要遵守自反性、對稱性、傳遞性、一致性以及對于任何非null的引用值x,x.equals(null)必須返回false的這幾個特性,目的是為了保證key在哈希表中的唯一性;
  • 總結(jié)
    • 采用合適的equals()和hashCode()方法的話,將會減少碰撞的發(fā)生,提高效率。不可變性使得能夠緩存不同鍵的hashcode,這將提高整個獲取對象的速度,使用String,Interger這樣的wrapper類作為鍵是非常好的選擇。
    • 技術(shù)博客大總結(jié)
3.0.2.0 HashMap是如何擴容的?如何理解HashMap的大小超過了負載因子定義的容量?重新調(diào)整HashMap大小存在什么問題嗎?
  • HashMap是為啥要擴容
    • 當鏈表數(shù)組的容量超過初始容量*加載因子(默認0.75)時,再散列將鏈表數(shù)組擴大2倍,把原鏈表數(shù)組的搬移到新的數(shù)組中。為什么需要使用加載因子?為什么需要擴容呢?因為如果填充比很大,說明利用的空間很多,如果一直不進行擴容的話,鏈表就會越來越長,這樣查找的效率很低,擴容之后,將原來鏈表數(shù)組的每一個鏈表分成奇偶兩個子鏈表分別掛在新鏈表數(shù)組的散列位置,這樣就減少了每個鏈表的長度,增加查找效率。
  • 如何理解HashMap的大小超過了負載因子(load factor)定義的容量?
    • 默認的負載因子大小為0.75,也就是說,當一個map填滿了75%的bucket時候,和其它集合類(如ArrayList等)一樣,將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組,來重新調(diào)整map的大小,并將原來的對象放入新的bucket數(shù)組中。這個過程叫作rehashing,因為它調(diào)用hash方法找到新的bucket位置。
  • 重新調(diào)整HashMap大小存在什么問題嗎?技術(shù)博客大總結(jié)
    • 當多線程的情況下,可能產(chǎn)生條件競爭。當重新調(diào)整HashMap大小的時候,確實存在條件競爭,因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了,它們會同時試著調(diào)整大小。在調(diào)整大小的過程中,存儲在鏈表中的元素的次序會反過來,因為移動到新的bucket位置的時候,HashMap并不會將元素放在鏈表的尾部,而是放在頭部,這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了,那么就死循環(huán)了。

其他介紹

01.關(guān)于博客匯總鏈接
  • 1.技術(shù)博客匯總
  • 2.開源項目匯總
  • 3.生活博客匯總
  • 4.喜馬拉雅音頻匯總
  • 5.其他匯總
02.關(guān)于我的博客
  • 我的個人站點:www.yczbj.org,www.ycbjie.cn
  • github:https://github.com/yangchong211
  • 知乎:https://www.zhihu.com/people/yang-chong-69-24/pins/posts
  • 簡書:http://www.jianshu.com/u/b7b2c6ed9284
  • csdn:http://my.csdn.net/m0_37700275
  • 喜馬拉雅聽書:http://www.ximalaya.com/zhubo/71989305/
  • 開源中國:https://my.oschina.net/zbj1618/blog
  • 泡在網(wǎng)上的日子:http://www.jcodecraeer.com/member/content_list.php?channelid=1
  • 郵箱:yangchong211@163.com
  • 阿里云博客:https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
  • segmentfault頭條:https://segmentfault.com/u/xiangjianyu/articles
  • 掘金:https://juejin.im/user/5939433efe88c2006afa0c6e
向AI問一下細節(jié)

免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI