java鏈表翻轉

1. java HashMap擴容的時候，為什麼要把Entry鏈表反轉

我覺得應該是效率問題，如何不做反轉在重新計算hash值後將要獲得當前鏈表的最後一個元素，然後對最後一個元素的next屬性添加一個節點信息，但是如果反轉的話就不用了。

例子：

voidtransfer(Entry[]newTable,booleanrehash){
intnewCapacity=newTable.length;
for(Entry<K,V>e:table){
while(null!=e){
Entry<K,V>next=e.next;
//重新計算hash值
if(rehash){
e.hash=null==e.key?0:hash(e.key);
}
inti=indexFor(e.hash,newCapacity);
//這個是反轉的寫法start
e.next=newTable[i];
newTable[i]=e;
e=next;
//反轉end
//這個是不反轉的寫法start

Entry<K,V>newEntry=newTable[i];
e.next=null;
if(newEntry!=null){

while(true){
if(newEntry.next==null){
newEntry.next=e;
break;
}

newEntry=newEntry.next;
}
}else{
newTable[i]=e;
}

e=next;
//不反轉end

}
}
}

2. Java和Rust在實現多線程編程時的異同

Java的實現
打開Follower.java里的這個函數

這里的Follower.this.invitations就是我們的消息隊列，定義是：private LinkedList<Invitation> invitations;LinkedList不是線性安全的集合，需要我們加同步。具體的同步方法就是函數里寫的，通過Java常見的用wait，notify和notifyall給對象加鎖。
處理並發有wait、notify和notiyall，有興趣的朋友可以去這里了解一下：http://www.importnew.com/16453.html。Follower就是一個等待leader發送invitation，處理並返回結果的過程。
Leader.java
這么一段代碼：

裡面就是Leader發送邀請inv，並等待follower返回結果的大概邏輯，通過對消息體加鎖，是Java傳統的實現多線程並發的方式。還有消費者的消息隊列也會加鎖，在Java里，有個對象叫LinkedBlockingQueue，是不用加鎖就可以put和take的，但在例子里，我們選用了更簡單的LinkedList，也是為了表現一下加鎖的邏輯。
Rust的實現
Leader的結構為：

Follower的結構為：

對於其他語言轉過來的同學，這里的Vec，i32，bool都很好理解，不過裡面出現的Arc和Mutex，Sender，Receiver就是新東西了，上面這4個都是Rust標准庫的東西，也是這次分享要介紹的重點對象，是這4個東西共同實現了消息的生產，傳遞和消費。
下面簡單介紹一下分別是做什麼用的：
Arc<T>實現了sync介面。Sync介面是做什麼呢？權威資料是這么說的：當一個類型T實現了Sync，它向編譯器表明這個類型在多線程並發時沒有導致內存不安全的可能性。
如果看不懂不要緊，我們先看看實際中是怎麼用的：

在這個例子里，我們關注這幾句：
let data = Arc::new(Mutex::new(vec![1u32, 2, 3]));
let data = data.clone();
let mut data = data.lock().unwrap();
下面分別解釋一下是做什麼的：
簡單的說Arc::new表明了這是通過clone()方法來使用的，每clone，都會給該對象原子計數+1，通過引用計數的方法來保證對象只要還被其中任何一個線程引用就不會被釋放掉，從而保證了前面說的：這個類型在多線程並發時沒有導致內存不安全的可能性。
如果我們不定義為Arc<>就傳到其他線程使用，編譯器會報：
error: capture of moved value: `data`
data[i] += 1;
我們可以記住clone()就是Arc的用法。
接下來我們看Mutex：
Mutex實現了send介面。同樣，在權威資料里是這么描述的：這個類型的所有權可以在線程間安全的轉移
那我們又是怎麼用Mutex的呢？就是用lock().unwrap()。lock()的作用是獲取對象，如果當前有其他線程正在使用Mutex<T>裡面的T對象時，本線程就會阻塞，從而保證同時只有一個線程來訪問對象，mutex也另外提供了try_lock()的方法，是不阻塞的，只要其他線程被佔用，就返回err，通常Arc和Mutex都是一起使用的。
回到我最原始的題目，Mutex和Arc實現了對象本身的線程共享，但是在線程間如何傳遞這個對象呢？就是靠channel，channel通常是這么定義的let (tx, rx) = mpsc::channel();它會返回兩個對象tx和rx，就是之前我提到的sender和receiver。
在我的Rust實現里，關鍵的語句是以下幾個：
let leaders = (0..leader_cnt).map(|i|
Arc::new(Mutex::new(Leader::new(i,dance_types.len() as i32)))
).collect::<Vec<_>>();
這一句是new一堆leader出來，Arc和Mutex表明leader是可以多線程共享和訪問的。
同樣Follower也是：
let followers = (0..follower_cnt).map(|i|
Arc::new(Mutex::new(Follower::new(i,dance_types.len() as i32,leader_cnt)))
).collect::<Vec<_>>();
接下來這幾句就有點不好理解了。

這里定義了一堆的sender和receiver，其中把他們都作為leader和follower的成員變數存起來。大概意思就是每一個leader都通過sender列表可以發送invitation給所有follower，同時又有單個receiver來接受所有follower發給自己的處理結果inviresult。
同樣follower也是這么做。這樣在之後每一個follower和leader作為一個線程跑起來之後，都能在相互之間建立了一條通信的通道。
這個是和Java實現多線程並發最大的不同之處！Java是通過給對象加鎖，Rust是通過channel轉移對象的所有權，在代碼里，leader發送inv給folloer是下面這一句
match self.senders[*follower_id as usize].lock().unwrap().send(inv){，其中的lock().unwrap()是獲得該leader對該follower的發送通道的所有權，send(inv)就是轉移具體的發送對象invitation所有權了。
這個轉移按照我的理解，應該是內存拷貝。就是在follower接收的時候，let inv = match self.receiver.recv() { ，原來leader裡面的inv在send之後已經是不可訪問了，如果你之後再次訪問了inv，會報use of moved value錯誤，而follower裡面的inv則是在follower的棧里新生成的對象，所以，在Java裡面我只定義了invitation對象，但是在Rust裡面，我要再定義一個InviResult，因為我即使在follower線程裡面填了result欄位，leader線程也不能繼續訪問inv了。所以需要依靠follower再次發送一個invresult給leader，所以整個Rust程序大概就是這么一個思路。
實踐總結
之前我測試比較Java和Rust實現的性能時，由於沒有把調試信息去掉，導致Java比Rust慢很多，特別是那些調試信息都是調用String.format，這是比幾個string相加慢上10倍的方法，兩者都去掉調試信息後，leader和follower都會2000的時候，在我低端外星人筆記本里，性能差別大概是2倍吧，沒我想像中大，Rust的程序整個寫下來比較費力，一方面是對ownership機制不熟，思維沒有轉變過來，另一方面Rust的確需要開發者分部分精力到語法細節上。
編者註：馮總也有一些其它的實踐體會，請參見CSDN對馮耀明的專訪，請戳這里。也可以查看他的個人博客里的總結。
下面摘錄采訪中關於Rust的內容過來：
首先Rust裡面的ownership和lifetime概念真的很酷，就因為這個概念實現無內存泄露，野指針和安全並發。
其次，Rust的語法不簡單，也是有不少坑的，據說Rust的潛在用戶應該是現在的C和C++程序員，他們可能會覺得比較習慣，說不定還 覺得更簡單。由於ownership機制，一些在其他語言能夠跑通的程序在Rust下就要調整實現了，它會改變你寫程序的思維方式。據說一些寫Rust超 過半年的程序員已經愛上它了！
我對Rust感受較深的是下面幾點：
初學者不熟悉ownership機制，會無數次編譯失敗。但一旦編譯成功，那麼程序只剩下邏輯錯誤了。同樣，由於ownership機制，將來在項目里修改Rust代碼將可能是痛苦的過程，因為原來編譯通過的代碼可能加入新功能就編譯不過了，這是我的猜測。
Rust編譯速度慢，不過據說最近每一個Rust新發布的版本編譯速度都比之前的版本提高了30%。
Rust沒有類，有的是結構體加方法，我喜歡這種簡單的概念。
Rust沒有類繼承，只有介面，雖然介面可以提供默認的實現。這樣一來，在大型項目里原來類繼承來重用代碼的效果是否就要用成員變數實例來完成呢？
Rust沒有null，取而代之的是None和Option<T>，也因此，結構體在初始化的時候必須初始化所有欄位。
Rust有我一直很想要的錯誤值返回機制，而不必通過拋異常或者需要每每定義包含結果和錯誤體實現。
Rust用send和sync兩個介面來處理多線程並發，其中Arc<T>和Mutex<T>分別實現了這兩個介面，簡單易用。
Rust目前沒有一個強大的IDE，支持斷點調試，變數監控等。
它跟現在動態語言是兩個截然不同的方向，它適合一些資深的程序員，我倒是覺得有必要有這么一本書，叫《從C++到Rust，你需要改善的20個編程 習慣》，能從實踐上告訴開發者Rust里我們應該遵從什麼樣的編程習慣。Rust未來是否像C那樣流行開來成為新一代的主流語言沒有人能夠知道，但它絕對 是值得你去了解和關注的語言。
進一步的思考：反轉鏈表 - Java和Rust的不同實現
Rust的list應該怎麼定義，譬如反轉列表又是怎麼做呢？
由於ownership的機制和不存在空指針的情況，很多在其他帶GC的語言能夠跑起來的程序在Rust下面就要換一種做法。最近試用Rust的基礎數據結構時，更加加強了我的看法。下面以最原始的鏈表list為例。
在Java中，考慮最基本的鏈表定義
class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
sb.append(val);
ListNode pNext = this.next;
while (pNext != null) {
sb.append(",");
sb.append(pNext.val);
pNext = pNext.next;
}
sb.append("]");
return String.format("%s", sb.toString());
}
}
如果我們要反轉鏈表，可以這么做：
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode pNext = head.next;
ListNode pPrevious = null;
while (head != null) {
pNext = head.next;
head.next = pPrevious;
pPrevious = head;
head = pNext;
}
return pPrevious;
}
那如果我們按照一般思維，在Rust里對應的實現就是這樣子的：
struct ListNode{
id :i32,
next :Option<Box<ListNode>>
}
反轉鏈表：
fn reverseList2(head :&mut Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match *head{
None => None,
Some(head) => {
let mut head = Some(head);
let mut pNext = head.unwrap().next;
let mut pPrevious:Option<Box<ListNode>> = None;
while true {
match head {
None =>{break;}
_ =>{}
}
pNext = head.unwrap().next;
head.unwrap().next = pPrevious;
pPrevious = head;
head = pNext;
}
pPrevious
}
}
}
然後編譯，報了以下錯誤：
=》match *head{

ERROR：cannot move out of borrowed content
=》 pNext = head.unwrap().next;
ERROR：cuse of moved value: `head`

這些錯誤就是因為Rust的ownership機制，讓我們無法像Java或者C++里保存臨時變數，特別是在循環里。反復試過各種寫法，都行不通。
最後，換成這么來做
鏈表定義：
use List::*;

enum List {
Cons1(i32, Box<List>),
Nil,
}

// Methods can be attached to an enum
impl List {
#[inline]
fn new() -> List {
Nil
}

#[inline]
fn prepend(self, elem: i32) -> List {
Cons1(elem, Box::new(self))
}

fn len(&self) -> i32 {
match *self {
Cons1(_, ref tail) => 1 + tail.len(),
Nil => 0
}
}

fn stringify(&self) -> String {
match *self {
Cons1(head, ref tail) => {
format!("{}, {}", head, tail.stringify())
},
Nil => {
format!("Nil")
},
}
}
}

fn reverseList(list:List, acc:List ) -> List{
match list{
Cons1(val,tail) => {
reverseList(*tail,acc.prepend(val))
}
Nil => acc
}
}

fn main() {
let mut head = List::new();
let mut i=0;
while i < 10 {
i+=1;
head = head.prepend(i);
}
println!("{:30}",head.stringify());
let result = List::new();
let result = reverseList(head,result);
<span style="white-space:pre"> </span>println!("{:30}",result.stringify());
}
從結果可以看到，鏈表已經實現反轉了。所以在Rust下面，很多做法都要換一下。有人說這就是Rust函數式編程的思維。我但願這種遞歸式的做法不會有溢出。

3. 在Java中怎麼將單鏈表中的兩個節點對調

有a b c d 四個節點，要對調 b 和 c ，那 a 指向 c ，b 指向 d ，c 再指向 b ，不就行了么？

中間可以把用一個臨時變數保存住 b 。

4. 作為一個面試官，我會問初級java工程師哪些問題

初級java工程師多數是剛畢業或者工作1,2年的新人。對於新人，面試中基礎問題會問道很多，因為先要考察這個人的基礎。

關於基礎類的題目，我在面試初級java工程師的時候一般會問下面兩大類問題，每類5個題目，這樣下來我就基本可以了解這位工程師的程度了。

java基礎類

面向對象基礎類

最後，如果前面問題回答的不錯，會補充兩個編程習慣問題。

1.在你寫過的代碼中，你寫過超過2層的循環嗎，怎麼實現的？

回答：沒有，就算ok；如果回答有，聽一下實現，如果原因說不出來，扣分。

2.在你寫過的代碼中，if語句最多嵌套了幾層，最多有多少分支，怎麼實現的？

回答：3層以下，就算ok；如果回答3層以上，聽一下實現，如果原因說不出來，扣分。

4，5個分支，就算ok；如果回答5個分支以上，聽一下實現，如果原因說不出來，扣分。

最後兩個題其實比較陷阱，但是正是一個反向的思考才能了解面試者之前的工作狀態。

如果面試者在平日里就有好的習慣，自然不用擔心。