国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

我的面試準備過程--容器(更新中)

zhisheng / 525人閱讀

摘要:底層實現是對象數組,優點是時間為,缺點是和時間為,需要留意的是擴容的過程以及的算法本節參考源碼中放最新的源碼為,組成鏈表或紅黑樹定義從整體上看,底層的存儲結構是基于數組和鏈表實現的。實現了所謂的線程安全,在很多方法上都加上了。

ArrayList

ArrayList底層實現是對象數組,優點是set、get時間為O(1),缺點是add和remove時間為O(n),需要留意的是擴容的過程以及remove的算法

public class MyArrayList{
    private static final int DEFAULT_CAPACITY = 10;
    Object[] elementData;
    int size;
    
    public int size(){
        return size;
    }
    
    public boolean isEmpty(){
        return size == 0;
    }
    
    public boolean contains(Object o){
        return indexOf >= 0;
    }
    
    public E remove(int index){
        rangeCheck(index);
        
        E oldValue = elementData[index];
        int numMoved = size - index - 1;
        
        if(numMoved > 0){
            System.copyarray(elementData, index + 1, elementData, index, numMoved);
        }
        
        elementData[--size] = null;
        return oldValue;
    }
    
    public boolean remove(Object o){
        if(o == null){
            for(int i = 0; i < size; i++){
                fastRemove(i);
                return true;
            }
        }else{
            for(int i = 0; i < size; i++){
                fastRemove(i);
                return true;
            }
        }
        return false;
    }
    
    public void fastRemove(int index){
        int numMoved = size - index - 1;
        
        if(numMoved > 0){
            System.copyarray(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
    }
    
    public boolean add(E e){
        ensureCapacity(size + 1);
        
        elementData[size++] = e;
        return true;
    }
    
    public E get(int index){
        rangeCheck(index);
        
        return elementData[index];
    }
    
    public E set(int index, E element){
        rangeCheck(index);
        
        E oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    } 
    
    public void ensureCapacity(int minCapacity){
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        
        if(minCapacity - elementData.length > 0){
        int oldCapacity = elementData.length;
        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);
        
    }
        
    private int hugeCapacity(int minCapacity){
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();

        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
    
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    private String outOfBoundsMsg(index){
        return "Size:" + size + ", Index:" + index;
    }
    
    public int indexOf(Object o){
        if(o == null){
            for(int i = 0; i < size; i++){
                if(elementData[i] == null){
                    return i;
                }
            }
        }else{
            for(int i = 0; i < size; i++){
                if(elementData[i].equals(o)){
                    return i;
                }
            }
        }
        return -1;
    }
}

本節參考 jdk1.8 源碼

HashMap

table中放Entry(最新的JDK源碼為Node),Entry組成鏈表或紅黑樹

Entry(Node定義)
    static class Node implements Map.Entry{
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

從整體上看,HashMap底層的存儲結構是基于數組和鏈表實現的。對于每一個要存入HashMap的鍵值對(Key-Value Pair),通過計算Key的hash值來決定存入哪個數組單元(bucket),為了處理hash沖突,每個數組單元實際上是一條Entry單鏈表的頭結點,其后引申出一條單鏈表。

存取過程

取值過程大致如下:先檢查table中的頭結點,table中如果是樹,從樹中找;不然從鏈表中找

    public V get(Object key){
        Node e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node getNode(int hash, Object key){
        Node[] tab; Node first, e; int n; K k;
        //桶中頭結點不為空,檢查頭結點
        if((tab = table) != null && (n = tab.length) > 0 && 
            (first = tab[(n - 1) & hash]) != null){
            if(first.hash == hash && 
            ((k = first.key)) == key || (key != null && key.equals(k))))
                return first;

            if((e = first.next) != null){
                //如果為紅黑樹,按樹遍歷
                if(first instanceof TreeNode)
                    return ((treeNode) first).getTreeNode(hash, key);
                do{
                    if(e.hash == hash &&
                    (k = e.key) == key || (key != null && key.equals(k)))
                        return e;
                }while((e = e.next) != null);
            }
        }

        return null;
    }

添加鍵值對put(key,value)的過程:
1,判斷鍵值對數組tab[]是否為空或為null,否則以默認大小resize();
2,根據鍵值key計算hash值得到插入的數組索引i,如果tab[i]==null,直接新建節點添加,否則轉入3
3,判斷當前數組中處理hash沖突的方式為鏈表還是紅黑樹(check第一個節點類型即可),分別處理

public V put(K key, V value) {  
        return putVal(hash(key), key, value, false, true);  
    }  
     /** 
     * Implements Map.put and related methods 
     * 
     * @param hash hash for key 
     * @param key the key 
     * @param value the value to put 
     * @param onlyIfAbsent if true, don"t change existing value 
     * @param evict if false, the table is in creation mode. 
     * @return previous value, or null if none 
     */  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
                   boolean evict) {  
        Node[] tab;   
    Node p;   
    int n, i;  
        if ((tab = table) == null || (n = tab.length) == 0)  
            n = (tab = resize()).length;  
    /*如果table的在(n-1)&hash的值是空,就新建一個節點插入在該位置*/  
        if ((p = tab[i = (n - 1) & hash]) == null)  
            tab[i] = newNode(hash, key, value, null);  
    /*表示有沖突,開始處理沖突*/  
        else {  
            Node e;   
        K k;  
    /*檢查第一個Node,p是不是要找的值*/  
            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))  
                e = p;  
            else if (p instanceof TreeNode)  
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);  
            else {  
                for (int binCount = 0; ; ++binCount) {  
        /*指針為空就掛在后面*/  
                    if ((e = p.next) == null) {  
                        p.next = newNode(hash, key, value, null);  
               //如果沖突的節點數已經達到8個,看是否需要改變沖突節點的存儲結構,               
            //treeifyBin首先判斷當前hashMap的長度,如果不足64,只進行  
                        //resize,擴容table,如果達到64,那么將沖突的存儲結構為紅黑樹  
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                            treeifyBin(tab, hash);  
                        break;  
                    }  
        /*如果有相同的key值就結束遍歷*/  
                    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))  
                        break;  
                    p = e;  
                }  
            }  
    /*就是鏈表上有相同的key值*/  
            if (e != null) { // existing mapping for key,就是key的Value存在  
                V oldValue = e.value;  
                if (!onlyIfAbsent || oldValue == null)  
                    e.value = value;  
                afterNodeAccess(e);  
                return oldValue;//返回存在的Value值  
            }  
        }  
        ++modCount;  
     /*如果當前大小大于門限,門限原本是初始容量*0.75*/  
        if (++size > threshold)  
            resize();//擴容兩倍  
        afterNodeInsertion(evict);  
        return null;  
    }  
擴容機制resize()

構造hash表時,如果不指明初始大小,默認大小為16(即Node數組大小16),如果Node[]數組中的元素達到(填充比*Node.length)重新調整HashMap大小 變為原來2倍大小,擴容很耗時,需要重新計算bucket的位置。

為什么通過計算h & (length-1)來獲得bucket的位置,而不是通過計算h % length?

實際上,在HashMap中,h & (length-1) == h % length,但是需要一個前提:length必須滿足是2的冪。這也正是在解釋DEFAULT_INITIAL_CAPACITY和HashMap構造方法時強調的HashMap的bucket容量必須是2的冪。當length是2的冪,那么length的二進制數可以表示為1000...000,因此length - 1的二進制數為0111...111,當h與length - 1位與時,除了h的最高位的被修改為0,其余位均保持不變,這也正是實現了h % length的效果。只是相比于h % length,h & (length-1)的效率會更高。

HashMap的bucket容量必須為2的冪的另一個重要原因是一旦滿足此條件,那么length即為偶數,length - 1便為奇數,所以length - 1的最后一位必為1。因此,h & (length - 1)得到的值既可能是奇數,也可能是偶數,這確保了散列的均勻性。如果length - 1是偶數,那么h & (length - 1)得到的值必為偶數,那么HashMap的空間便浪費了一半。

  final Node[] resize() {  
       Node[] oldTab = table;  
       int oldCap = (oldTab == null) ? 0 : oldTab.length;  
       int oldThr = threshold;  
       int newCap, newThr = 0;  
      
/*如果舊表的長度不是空*/  
       if (oldCap > 0) {  
           if (oldCap >= MAXIMUM_CAPACITY) {  
               threshold = Integer.MAX_VALUE;  
               return oldTab;  
           }  
/*把新表的長度設置為舊表長度的兩倍,newCap=2*oldCap*/  
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                    oldCap >= DEFAULT_INITIAL_CAPACITY)  
      /*把新表的門限設置為舊表門限的兩倍,newThr=oldThr*2*/  
               newThr = oldThr << 1; // double threshold  
       }  
    /*如果舊表的長度的是0,就是說第一次初始化表*/  
       else if (oldThr > 0) // initial capacity was placed in threshold  
           newCap = oldThr;  
       else {               // zero initial threshold signifies using defaults  
           newCap = DEFAULT_INITIAL_CAPACITY;  
           newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
       }  
      
      
      
       if (newThr == 0) {  
           float ft = (float)newCap * loadFactor;//新表長度乘以加載因子  
           newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
                     (int)ft : Integer.MAX_VALUE);  
       }  
       threshold = newThr;  
       @SuppressWarnings({"rawtypes","unchecked"})  
/*下面開始構造新表,初始化表中的數據*/  
       Node[] newTab = (Node[])new Node[newCap];  
       table = newTab;//把新表賦值給table  
       if (oldTab != null) {//原表不是空要把原表中數據移動到新表中      
           /*遍歷原來的舊表*/        
           for (int j = 0; j < oldCap; ++j) {  
               Node e;  
               if ((e = oldTab[j]) != null) {  
                   oldTab[j] = null;  
                   if (e.next == null)//說明這個node沒有鏈表直接放在新表的e.hash & (newCap - 1)位置  
                       newTab[e.hash & (newCap - 1)] = e;  
                   else if (e instanceof TreeNode)  
                       ((TreeNode)e).split(this, newTab, j, oldCap);  
/*如果e后邊有鏈表,到這里表示e后面帶著個單鏈表,需要遍歷單鏈表,將每個結點重*/  
                   else { // preserve order保證順序  
                ////新計算在新表的位置,并進行搬運  
                       Node loHead = null, loTail = null;  
                       Node hiHead = null, hiTail = null;  
                       Node next;  
                      
                       do {  
                           next = e.next;//記錄下一個結點  
          //新表是舊表的兩倍容量,實例上就把單鏈表拆分為兩隊,  
             //e.hash&oldCap為偶數一隊,e.hash&oldCap為奇數一對  
                           if ((e.hash & oldCap) == 0) {  
                               if (loTail == null)  
                                   loHead = e;  
                               else  
                                   loTail.next = e;  
                               loTail = e;  
                           }  
                           else {  
                               if (hiTail == null)  
                                   hiHead = e;  
                               else  
                                   hiTail.next = e;  
                               hiTail = e;  
                           }  
                       } while ((e = next) != null);  
                      
                       if (loTail != null) {//lo隊不為null,放在新表原位置  
                           loTail.next = null;  
                           newTab[j] = loHead;  
                       }  
                       if (hiTail != null) {//hi隊不為null,放在新表j+oldCap位置  
                           hiTail.next = null;  
                           newTab[j + oldCap] = hiHead;  
                       }  
                   }  
               }  
           }  
       }  
       return newTab;  
   }  
HashMap的總結

本節參考

HashMap的默認大小為16,即桶數組的默認長度為16;

HashMap的默認裝載因子是0.75;

HashMap內部的桶數組存儲的是Entry對象,也就是鍵值對對象。

構造器支持指定初始容量和裝載因子,為避免數組擴容帶來的性能問題,建議根據需求指定初始容量。裝載因子盡量不要修改,0.75是個比較靠譜的值。

桶數組的長度始終是2的整數次方(大于等于指定的初始容量),這樣做可以減少沖突概率,提高查找效率。(可以從indexfor函數中看出,h&(length-1),若length為奇數,length-1為偶數那么h&(length-1)結果的最后一位必然為0,也就是說所有鍵都被散列到數組的偶數下標位置,這樣會浪費近一半空間。另外,length為2的整數次方也保證了h&(length-1)與h%length等效).

HashMap接受null鍵;

HashMap不允許鍵重復,但是值是可以重復的。若鍵重復,那么新值會覆蓋舊值。

HashMap通過鏈表法解決沖突問題,每個Entry都有一個next指針指向下一個Entry,沖突元素(不是鍵相同,而是hash值相同)會構成一個鏈表。并且最新插入的鍵值對始終位于鏈表首部。

當容量超過閾值(threshold)時,會發生擴容,擴容后的數組是原數組的兩倍。擴容操作需要開辟新數組,并對原數組中所有鍵值對重新散列,非常耗時。我們應該盡量避免HashMap擴容。

HashMap非線程安全。

線程安全與HashTable

HashMap是一個非線程安全的,因此適合運用在單線程環境下。如果是在多線程環境,可以通過Collections的靜態方法synchronizedMap獲得線程安全的HashMap,如下代碼所示。

Map map = Collections.synchronizedMap(new HashMap());

HashTable和HashMap底層采用相同的存儲結構,在很多方法的實現上二者的思路基本一致。最主要的區別主要有兩點。

HashTable實現了所謂的線程安全,在HashTable很多方法上都加上了synchronized。

在HashMap的分析中,我們發現當我們新增鍵值對時,HashMap是允許Key和Value均為null。但是HashTable不允許Key或Value為null,關于這一點我們可以通過查看HashTable源碼得知。

    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) { // 若value為空則拋出NullPointerException。
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = key.hashCode(); // 若key為空則拋出NullPointerException。
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry entry = (Entry)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }
關于HashSet

HashSet基于HashMap實現;而Map是鍵值對形式的,因此構造一個PRESENT假裝為值。

private static final Object PRESENT = new Object();

另外,

HashSet無序;允許值為null;非線程安全;底層增刪等操作基于HashMap實現;

LinkedHashSet有序;允許值為null;非線程安全;依賴于HashSet,底層增刪等操作基于LinkedHashMap實現;

TreeSet有序;不允許為null;非線程安全;底層增刪等操作基于TreeMap實現。

本節參考 https://segmentfault.com/a/11...
http://blog.csdn.net/tuke_tuk...

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/70147.html

相關文章

  • 一個 16年畢業生所經歷的 PHP 面試

    摘要:正確做法是給加索引,還有聯合索引,并不能避免全表掃描。 前言:有收獲的話請加顆小星星,沒有收獲的話可以 反對 沒有幫助 舉報三連 有心的同學應該會看到我這個noteBook下面的其它知識,希望對你們有些許幫助。 本文地址 時間點:2017-11 一個16年畢業生所經歷的php面試 一、什么是面試 二、面試準備 1. 問:什么時候開始準備? 2. 問:怎么準備? 三、面試...

    dabai 評論0 收藏0
  • 一位大佬的親身經歷總結:簡歷和面試的技巧

    摘要:我覺得了解簡歷和面試的技巧可以幫助你更好的去學習重要的知識點以及更好地去準備面試以及面試,說實話,我個人覺得這些東西還挺重要的。在本文里,我將介紹我這段時間里更新簡歷和面試的相關經歷。 分享一篇很不錯的文章!本文作者曾經寫過《Java Web輕量級開發面試教程》和 《Java核心技術及面試指南》這兩本書。我覺得了解簡歷和面試的技巧可以幫助你更好的去學習重要的知識點以及更好地去準備面試以...

    pingan8787 評論0 收藏0
  • 我的面試準備過程--查找算法(更新)

    摘要:把準備過程紀錄下來,共勉。線性查找二分查找二分查找英語,也稱折半查找英語對數查找英語,是一種在有序數組中查找某一特定元素的搜索算法。 寫在最前面 導師貪腐出逃美國,兩年未歸,可憐了我。拿了小米和美團的offer,要被延期,offer失效,工作重新找。把準備過程紀錄下來,共勉。 線性查找 public static int search(int[] data, int target) {...

    Soarkey 評論0 收藏0
  • 我的面試準備過程--多線程(更新)

    摘要:但是,實際中無法保證達到讓步目的,因為讓步的線程還有可能被線程調度程序再次選中。在大多數情況下,將導致線程從運行狀態轉到可運行狀態,但有可能沒有效果。 多線程編程 線程狀態圖 總是無法上傳,稍后上傳 常用函數 狀態轉換 運行中->阻塞 sleep(long millis) 在指定的毫秒數內讓當前正在執行的線程休眠 join() 等待t線程終止 使用方式 Thread t =...

    zoomdong 評論0 收藏0
  • 我的面試準備過程--隊列與棧(更新)

    摘要:和三個方法的時間復雜度必須為兩種解法,解法一,將最小值存入自有的數據結構中,如下所示原本的值最小值解法二,用兩個棧 堆棧和隊列統稱線性表 簡單的線性結構 數組和鏈表可以實現這兩種數據結構 堆棧 基本理解 DFS 深度優先---按深度遍歷 遞歸轉非遞歸 隊列 基本理解 BFS 廣度優先---按層序遍歷 出入棧的合法性模擬出入棧的過程,不是入棧,就是...

    EastWoodYang 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<