欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

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

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

好消息

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

  • System.arraycopy()和Arrays.copyOf()代碼說(shuō)明？

    創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的館陶網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

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

  • ArrayList如何序列化？

    • ArrayList 基于數(shù)組實(shí)現(xiàn)，并且具有動(dòng)態(tài)擴(kuò)容特性，因此保存元素的數(shù)組不一定都會(huì)被使用，那么就沒(méi)必要全部進(jìn)行序列化。
    • 技術(shù)博客大總結(jié)
    • 保存元素的數(shù)組 elementData 使用 transient 修飾，該關(guān)鍵字聲明數(shù)組默認(rèn)不會(huì)被序列化。 
      transient Object[] elementData; // non-private to simplify nested class access
    • ArrayList 實(shí)現(xiàn)了 writeObject() 和 readObject() 來(lái)控制只序列化數(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();
    }
    }

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

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

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

其他介紹

01.關(guān)于博客匯總鏈接
  • 1.技術(shù)博客匯總
  • 2.開(kāi)源項(xiàng)目匯總
  • 3.生活博客匯總
  • 4.喜馬拉雅音頻匯總
  • 5.其他匯總
02.關(guān)于我的博客
  • 我的個(gè)人站點(diǎn)：www.yczbj.org，www.ycbjie.cn
  • github：https://github.com/yangchong211
  • 知乎：https://www.zhihu.com/people/yang-chong-69-24/pins/posts
  • 簡(jiǎn)書：http://www.jianshu.com/u/b7b2c6ed9284
  • csdn：http://my.csdn.net/m0_37700275
  • 喜馬拉雅聽(tīng)書：http://www.ximalaya.com/zhubo/71989305/
  • 開(kāi)源中國(guó)：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

當(dāng)前文章：03.Java數(shù)據(jù)結(jié)構(gòu)問(wèn)題
網(wǎng)頁(yè)鏈接：http://www.chinadenli.net/article30/iigiso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、App開(kāi)發(fā)、云服務(wù)器、網(wǎng)站排名、用戶體驗(yàn)、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都定制網(wǎng)站建設(shè)