Posted in Java, 技术

Java 容器 & 泛型:三、HashSet,TreeSet 和 LinkedHashSet比较

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

上一篇总结了下ArrayList 、LinkedList和Vector比较,今天泥瓦匠总结下Hash 、LinkedList和Vector比较。其实大家都是Collection,只不过有点各自特性。那就是数据结构的不同表现。

 

一、Set回顾

一个不包括重复元素(包括可变对象)的Collection,是一种无序的集合。Set不包含满 a.equals(b) 的元素对a和b,并且最多有一个null。
泥瓦匠的记忆宫殿:
1、不允许包含相同元素

2、判断对象是否相同,根据equals方法

java-collection-hierarchy

 

二、HashSet

一个按着Hash算法来存储集合中的元素,其元素值可以是NULL。它不能保证元素的排列顺序。同样,HashSet是不同步的,如果需要多线程访问它的话,可以用 Collections.synchronizedSet 方法来包装它:

Set s = Collections.synchronizedSet(new HashSet(...));

同上一节一样,用迭代器的时候,也要注意 并发修改异常ConcurrentModificationException

 

要注意的地方是,HashSet集合判断两个元素相等不单单是equals方法,并且必须hashCode()方法返回值也要相等。看下面的例子:

import java.util.HashSet;

class EuqalsObj 
{
	public boolean equals(Object obj)
	{
		return true;
	}
}

class HashCodeObj
{
	public int hashCode()
	{
		return 1;
	}
}

class HashSetObj
{
	public int hashCode()
	{
		return 2;
	}

	public boolean equals(Object obj)
	{
		return true;
	}
}

public class HashSetTest
{
	public static void main(String[] args)
	{
		HashSet objs = new HashSet();
		objs.add(new EuqalsObj());
		objs.add(new EuqalsObj());
		objs.add(new HashCodeObj());
		objs.add(new HashCodeObj());
		objs.add(new HashSetObj());
		objs.add(new HashSetObj());
		
		System.out.println("HashSet Elements:");
		System.out.print("\t" + objs + "\n");
	}
}

Run 一下,控制台如下输出:

HashSet Elements:
	[HashCodeObj@1, HashCodeObj@1, HashSetObj@2, EuqalsObj@1471cb25, EuqalsObj@3acff49f]

泥瓦匠根据结果,一一到来。首先,排列顺序不定。

HashSetObj 类满足我们刚刚的要求,所以集合中只有一个且它的HashCode值为2。

HashCodeObj 类虽然它们HashCode值为1,但是他们不相等。(其实当HashCode值一样,这个存储位置会采用链式结构保存两个HashCodeObj对象。)

同样,EqualsObj 类他们相等,但是他们HashCode值不等,分别为1471cb25、3acff49f。

 

因此,用HashSet添加可变对象,要注意当对象有可能修改后和其他对象矛盾,这样我们无法从HashSet找到准确我们需要的对象。

 

三、LinkedHashList

HashSet的子类,也同样有HashCode值来决定元素位置。但是它使用链表维护元素的次序。记住两个字:有序

有序的妙用,复制。比如泥瓦匠实现一个HashSet无序添加,然后复制一个一样次序的HashSet来。代码如下:

package com.sedion.bysocket.collection;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashListTest
{
	public static void main(String[] args)
	{
		/* 复制HashSet */
		Set h1 = new HashSet<String>();
		h1.add("List");
		h1.add("Queue");
		h1.add("Set");
		h1.add("Map");
		
		System.out.println("HashSet Elements:");
		System.out.print("\t" + h1 + "\n");
		
		Set h2 = copy(h1);
		System.out.println("HashSet Elements After Copy:");
		System.out.print("\t" + h2 + "\n");
	}
	
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static Set copy(Set set)
	{
		Set setCopy = new LinkedHashSet(set);
		return setCopy;
	}
	
}

Run 一下,控制台输出:

HashSet Elements:
	[Map, Queue, Set, List]
HashSet Elements After Copy:
	[Map, Queue, Set, List]

可见,每个数据结构都有它存在的理由。

 

四、TreeSet

TreeSet使用树结构实现(红黑树),集合中的元素进行排序,但是添加、删除和包含的算法复杂度为O(log(n))。

举个例子吧,首先我们定义一个Bird类。(鸟是泥瓦匠最喜欢的动物)

class Bird 
{
	int size;
	
	public Bird(int s)
	{
		size = s;
	}
	
	public String toString()
	{
		return size + "";
	}

}

然后用TreeSet添加Bird类。

public class TreeSetTest
{
	public static void main(String[] args)
	{
		TreeSet<Bird> bSet = new TreeSet<Bird>();
		bSet.add(new Bird(1));
		bSet.add(new Bird(3));
		bSet.add(new Bird(2));
		
		Iterator<Bird> iter = bSet.iterator();
		
		while (iter.hasNext())
		{
			Bird bird = (Bird) iter.next();
			System.out.println(bird);
		}
	}
}

Run一下,控制台输出如下:

Exception in thread "main" java.lang.ClassCastException: Bird cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(Unknown Source)
	at java.util.TreeMap.put(Unknown Source)
	at java.util.TreeSet.add(Unknown Source)
	at com.sedion.bysocket.collection.TreeSetTest.main(TreeSetTest.java:29)

答案很明显,TreeSet是排序的。所以Bird需要实现Comparable此接口。

java.lang.Comparable此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序,类的 compareTo 方法被称为它的自然比较方法

 

修改Bird如下:

class Bird implements Comparable<Bird>
{
	int size;
	
	public Bird(int s)
	{
		size = s;
	}
	
	public String toString()
	{
		return size + "号鸟";
	}

	@Override
	public int compareTo(Bird o)
	{
		return size - o.size;
	}
	
}

再次Run一下:

1号鸟
2号鸟
3号鸟

 

五、性能测试比较

针对上面三种Set集合,我们对它们的Add方法进行性能测试:

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.TreeSet;

class Bird implements Comparable<Bird>
{
	int size;
	
	public Bird(int s)
	{
		size = s;
	}
	
	public String toString()
	{
		return size + "号鸟";
	}

	@Override
	public int compareTo(Bird o)
	{
		return size - o.size;
	}
	
}
public class Set
{
	public static void main(String[] args)
	{
		Random r = new Random();
		 
		HashSet<Bird> hashSet = new HashSet<Bird>();
		TreeSet<Bird> treeSet = new TreeSet<Bird>();
		LinkedHashSet<Bird> linkedSet = new LinkedHashSet<Bird>();
	 
		// start time
		long startTime = System.nanoTime();
	 
		for (int i = 0; i < 1000; i++) {
			int x = r.nextInt(1000 - 10) + 10;
			hashSet.add(new Bird(x));
		}
		// end time
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("HashSet: " + duration);
	 
		// start time
		startTime = System.nanoTime();
		for (int i = 0; i < 1000; i++) {
			int x = r.nextInt(1000 - 10) + 10;
			treeSet.add(new Bird(x));
		}
		// end time
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("TreeSet: " + duration);
	 
		// start time
		startTime = System.nanoTime();
		for (int i = 0; i < 1000; i++) {
			int x = r.nextInt(1000 - 10) + 10;
			linkedSet.add(new Bird(x));
		}
		// end time
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedHashSet: " + duration);
	}
}

Run一下,可以在控制台中看出:

HashSet: 2610998
TreeSet: 3195378
LinkedHashSet: 2673782

可见,TreeSet因为需要进行比较,所以性能比较差。

 

六、总结

HashSet:equlas hashcode

LinkedHashSet:链式结构

TreeSet:比较,Comparable接口,性能较差

Posted in Working Skills, 技术

JavaEE 并发:一、FOR UPDATE 实战,监测并解决。

synchronized

 

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

 

一、前言

针对并发,老生常谈了。目前一个通用的做法有两种:锁机制:1.悲观锁;2.乐观锁。

但是这篇我主要用于记录我这次处理的经历,另外希望能看的大神,大牛,技师者,学长,兄长,大哥们能在评论中发表自己的看法和解决技巧等。

 

二、故事是这样的

一个表,暂且叫 wallet,其中3个字段是 金额。初始值为0,如下图所示:
image

 

然后我们写了一个极为简单的Controller,并写了下面的Service代码:

@Override
	public void testLock(int lockId)
	{
		Wallet wallet = walletMapper.selectByPrimaryKey(4);
		
		BigDecimal one = new BigDecimal(1.00);
		BigDecimal two = new BigDecimal(2.00);
		BigDecimal three = new BigDecimal(3.00);
		
		wallet.setWalletAmount(wallet.getWalletAmount().add(one));
		wallet.setWalletAvailableAmount(wallet.getWalletAvailableAmount().subtract(two));
		wallet.setOldAmount(wallet.getOldAmount().add(three));		
		
		walletMapper.updateByPrimaryKeySelective(wallet);
	}

就简单的通过主键读取到一个对象,注意这个对象是没加锁的。也就是说,所对应的SQL如下:

SELECT 
    <include refid="Base_Column_List" />
    FROM wallet
    WHERE wallet_id = #{walletId,jdbcType=INTEGER}

我这边是MyBiatis,大家应该看得懂的。然后一个增加1 一个减少2 一个增加 3。

 

三、测试是这样

我用了Web应用压力测试工具:Boomhttps://github.com/rakyll/boom Go编写的HTTP(S)负载生成器,ApacheBench(AB)的替代工具。Boom是一个微型程序,能够对Web应用程序进行负载测试。它类似于 Apache Bench ,但在不同的平台上有更好的可用性,安装使用也比较简单。

简单使用方式如下:

boom -n 1000 -c 200 http://www.baidu.com

Options:
  -n  Number of requests to run.
  -c  Number of requests to run concurrently. Total number of requests cannot
      be smaller than the concurency level.
  -q  Rate limit, in seconds (QPS).
  -o  Output type. If none provided, a summary is printed.
      "csv" is the only supported alternative. Dumps the response
      metrics in comma-seperated values format.
 
  -m  HTTP method, one of GET, POST, PUT, DELETE, HEAD, OPTIONS.
  -h  Custom HTTP headers, name1:value1;name2:value2.
  -d  HTTP request body.
  -T  Content-type, defaults to "text/html".
  -a  Basic authentication, username:password.
 
  -allow-insecure Allow bad/expired TLS/SSL certificates.

所以我就如图进行压力测试,可见这个小工具还挺美的,这里我连接数1000,并发数100
image
可见后台程序报错了。什么错误呢?

Caused by: com.mysql.jdbc.exceptions.jdbc4.MySQLTransactionRollbackException: Deadlock found when trying to get lock; try restarting transaction

原来并发导致update死表了。数据库的数据不用看了肯定是错误的。

 

四、FOR UPDATE的使用

先补一下其知识:利用select * for update 可以锁表/锁行。自然锁表的压力远大于锁行。所以我们采用锁行。什么时候锁表呢?

假设有个表单products ,里面有id跟name二个栏位,id是主键。
例1: (明确指定主键,并且有此笔资料,row lock)
SELECT * FROM wallet WHERE id=’3′ FOR UPDATE;
例2: (明确指定主键,若查无此笔资料,无lock)
SELECT * FROM wallet WHERE id=’-1′ FOR UPDATE;
例2: (无主键,table lock)
SELECT * FROM wallet WHERE name=’Mouse’ FOR UPDATE;
例3: (主键不明确,table lock)
SELECT * FROM wallet WHERE id<>’3′ FOR UPDATE;
例4: (主键不明确,table lock)
SELECT * FROM wallet WHERE id LIKE ‘3’ FOR UPDATE;

 

因此我们更新了下Service层的Mapper方法:

@Override
	public void testLock(int lockId)
	{
		Wallet wallet = walletMapper.selectForUpdate(4);
		
		BigDecimal one = new BigDecimal(1.00);
		BigDecimal two = new BigDecimal(2.00);
		BigDecimal three = new BigDecimal(3.00);
		
		wallet.setWalletAmount(wallet.getWalletAmount().add(one));
		wallet.setWalletAvailableAmount(wallet.getWalletAvailableAmount().subtract(two));
		wallet.setOldAmount(wallet.getOldAmount().add(three));		
		
		walletMapper.updateByPrimaryKeySelective(wallet);
	}

所对应的SQL如下:

  <select id="selectForUpdate" resultMap="BaseResultMap" parameterType="java.lang.Integer" >
    SELECT 
    <include refid="Base_Column_List" />
    FROM wallet
    WHERE wallet_id = #{walletId,jdbcType=INTEGER}
    FOR UPDATE
  </select>

自然大家可以看到,我这边加了锁,是通过主键锁行。

 

按着上面的测试连接数1000,并发数100,控制台没报错。

image

数据库结果也是很不错。

image

 

五、加大压力

按着上面的测试连接数5000,并发数350,控制台还是没报错。

image

数据库结果却是很出错了!!!
image

少update了很多值。为什么呢?

 

六、jvisualvm 小工具检测,发现Tomcat线程连接数默认不够

然后我用jvisualvm 小工具检测。多测了几次,发现连接数5000,并发数350,并发数上升。有一个图的值始终不变。如图:

QQ截图20150322124739

发现图中 tomcat的守护线程一直在200左右。后来我去找了下tomcat的server.xml发现了,使用了默认,大概就是200左右。

 

所以就配置了一下,大致配置方法有两种如下:

第1种方式:配置Connector
maxThreads:tomcat可用于请求处理的最大线程数
minSpareThreads:tomcat初始线程数,即最小空闲线程数
maxSpareThreads:tomcat最大空闲线程数,超过的会被关闭
acceptCount:当所有可以使用的处理请求的线程数都被使用时,可以放到处理队列中的请求数,超过这个数的请求将不予处理

<Connectorport="8080"maxHttpHeaderSize="8192"maxThreads="150"minSpareThreads="25"maxSpareThreads="75"enableLookups="false"redirectPort="8443"acceptCount="100"connectionTimeout="20000"disableUploadTimeout="true"/>

 

第2种方式:配置Executor和Connector

name:线程池的名字
class:线程池的类名
namePrefix:线程池中线程的命名前缀
maxThreads:线程池的最大线程数
minSpareThreads:线程池的最小空闲线程数
maxIdleTime:超过最小空闲线程数时,多的线程会等待这个时间长度,然后关闭
threadPriority:线程优先级

<Executorname="tomcatThreadPool"namePrefix="req-exec-"maxThreads="1000"minSpareThreads="50"maxIdleTime="60000"/>

<Connectorport="8080"protocol="HTTP/1.1"executor="tomcatThreadPool"/>

 

maxThreads:线程池的最大线程数,直接配置1000,然后用连接数10000,并发数800测试。轻松见图:

UFRJFLLO6@F1)LWQ6EQJ8P8

image

七、总结

感谢帮助我的人。希望有大牛在此讨论相关。小生感激不尽。

Posted in Java, 技术

Java 容器 & 泛型:二、ArrayList 、LinkedList和Vector比较

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

继续上一篇的容器文章认识容器,泥瓦匠慢慢带你们走进List的容器解说。今天泥瓦匠想说说 ArrayList 、LinkedList和Vector比较。

一、List回顾

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1e2,并且如果列表本身允许 null 元素的话,通常它们允许多个 null 元素。实现List的有:ArrayList、LinkedList、Vector、Stack等。值得一提的是,Vector在JDK1.1的时候就有了,而List在JDK1.2的时候出现,待会我们会聊到ArrayList和Vector的区别。

 

二、ArrayList vs. Vector

ArrayList是一个可调整大小的数组实现的序列。随着元素增加,其大小会动态的增加。此类在Iterator或ListIterator迭代中,调用容器自身的remove和add方法进行修改,会抛出ConcurrentModificationException并发修改异常。

注意,此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须 保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成,以防止意外对列表进行不同步的访问:

List list = Collections.synchronizedList(new ArrayList(...));

下面演示下相关ArrayList例子。

ArrayList基本方法代码:

@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void listMethods()
	{
		
		List a1 = new ArrayList<String>();
		
		a1.add("List01");
		a1.add("List03");
		a1.add("List04");
		System.out.print("原来集合:\n\t"+a1+"\n");
		
		a1.add(1,"List02");
		System.out.print("指定角标1插入:\n\t"+a1+"\n");
		
		a1.remove(2);
		System.out.print("指定角标2删除:\n\t"+a1+"\n");
		
		System.out.print("指定角标2查询:\n\t"+a1.get(2)+"\n");
		
		Iterator i1 = a1.iterator();
		System.out.println("用迭代器查询全部元素:");
		while (i1.hasNext())
		{
			System.out.print(i1.next()+",");
		}
	}

可以从控制台可以看出:

原来集合:
	[List01, List03, List04]
指定角标1插入:
	[List01, List02, List03, List04]
指定角标2删除:
	[List01, List02, List04]
指定角标2查询:
	List04
用迭代器查询全部元素:
List01,List02,List04

在上面我们可以根据角标来增加(add)、删除(remove)、获取(get)列表里面元素。ArrayList提供了Iterator迭代器来遍历序列。值得注意的是,迭代器的就相当于一个指针指向角标,next()方法就相当于指针往后移一位。所以切记,用迭代器中一次循环用一次next()。

 

下面演示下在ConcurrentModificationException的出现,及处理方案。泥瓦匠用Iterator演示这个异常的出现:

public static void iteratorTest()
{
List a1 = new ArrayList<String>();

a1.add("List01");
a1.add("List02");
a1.add("List04");
a1.add("List05");

Iterator i1 = a1.iterator();
while (i1.hasNext())
{
Object obj = i1.next();
if (obj.equals("List02"))
a1.add("List03");
}

System.out.print("集合:\n\t"+a1+"\n");
}

运行,我们可以在控制台看到:
image

怎么解决的,先看清楚这个问题。问题描述很清楚,在创建迭代器之后,除非通过迭代器自身的 removeadd 方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出 ConcurrentModificationException

因此我们应该这样修改代码,用ListIterator迭代器提供方法,:

@SuppressWarnings({ "unchecked", "rawtypes" })
	public static void listIterator()
	{
		
		List a1 = new ArrayList<String>();
		
		a1.add("List01");
		a1.add("List");
		a1.add("List03");
		a1.add("List04");
		
		ListIterator l1 = a1.listIterator();
		while (l1.hasNext())
		{
			Object obj = l1.next();
			if (obj.equals("List"))
			{
				l1.remove();
				l1.add("List02");
			}
		}
		System.out.print("集合:\n\t"+a1+"\n");
	}

运行下,我们可以看到:

集合:
	[List01, List02, List03, List04]

这样,我们成功解决了这个并发修改异常。把其中‘List’元素删除,新增了一个‘List02’的元素。

 

Vector非常类似ArrayList。早在JDK1.1的时候就出现了,以前没有所谓的List接口,现在此类被改进为实现List接口。但与新的Collection不同的是,Vector是同步的。泥瓦匠想说的是Vector,在像查询的性能上会比ArrayList开销大。下面演示下Vector的基本例子:

@SuppressWarnings({ "unchecked", "rawtypes" })
	public static void vectorMethods()
	{
		Vector v1 = new Vector<String>();
		
		v1.add("Vector001");
		v1.add("Vector002");
		v1.add("Vector003");
		v1.add("Vector004");
		v1.add("Vector005");
		
		Enumeration e1 =v1.elements();
		while (e1.hasMoreElements())
		{
			Object object = e1.nextElement();
			System.out.println(object);
		}
	}

从方法上看几乎没差别,同样注意的是:此接口的功能与 Iterator 接口的功能是重复的。此外,Iterator 接口添加了一个可选的移除操作,并使用较短的方法名。新的实现应该优先考虑使用 Iterator 接口而不是 Enumeration 接口。

 

三、LinkedList及其与ArrayList性能比

LinkedList与ArrayList一样实现List接口,LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些。LinkedList实现所有可选的列表操作,并允许所有的元素包括null。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列

LinkedList和ArrayList的方法时间复杂度总结如下图所示。
image

表中,添加add()指添加元素的方法,remove()是指除去(int index)角标。ArrayList具有O(N)的任意指数时间复杂度的添加/删除,但O(1)的操作列表的末尾。链表的O(n)的任意指数时间复杂度的添加/删除,但O(1)操作端/列表的开始。

 

泥瓦匠用代码验证下这个结论:

public static void testPerBtwnArlAndLkl()
	{
		ArrayList<Integer> arrayList   = new ArrayList<Integer>();
		LinkedList<Integer> linkedList = new LinkedList<Integer>();
				
		// ArrayList add
		long startTime	= System.nanoTime();
		long endTime;
		long duration; 
		 
		for (int i = 0; i < 100000; i++) {
			arrayList.add(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList add:  " + duration);
		 
		// LinkedList add
		startTime = System.nanoTime();
		 
		for (int i = 0; i < 100000; i++) {
			linkedList.add(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList add: " + duration);
		 
		// ArrayList get
		startTime = System.nanoTime();
		 
		for (int i = 0; i < 10000; i++) {
			arrayList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList get:  " + duration);
		 
		// LinkedList get
		startTime = System.nanoTime();
		 
		for (int i = 0; i < 10000; i++) {
			linkedList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList get: " + duration);
		 
		// ArrayList remove
		startTime = System.nanoTime();
		 
		for (int i = 9999; i >=0; i--) {
			arrayList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList remove:  " + duration);
		 
		// LinkedList remove
		startTime = System.nanoTime();
		 
		for (int i = 9999; i >=0; i--) {
			linkedList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList remove: " + duration);
	}

控制台输出如下:

ArrayList add:  16904776
LinkedList add: 12015418
ArrayList get:  1304593
LinkedList get: 108950741
ArrayList remove:  787388127
LinkedList remove: 128145950

对比下的话,其性能差距很明显。LinkedList在添加和删除中性能快,但在获取中性能差。从复杂度和测试结果,我们应该懂得平时在添加或者删除操作频繁的地方,选择LinkedList时考虑:

1、没有大量的元素的随机访问

2、添加/删除操作

 

自然我下面用LinedList实现一个数据结构–栈。泥瓦匠留给大家LinkedList的一些方法自己消化下。

package com.sedion.bysocket.collection;
import java.util.LinkedList;

/**
 * 用LinkedList实现栈
 * 队列和栈区别:队列先进先出,栈先进后出。
 */
public class Stack<T> 
{
    private LinkedList<T> storage = new LinkedList<T>();

    /** 入栈 */
    public void push(T v) 
    {
        storage.addFirst(v);
    }

    /** 出栈,但不删除 */
    public T peek() 
    {
        return storage.getFirst();
    }

    /** 出栈,删除 */
    public T pop() 
    {
        return storage.removeFirst();
    }

    /** 栈是否为空 */
    public boolean empty()
    {
        return storage.isEmpty();
    }

    /** 输出栈元素 */
    public String toString()
    {
        return storage.toString();
    }
    
    public static void main(String[] args) 
    {
        Stack stack=new Stack<String>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        System.out.println(stack.toString());
        Object obj=stack.peek();
        System.out.println(obj+"--"+stack.toString());
        obj=stack.pop();
        System.out.println(obj+"--"+stack.toString());
        System.out.println(stack.empty());
    }
}

四、总结

泥瓦匠总结如下:

Vector和ArrayList

1、vector是线程同步的,所以它也是线程安全的,而arraylist是线程异步的,是不安全的。

2、记住并发修改异常 java.util.ConcurrentModificationException ,优先考虑ArrayList,除非你在使用多线程所需。

Aarraylist和Linkedlist
1、对于随机访问get和set,ArrayList觉得优于LinkedList,LinkedList要移动指针。
2、于新增和删除操作add和remove,LinedList比较占优势,ArrayList要移动数据。
3、
单条数据插入或删除,ArrayList的速度反而优于LinkedList.原因是:LinkedList的数据结构是三个对象,组大小恰当就会比链表快吧,直接赋值就完了,不用再设置前后指针的值。
若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。

Posted in Java, 技术

Java 容器 & 泛型:一、认识容器

Writer:BYSocket(泥沙砖瓦浆木匠)

微博:BYSocket

豆瓣:BYSocket

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:Collection和Map

 

一、Collection vs Collections

首先,Collection 和 Collections 是两个不同的概念。之所以放在一起,是为了更好的比较。Collection是容器层次结构中根接口。而Collections是一个提供一些处理容器类静态方法的类。

CollectionVsCollections

JDK不提供Collection接口的具体实现,而是提供了更加具体的子接口(如Set和List)实现

那Collection接口存在有何作用呢?存在即是道理。

原因在于:所有容器的实现类(如ArrayList实现了List接口,HashSet实现了Set接口)提供了两个‘标准’的构造函数来实现:1、一个无参的构造方法(void)2、一个带有Collection类型单参数构造方法,用于创建一个具有其参数相同元素新的Collection及其实现类等。实际上:因为所有通用的容器类遵从Collection接口,用第二种构造方法是允许容器之间相互的复制。

 

二、Collection的类层次结构

下面的图是关于Collection的类的层次结构。

java-collection-hierarchy

 

Set

一个不包括重复元素(包括可变对象)的Collection,是一种无序的集合。Set不包含满足 a.equals(b) 的元素对a和b,并且最多有一个null。实现Set的接口有:EnumSet、HashSet、TreeSet等。下图是Set的JDK源码UML图。

Set

 

List

一个有序的Collection(也称序列),元素可以重复。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1e2,并且如果列表本身允许 null 元素的话,通常它们允许多个 null 元素。实现List的有:ArrayList、LinkedList、Vector、Stack等。下图是List的JDK源码UML图。

list

 

Queue

一种队列则是双端队列,支持在头、尾两端插入和移除元素,主要包括:ArrayDeque、LinkedBlockingDeque、LinkedList。另一种是阻塞式队列,队列满了以后再插入元素则会抛出异常,主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。虽然接口并未定义阻塞方法,但是实现类扩展了此接口。下图是Queue的JDK源码UML图。

queue

 

三、Map的类的层次结构

下面的图是Map的层次结构图MapClassHierarchy-600x354

Map:

是一个键值对的集合。也就是说,一个映射不能包含重复的键,每个键最多映射到一个值。该接口取代了Dictionary抽象类。实现map的有:HashMap、TreeMap、HashTable、Properties、EnumMap。下图是Map的JDK源码UML图。

map

 

四、容器接口的小结

collection-summary

 

五、代码样例

对HashMap,HashSet,LinkedList,ArrayList,TreeMap,TreeSet的例子如下:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

@SuppressWarnings("unchecked")
public class CollectionAll
{
	
	public static void main(String[] args)
	{
		printLists();
		
		printSets();
		
		printMaps();
	}

	private static void printLists()
	{
		List<String> a1 = new ArrayList<String>();
		a1.add("List");
		a1.add("Set");
		a1.add("Queue");
		a1.add("Map");
		System.out.println("ArrayList Elements:");
		System.out.print("\t" + a1 + "\n");
		
		List<String> l1 = new LinkedList<String>();
		l1.add("List");
		l1.add("Set");
		l1.add("Queue");
		l1.add("Map");
		System.out.println("LinkedList Elements:");
		System.out.print("\t" + l1 + "\n");
	}
	@SuppressWarnings("rawtypes")
	private static void printSets()
	{
		Set h1 = new HashSet<String>();
		h1.add("List");
		h1.add("Set");
		h1.add("Queue");
		h1.add("Map");
		System.out.println("HashSet Elements:");
		System.out.print("\t" + h1 + "\n");
		
		Set t1 = new TreeSet<String>();
		t1.add("List");
		t1.add("Set");
		t1.add("Queue");
		t1.add("Map");
		System.out.println("TreeSet Elements:");
		System.out.print("\t" + t1 + "\n");
	}
	
	private static void printMaps()
	{
		Map<String, String> h1 = new HashMap<String, String>();
		h1.put("List", "ArrayList");
		h1.put("Set", "HashSet");
		h1.put("Queue", "PriorityQueue");
		h1.put("Map", "HashMap");
		System.out.println("HashMap Elements:");
		System.out.print("\t" + h1 + "\n");
		
		Map<String, String> t1 = new TreeMap<String,String>();
		t1.put("List", "ArrayList");
		t1.put("Set", "HashSet");
		t1.put("Queue", "PriorityQueue");
		t1.put("Map", "HashMap");
		System.out.println("TreeMap Elements:");
		System.out.print("\t" + t1 + "\n");
		
	}
}

控制台打印如下:

ArrayList Elements:
	[List, Set, Queue, Map]
LinkedList Elements:
	[List, Set, Queue, Map]
HashSet Elements:
	[Map, Queue, Set, List]
TreeSet Elements:
	[List, Map, Queue, Set]
HashMap Elements:
	{Map=HashMap, Queue=PriorityQueue, Set=HashSet, List=ArrayList}
TreeMap Elements:
	{List=ArrayList, Map=HashMap, Queue=PriorityQueue, Set=HashSet}

 

六、总结

异同点

出处:http://blog.csdn.net/softwave/article/details/4166598

Vector和ArrayList

1,vector是线程同步的,所以它也是线程安全的,而arraylist是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用arraylist效率比较高。
2,如果集合中的元素的数目大于目前集合数组的长度时,vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据,用vector有一定的优势。
3,如果查找一个指定位置的数据,vector和arraylist使用的时间是相同的,都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)n为总长度,这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。

ArrayList 和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要设计到数组元素移动等内存操作,所以索引数据快插入数据慢,Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快!

Aarraylist和Linkedlist

1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。

HashMap与TreeMap

1、HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。HashMap中元素的排列顺序是不固定的)。

2、  HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。集合框架”提供两种常规的Map实现:HashMap和TreeMap (TreeMap实现SortedMap接口)。

3、在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项,因为该树总处于平衡状态。

hashtable与hashmap

1、历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现 。

2、同步性:Hashtable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的 。

3、值:只有HashMap可以让你将空值作为一个表的条目的key或value 。

collection

Posted in Java, 技术

JAVA UUID 生成唯一标识

Writer:BYSocket(泥沙砖瓦浆木匠)

Reprint it anywhere u want

需求

    项目在设计表的时候,要处理并发多的一些数据,类似订单号不能重复,要保持唯一。原本以为来个时间戳,精确到毫秒应该不错了。后来觉得是错了,测试环境下很多一样的ID,不能达到唯一标识。

UUID

    JDK API 是这么说的:
“表示通用唯一标识符 (UUID) 的类。 UUID 表示一个 128 位的值。”

    详细的说就是:
“UUID含义是通用唯一识别码 (Universally Unique Identifier),这 是一个软件建构的标准,也是被开源软件基金会 (Open Software Foundation, OSF) 的组织在分布式计算环境 (Distributed Computing Environment, DCE) 领域的一部份。UUID 的目的,是让分布式系统中的所有元素,都能有唯一的辨识资讯,而不需要透过中央控制端来做辨识资讯的指定。如此一来,每个人都可以建立不与其它人冲突的 UUID。在这样的情况下,就不需考虑数据库建立时的名称重复问题。目前最广泛应用的 UUID,即是微软的 Microsoft’s Globally Unique Identifiers (GUIDs),而其他重要的应用,则有 Linux ext2/ext3 档案系统、LUKS 加密分割区、GNOME、KDE、Mac OS X 等等。”

 

UUID由以下几部分的组合:   

(1)当前日期和时间,UUID的第一个部分与时间有关,如果你在生成一个UUID之后,过几秒又生成一个UUID,则第一个部分不同,其余相同。   

(2)时钟序列   

(3)全局唯一的IEEE机器识别号,如果有网卡,从网卡MAC地址获得,没有网卡以其他方式获得。

 

代码实现

    很方便的,直接调用UUID的randomUUID方法,即可获得UUID对象,然后就获取了这个唯一标识码。

	public static void main(String[] args)
	{
		UUID uuid = UUID.randomUUID();
		System.out.println(uuid);
	}

    RUN一下,可以从控制台发现:

     65752c66-bd3f-4564-b8d6-92d66796e007

    这就是唯一标志码。但显得冗长,不够友好。如果在URL后面做参数,更加不够友好。还有存储一个UUID要花费更多的空间。获取的时间倒不必考虑太多。

 

获取八位UUID标识码

仿着网上大牛代码,直接上代码:

public static String[] chars = new String[] 
		{
			"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
			"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
			"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V","W", "X", "Y", "Z" 
		};  


	public static String getShortUuid() 
	{  
		StringBuffer stringBuffer = new StringBuffer();  
		String uuid = UUID.randomUUID().toString().replace("-", "");  
		for (int i = 0; i < 8; i++) 
		{  
			String str 		= uuid.substring(i * 4, i * 4 + 4);  
			int strInteger 	= Integer.parseInt(str, 16);  
			stringBuffer.append(chars[strInteger % 0x3E]);  
		}  
		
		return stringBuffer.toString();  
	}

 

用300个测试下,没问题。足够用了,能适应环境场景即可。

 

Writer:BYSocket(泥沙砖瓦浆木匠)

Reprint it anywhere u want