騰訊-Java開發(fā)面經(jīng)（一）

1、繼承的父類不同

HashMap繼承自AbstractMap類。但二者都實現(xiàn)了Map接口。

Hashtable繼承自Dictionary類，Dictionary類是一個已經(jīng)被廢棄的類（見其源碼中的注釋）。父類都被廢棄，自然而然也沒人用它的子類Hashtable了。

2、HashMap線程不安全,HashTable線程安全

  javadoc中關于hashmap的一段描述如下：此實現(xiàn)不是同步的。如果多個線程同時訪問一個哈希映射，**而其中至少一個線程從結(jié)構(gòu)上修改了該映射**，則它必須保持外部同步。

  Hashtable 中的方法大多是Synchronize的，而HashMap中的方法在一般情況下是非Synchronize的。在多線程并發(fā)的環(huán)境下，可以直接使用Hashtable，不需要自己為它的方法實現(xiàn)同步，但使用HashMap時就必須要自己增加同步處理。HashTable實現(xiàn)線程安全的代價就是效率變低，因為會鎖住整個HashTable,而ConcurrentHashMap做了相關優(yōu)化,因為ConcurrentHashMap使用了分段鎖，并不對整個數(shù)據(jù)進行鎖定,效率比HashTable高很多。

  **HashMap底層是一個Entry數(shù)組，當發(fā)生hash沖突的時候，hashmap是采用鏈表的方式來解決的，在對應的數(shù)組位置存放鏈表的頭結(jié)點。對鏈表而言，新加入的節(jié)點會從頭結(jié)點加入。**

  HashMap的put方法：

void addEntry(int hash, K key, V value, int bucketIndex) { //新增Entry,將“key-value”插入指定位置，bucketIndex是位置索引。        Entry<K,V> e = table[bucketIndex];  保存“bucketIndex”位置的值到“e”中        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);         if (size++ >= threshold)       // 若HashMap的實際大小 不小于 “閾值”，則調(diào)整HashMap的大小2倍            resize(2 * table.length);    }

在hashmap的put方法調(diào)用addEntry()方法，假如A線程和B線程同時對同一個數(shù)組位置調(diào)用addEntry，兩個線程會同時得到現(xiàn)在的頭結(jié)點，然后A寫入新的頭結(jié)點之后，B也寫入新的頭結(jié)點，那B的寫入操作就會覆蓋A的寫入操作造成A的寫入操作丟失。

故解決方法就是使用 使用ConcurrentHashMap。

這里要說一下 就是HashMap的迭代器(Iterator)是fail-fast迭代器，故當有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素），將會拋出ConcurrentModificationException異常，而Hashtable的enumerator迭代器不是fail-fast的。但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這并不是一個一定發(fā)生的行為，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別。

3.包含的contains方法不同

HashMap是沒有contains方法的，而包括containsValue和containsKey方法；hashtable則保留了contains方法，效果同containsValue,還包括containsValue和containsKey方法。

4.是否允許null值

Hashmap是允許key和value為null值的，用containsValue和containsKey方法判斷是否包含對應鍵值對；HashTable鍵值對都不能為空，否則包空指針異常。

5.計算hash值方式不同

為了得到元素的位置，首先需要根據(jù)元素的 KEY計算出一個hash值，然后再用這個hash值來計算得到最終的位置。

①：HashMap有個hash方法重新計算了key的hash值,因為hash沖突變高，所以通過一種方法重算hash值的方法：

static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }

注意這里計算hash值，先調(diào)用hashCode方法計算出來一個hash值，再將hash與右移16位后相異或，從而得到新的hash值。

**②：Hashtable通過計算key的hashCode()**來得到hash值就為最終hash值。

它們計算索引位置方法不同：

HashMap在求hash值對應的位置索引時，index = (n - 1) & hash。將哈希表的大小固定為了2的冪，因為是取模得到索引值，故這樣取模時，不需要做除法，只需要做位運算。位運算比除法的效率要高很多。

HashTable在求hash值位置索引時計算index的方法：

int index = (hash & 0x7FFFFFFF) % tab.length;

&0x7FFFFFFF的目的是為了將負的hash值轉(zhuǎn)化為正值，因為hash值有可能為負數(shù)，而&0x7FFFFFFF后，只有符號位改變，而后面的位都不變。

6.擴容方式不同（容量不夠）

當容量不足時要進行resize方法，而resize的兩個步驟：

①擴容；

②rehash:這里HashMap和HashTable都會會重新計算hash值而這里的計算方式就不同了（看5）；

HashMap 哈希擴容必須要求為原容量的2倍，而且一定是2的冪次倍擴容結(jié)果，而且每次擴容時，原來數(shù)組中的元素依次重新計算存放位置，并重新插入；

而Hashtable擴容為原容量2倍加1；

7.解決hash沖突方式不同（地址沖突）

先看jdk8之前：

查找時間復雜度慢慢變高；

Java8，HashMap中，當出現(xiàn)沖突時可以：

1.如果沖突數(shù)量小于8，則是以鏈表方式解決沖突。

2.而當沖突大于等于8時，就會將沖突的Entry轉(zhuǎn)換為**紅黑樹進行存儲。**

3.而又當數(shù)量小于6時，則又轉(zhuǎn)化為鏈表存儲。

而在HashTable中， 都是以鏈表方式存儲。

阻塞與非阻塞

　　阻塞就是卡在那兒什么也不做，雙方之間也沒有信息溝通。

　　非阻塞就是即使對方不能馬上完成請求，雙方之間也有信息的溝通。

同步與異步

　　同步就是一件事件只由一個過程處理完成，不論阻塞與非阻塞，最后完成這個事情的都是同一個過程

　　異步就是一件事由兩個過程完成，前面一個過程通知，后面一個過程接受返回的結(jié)果。

異步和事件驅(qū)動（multi IO）

　　異步是指數(shù)據(jù)準備好并且已經(jīng)拷貝到用戶空間，在通知用戶來取數(shù)據(jù)

       事件驅(qū)動理解為準備好數(shù)據(jù)了但是沒有拷貝到用戶空間，這個時候去通知用戶，用戶再去取數(shù)據(jù)，經(jīng)過拷貝過程取得數(shù)據(jù)。 

5種常見的網(wǎng)絡I/O模型

blocking I/O  -- 阻塞類型的I/O

nonblocking I/O -- 非阻塞類型的I/O

 I/O Multiplexing -- 多路復用型I/O　

 Signal-Driven I/O -- 信號驅(qū)動型I/O

 Asynchronous I/O -- 異步I/O　

1. blocking I/O  -- 阻塞類型的I/O

　　流程圖如下：

　　linux下socket默認是阻塞的，阻塞模式在準備數(shù)據(jù)和拷貝數(shù)據(jù)兩個過程都是阻塞的，在這期間客戶端一直卡著，雙方也沒有數(shù)據(jù)交流。

2.nonblocking I/O -- 非阻塞類型的I/O

　　流程圖：

 　   linux下使用fcntl方法將socket設置為非阻塞模式 

　　　　flags = fcntl(sockfd, F_GETFL, 0);                        //獲取文件的flags值。

              fcntl(sockfd, F_SETFL, flags | O_NONBLOCK);   //設置成非阻塞模式；

　　非阻塞模式下，如果數(shù)據(jù)還沒有準備好，服務端會返回error，客戶端根據(jù)這個error判斷后，再次發(fā)起recv，直到數(shù)據(jù)準備好，這個過程雖然客戶端也在這里卡著了，但是這期間一直和服務有著信息交換。

3.I/O Multiplexing -- 多路復用型I/O

　　流程圖：

　　多路復用型IO，有的也稱為事件驅(qū)動型IO，常用select，poll，epoll來處理多個IO連接狀態(tài)。當某個IO連接的數(shù)據(jù)準備好了，select返回，通知用戶進行read操作，這種IO的好處是一次可以監(jiān)聽多個連接，壞處是要兩次調(diào)用，兩次返回，單個連接和非阻塞IO沒有多大的性能提升。

　　  在多路復用模型中，對于每一個socket，一般都設置成為non-blocking，但是，如上圖所示，整個用戶的process其實是一直被block的。只不過process是被select這個函數(shù)block，而不是被socket IO給block。因此select()與非阻塞IO類似。

4.Signal-Driven I/O -- 信號驅(qū)動型I/O

　　流程圖：

　　首先我們允許套接口進行信號驅(qū)動I/O,并安裝一個信號處理函數(shù)，進程繼續(xù)運行并不阻塞。當數(shù)據(jù)準備好時，進程會收到一個SIGIO信號，可以在信號處理函數(shù)中調(diào)用I/O操作函數(shù)處理數(shù)據(jù)。

5.Asynchronous I/O -- 異步I/O

 　　流程圖：

　　當一個異步過程調(diào)用發(fā)出后，調(diào)用者不能立刻得到結(jié)果。實際處理這個調(diào)用的部件在完成后，通過狀態(tài)、通知和回調(diào)來通知調(diào)用者的輸入輸出操作