Posted in 技术, 网络

JavaEE 要懂的小事:一、图解Http协议

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

微         博:BYSocket

豆         瓣:BYSocket

FaceBook:BYSocket

Twitter    :BYSocket

泥瓦匠记得和左潇龙【博客园】上次聊天时,龙哥问了个Session的问题。我当时的理解就是云里雾里,先从Http协议理解开始吧。

一、技术基石及概述

问:什么是HTTP?
答:HTTP是一个客户端和服务器端请求响应标准TCP。其实建立在TCP之上的。

当我们打开百度网页时,是这样的:

https://www.baidu.com

多了个S,其实S表示TLS、SSL。在这里不做解释,因此HTTP的技术基石如图所示:

绘图1

那HTTP协议呢?HTTP协议(HyperText Transfer Protocol),即超文本传输协议是用于服务器传输到客户端浏览器的传输协议。Web上,服务器和客户端利用HTTP协议进行通信会话。有OOP思想的得出结论:其会话的结构是一个简单的请求/响应序列,即浏览器发出请求和服务器做出响应。

绘图1

 

二、深入理解技术基石和工作流程

既然HTTP是基于传输层的TCP协议,而TCP协议是面向连接端到端的协议。因此,使用HTTP协议传输前,首先建立TCP连接,就是因此在谈的TCP链接过程的“三次握手”。如图

绘图1

在Web上,HTTP协议使用TCP协议而不是UDP协议的原因在于一个网页必须传送很多数据,而且保证其完整性。TCP协议提供传输控制,按顺序组织数据和错误纠正的一系列功能。

一次HTTP操作称为一个事务,其工作过程可分为四步:

1、客户端与服务器需要建立连接。(比如某个超级链接,HTTP就开始了。)

2、建立连接后,发送请求。

3、服务器接到请求后,响应其响应信息。

4、客户端接收服务器所返回的信息通过浏览器显示在用户的显示屏上,然后客户机与服务器断开连接。

建立连接,其实建立在TCP连接基础之上。图解核心工作过程(即省去连接过程)如下:

绘图1

三、详解工作过程的HTTP报文

HTTP报文由从客户机到服务器的请求和从服务器到客户机的响应构成。

一、请求报文格式如下:

请求行

通用信息头

请求头

实体头

(空行)

报文主体

如图,请求我博客一篇文章时发送的报文内容:

image

对于其中请求报文详解:

1、请求行

方法字段 + URL + Http协议版本

2、通用信息头

Cache-Control头域:指定请求和响应遵循的缓存机制。

keep-alive 是其连接持续有效【在下面百度的例子,会得到验证】

3、请求头

Host头域,脑补吧

Referer头域:允许客户端指定请求URL的资源地址。

User-Agent头域:请求用户信息。【可以看出一些客户端浏览器的内核信息】

4、报文主体

如图中的 “ p=278 ”一般来说,请求主体少不了请求参数。

二、应答报文格式如下:

状态行

通用信息头

响应头

实体头

(空行)

报文主体

如图,就是这篇博客响应的内容:

image

对其中响应报文详解:

1、状态行

HTTP协议版本 + 状态码 + 状态代码的文本描述

【比如这里,200 代表请求成功】

2、通用信息头

keep-alive 是其连接持续有效【在下面百度的例子,会得到验证】

Date头域:时间描述

3、响应头

Server头:处理请求的原始服务器的软件信息。

4、实体头

Content-Type头:便是接收方实体的介质类型。(这也表示了你的报文主体是什么。)

(空行)

5、报文主体

这里就是HTML响应页面了,在截图tab页中的response中可查看。

一次简单的请求/响应就完成了。

三、HTTP协议知识补充

请求报文相关:

请求行-请求方法

GET            请求获取Request-URI所标识的资源
POST          在Request-URI所标识的资源后附加新的数据
HEAD         请求获取由Request-URI所标识的资源的响应消息报头
PUT            请求服务器存储一个资源,并用Request-URI作为其标识
DELETE       请求服务器删除Request-URI所标识的资源
TRACE        请求服务器回送收到的请求信息,主要用于测试或诊断
CONNECT  保留将来使用
OPTIONS   请求查询服务器的性能,或者查询与资源相关的选项和需求

响应报文相关:

响应行-状态码

1xx:指示信息–表示请求已接收,继续处理
2xx:成功–表示请求已被成功接收、理解、接受
3xx:重定向–要完成请求必须进行更进一步的操作
4xx:客户端错误–请求有语法错误或请求无法实现
5xx:服务器端错误–服务器未能实现合法的请求

常见的状态码

200 OK

请求成功(其后是对GET和POST请求的应答文档。)

 

304 Not Modified

未按预期修改文档。客户端有缓冲的文档并发出了一个条件性的请求(一般是提供If-Modified-Since头表示客户只想比指定日期更新的文档)。服务器告诉客户,原来缓冲的文档还可以继续使用。

 

404 Not Found

服务器无法找到被请求的页面。

 

500 Internal Server Error

请求未完成。服务器遇到不可预知的情况。

比如304,在浏览器第一次打开百度时,如图所示:

3AD)@_I2E8DMDH]35GHV1DL

刷新一下:

image

这上面的304就证明了

1、304状态码:有些图片和js文件在本地客户端缓存,再次请求后,缓存的文件可以使用。

2、以上所以HTTP请求,只靠一个TCP连接,这就是所谓的持久连接

四、关于HTTP协议的Web应用框架或者规范

JavaEE的人会知道Servlet规范。其中Web应用容器都实现了HTTP协议中的对象,即请求和响应对象。比如 javax.servlet.http.HttpServletResponse 对象中肯定有对状态码描述,如图

image

至于如何使用它们,坐等系列文章吧。

五、总结

回顾全文,HTTP协议其实就是我们对话一样,语言就是其中的协议。所以掌握HTTP协议明白以下几点就好:

1、用什么通过HTTP协议通信

2、怎么通过HTTP协议通信

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

微         博:BYSocket

豆         瓣:BYSocket

FaceBook:BYSocket

Twitter    :BYSocket

Posted in Java, 技术

Java 容器 & 泛型:六、容器讲到为什么要使用泛型

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

微博:BYSocket

豆瓣:BYSocket

ArrayList是集合类中无处不在的,泛型也是,泛型对集合类尤其有用。但是为啥要使用泛型?理解好了这个问题可以帮助理解相关的更多知识点。下面泥瓦匠以最简单的例子来验证这个问题。

一、泛型

泛型的目的是为了可以让更多不同类型的对象重用。没错,这样理解就太low。真正目的是为了在编译时找到bug,而不是在运行时。(编译时,指的是源代码翻译成机器识别的代码的时候。运行时,是指代码在机器中运行的时候。)泛型只存在编译时,理解这个可以帮助你更好的理解泛型。

这样,在编译时会比在运行时更容易地找到bug和修复。

二、实现没有泛型的简易版ArrayList

简易版的ArrList有个Obejct对象(因为是Object,我们可以add任意类型。)比如说,Integer 和 String的。代码如下:

package javaBasic.generic;

/**
 * 简易版ArrayList
 */
class ArrList
{
	private Object obj;

	public Object getObj()
	{
		return obj;
	}

	public void add(Object obj)
	{
		this.obj = obj;
	}
	
}

public class TestArrayList
{
	public static void main(String[] args)
	{
		ArrList arrList = new ArrList();
		arrList.add(1);
		arrList.add("1");
		
		Integer objInt = (Integer) arrList.getObj();
		System.out.println(objInt);
	}
}

运行可以看出会出现ClassCastException:

Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer
	at javaBasic.generic.TestArrayList.main(TestArrayList.java:30)

想问的问题是:”这Object对象属性,怎么不能强转呢?“

:编译时,代码没错的。运行main时,当set了String类型时,将结果强制转换为Integer就会报错这个错了。

泥瓦匠的记忆宫殿又来了:

1、使用泛型比那些杂乱的需要强制转换的Object代码具有更好的安全性和可读性。

2、使用泛型可以在编译时轻松找到和解决bugs

三、使用改写简易版ArrayList

使用泛型代码如下:

package javaBasic.generic;

/**
 * 简易版ArrayList
 */
class ArrList<T>
{
	private T obj;

	public T getObj()
	{
		return obj;
	}

	public void add(T obj)
	{
		this.obj = obj;
	}
	
}

public class TestArrayList
{
	public static void main(String[] args)
	{
		ArrList<Integer> arrList = new ArrList<>();
		arrList.add(1);
//		arrList.add("1");
		
		Integer objInt = arrList.getObj();
		System.out.println(objInt);
	}
}

这时候如果想用

arrList.add("1");

会发现:

image

这时候就是泛型大显身手的时候,也不用需要对属性 get 方法时的强制转换。其实,  Java 泛型只是编译时的概念,因为编译后类型会被擦除,还原本真。这里T就相当于Integer。

四、小结

泥瓦匠记忆宫殿

1、在编译时检查强类型

2、显示转换的消除(上面的Integer get省去)

3、更好地实现代码重用和泛型算法

4、使用泛型比那些杂乱的需要强制转换的Object代码具有更好的安全性和可读性。

Java 泛型只是编译时的概念,因为编译后类型会被擦除,还原本真。哈哈~下次说这个。

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

微博:BYSocket

豆瓣:BYSocket

Posted in Java, 技术

Java 容器 & 泛型:五、HashMap 和 TreeMap的自白

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

微博:BYSocket

豆瓣:BYSocket

Java 容器的文章这次应该是最后一篇了:Java 容器 系列。 今天泥瓦匠聊下 Maps。

一、Map回顾

    Map,又称映射表,是将键映射到值的对象。有四种实现Map接口并且经常使用的Map集合为:HashMap,TreeMap,Hashtable 和 LinkedHashMap.

泥瓦匠记忆宫殿:

    1、一个映射不包含重复的键

    2、每个键最多只能映射到一个值。

MapClassHierarchy-600x354

二、HashMap

    HashMap是基于哈希表的Map接口的实现。其对键进行散列,散列函数只能作用于键。下面模拟下,公司员工和找员工的例子:

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

class Employee
{}

public class HaspMap01
{
	public static void main(String[] args)
	{
		Map<String, Employee> employees = new HashMap<String, Employee>();
		employees.put("1206010035", new Employee());
		System.out.println(employees);
		
		String number = "1206010035";
		System.out.println(employees.get(number));
	}
}

Run一下,大家可以见到结果:put方法,可以将键值映射添加进表。get方法则返回指定键所映射的值。从他们 hashCode 可以看出是同一个对象。

    HaspMap的键必须唯一,同样其同一个键不能存放两个值,如果对同一个键两次调用put方法,第二个值会取代第一个值。同样是允许使用 null 值和 null 键。下面泥瓦匠用一个简单的例子解释下:

package javaBasic.collection.map;

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


public class HaspMap02
{
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public static void main(String[] args)
	{
		Map map = new HashMap<String, String>();
		map.put(null, "null01");
		map.put(null, "null02");
		System.out.println(map);
		System.out.println(map.get(null));
	}
}

结果如下:

{null=null02}
null02

由此可见,第一个值被第二个值所替换了。

下面有三点是HashMap重要之处:

1、HashMap的构造函数

   HaspMap构造函数涉及两个参数:初始容量和加载因子。初试容量是哈希表创建时的其中桶的含量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。这两个参数都是影响HashMap的性能。默认构造一个具有默认初始容量 (16) 和默认加载因子 (0.75)。默认加载因子 (.75) 在时间和空间成本上是一种折衷的考虑。

2、和上次总结的Set都差不多,这个HashMap线程是不安全不同步的。如果想防止意外发生,则设置成同步即可:

 Map m = Collections.synchronizedMap(new HashMap(...));

3、不同步的话,意味着存在快速失败导致的并发修改异常。

下面看一个复杂例子:

package javaBasic.collection.map;

import java.util.HashMap;
import java.util.Map.Entry;

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

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

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

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

public class HashMap03
{
	public static void main(String[] args)
	{
		HashMap<A, Integer> hashMapA = new HashMap<A, Integer>();
		hashMapA.put(new A(), 10);
		hashMapA.put(new A(), 5);
		
		System.out.println("HashMapA Elements:");
		System.out.print("\t" + hashMapA + "\n");
		
		// loop HashMapA
		for(Entry<A, Integer> entryA : hashMapA.entrySet())
		{
			System.out.println(entryA.getKey().toString()+"-"+entryA.getValue());
		}
		
		HashMap<B, Integer> hashMapB = new HashMap<B, Integer>();
		hashMapB.put(new B(), 10);
		hashMapB.put(new B(), 5);
		
		System.out.println("HashMapB Elements:");
		System.out.print("\t" + hashMapB + "\n");
		
		// loop HashMapB
		for(Entry<B, Integer> entryB : hashMapB.entrySet())
		{
			System.out.println(entryB.getKey().toString()+"-"+entryB.getValue());
		}
		
		HashMap<C, Integer> hashMapC = new HashMap<C, Integer>();
		hashMapC.put(new C(), 10);
		hashMapC.put(new C(), 5);
		
		System.out.println("HashMapC Elements:");
		System.out.print("\t" + hashMapC + "\n");
		
		// loop HashMap
		for(Entry<C, Integer> entryC : hashMapC.entrySet())
		{
			System.out.println(entryC.getKey().toString()+"-"+entryC.getValue());
		}
	}
}

运行一下,可以看到以下结果:


由此可见,其中和 Java 容器 & 泛型:三、HashSet,TreeSet 和 LinkedHashSet比较 中涉及的知识点一致:

集合判断两个元素相等不单单是equals方法,并且必须hashCode()方法返回值也要相等。


三、TreeMap

    TreeMap使用树结构实现(红黑树),集合中的元素进行排序,但是添加、删除和包含的算法复杂度为O(log(n))。其实Map特性基本都是一致的,比如看下面的简单例子:

public class TreeMap01
{	
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void main(String[] args)
	{
		Map map = new TreeMap();
		map.put("1", "1");
		map.put("4", "4");
		map.put("2", "2");
		map.put("2", "3");
		System.out.println(map);
	}
}

结果如下:

{1=1, 2=3, 4=4}

从中我们可以看出

1、TreeMap实现了SortedMap,顾名思义,其表示为有排序的集合。

2、同样其同一个键不能存放两个值,如果对同一个键两次调用put方法,第二个值会取代第一个值。

四、总结

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没有调优选项,因为该树总处于平衡状态。

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

微博:BYSocket

豆瓣:BYSocket

Posted in Java, 技术

Java 基础:hashCode方法

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

微博:BYSocket

豆瓣:BYSocket

一、前言

    泥瓦匠最近被项目搞的天昏地暗。发现有些要给自己一些目标,关于技术的目标:

专注很重要。专注Java 基础 + H5(学习)

    其他操作系统,算法,数据结构当成课外书博览。有时候,就是那样你越是专注方面越多对自己打击越大学啥啥都不好。今天带来Java基础:hashCode方法

二、hashCode方法

    hash code(散列码,也可以叫哈希码值)是对象产生的一个整型值。其生成没有规律的。二者散列码可以获取对象中的信息,转成那个对象的“相对唯一”的整型值。所有对象都有一个散列码,hashCode()是根类 Object 的一个方法。散列表的工作原理在Java基础不展开讲,只要知道它是一种快速的“字典”即可。下面引用老外一张图:

三、两个小例子

    首先泥瓦匠引用一段来自 Object规范 【JavaSE6】:

hashCode的常规协定是:

            • 1、在 Java 应用程序执行期间,在对同一对象多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。
  • 2、如果根据 equals(Object) 方法,两个对象是相等的,那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。
    • 3、如果根据equals方法,两个对象不相等,那么对这两个对象中的任一对象上调用 hashCode 方法 要求一定生成不同的整数结果。但是,程序员应该意识到,为不相等的对象生成不同整数结果可以提高哈希表的性能。
  •     由于hashCode定义在根类Object,所以每个对象都是Object,都具有一个默认的散列值,即是对象的存储地址。泥瓦匠请大家看一下这个例子:
public class HashCodeTest
{
	public static void main(String[] args)
	{
		String s = "hashCode";
		StringBuilder sb = new StringBuilder(s);
		System.out.println("hashCode1: " + s.hashCode() + " " + sb.hashCode());
		
		String s1 = new String("hashCode");
		StringBuilder sb1 = new StringBuilder(s1);
		System.out.println("hashCode2: " + s1.hashCode() + " " + sb1.hashCode());
		
		// are they equals?
		System.out.println("s  s1 : " + s.equals(s1));
		System.out.println("sb sb1: " + sb.equals(sb1));
	}
}

   run 一下,可以在控制台看到:

hashCode1: 147696667 1385112968
hashCode2: 147696667 870919696
s  s1 : true
sb sb1: false

   泥瓦匠小结

1、s 与 s1相等,且hashCode一样。验证了【hashCode的常规协定】的第二条。原因是字符串的散列码由内容导出的。(这个第二个例子我们会验证)

2、StringBuilder 里面没有定义hashCode方法,所以导出的是Object默认的对对象存储的地址。(注意到Object的hashCode方法前面有个native的修饰符,这表示hashCode方法是由非java语言实现的,具体的方法实现在外部,返回内存对象的地址。)详情请看认识&理解关键字 native 实战篇

    泥瓦匠刚刚提到字符串散列码是由内容导出的。下面看看String的hashCode的实现。

       /** The value is used for character storage */
	private char value[];
	
	private int hash;// Default to 0
	
    /**
     * Returns a hash code for this string. The hash code for a
     * String object is computed as
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     */
	public int hashCode()
	{
		int h = hash;
		if (h == 0 && value.length > 0)
		{
			char val[] = value;
			
			for (int i = 0; i < value.length; i++)
			{
				h = 31 * h + val[i];
			}
			hash = h;
		}
		return h;
	}

    泥瓦匠小结

1、s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]  数学公式代表什么?

s[i]是string的第i个字符,n是String的长度。31为啥呢?下面引用《Effective Java》的原话:

之所以选择31,是因为它是个奇素数,如果乘数是偶数,并且乘法溢出的话,信息就会丢失,因为与2相乘等价于移位运算。使用素数的好处并不是很明显,但是习惯上都使用素数来计算散列结果。31有个很好的特性,就是用移位和减法来代替乘法,可以得到更好的性能:31*i==(i<<5)-i。现在的VM可以自动完成这种优化。

四、结论和忠告

确实hashCode有点晦涩,有可能是因为那个数学散列函数。下面是《Effective Java》中的结论点:

1、如果对象有相同的散列码,被映射到同一个散列桶,这样散列表退化称为 链表 ,这样性能降低。

2、相等的对象必须具有相等的散列码

3、为不相等的对象产生不相等的散列码

4、不要试图从散列码计算中排除掉一个对象关键部分来提高性能

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

微博:BYSocket

豆瓣:BYSocket

Posted in Java, 技术

Java 基础:认识&理解关键字 native 实战篇

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

微博:BYSocket

豆瓣:BYSocket

泥瓦匠初次遇见 native是在 java.lang.Object 源码中的一个hashCode方法:

public native int hashCode();

为什么有个native呢?这是我所要学习的地方。所以今天泥瓦匠想要总结下native。

一、认识 native 即 JNI,Java Native Interface

凡是一种语言,都希望是纯。比如解决某一个方案都喜欢就单单这个语言来写即可。Java平台有个用户和本地C代码进行互操作的API,称为Java Native Interface (Java本地接口)。

image

二、用 Java 调用 C 的“Hello,JNI”

我们需要按照下班方便的步骤进行:

1、创建一个Java类,里面包含着一个 native 的方法和加载库的方法 loadLibrary。HelloNative.java 代码如下:

public class HelloNative
{
	static
	{
		System.loadLibrary("HelloNative");
	}
	
	public static native void sayHello();
	
	@SuppressWarnings("static-access")
	public static void main(String[] args)
	{
		new HelloNative().sayHello();
	}
}

首先泥瓦匠让大家注意的是native方法,那个加载库的到后面也起作用。native 关键字告诉编译器(其实是JVM)调用的是该方法在外部定义,这里指的是C。如果大家直接运行这个代码,  JVM会告之:“A Java Exception has occurred.”控制台输出如下:

Exception in thread "main" java.lang.UnsatisfiedLinkError: no HelloNative in java.library.path
	at java.lang.ClassLoader.loadLibrary(Unknown Source)
	at java.lang.Runtime.loadLibrary0(Unknown Source)
	at java.lang.System.loadLibrary(Unknown Source)
	at HelloNative.<clinit>(HelloNative.java:5)

这是程序使用它的时候,虚拟机说不知道如何找到sayHello。下面既可以手动写,自然泥瓦匠是用

    2、运行javah,得到包含该方法的C声明头文件.h

泥瓦匠将HelloNative.java ,简单地 javac javah,如图

image

就得到了下面的 HelloNative.h文件

/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class HelloNative */

#ifndef _Included_HelloNative
#define _Included_HelloNative
#ifdef __cplusplus
extern "C" {
#endif
/*
 * Class:     HelloNative
 * Method:    sayHello
 * Signature: ()V
 */
JNIEXPORT void JNICALL Java_HelloNative_sayHello
  (JNIEnv *, jclass);

#ifdef __cplusplus
}
#endif
#endif

jni.h 这个文件,在/%JAVA_HOME%include

3、根据头文件,写C实现本地方法

这里我们简单地实现这个sayHello方法如下:

#include "HelloNative.h"
#include <stdio.h>

JNIEXPORT void JNICALL Java_HelloNative_sayHello
{
	printf("Hello,JNI");	
}

4、生成dll共享库,然后Java程序load库,调用即可。

在Windows上,MinGW GCC 运行如下

gcc -m64  -Wl,--add-stdcall-alias -I"C:\Program Files\Java\jdk1.7.0_71\include" -I"C:\Program Files\Java\jdk1.7.0_71\include\include\win32" -shared -o HelloNative.dll HelloNative.c

-m64表示生成dll库是64位的。然后运行 HelloNative:

    java HelloNative

 

终于成功地可以看到控制台打印如下:

Hello,JNI

三、JNI 调用 C 流程图

 

绘图1

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

微博:BYSocket

豆瓣:BYSocket

Posted in Java, 技术

Java 容器 & 泛型:四、Colletions.sort 和 Arrays.sort 的算法

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

微博:BYSocket

豆瓣:BYSocket

本来准备讲 Map集合 ,还是喜欢学到哪里总结吧。最近面试期准备准备,我是一员,成功被阿里在线笔试秒杀回绝。平常心,继续努力。这次带来 Collections 和 Arrays 类中的经典算法剖析。

 

一、Colletions和Arrays

Collentions 此类完全是服务容器的”包装器“。提供了一些操作或者返回容器的静态方法。而Arrays是用来操作数组的各种方法。其中它们的联系在于其中的Sort方法,也就是这次博客的主题。

 

二、插入,快速、归并基本算法

① 插入排序

{a1},{a2,a3,a4,…,an}}

{{a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}}

{{a1(n-1),a2(n-1) ,…},{an(n-1)}}

原理及记忆方法:每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。这通俗的是找座位思想。Java版实现如下

import java.util.Arrays;

public class InsertionSort
{
	public static void main(String[] args)
	{
		int[] intA = new int[]{2,1,3,4,6,7,5};
		System.out.println(Arrays.toString(intA));
		insertionSort(intA);
		System.out.println(Arrays.toString(intA));
	}
	
	public static void insertionSort(int[] a)
	{
		int p,right;
		int temp;
		for (p = 0; p < a.length; p++)
		{
			temp = a[p];
			/**
			 * 将a[p]值往左侧有序列比较,插入。
			 */
			for (right = p; right > 0 && a[right-1] > temp ; right--)
				a[right] = a[right-1];// 置换
			a[right] = temp;
		}
	}
}

右键,run一下可以看到控制台结果:

[2, 1, 3, 4, 6, 7, 5]
[1, 2, 3, 4, 5, 6, 7]

 

② 快速排序

QQ图片20150414181507

快排是基于分治策略的算法,不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。 Java版实现如下:

package javaBasic.algorithm;

import java.util.Arrays;

public class QuickSort
{
	public static void main(String[] args)
	{
		int[] intA = new int[]{2,1,3,4,6,7,5};
		System.out.println(Arrays.toString(intA));
		//middleSort(intA, 0, intA.length - 1);
		//System.out.println(Arrays.toString(intA));
		sort(intA, 0, intA.length - 1);
		System.out.println(Arrays.toString(intA));
	}
	
	// 快速排序中的一个划分过程
	public static int  middleSort(int a[] , int left , int right)
	{
		int temp = a[left];	// 作为中间轴数
		while( left  < right)
		{
			/**
			 * 从右到左,找到第一个比中间轴数小的,移到左端
			 */
			while( left < right && a[right] > temp )
				right--;
			a[left] = a[right];
			
			/**
			 * 从左到右,找到第一个比中间轴数大的,移到右端
			 */
			while( left < right && a[left] < temp)
				left++;
			a[right] = a[left];
		}
		
		/**
		 * 将中间轴数赋值
		 */
		a[left] = temp;
		return left;
	}
	
	// 快速排序
	public static void sort(int[] a , int left, int right)
	{
		if (left < right)
		{
			/**
			 * 根据左右索引相同才停止。
			 * 不同的话,按着分治思想。
			 * 找到中间轴数,一分为二,以此类推。
			 */
			int middle = middleSort(a, left, right);
			sort(a, left, middle - 1);
			sort(a, middle + 1, right);
		}
	}
	
}

记忆方法:分治,就是分工。这里演示的是对分。大量经验数据表面,采用两个枢轴来划分成3份的算法更高效,这就是DualPivotQuicksort。这样也是我们后面讲的JDK源码。右键,run一下可以看到控制台和插入排序一样的结果。

③ 归并排序

c8177f3e6709c93d673b9ed49d3df8dcd000[1]

如图,来自百度百科。归并排序也是一种分治思想的算法,之不用快速是对分。归并是一种分解到合并的算法。如下实现方式:

package javaBasic.algorithm;

import java.util.Arrays;

public class MergeSort
{
	public static void main(String[] args)
	{
		int[] intA = new int[]{10,4,6,3,8,2,5,7};
		System.out.println(Arrays.toString(intA));
		mergeSort(intA,0,intA.length-1);
		System.out.println(Arrays.toString(intA));
	}
	
	public static void mergeSort(int[] a, int left ,int right)
	{
		if (left < right)
		{
			int middle = (left + right) / 2; // 中间索引
			
			mergeSort(a, left, middle);	// 对左侧数组递归
			mergeSort(a, middle+1, right); // 对右侧数组递归
			
			merge(a,left,middle,right); // 归并算法
		}
	}

	private static void merge(int[] a, int left, int middle, int right)
	{
		int [] tmpArr = new int[a.length];
		
		int mid = middle+1;
		int tmpArrLeft = left;// 记录左侧数组的索引
		int tmpLeft = left;
		
		/**
		 * 从两个数组中取出小的一部分复制
		 */
		while (left <= middle && mid <= right) 
		{
			if (a[left] <= a[mid])
				tmpArr[tmpArrLeft++] = a[left++];
			else
				tmpArr[tmpArrLeft++] = a[mid++];
		}
		
		/**
		 * 剩余部分右侧复制
		 */
		while (mid <= right)
		{
			tmpArr[tmpArrLeft++] = a[mid++];
		}
		
		/**
		 * 剩余部分左侧复制
		 */
		while (left <= middle)
		{
			tmpArr[tmpArrLeft++] = a[left++];
		}
		
		/**
		 * 分了再合
		 */
		while(tmpLeft <= right)
		{
			a[tmpLeft] = tmpArr[tmpLeft++];
		}
	}
	
}

结果和上图一样:

[10, 4, 6, 3, 8, 2, 5, 7]
[2, 3, 4, 5, 6, 7, 8, 10]

 

三、JDK数则

在此谢谢@江南白衣大哥的文章,对我帮助很大。以下引用的:

5. JDK7/8中排序算法的改进
面试季的同学背一脑袋的插入、归并、冒泡、快排,那,JDK到底看上了哪家的排序算法?

Colletions.sort(list) 与 Arrays.sort(T[])
Colletions.sort()实际会将list转为数组,然后调用Arrays.sort(),排完了再转回List。
而Arrays.sort(),对原始类型(int[],double[],char[],byte[]),JDK6里用的是快速排序,对于对象类型(Object[]),JDK6则使用归并排序。为什么要用不同的算法呢?

JDK7的进步
到了JDK7,快速排序升级为双基准快排(双基准快排 vs 三路快排);归并排序升级为归并排序的改进版TimSort,一个JDK的自我进化。

JDK8的进步
再到了JDK8, 对大集合增加了Arrays.parallelSort()函数,使用fork-Join框架,充分利用多核,对大的集合进行切分然后再归并排序,而在小的连续片段里,依然使用TimSort与DualPivotQuickSort。

结论
JDK团队的努力,从一些简单的New Features / Change List 根本看不到,所以没事升级一下JDK还是好的

 

我也查看了关于算法追踪到DualPivotQuicksort类,但是这类却不在JDK API。(抛出个问题:为什么这个类不出现在API里面?)哈哈,一看作者是Java之父参与写的,瞬间有研究的激情。根据白衣大哥说的,快速排序由双基准排序到三路快速排序。这也是在大量经验数据表面,采用两个枢轴来划分成3份的算法更高效。算法的思想也是分治思想。

下面又看到了一段发人自省的注释:

/**
    * If the length of an array to be sorted is less than this
    * constant, Quicksort is used in preference to merge sort.
    *  当数组长度小于286,为什么快速排序比归并排序好?
    */
   private static final int QUICKSORT_THRESHOLD = 286;

   /**
    * If the length of an array to be sorted is less than this
    * constant, insertion sort is used in preference to Quicksort.
    * 当数组长度小于47,为什么插入排序比快速排序好?
    */
   private static final int INSERTION_SORT_THRESHOLD = 47;

 

为什么?第二个问题,欢迎大神解答。

我的理解:第一,建立在大量经验数据结果。第二,根据算法时间复杂度和空间复杂度。至于深入了解需要大神解答。

JDK排序顺序图如下:

绘图1

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

微博:BYSocket

豆瓣:BYSocket

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