Posted in Java, 技术, 系列文章

[Java 容器 & 泛型] 系列文章

容器是Java语言学习中重要的一部分。

java-collection-hierarchy_thumb

文章如下:

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

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

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

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

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

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

 

文章源码地址:https://github.com/JeffLi1993

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 容器 & 泛型:四、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 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