存档三月 2017

JavaScript数据结构——链表的实现

  前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素。如果你在使用数组的时候发现很慢,就可以考虑使用链表。

 

  链表的概念

  链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量,以head表示,它存放一个地址,指向一个元素。每个结点都使用一个对象的引用指标它的后继,指向另一个结点的引用叫做链。

  

 

  数组元素依靠下标(位置)来进行引用,而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高,下图演示了链表结点d的插入过程:  

  删除过程:

  

  基于对象的链表

  我们定义2个类,Node类与LinkedList类,Node为结点数据,LinkedList保存操作链表的方法。

  首先看Node类:  

1 function Node(element){
2     this.element = element;
3     this.next = null;
4 }

  element用来保存结点上的数据,next用来保存指向一下结点的的链接。  

  LinkedList类:

 1 function LinkedList(){
 2 
 3          this.head = new Node('head');
 4 
 5          this.find = find;
 6 
 7          this.insert = insert;
 8 
 9          this.remove = remove;
10 
11          this.show = show;
12 
13 }

  find()方法,从头结点开始,沿着链表结点一直查找,直到找到与item内容相等的element则返回该结点,没找到则返回空。

1 function find(item){
2          var currentNode = this.head;//从头结点开始
3          while(currentNode.element!=item){
4                   currentNode =  currentNode.next;
5          }
6          return currentNode;//找到返回结点数据,没找到返回null
7 }

  Insert方法。通过前面元素插入的演示可以看出,实现插入简单四步:

1、创建结点

2、找到目标结点

3、修改目标结点的next指向链接

4、将目标结点的next值赋值给要插入的结点的next

1 function insert(newElement,item){
2          var newNode = new Node(newElement);
3          var currentNode = this.find(item);
4          newNode.next = currentNode.next;
5          currentNode.next = newNode;
6 }

  Remove()方法。删除某一节点需要先找到被删除结点的前结点,为此我们定义方法frontNode():

1 function frontNode(item){
2          var currentNode = this.head;
3          while(currentNode.next.element!=item&&currentNode.next!=null){
4                   currentNode = currentNode.next;
5          }      
6          return currentNode;
7 }

  简答三步:

1、创建结点

2、找到目标结点的前结点

3、修改前结点的next指向被删除结点的n后一个结点

1 function remove(item){
2          var frontNode = this.frontNode(item);
3          //console.log(frontNode.element);
4          frontNode.next = frontNode.next.next;
5 }

  Show()方法:

1 function show(){
2          var currentNode = this.head,result;
3          while(currentNode.next!=null){
4                   result += currentNode.next.element;//为了不显示head结点
5                   currentNode = currentNode.next;
6          }
7 }

  测试程序:

1 var list = new LinkedList();
2 list.insert("a","head");
3 list.insert("b","a");
4 list.insert("c","b");
5 console.log(list.show());
6 list.remove("b");
7 console.log(list.show());

  输出:

 

  双向链表

  从链表的头节点遍历到尾节点很简单,但有的时候,我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性,该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。

 

  首先我们先给Node类增加front属性:  

1 function Node(element){
2     this.element = element;
3     this.next = null;
4     this.front = null;
5 }

  当然,对应的insert()方法和remove()方法我们也需要做相应的修改:  

 1 function insert(newElement,item){
 2     var newNode = new Node(newElement);
 3     var currentNode = this.find(item);
 4     newNode.next = currentNode.next;
 5     newNode.front = currentNode;//增加front指向前驱结点
 6     currentNode.next = newNode;
 7 }
 8 
 9 
10 function remove(item){   
11     var currentNode = this.find(item);//找到需要删除的节点
12     if (currentNode.next != null) {
13         currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
14         currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
15         currentNode.next = null;//并设置前驱与后继的指向为空
16         currentNode.front = null;       
17     }    
18 }

  反序显示链表:

  需要给双向链表增加一个方法,用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点,可以免除从前往后遍历链。

1 function findLast() {//查找链表的最后一个节点
2     var currentNode = this.head;
3     while (currentNode.next != null) {
4         currentNode = currentNode.next;
5     }
6     return currentNode;
7 }

  实现反序输出:

1 function showReverse() {
2     var currentNode = this.head, result = "";
3     currentNode = this.findLast();  
4     while(currentNode.front!=null){
5         result += currentNode.element + " ";
6         currentNode = currentNode.front;
7     }
8     return result;
9 }

  测试程序:

1 var list = new LinkedList();
2 list.insert("a","head");
3 list.insert("b","a");
4 list.insert("c","b");
5 console.log(list);
6 list.remove("b");
7 console.log(list.show());
8 console.log(list.showReverse());

  输出:

 

 

  循环链表

 

  循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身,即:

1 head.next = head

  这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表:

  

  

  修改构造方法:

1 function LinkedList(){
2     this.head = new Node('head');//初始化
3     this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
4     this.find = find;
5     this.frontNode = frontNode;
6     this.insert = insert;
7     this.remove = remove;
8     this.show = show;  
9 }

  这时需要注意链表的输出方法show()与find()方法,原来的方式在循环链表里会陷入死循环,while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
    var currentNode = this.head;//从头结点开始
    while(currentNode.element!=item&&currentNode.next.element!='head'){
        currentNode =  currentNode.next;
    }
    return currentNode;//找到返回结点数据,没找到返回null
}
function show(){
    var currentNode = this.head,result = "";
    while (currentNode.next != null && currentNode.next.element != "head") {      
        result += currentNode.next.element + " ";
        currentNode = currentNode.next;
    }
    return result;
}

  测试程序:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

  测试结果:

 

  本文用到的示例代码地址:https://github.com/LJunChina/JavaScript

 

JavaScript数据结构——队列的实现

  前面楼主简单介绍了JavaScript数据结构栈的实现,http://www.cnblogs.com/qq503665965/p/6537894.html,本次将介绍队列的实现。  

  队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

  队列的两种主要操作是:向队列中插入新元素和删除队列中的元素。插入操作也叫做入队,删除操作也叫做出队。入队操作在队尾插入新元素,出队操作删除队头的元素。下图演示了这两个操作。

 

  队列的另外一项重要操作是读取队头的元素。这个操作叫做 peek() 。该操作返回队头元素,但不把它从队列中删除。除了读取队头元素,我们还想知道队列中存储了多少元素,可以使用 length 属性满足该需求;要想清空队列中的所有元素,可以使用 clear() 方法来实现。下表定义了队列的一些主要方法:

 dataStorage Array 存储数据的底层数据结构
enqueue int 入队
dequeue fucntion 出队
front fucntion 返回队首元素
back fucntion 返回队尾元素
toString fucntion   显示队列内的所有元素
empty function   判断队列是否为空

  

 

 

 

 

 

 

队列的实现

 1 function Queue(array) {   
 2     if (array instanceof Array) {
 3         this.dataStorage = array;
 4     } else {
 5         throw "'"+array + "' is not an Array";
 6     }
 7 }
 8 
 9 Queue.prototype = {
10     enqueue: function (element) {//向队列中添加元素
11         this.dataStorage.push(element);
12     },
13     dequeue: function () {//删除队首元素
14         return this.dataStorage.shift();
15     },
16     front: function () {//返回队首元素
17         return this.dataStorage[0];
18     },
19     back: function () {//返回队尾元素
20         return this.dataStorage[this.dataStorage.length - 1];
21     },
22     toString: function () {//输出队列中所有元素
23         var result = "";
24         for (var i = 0; i this.dataStorage.length; i++) {
25             result += this.dataStorage[i] + "\t";
26         }
27         return result;
28     },
29     empty: function () {//判定队列是否为空
30         if (this.dataStorage.length == 0) {
31             return true;
32         }
33         return false;
34     }
35 }

  测试:  

1  var queue = new Queue(['a','b']);       
2 console.log(queue.toString());
3 //queue.dequeue();//a出队
4 //console.log(queue.toString());
5 console.log(queue.front());//队头元素
6 console.log(queue.back());//队尾元素
7 queue.dequeue();
8 queue.dequeue();
9 console.log(queue.empty());

 

队列的应用——基数排序

  原理:对于 0~99 的数字,基数排序将数据集扫描两次。第一次按个位上的数字进行排序,第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。

  假设有这样一个数组:{4, 73, 51, 76, 70, 19, 63, 64, 43, 12},经过基数排序第一次扫描之后,数字被分配到如下盒子中:  

 1 Box 0: 70
 2 Box 1: 51
 3 Box 2: 12
 4 Box 3: 73,63,43
 5 Box 4: 4,64
 6 Box 5: 76
 7 Box 6: 
 8 Box 7:
 9 Box 8:
10 Box 9: 19

  根据盒子的顺序,对数字进行第一次排序的结果如下:

  70,51,12,73,63,43,4,64,76,19

  然后根据十位上的数值再将上次排序的结果分配到不同的盒子中:

 1 Box 0: 4
 2 Box 1: 12,19
 3 Box 2: 
 4 Box 3: 
 5 Box 4: 43
 6 Box 5: 51
 7 Box 6: 63,64
 8 Box 7: 70,73,76
 9 Box 8: 
10 Box 9: 

  最后,将盒子中的数字取出,组成一个新的列表,该列表即为排好序的数字:

  4,12,19,43,51,63,64,70,73,76

  使用队列代表盒子,可以实现这个算法。我们需要九个队列,每个对应一个数字。将所有队列保存在一个数组中,使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应的队列,根据个位数值对其重新排序,然后再根据十位上的数值进行排序,结果即为排好序的数字。

  下面是根据相应位(个位或十位)上的数值,将数字分配到相应队列的方法:  

 1      function allocation(nums,queues,n,digit) {
 2             for (var i = 0; i i) {
 3                 if (digit == 1) {
 4                     queues[nums[i] % 10].enqueue(nums[i]);
 5                 }
 6                 else {
 7                     queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
 8                 }
 9             }
10         }

  下面是从队列中收集数字的方法: 

1     function collection(queues, nums) {
2             var i = 0;
3             for (var digit = 0; digit digit) {
4                 while (!queues[digit].empty()) {
5                     nums[i++] = queues[digit].dequeue();
6                 }
7             }
8         }

  测试程序:

 1         var queues = [];
 2         for (var i = 0; i i) {
 3             queues[i] = new Queue([]);
 4         }
 5         var nums = [];
 6         for (var i = 0; i //目标排序数组
 7             nums[i] = Math.floor(Math.floor(Math.random() * 101));
 8         }
 9         console.log("排序前:");
10         showArray(nums);
11         allocation(nums, queues, 10, 1);
12         collection(queues, nums);
13         allocation(nums,queues,10,10);
14         collection(queues, nums);
15         console.log("排序后");
16         showArray(nums);
17 
18         function showArray(array) {
19             console.log(array);
20         }     

  结果:

  下篇楼主将带来,链表的实现。

  本文的示例代码地址:https://github.com/LJunChina/JavaScript

JavaScript数据结构——栈的实现

  栈(stack)是一种运算受限的线性表。栈内的元素只允许通过列表的一端访问,这一端被称为栈顶,相对地,把另一端称为栈底。装羽毛球的盒子是现实中常见的栈例子。栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

  下图演示了入栈和出栈的过程:

  

  我们知道pop()方法虽然可以访问栈顶元素,但是调用该方法后,栈顶元素被删除,而peek()方法返回栈顶元素,并不改变栈。push(),pop(),peek()是实现栈的三个主要方法,下表定义了栈的主要方法:

主要方法及属性

dataStorage Array 存储数据的底层数据结构
top int 记录栈顶元素位置
push fucntion 入栈方法
pop fucntion 出栈方法
peek fucntion 返回栈顶元素
length     fucntion   返回栈内元素个数
clear function   清空栈元素

  

 

 

 

 

 

 

栈的实现

  构造方法:  

1 function Stack() {
2     this.dataStorage = [];
3     this.top = 0;
4     this.push = push;
5     this.pop = pop;
6     this.peek = peek;
7     this.length = length;
8     this.clear = clear;
9 }

  我们用数组来存储栈内元素,构造方法将其初始化为一个空数组,变量top记录栈顶元素位置,被构造方法初始化为0,表示栈顶元素的初始位置为0,当有元素入栈,top也随之改变。

  push()方法的实现:  

1 function push(element) {
2     this.dataStorage[this.top++] = element;//将元素保存在数组top位置,并指向下一空位置
3 }

  当向栈中压入一个新元素时,需要将其保存在数组中变量 top 所对应的位置,然后将 top 值加 1,让其指向数组中下一个空位置。这里要特别注意 ++ 操作符的位置,它放在 this.top 的后面,这样新入栈的元素就被放在top 的当前值对应的位置,然后再将变量 top 的值加 1,指向下一个空位置。

  pop方法的实现:  

1 function pop() {
2     return this.dataStorage[--this.top];//返回数组top位置的元素,并让top指向top-1位置元素
3 }

  pop() 方法恰好与 push() 方法相反——它返回栈顶元素,同时将变量 top 的值减 1。

  peek() 方法的实现:  

1 function peek() {
2     return this.dataStorage[this.top-1];//返回数组top-1位置的元素
3 }

  这里需要考虑到空栈调用peek方法时候,返回的是-1位置元素,为undefined。

  length()方法的实现:  

1 function length() {
2     return this.top;
3 }

  如果需要知道栈内到底存了多少个元素,可通过调用length()方法,栈元素的个数即top的值。

  清空栈clear()饭方法的实现:

1 function clear() {
2     this.top = 0;
3 }

  将top设置为0,即栈顶元素位置为0,此时为空栈。

  下面我们来测试下: 

 1         var s = new Stack();
 2         s.push("a");//向栈顶压入元素
 3         s.push("b");
 4         s.push("c");
 5         console.log(s.length());//输出栈内元素个数 
 6         console.log(s.pop());//返回栈顶元素并删除
 7         console.log(s.length());
 8         console.log(s.peek());//返回栈顶元素不删除
 9         s.clear();
10         console.log(s.length());
11         console.log(s.peek());

  输出结果:

  

  最后一行返回undefined,是因为栈内元素被清空后,栈顶无值。

  Stack实际应用  

  我们来模拟一个简单的递归过程,计算数的阶乘。

  先使用递归实现:  

1 function Factorial(num) {
2             if (num == 0) {
3                 return 1;//0的阶乘为1
4             } else {
5                 return num*Factorial(num - 1);
6             }
7 
8         }

  用栈来计算,首先需要将数字1~num全部压入栈,然后将数字连乘。 

 1         function StackFactorial(num) {
 2             var stack = new Stack();
 3             while (num > 1) {
 4                 stack.push(num--);//将1~num压入栈
 5             }
 6             var result = 1;
 7             while (stack.length() > 0) {
 8                 result *= stack.pop();//连乘从栈顶取出的元素
 9             }
10             return result;
11         }

  测试结果:  

1 console.log(Factorial(10));//输出3628800
2 console.log(StackFactorial(10));//输出3628800

  本文的示例代码地址:https://github.com/LJunChina/JavaScript

多线程等待唤醒机制之生产消费者模式

  上篇楼主说明了多线程中死锁产生的原因并抛出问题——死锁的解放方案,那么在本篇文章,楼主将引用一个KFC生产汉堡,顾客购买汉堡的过程来说明死锁解决方案及多线程的等待唤醒机制。

简单地用一幅图来说明KFC生产汉堡,顾客来消费的过程:

场景分析:

  1. 资源类:Hamburger   
  2. 设置汉堡数据:SetThread(生产者)
  3. 获取汉堡数据:GetThread(消费者)
  4. 测试类:HamburgerTest
  5. 不同种类的线程(生产者、消费者)针对同一资源(汉堡)的操作
  6. 当汉堡有存货的时候,汉堡师傅不再生产,顾客可消费;反之,汉堡师傅生产,顾客不可消费
  7. 是否有线程安全问题?当然。楼主在《线程安全问题》那篇文章给出了判定方式,在该场景全部满足。

代码构建:类里面的i属性是楼主为了效果好一些特意加的,与本文要说明的问题无关;

  首先是资源类Hamburger.java,楼主这里为了模拟只简单的构造了3个字段,其中flag用来表示资源是否有数据。

 1 package com.jon.hamburger;
 2 
 3 public class Hamburger {
 4     private String name;//汉堡名称
 5     private double price;//汉堡价格
 6     private boolean flag;//汉堡是否有数据的标志,默认为false,表示没有数据
 7     public String getName() {
 8         return name;
 9     }
10     public void setName(String name) {
11         this.name = name;
12     }
13     public double getPrice() {
14         return price;
15     }
16     public void setPrice(double price) {
17         this.price = price;
18     }
19     public boolean isFlag() {
20         return flag;
21     }
22     public void setFlag(boolean flag) {
23         this.flag = flag;
24     }
25     
26 }

  接着是生产者SetThread.java与GetThread.java,都需要实现Runnable接口。场景分析中的第7点已经说明,场景存在线程安全的问题,楼主在前篇文章已经说明,线程安全的问题可以通过加锁来进行解决,但是这里涉及到不同种类的线程,所以必须要满足2点:

  1. 不同种类的线程都要加锁
  2. 不同种类的线程加的锁必须是同一把

SetThread.java

 1 package com.jon.hamburger;
 2 
 3 public class SetThread implements Runnable {
 4     private Hamburger hamburger;
 5     private int i;
 6 
 7     public SetThread(Hamburger hamburger) {
 8         this.hamburger = hamburger;
 9     }
10     @Override
11     public void run() {
12         while (true) {//为了数据效果好一些,楼主加入了判断
13             synchronized (hamburger) {
14                 if(this.hamburger.isFlag()){//如果有存货
15                     try {
16                         hamburger.wait();//线程等待
17                     } catch (InterruptedException e) {                        
18                         e.printStackTrace();
19                     }
20                 }
21                 //如果没有存货,这模拟生产
22                 if (i % 2 == 0) {
23                     this.hamburger.setPrice(25.0);
24                     this.hamburger.setName("俊锅的汉堡");
25                 } else {
26                     this.hamburger.setPrice(26.0);
27                     this.hamburger.setName("大俊锅的汉堡");
28                 }
29                 this.hamburger.setFlag(true);//生产完成后更改标志
30                 hamburger.notify();//唤醒当前等待的线程
31                 i++;//只为数据效果好一些,无实际意义
32             }
33 
34         }
35 
36     }
37 
38 }

GetThread.java

 1 package com.jon.hamburger;
 2 
 3 public class GetThread implements Runnable {
 4 
 5     private Hamburger hamburger;
 6     /**
 7      * 为了让同步锁使用同一个对象锁,这里通过构造方法进行传递
 8      * @param hamburger
 9      */
10     public GetThread(Hamburger hamburger){
11         this.hamburger = hamburger;
12     }
13     @Override
14     public void run() {
15         while(true){
16             synchronized (hamburger) {
17                 if(!this.hamburger.isFlag()){//如果没有存货,线程等待
18                     try {
19                         hamburger.wait();
20                     } catch (InterruptedException e) {                        
21                         e.printStackTrace();
22                     }
23                 }
24                 //如果有数据则进行输出
25                 System.out.println(this.hamburger.getName()+"-----"+this.hamburger.getPrice());
26                 this.hamburger.setFlag(false);//更改标志
27                 hamburger.notify();//唤醒线程
28             }    
29         }        
30         
31     }
32 
33 }

   可以看到两个线程类的run方法中都使用了sysnchronized进行了加锁,并使用同一个hamburger对象锁。

  再看测试类HamburgerTest.java及输出:

 1 package com.jon.hamburger;
 2 
 3 
 4 
 5 public class HamburgerTest {
 6 
 7 
 8     public static void main(String[] args) {
 9         Hamburger hamburger = new Hamburger();
10         
11         SetThread st = new SetThread(hamburger);//通过构造方法传入共享资源数据hamburger
12         GetThread gt = new GetThread(hamburger);
13         
14         Thread td1 = new Thread(st);
15         Thread td2 = new Thread(gt);
16         
17         td1.start();
18         td2.start();
19 
20     }
21 
22 }

  测试类中,我们通过构造方法给SetThread和GetThread传入了同一个对象,以保证锁对象为同一把。

  输出结果,线程间不相互影响,同时都无NULL——0.0的情况输出:

  

1 俊锅的汉堡-----25.0
2 大俊锅的汉堡-----26.0
3 俊锅的汉堡-----25.0
4 大俊锅的汉堡-----26.0
5 俊锅的汉堡-----25.0
6 大俊锅的汉堡-----26.0
7 俊锅的汉堡-----25.0
8 大俊锅的汉堡-----26.0

代码分析:

  我们假设线程t2先抢到CPU的执行权,那么程序执行流程可用下图表示:

  根据程序代码分析也可见,由于线程之间相互等待产生的死锁问题也得以解决,解决方案就是通过唤醒。另外,文本楼主还使用了另一种方式,思路也差不多,示例代码与本文的示例代码放在一起,已上传到GitHub。

  本文示例代码地址:https://github.com/LJunChina/JavaResource  中的Hamburger

 

多线程之死锁产生

本篇楼主接着上篇多线程的安全问题继续讨论多线程的死锁问题。

我们可以构造这样一种场景:传统(理想)情况下,楼主吃饭必须用两支筷子,而楼主老板(美国人)吃饭必须要用一刀,一叉;现在,楼主手上有一支筷子和一把刀,老板手上有一支筷子和一把叉;当我们都在互相等待对方把餐具给我们时,出现相互等待的现象,都吃不了饭,从而形成死锁。

所以上篇所说到的解决多线程同步的安全问题又衍生出了:如果出现同步嵌套,就容易产生死锁的问题。上面的场景我们先用代码来实现看一看。

构建MyLock类,创建楼主,老板两个锁对象:

1 package com.jon.dielock;
2 
3 public class MyLock{
4     //创建2把所对象
5     public static final Object objA = new Object();
6     public static final Object objB = new Object();
7 }

创建DieLock类集成Thread,构建死锁场景(同步嵌套):

 1 package com.jon.dielock;
 2 
 3 public class DieLock extends Thread {
 4     private boolean flag;//线程创建时给定不同的标记以表示不同的人
 5     public DieLock(boolean flag){
 6         this.flag = flag;
 7     }
 8     @Override
 9     public void run() {
10         if(flag){
11             synchronized(MyLock.objA){
12                 System.out.println("if objA");
13                 synchronized(MyLock.objB){
14                     System.out.println("if objB");
15                 }    
16             }            
17         }else{
18             synchronized(MyLock.objB){
19                 System.out.println("else objB");
20                 synchronized(MyLock.objA){
21                     System.out.println("else objA");
22                 }    
23             }            
24         }
25     }
26 }

创建测试类TestDieLock:

 1 package com.jon.dielock;
 2 
 3 public class TestDieLock {
 4 
 5     public static void main(String[] args) {
 6         DieLock dl1 = new DieLock(true);
 7         DieLock dl2 = new DieLock(false);
 8         
 9         dl1.start();
10         dl2.start();
11     }
12 
13 }

我们运行看输出结果:

1 else objB
2 if objA

很明显if和else都没执行完,理想情况下应全部输出。

下面还是习惯性的以图来说明(假设线程dl2先抢到CPU的执行权):

此场景形成死锁的解决方案楼主在下一篇将会具体说明。本文用到的相关代码地址:https://github.com/LJunChina/JavaResource的DieLock工程。

 

线程安全问题

本文楼主主要以用户在售票厅购买车票为背景进行多线程的实现。假设A市到B市的车票共50张,共有3个售票窗口在进行售票,使用多线程来模拟理想情况下的用户购票:

实现Runnable的Ticket类:

 1 package com.jon.thread;
 2 
 3 public class TicketSell implements Runnable {
 4     private int tickets = 50;//设置车票数量
 5     @Override
 6     public void run() {
 7         while(true){
 8             if(tickets>0){        
 9                 //输出当前是哪个线程在出售第几张车票
10                 System.out.println(Thread.currentThread().getName() + "正在售第" + (tickets--) + "张车票");
11             }
12         }
13     }
14 
15 }

简单的售票业务构建好后,我们用三个线程模拟售票窗口来进行测试:

 1 package com.jon.thread;
 2 
 3 public class TicketSellTest {
 4     public static void main(String[] args) {
 5         TicketSell ts = new TicketSell();
 6         Thread td1 = new Thread(ts, "售票窗口1");//设置线程名称以区分哪个售票窗口
 7         Thread td2 = new Thread(ts, "售票窗口2");
 8         Thread td3 = new Thread(ts, "售票窗口3");
 9         td1.start();
10         td2.start();
11         td3.start();
12     }
13 }

输出结果可以看到,三个线程抢占式地将50张车票完全售出:

 1 售票窗口2正在售第50张车票
 2 售票窗口3正在售第49张车票
 3 售票窗口1正在售第48张车票
 4 售票窗口3正在售第46张车票
 5 售票窗口2正在售第47张车票
 6 售票窗口3正在售第44张车票
 7 售票窗口1正在售第45张车票
 8 售票窗口3正在售第42张车票
 9 售票窗口2正在售第43张车票
10 售票窗口3正在售第40张车票
11 售票窗口1正在售第41张车票
12 售票窗口3正在售第38张车票
13 售票窗口2正在售第39张车票
14 售票窗口2正在售第35张车票
15 售票窗口3正在售第36张车票
16 售票窗口3正在售第33张车票
17 售票窗口3正在售第32张车票
18 售票窗口3正在售第31张车票
19 售票窗口3正在售第30张车票
20 售票窗口3正在售第29张车票
21 售票窗口3正在售第28张车票
22 售票窗口1正在售第37张车票
23 售票窗口3正在售第27张车票
24 售票窗口2正在售第34张车票
25 售票窗口3正在售第25张车票
26 售票窗口1正在售第26张车票
27 售票窗口1正在售第22张车票
28 售票窗口1正在售第21张车票
29 售票窗口1正在售第20张车票
30 售票窗口1正在售第19张车票
31 售票窗口1正在售第18张车票
32 售票窗口1正在售第17张车票
33 售票窗口1正在售第16张车票
34 售票窗口1正在售第15张车票
35 售票窗口1正在售第14张车票
36 售票窗口1正在售第13张车票
37 售票窗口1正在售第12张车票
38 售票窗口1正在售第11张车票
39 售票窗口1正在售第10张车票
40 售票窗口1正在售第9张车票
41 售票窗口1正在售第8张车票
42 售票窗口1正在售第7张车票
43 售票窗口1正在售第6张车票
44 售票窗口1正在售第5张车票
45 售票窗口1正在售第4张车票
46 售票窗口1正在售第3张车票
47 售票窗口1正在售第2张车票
48 售票窗口1正在售第1张车票
49 售票窗口3正在售第23张车票
50 售票窗口2正在售第24张车票

View Code

但是在实际应用场景中,我们通常要考虑到因为网络延迟等其他因素造成的购票延迟,这里我们将Ticket稍微进行了改造:

 1 package com.jon.thread;
 2 
 3 public class TicketSell implements Runnable {
 4     private int tickets = 50;//设置车票数量
 5     @Override
 6     public void run() {
 7         while(true){
 8             try {
 9                 Thread.sleep(100);//将线程睡眠100毫秒用来模拟延迟
10             } catch (InterruptedException e) {                
11                 e.printStackTrace();
12             }
13             if(tickets>0){        
14                 //输出当前是哪个线程在出售第几张车票
15                 System.out.println(Thread.currentThread().getName() + "正在售第" + (tickets--) + "张车票");
16             }
17         }
18     }
19 
20 }

再次运行,可以看到有些售票窗口售出了相同的票,甚至还出现了-1、0 ,很明显出现了线程安全问题:

 1 售票窗口1正在售第49张车票
 2 售票窗口2正在售第49张车票
 3 售票窗口3正在售第50张车票
 4 售票窗口2正在售第48张车票
 5 售票窗口1正在售第46张车票
 6 售票窗口3正在售第47张车票
 7 售票窗口2正在售第45张车票
 8 售票窗口1正在售第44张车票//窗口1,3出售了相同的44号车票
 9 售票窗口3正在售第44张车票
10 售票窗口2正在售第43张车票
11 售票窗口1正在售第41张车票
12 售票窗口3正在售第42张车票
13 售票窗口2正在售第40张车票
14 售票窗口3正在售第39张车票
15 售票窗口1正在售第39张车票
16 售票窗口1正在售第38张车票
17 售票窗口2正在售第37张车票
18 售票窗口3正在售第36张车票
19 售票窗口1正在售第35张车票
20 售票窗口3正在售第33张车票
21 售票窗口2正在售第34张车票
22 售票窗口1正在售第32张车票
23 售票窗口3正在售第31张车票
24 售票窗口2正在售第30张车票
25 售票窗口3正在售第29张车票
26 售票窗口1正在售第29张车票
27 售票窗口2正在售第28张车票
28 售票窗口3正在售第27张车票
29 售票窗口1正在售第27张车票
30 售票窗口2正在售第26张车票
31 售票窗口1正在售第25张车票
32 售票窗口3正在售第24张车票
33 售票窗口2正在售第23张车票
34 售票窗口1正在售第22张车票
35 售票窗口3正在售第21张车票
36 售票窗口2正在售第20张车票
37 售票窗口1正在售第19张车票
38 售票窗口3正在售第18张车票
39 售票窗口2正在售第17张车票
40 售票窗口3正在售第16张车票
41 售票窗口1正在售第15张车票
42 售票窗口2正在售第14张车票
43 售票窗口3正在售第13张车票
44 售票窗口1正在售第12张车票
45 售票窗口2正在售第11张车票
46 售票窗口1正在售第10张车票
47 售票窗口3正在售第9张车票
48 售票窗口2正在售第8张车票
49 售票窗口1正在售第7张车票
50 售票窗口3正在售第6张车票
51 售票窗口2正在售第5张车票
52 售票窗口1正在售第4张车票
53 售票窗口2正在售第2张车票
54 售票窗口3正在售第3张车票
55 售票窗口1正在售第0张车票
56 售票窗口3正在售第1张车票
57 售票窗口2正在售第-1张车票//甚至出现了-1号、0号

产生这种结果的原因:

  假设系统在出售“第44张车票”的时候,线程“售票窗口1”获取到了CPU的执行权,流程用下图表示:

判断应用程序是否有线程安全的问题不外乎以下几点:  

*是否是多线程环境
*是否有共享数据
*是否有多条语句操作共享数据

很明显上面的程序都满足这三点,解决思路:把多个语句操作共享数据的代码给锁起来,让任意时刻只能有一个线程执行即可。楼主这里使用同步代码块改造Ticket类如下:

 1 package com.jon.thread;
 2 
 3 public class TicketSell implements Runnable {
 4     private int tickets = 50;
 5     private Object obj = new Object();
 6     @Override
 7     public void run() {
 8         while(true){
 9             synchronized (obj) {
10                 try {
11                     Thread.sleep(100);
12                 } catch (InterruptedException e) {                
13                     e.printStackTrace();
14                 }
15                 if(tickets>0){                
16                     System.out.println(Thread.currentThread().getName() + "正在售第" + (tickets--) + "张车票");
17                 }
18             }            
19         }
20     }
21 
22 }

再来运行,结果如下:

 1 售票窗口3正在售第50张车票
 2 售票窗口3正在售第49张车票
 3 售票窗口3正在售第48张车票
 4 售票窗口1正在售第47张车票
 5 售票窗口1正在售第46张车票
 6 售票窗口1正在售第45张车票
 7 售票窗口2正在售第44张车票
 8 售票窗口2正在售第43张车票
 9 售票窗口2正在售第42张车票
10 售票窗口2正在售第41张车票
11 售票窗口1正在售第40张车票
12 售票窗口1正在售第39张车票
13 售票窗口3正在售第38张车票
14 售票窗口1正在售第37张车票
15 售票窗口2正在售第36张车票
16 售票窗口2正在售第35张车票
17 售票窗口2正在售第34张车票
18 售票窗口2正在售第33张车票
19 售票窗口2正在售第32张车票
20 售票窗口2正在售第31张车票
21 售票窗口1正在售第30张车票
22 售票窗口3正在售第29张车票
23 售票窗口3正在售第28张车票
24 售票窗口3正在售第27张车票
25 售票窗口3正在售第26张车票
26 售票窗口3正在售第25张车票
27 售票窗口3正在售第24张车票
28 售票窗口3正在售第23张车票
29 售票窗口3正在售第22张车票
30 售票窗口3正在售第21张车票
31 售票窗口1正在售第20张车票
32 售票窗口1正在售第19张车票
33 售票窗口1正在售第18张车票
34 售票窗口2正在售第17张车票
35 售票窗口2正在售第16张车票
36 售票窗口2正在售第15张车票
37 售票窗口1正在售第14张车票
38 售票窗口3正在售第13张车票
39 售票窗口3正在售第12张车票
40 售票窗口3正在售第11张车票
41 售票窗口1正在售第10张车票
42 售票窗口1正在售第9张车票
43 售票窗口2正在售第8张车票
44 售票窗口2正在售第7张车票
45 售票窗口2正在售第6张车票
46 售票窗口1正在售第5张车票
47 售票窗口1正在售第4张车票
48 售票窗口1正在售第3张车票
49 售票窗口3正在售第2张车票
50 售票窗口3正在售第1张车票

View Code

可以看到,不再有重复的票出现。当然同步代码块也有它的弊端,当线程相当多时,因为每个线程都会去判断同步上的锁,这是很耗费资源的,无形中会降低程序的运行效率。

 有兴趣的小伙伴可以到这里下载文章中用到的代码:https://github.com/LJunChina/JavaResource

Bean复制

有的时候我们需要将一个bean的属性赋值到另一个bean的属性中,比如用户提交过来的表单bean需要将该bean中的属性值赋值到对应的数据库bean,我们通常会以这样的方式做:

1 User user = new User("1", "Jon_China", "123456", "1992-11-17", "127.0.0.1");
2 TargetUser target = new TargetUser();
3 target.setId(user.getId());
4 target.setUserName(user.getUserName());
5 target.setPassword(user.getPassword());

当bean的属性过多时是不是感觉“嘿打脑壳”。不要紧,Apache提供bean的copy工具BeanUtil. 

当然是用也是比较简单的,楼主一步一步说明:

1、先搞两个bean

package com.jon.china.beancopy;
//假设是用户提交过来的bean
public class User {
    private String Id;
    private String userName;
    private String password;
    private String birthday;
    private String loginIp;
    public String getId() {
        return Id;
    }
    public void setId(String id) {
        Id = id;
    }
    public String getUserName() {
        return userName;
    }
    public void setUserName(String userName) {
        this.userName = userName;
    }
    public String getPassword() {
        return password;
    }
    public void setPassword(String password) {
        this.password = password;
    }
    public String getBirthday() {
        return birthday;
    }
    public void setBirthday(String birthday) {
        this.birthday = birthday;
    }
    public String getLoginIp() {
        return loginIp;
    }
    public void setLoginIp(String loginIp) {
        this.loginIp = loginIp;
    }
    public User(String id, String userName, String password, String birthday,
            String loginIp) {        
        Id = id;
        this.userName = userName;
        this.password = password;
        this.birthday = birthday;
        this.loginIp = loginIp;
    }
    
}

定义目标bean,目的将User属性值复制到TargetUser中,需要注意的是属性birthday类型的变化。

package com.jon.china.beancopy;

import java.util.Date;

public class TargetUser {
    private String Id;
    private String userName;
    private String password;
    private Date birthday;
    private String loginIp;
    public String getId() {
        return Id;
    }
    public void setId(String id) {
        Id = id;
    }
    public String getUserName() {
        return userName;
    }
    public void setUserName(String userName) {
        this.userName = userName;
    }
    public String getPassword() {
        return password;
    }
    public void setPassword(String password) {
        this.password = password;
    }
    public Date getBirthday() {
        return birthday;
    }
    public void setBirthday(Date birthday) {
        this.birthday = birthday;
    }
    public String getLoginIp() {
        return loginIp;
    }
    public void setLoginIp(String loginIp) {
        this.loginIp = loginIp;
    }
    
}

2、由于birthday需要将String转换为Date类型,这里定义个转换器,实现Converter接口:

package com.jon.china.beancopy;

import java.text.ParseException;
import java.text.SimpleDateFormat;

import org.apache.commons.beanutils.Converter;

public class BeanConvert implements Converter {
    /**
     * 日期类型转换器
     */
    @Override
    public Object convert(Class type, Object value) {
        if(value==null){
            return null;
        }
        String v = (String) value;
        if("".equals(v.trim())){
            return null;
        }
        SimpleDateFormat sf = new SimpleDateFormat("yyyy-mm-dd");
        try {
            return sf.parse(v);
        } catch (ParseException e) {
            throw new RuntimeException(e);
        }        
    }

}

3、初始化User,注册转换器,开始转换:

package com.jon.china.beancopy;


import java.util.Date;

import org.apache.commons.beanutils.BeanUtils;
import org.apache.commons.beanutils.ConvertUtils;

public class Test {

    
    public static void main(String[] args) {
        User user = new User("1", "Jon_China", "123456", "1992-11-17", "127.0.0.1");
        TargetUser target = new TargetUser();        
        //注册日期转换器
        ConvertUtils.register(new BeanConvert(), Date.class);
        try {
            BeanUtils.copyProperties(target, user);//开始复制bean
        } catch (Exception e) {
            throw new RuntimeException(e);
        } 
        System.out.println(target.getLoginIp());
    }

}

4、成功,结束。

源码地址:https://github.com/LJunChina/BeanCopy

 

java中map集合的迭代

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class TestMap {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put(1, "a");
        map.put(2, "b");
        map.put(3, "ab");
        map.put(4, "ab");
        map.put(4, "ab");// 和上面相同 , 会自己筛选
        System.out.println(map.size());
        // 第一种:
        /*
         * Set set = map.keySet(); //得到所有key的集合
         * 
         * for (Integer in : set) { String str = map.get(in);
         * System.out.println(in + "     " + str); }
         */
        System.out.println("第一种:通过Map.keySet遍历key和value:");
        for (Integer in : map.keySet()) {
            //map.keySet()返回的是所有key的值
            String str = map.get(in);//得到每个key多对用value的值
            System.out.println(in + "     " + str);
        }
        // 第二种:
        System.out.println("第二种:通过Map.entrySet使用iterator遍历key和value:");
        Iterator> it = map.entrySet().iterator();
        while (it.hasNext()) {
             Map.Entry entry = it.next();
               System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
        }
        // 第三种:推荐,尤其是容量大时
        System.out.println("第三种:通过Map.entrySet遍历key和value");
        for (Map.Entry entry : map.entrySet()) {
            //Map.entry 映射项(键-值对)  有几个方法:用上面的名字entry
            //entry.getKey() ;entry.getValue(); entry.setValue();
            //map.entrySet()  返回此映射中包含的映射关系的 Set视图。
            System.out.println("key= " + entry.getKey() + " and value= "
                    + entry.getValue());
        }
        // 第四种:
        System.out.println("第四种:通过Map.values()遍历所有的value,但不能遍历key");
        for (String v : map.values()) {
            System.out.println("value= " + v);
        }
    }
}