//反转方法 ，传入一个链表
public static LinkNode reversal(LinkNode list){
//pre用来存放前一个链表节点
LinkNode pre =list
//取出下一个链表节点 ,cru 用来存放当前链表节点
LinkNode cru = list.getNext()
//next用来存放下一个链表节点
LinkNode next
//如果当前节点不为空(这里意思是 如果传进来的list 有下一个节点就继续执行)
while(null!=cru){
//取出当前节点的下一个节点
next = cru.getNext()
//把前一个节点赋予当前节点的下一个节点(这里产生实际改变)
cru.setNext(pre)
//把当前节点变量赋予前一个节点的变量
pre=cru
//把下一个节点变量赋予当前
cru = next
}
//循环体内会循环到方法传入的LinkNode 没有前一个节点为止
//因为几次交换的原因
//因为循环结束,所以把next赋空
list.setNext(null)
//因为循环的原因,前一个节点实际是第一个节点
list=pre
//返回第一个节点
return list
}
public static void main(String[] args) {
LinkNode head = new LinkNode(0)
LinkNode tmp = null
LinkNode cur = null
for (int i = 1 i < 10 i++) {
tmp = new LinkNode(i)
if (1 == i) {
head.setNext(tmp)
} else {
cur.setNext(tmp)
}
cur = tmp
}
LinkNode h = head
while (null != h) {
System.out.print(h.getVal() + " ")
h = h.getNext()
}
head = reversal(head)
System.out.println("\n**************************")
//打印反转后的结果
while (null != head) {
System.out.print(head.getVal() + " ")
head = head.getNext()
}
}
}
我觉得应该是效率问题，如何不做反转在重新计算hash值后将要获得当前链表的最后一个元素，然后对最后一个元素的next属性添加一个节点信息，但是如果反转的话就不用了。
例子：
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = 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)
}
int i = 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
}
}
}
Java的实现打开Follower.java里的这个函数
这里的Follower.this.invitations就是我们的消息队列，定义是：private LinkedList<Invitation>invitationsLinkedList不是线性安全的集合，需要我们加同步。具体的同步方法就是函数里写的，通过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函数式编程的思维。我但愿这种递归式的做法不会有溢出。
