import java.util.List; import java.util.ArrayList; import java.util.LinkedList; import java.util.Map; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.TreeMap; import java.util.Set; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.TreeSet; import java.util.Vector; import java.util.Hashtable; list:提供基于索引的对成员的随机访问2007-10-3 1、java.util.ArrayList 注意，此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须 保持外部同步 List list = Collections.synchronizedList(new ArrayList(...)); 2、java.util.LinkedList List list = Collections.synchronizedList(new LinkedList(...)); ArrayList进行随机访问，可在常量时间完成，不论你选择的元素为何，所需要的时间相同 LInkedList而言，随机选择某一元素的动作需要在链表上进行，越靠近链表尾端，花费的时间愈久。 如果将元素安插至序列的中央位置，对 LinkedList来说花费的代价明显小于ArrayList ？？ 3. java.lang.Object java.util.AbstractCollection java.util.AbstractList java.util.Vector 4、java.util.Hashtable Hashtable 是同步的 java.lang.Object java.util.Dictionary java.util.Hashtable 此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值 下面这个示例创建了一个数字的哈希表。它将数字的名称用作键： Hashtable numbers = new Hashtable(); numbers.put("one", new Integer(1)); numbers.put("two", new Integer(2)); numbers.put("three", new Integer(3));要检索一个数字，可以使用以下代码： Integer n = (Integer)numbers.get("two"); if (n != null) { System.out.println("two = " + n); } 5、java.util.HashMap java.lang.Object java.util.AbstractMap java.util.HashMap 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键 Map m = Collections.synchronizedMap(new HashMap(...)); 6、java.util.TreeMap java.lang.Object java.util.AbstractMap java.util.TreeMap Map m = Collections.synchronizedMap(new TreeMap(...)); SortedMap 接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字，根据使用的构造方法不同，可能会按照键的类的自然顺序 进行排序（参见 Comparable），或者按照创建时所提供的比较器进行排序。 7、java.util.TreeSet java.lang.Object java.util.AbstractCollection java.util.AbstractSet java.util.TreeSet 此类实现 Set 接口，该接口由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素，根据使用的构造方法不同，可能会按照元素的自然顺序 进行排序（参见 Comparable），或按照在创建 set 时所提供的比较器进行排序。 SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...)); 应用 package test.jihe; import java.util.Comparator; import java.util.Iterator; import java.util.TreeMap; public class testone { public static void main (String[] args) { TreeMap map = new TreeMap((Comparator) new MyComparator()); map.put("sungnag", ""); map.put("yangmin", ""); map.put("zhangliang", ""); map.put("laoli", ""); map.put("yuzong", ""); for( Iterator it = map.keySet().iterator(); it.hasNext(); ) { String key = (String)it.next(); System.out.println( "Key: "+key ); } } static class MyComparator implements Comparator { public int compare(Object element1,Object element2) { System.out.println("begin...."); String a = element1.toString().toLowerCase(); System.out.print("a = "+a); String b = element2.toString().toLowerCase(); System.out.print(" b = "+b+" rs ="+a.compareTo( b )); System.out.println(""); return a.compareTo( b ); } } } begin.... a = yangmin b = sungnag rs =6 begin.... a = zhangliang b = sungnag rs =7 begin.... a = zhangliang b = yangmin rs =1 begin.... a = laoli b = yangmin rs =-13 begin.... a = laoli b = sungnag rs =-7 begin.... a = yuzong b = yangmin rs =20 begin.... a = yuzong b = zhangliang rs =-1 Key: laoli Key: sungnag Key: yangmin Key: yuzong Key: zhangliang public class myComparator implements Comparator { public int compare(Object element1, Object element2) { Integer Int1 = (Integer) element1; Integer Int2 = (Integer) element2; int num1 = Int1.intValue(); int num2 = Int2.intValue(); return num1 - num2; } } 1 |——SortedSet接口——TreeSet实现类 2Set接口——|——HashSet实现类 3 |——LinkedHashSet实现类 4HashSet 5此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证集合的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。 6此类为基本操作提供了稳定性能，这些基本操作包括 add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。对此集合进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。 7 8我们应该为要存放到散列表的各个对象定义hashCode()和equals(); 9import java.util.HashSet; 10import java.util.Iterator; 11public class HashSetTest { 12 public static void main(String[] args) 13 { 14 HashSet hs=new HashSet(); 15 /**//*hs.add("one"); 16 hs.add("two"); 17 hs.add("three"); 18 hs.add("four");*/ 19 hs.add(new Student(1,"zhangsan")); 20 hs.add(new Student(2,"lishi")); 21 hs.add(new Student(3,"wangwu")); 22 hs.add(new Student(1,"zhangsan")); 23 24 Iterator it=hs.iterator(); 25 while(it.hasNext()) 26 { 27 System.out.println(it.next()); 28 } 29 } 30} 31class Student //HashSet要重写hashCode和equals方法 32{ 33 int num; 34 String name; 35 Student(int num,String name) 36 { 37 this.num=num; 38 this.name=name; 39 } 40 public String toString() 41 { 42 return "num :"+num+" name:"+name; 43 } 44 public int hashCode() 45 { 46 return num*name.hashCode(); 47 } 48 public boolean equals(Object o) 49 { 50 Student s=(Student)o; 51 return num==s.num && name.equals(s.name); 52 } 53} 54 55TreeSet 56此类实现 Set 接口，该接口由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素，根据使用的构造方法不同，可能会按照元素的自然顺序 进行排序，或按照在创建 set 时所提供的比较器进行排序。 57是一个有序集合,元素中安升序排序,缺省是按照自然顺序进行排序,意味着TreeSet中元素要实现Comparable接口; 58我们可以构造TreeSet对象时,传递实现了Comparator接口的比较器对象. 59import java.util.*; 60public class TreeSetTest { 61 public static void main(String[] args) 62 { 63 //TreeSet ts=new TreeSet(); 64 TreeSet ts=new TreeSet(new Students.compareToStudent()); 65 ts.add(new Students(2,"zhangshan")); 66 ts.add(new Students(3,"lishi")); 67 ts.add(new Students(1,"wangwu")); 68 ts.add(new Students(4,"maliu")); 69 70 Iterator it=ts.iterator(); 71 while(it.hasNext()) 72 { 73 System.out.println(it.next()); 74 } 75 } 76} 77class Students implements Comparable 78{ 79 int num; 80 String name; 81 Students(int num,String name) 82 { 83 this.num=num; 84 this.name=name; 85 } 86 static class compareToStudent implements Comparator //定义一个内部类来实现比较器 87 { 88 public int compare(Object o1, Object o2) { 89 Students s1=(Students)o1; 90 Students s2=(Students)o2; 91 int rulst= s1.num > s2.num ? 1 : (s1.num==s2.num ? 0 :-1); 92 if(rulst==0) 93 { 94 rulst=s1.name.compareTo(s2.name); 95 } 96 return rulst; 97 } 98 } 99 public int compareTo(Object o) //写具体的比较方法 100 { 101 int result; 102 Students s=(Students)o; 103 result=num >s.num ? 1:(num==s.num ? 0 : -1); 104 if(result==0) 105 { 106 result=name.compareTo(s.name); 107 } 108 return result; 109 } 110 public String toString() 111 { 112 return num+":"+name; 113 } 114} 115总结 116HashSet是基于Hash算法实现的,其性能通常优于TreeSet,我们通常都应该使用HashSet,在我们需要排序的功能时,我门才使用TreeSet 8、java.util.HashSet java.lang.Object java.util.AbstractCollection java.util.AbstractSet java.util.HashSet 所有已实现的接口： Serializable, Cloneable, Iterable, Collection, Set 直接已知子类： JobStateReasons, LinkedHashSet 此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证集合的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。 Set s = Collections.synchronizedSet(new HashSet(...)); 三、之间的区别 1、Vector类和ArrayList类 主要不同之处在于同步。Vector是线程安全的，但ArrayList不是。这使得ArrayList要比Vector快速，其性能也更好一些。 如果要从Java SDK得到一个线程安全的LinkedList，你可以利用一个同步封装器从Collections.synchronizedList(List)得到一个。然而，使用同步封装器相当于加入了一个间接层，它会带来昂贵的性能代价。和Vector相比，经过同步封装的LinkedList在性能上处于显著的劣势，因为Vector不需要为了线程安全而进行任何额外的间接调用。 只有List和Map具有高效的线程安全实现（分别是Vector和Hashtable类）。这两个高效的线程安全类的存在只是为了向后兼容，而不是出于性能上的考虑。 ArrayList和Vector通常比LinkedList和同步封装之后的LinkedList有着更好的性能。有些情况下LinkedList会有更好的性能，例如，当大量元素需要同时加入到大型集合的开头和末尾时。一般而言，建议优先使用ArrayList/Vector类，只有当它们存在明显的性能问题而LinkedList能够改进性能时，才使用LinkedList HashTable和HashMap的区别： HashTable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。 HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。 HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样。 HashTable使用Enumeration，HashMap使用Iterator。 HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
