Java中的Set主要有：HashSet、TreeSet、LinkedHashSet。
一：HashSet
HashSet 是一个没有重复元素的无序集合。 HashSet由HashMap实现的，不保证元素的顺序，允许使用null元素，一系列操作的实现都是调用其底层的map的方法而已。
1：HashSet元素的存储顺序：由于HashSet底层是用HashMap存储元素的，每组数据都没有索引，很多list可用的方法他都没有，凡是需要通过索引来进行操作的方法都没有，也不能使用普通for循环来进行遍历，只有加强型for和迭代器两种遍历方法
2：HashSet如何保证元素不重复：HashSet在调用add(obj)方法插入元素时，首先调用元素的hashcode()方法，如果map中对应索引位还没有内容，则把元素值储存；如果索引位已有内容，则继续调用 元素的equals()方法把新增元素与已有元素值进行比较，如果是相等的，则新值不插入（因为重复了），如果是不相等的，则把新元素插入到该索引位元素列表的末尾。【原因：哈希码是存在冲突的，我们只规定了相等对象必定有相同哈希码，却没有规定不同对象不能有相同哈希码。当不同对象拥有同一哈希码时，就只能在哈希码索引位上建立链表来存放了。】
主要源码：(基于JDK1.6.0_45)
1 package java.util; 2 public class HashSet<E> 3 extends AbstractSet<E> 4 implements Set<E>, Cloneable, java.io.Serializable 5 { 6 7 static final long serialVersionUID = -5024744406713321676L; 8 // 使用 HashMap 的 key 保存 HashSet 中所有元素 9 private transient HashMap<E,Object> map; 10 //定义一个虚拟的 Object 对象作为 HashMap 的 value 11 private static final Object PRESENT = new Object(); 12 13 // 默认构造函数 14 public HashSet() { 15 // 调用HashMap的默认构造函数，创建map 16 map = new HashMap<E,Object>(); 17 } 18 // 带集合的构造函数 19 public HashSet(Collection<? extends E> c) { 20 21 // HashMap的加载因子是0.75，(c.size()/.75f) + 1 正好是总的空间大小。 22 // 指定为16是从性能考虑，2的指数倍，避免重复计算。 23 map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16)); 24 // 将集合(c)中的全部元素添加到HashSet中 25 addAll(c); 26 } 27 // 指定HashSet初始容量和加载因子的构造函数 28 public HashSet(int initialCapacity, float loadFactor) { 29 map = new HashMap<E,Object>(initialCapacity, loadFactor); 30 } 31 // 指定HashSet初始容量的构造函数 32 public HashSet(int initialCapacity) { 33 map = new HashMap<E,Object>(initialCapacity); 34 } 35 HashSet(int initialCapacity, float loadFactor, boolean dummy) { 36 map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor); 37 } 38 // 返回HashSet的迭代器 39 public Iterator<E> iterator() { 40 // 实际上返回的是HashMap的“key集合的迭代器” 41 return map.keySet().iterator(); 42 } 43 public int size() { 44 return map.size(); 45 } 46 public boolean isEmpty() { 47 return map.isEmpty(); 48 } 49 public boolean contains(Object o) { 50 return map.containsKey(o); 51 } 52 // 将元素(e)添加到HashSet中 53 public boolean add(E e) { 54 return map.put(e, PRESENT)==null; 55 } 56 // 删除HashSet中的元素(o) 57 public boolean remove(Object o) { 58 return map.remove(o)==PRESENT; 59 } 60 public void clear() { 61 map.clear(); 62 } 63 // 克隆一个HashSet，并返回Object对象 64 public Object clone() { 65 try { 66 HashSet<E> newSet = (HashSet<E>) super.clone(); 67 newSet.map = (HashMap<E, Object>) map.clone(); 68 return newSet; 69 } catch (CloneNotSupportedException e) { 70 throw new InternalError(); 71 } 72 } 73 // java.io.Serializable的写入函数 74 // 将HashSet的“总的容量，加载因子，实际容量，所有的元素”都写入到输出流中 75 private void writeObject(java.io.ObjectOutputStream s) 76 throws java.io.IOException { 77 // Write out any hidden serialization magic 78 s.defaultWriteObject(); 79 // Write out HashMap capacity and load factor 80 s.writeInt(map.capacity()); 81 s.writeFloat(map.loadFactor()); 82 // Write out size 83 s.writeInt(map.size()); 84 // Write out all elements in the proper order. 85 for (Iterator i=map.keySet().iterator(); i.hasNext(); ) 86 s.writeObject(i.next()); 87 } 88 // java.io.Serializable的读取函数 89 // 将HashSet的“总的容量，加载因子，实际容量，所有的元素”依次读出 90 private void readObject(java.io.ObjectInputStream s) 91 throws java.io.IOException, ClassNotFoundException { 92 // Read in any hidden serialization magic 93 s.defaultReadObject(); 94 // Read in HashMap capacity and load factor and create backing HashMap 95 int capacity = s.readInt(); 96 float loadFactor = s.readFloat(); 97 map = (((HashSet)this) instanceof LinkedHashSet ? 98 new LinkedHashMap<E,Object>(capacity, loadFactor) : 99 new HashMap<E,Object>(capacity, loadFactor)); 100 // Read in size 101 int size = s.readInt(); 102 // Read in all elements in the proper order. 103 for (int i=; i<size; i++) { 104 E e = (E) s.readObject(); 105 map.put(e, PRESENT); 106 } 107 } 108 }
HashSet主要的API
boolean add(E object) void clear() Object clone() boolean contains(Object object) boolean isEmpty() Iterator<E> iterator() boolean remove(Object object) int size()
HashSet与Map关系如下图：
从图中可以看出：
(01) HashSet继承于AbstractSet，并且实现了Set接口。
(02) HashSet的本质是一个"没有重复元素"的集合，它是通过HashMap实现的。HashSet中含有一个"HashMap类型的成员变量"map，HashSet的操作函数，实际上都是通过map实现的。
HashSet遍历方式
遍历实例：
import java.util.Random; import java.util.Iterator; import java.util.HashSet; /* * @desc 介绍HashSet遍历方法 * * @author hdb */ public class HashSetIteratorTest { public static void main(String[] args) { // 新建HashSet HashSet set = new HashSet(); // 添加元素 到HashSet中 for (int i=0; i<5; i++){
set.add(""+i);
} // 通过Iterator遍历HashSet iteratorHashSet(set) ; // 通过for-each遍历HashSet foreachHashSet(set); } /* * 通过Iterator遍历HashSet。推荐方式.
* 第一步：根据iterator()获取HashSet的迭代器
* 第二步：遍历迭代器获取各个元素。 */ private static void iteratorHashSet(HashSet set) { for(Iterator iterator = set.iterator(); iterator.hasNext(); ) { System.out.printf("iterator : %s\n", iterator.next()); }
//另一种写法
//Iterator iterator = set.iterator();
//while (iterator.hasNext()) {
// System.out.printf("iterator : %s\n", iterator.next());
//}
} /* * 通过for-each遍历HashSet。不推荐！此方法需要先将Set转换为数组
* 第一步：根据toArray()获取HashSet的元素集合对应的数组
* 第二步：遍历数组，获取各个元素 */ private static void foreachHashSet(HashSet set) { String[] arr = (String[])set.toArray(new String[0]); for (String str:arr){
System.out.printf("for each : %s\n", str);
} } }
实例学习如何使用HashSet
import java.util.Iterator; import java.util.HashSet; /* * @desc HashSet常用API的使用。 * * @author hdb */ public class HashSetTest { public static void main(String[] args) { // HashSet常用API testHashSetAPIs() ; } /* * HashSet除了iterator()和add()之外的其它常用API */ private static void testHashSetAPIs() { // 新建HashSet HashSet set = new HashSet(); // 将元素添加到Set中 set.add("a"); set.add("b"); set.add("c"); set.add("d"); set.add("e"); // 打印HashSet的实际大小 System.out.printf("size : %d\n", set.size()); // 判断HashSet是否包含某个值 System.out.printf("HashSet contains a :%s\n", set.contains("a")); System.out.printf("HashSet contains g :%s\n", set.contains("g")); // 删除HashSet中的“e” set.remove("e"); // 新建一个包含b、c、f的HashSet HashSet otherset = new HashSet(); otherset.add("b"); otherset.add("c"); otherset.add("f"); // 克隆一个removeset，内容和set一模一样 HashSet removeset = (HashSet)set.clone(); // 删除“removeset中，属于otherSet的元素” removeset.removeAll(otherset); // 打印removeset System.out.printf("removeset : %s\n", removeset); // 克隆一个retainset，内容和set一模一样 HashSet retainset = (HashSet)set.clone(); // 保留“retainset中，属于otherSet的元素” retainset.retainAll(otherset); // 打印retainset System.out.printf("retainset : %s\n", retainset); // 遍历HashSet,推荐方式 for(Iterator iterator = set.iterator(); iterator.hasNext(); ) {
System.out.printf("iterator : %s\n", iterator.next());
}
// 将Set转换为数组，遍历HashSet,不推荐
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr) {
System.out.printf("for each : %s\n", str);
} // 清空HashSet set.clear(); // 输出HashSet是否为空 System.out.printf("%s\n", set.isEmpty()?"set is empty":"set is not empty"); } }
HashSet线程同步问题
HashSet是非同步的。如果多个线程同时访问一个HashSet，而其中至少一个线程修改了该HashSet，那么它必须保持外部同步。通常是通过对自然封装该HashSet的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：
Set s = Collections.synchronizedSet(new HashSet(...));
HashSet通过iterator()返回的迭代器是fail-fast的。
二：TreeSet
TreeSet在保持元素唯一性的基础上，更增加了使插入元素有序的特性。TreeSet的底层实际上是TreeMap，在TreeSet上的操作的实现都是调用了底层的TreeMap的方法。
1：TreeSet的排序规则制定：
1）元素自身具备比较性：元素类实现Comparable接口，重写compareTo方法，这种方式叫做元素的自然排序（默认排序）。
2）在创建TreeSet时指定比较器：定义一个比较器类实现接口Comparator，重写compare方法，在创建TreeSet时把比较器对象传进去。
2：TreeSet中元素的唯一性保证：通过元素的compareTo方法或者treeset创建时的比较器compare方法，如果return 0则说明有相等元素存在，则新元素不插入。
部分主要源码：
1 package java.util; 2 3 public class TreeSet<E> extends AbstractSet<E> 4 implements NavigableSet<E>, Cloneable, java.io.Serializable 5 { 6 // NavigableMap对象 7 private transient NavigableMap<E,Object> m; 8 9 // TreeSet是通过TreeMap实现的， 10 // PRESENT是键-值对中的值。 11 private static final Object PRESENT = new Object(); 12 13 // 不带参数的构造函数。创建一个空的TreeMap 14 public TreeSet() { 15 this(new TreeMap<E,Object>()); 16 } 17 18 // 将TreeMap赋值给 "NavigableMap对象m" 19 TreeSet(NavigableMap<E,Object> m) { 20 this.m = m; 21 } 22 23 // 带比较器的构造函数。 24 public TreeSet(Comparator<? super E> comparator) { 25 this(new TreeMap<E,Object>(comparator)); 26 } 27 28 // 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中 29 public TreeSet(Collection<? extends E> c) { 30 this(); 31 // 将集合c中的元素全部添加到TreeSet中 32 addAll(c); 33 } 34 35 // 创建TreeSet，并将s中的全部元素都添加到TreeSet中 36 public TreeSet(SortedSet<E> s) { 37 this(s.comparator()); 38 addAll(s); 39 } 40 41 // 返回TreeSet的顺序排列的迭代器。 42 // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器 43 public Iterator<E> iterator() { 44 return m.navigableKeySet().iterator(); 45 } 46 47 // 返回TreeSet的逆序排列的迭代器。 48 // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器 49 public Iterator<E> descendingIterator() { 50 return m.descendingKeySet().iterator(); 51 } 52 53 // 返回TreeSet的大小 54 public int size() { 55 return m.size(); 56 } 57 58 // 返回TreeSet是否为空 59 public boolean isEmpty() { 60 return m.isEmpty(); 61 } 62 63 // 返回TreeSet是否包含对象(o) 64 public boolean contains(Object o) { 65 return m.containsKey(o); 66 } 67 68 // 添加e到TreeSet中 69 public boolean add(E e) { 70 return m.put(e, PRESENT)==null; 71 } 72 73 // 删除TreeSet中的对象o 74 public boolean remove(Object o) { 75 return m.remove(o)==PRESENT; 76 } 77 78 // 清空TreeSet 79 public void clear() { 80 m.clear(); 81 } 82 83 // 将集合c中的全部元素添加到TreeSet中 84 public boolean addAll(Collection<? extends E> c) { 85 // Use linear-time version if applicable 86 if (m.size()==0 && c.size() > 0 && 87 c instanceof SortedSet && 88 m instanceof TreeMap) { 89 SortedSet<? extends E> set = (SortedSet<? extends E>) c; 90 TreeMap<E,Object> map = (TreeMap<E, Object>) m; 91 Comparator<? super E> cc = (Comparator<? super E>) set.comparator(); 92 Comparator<? super E> mc = map.comparator(); 93 if (cc==mc || (cc != null && cc.equals(mc))) { 94 map.addAllForTreeSet(set, PRESENT); 95 return true; 96 } 97 } 98 return super.addAll(c); 99 } 100 101 // 返回子Set，实际上是通过TreeMap的subMap()实现的。 102 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, 103 E toElement, boolean toInclusive) { 104 return new TreeSet<E>(m.subMap(fromElement, fromInclusive, 105 toElement, toInclusive)); 106 } 107 108 // 返回Set的头部，范围是：从头部到toElement。 109 // inclusive是是否包含toElement的标志 110 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 111 return new TreeSet<E>(m.headMap(toElement, inclusive)); 112 } 113 114 // 返回Set的尾部，范围是：从fromElement到结尾。 115 // inclusive是是否包含fromElement的标志 116 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 117 return new TreeSet<E>(m.tailMap(fromElement, inclusive)); 118 } 119 120 // 返回子Set。范围是：从fromElement(包括)到toElement(不包括)。 121 public SortedSet<E> subSet(E fromElement, E toElement) { 122 return subSet(fromElement, true, toElement, false); 123 } 124 125 // 返回Set的头部，范围是：从头部到toElement(不包括)。 126 public SortedSet<E> headSet(E toElement) { 127 return headSet(toElement, false); 128 } 129 130 // 返回Set的尾部，范围是：从fromElement到结尾(不包括)。 131 public SortedSet<E> tailSet(E fromElement) { 132 return tailSet(fromElement, true); 133 } 134 135 // 返回Set的比较器 136 public Comparator<? super E> comparator() { 137 return m.comparator(); 138 } 139 140 // 返回Set的第一个元素 141 public E first() { 142 return m.firstKey(); 143 } 144 145 // 返回Set的最后一个元素 146 public E first() { 147 public E last() { 148 return m.lastKey(); 149 } 150 151 // 返回Set中小于e的最大元素 152 public E lower(E e) { 153 return m.lowerKey(e); 154 } 155 156 // 返回Set中小于/等于e的最大元素 157 public E floor(E e) { 158 return m.floorKey(e); 159 } 160 161 // 返回Set中大于/等于e的最小元素 162 public E ceiling(E e) { 163 return m.ceilingKey(e); 164 } 165 166 // 返回Set中大于e的最小元素 167 public E higher(E e) { 168 return m.higherKey(e); 169 } 170 171 // 获取第一个元素，并将该元素从TreeMap中删除。 172 public E pollFirst() { 173 Map.Entry<E,?> e = m.pollFirstEntry(); 174 return (e == null)? null : e.getKey(); 175 } 176 177 // 获取最后一个元素，并将该元素从TreeMap中删除。 178 public E pollLast() { 179 Map.Entry<E,?> e = m.pollLastEntry(); 180 return (e == null)? null : e.getKey(); 181 } 182 183 // 克隆一个TreeSet，并返回Object对象 184 public Object clone() { 185 TreeSet<E> clone = null; 186 try { 187 clone = (TreeSet<E>) super.clone(); 188 } catch (CloneNotSupportedException e) { 189 throw new InternalError(); 190 } 191 192 clone.m = new TreeMap<E,Object>(m); 193 return clone; 194 } 195 196 // java.io.Serializable的写入函数 197 // 将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中 198 private void writeObject(java.io.ObjectOutputStream s) 199 throws java.io.IOException { 200 s.defaultWriteObject(); 201 202 // 写入比较器 203 s.writeObject(m.comparator()); 204 205 // 写入容量 206 s.writeInt(m.size()); 207 208 // 写入“TreeSet中的每一个元素” 209 for (Iterator i=m.keySet().iterator(); i.hasNext(); ) 210 s.writeObject(i.next()); 211 } 212 213 // java.io.Serializable的读取函数：根据写入方式读出 214 // 先将TreeSet的“比较器、容量、所有的元素值”依次读出 215 private void readObject(java.io.ObjectInputStream s) 216 throws java.io.IOException, ClassNotFoundException { 217 // Read in any hidden stuff 218 s.defaultReadObject(); 219 220 // 从输入流中读取TreeSet的“比较器” 221 Comparator<? super E> c = (Comparator<? super E>) s.readObject(); 222 223 TreeMap<E,Object> tm; 224 if (c==null) 225 tm = new TreeMap<E,Object>(); 226 else 227 tm = new TreeMap<E,Object>(c); 228 m = tm; 229 230 // 从输入流中读取TreeSet的“容量” 231 int size = s.readInt(); 232 233 // 从输入流中读取TreeSet的“全部元素” 234 tm.readTreeSet(size, s, PRESENT); 235 } 236 237 // TreeSet的序列版本号 238 private static final long serialVersionUID = -2479143000061671589L; 239 }
三：LinkedHashSet
LinkedHashSet的特性是：记录了元素的插入顺序。在遍历时可以按照元素的插入顺序进行遍历。
LinkHashSet维护了一个双向链表，记录元素的插入顺序，然后再根据元素值，采用hashcode()、equals()方法来存储元素值并实现元素的唯一性。