简介
这篇文章我们来整理下基于Set接口实现的数据结构类。Set是一个不允许元素重复的数据结构，它的主要实现类有HashSet、TreeSet，以及android的ArraySet三个。
这几个类的实现涉及到Map的相关类，如果对Map的相关类不熟悉的可以先去看第四章对Map的介绍。
一、HashSet
HashSet内部是使用HashMap来实现的元素存储。HashSet以存储的元素作为HashMap的key，因为HashMap的key是不允许重复，所以HashSet的元素也就不会出现重复。源码如下：
public boolean add(E e) {
// 代码很简单，就是以要添加的元素作为HashMap的key，以一个内部固定的对象作为value存储到HashMap中，
// 利用HashMap的key不能重复的特性来实现元素的唯一性
// 通过map的返回值（如果不存在指定的key则返回null，否则返回的是PRESENT对象）来判断是否重复
return map.put(e, PRESENT)==null;
}
private static final Object PRESENT = new Object();
因为HashSet使用的是HashMap来实现的，所以它的元素是无序的，因此HashSet也就没有类似于get(index)的方法了。如果要遍历HashSet的元素需要使用迭代器方法iterator()返回一个迭代器来进行元素的遍历操作。
同样，HashSet也不是线程安全的。
二、TreeSet
上面的HashSet内部是使用HashMap来实现的元素存储，TreeSet则是使用的TreeMap来实现的元素存储。同样是以存储的元素作为TreeMap的key，所以元素也是不能重复的。另外因为TreeMap的key是有序的，所以TreeSet是一个有序的集合。
但是TreeSet同样没有get(index)方法。为什么呐？因为HashSet的有序不是指的插入顺序，它的顺序是使用Comparator（或者Comparable）接口来确定的。和TreeMap一样，指定Comparator的方式有两种，一是让要存储的元素实现java.util.Comparator接口；二是在创建HashSet对象的时候指定一个实现了java.lang.Comparable接口的对象。
同样，TreeSet也不是线程安全的。
三、ArraySet
ArraySet是Android在API 23的时候设计添加的一个数据结构，在android.util包下。它主要是用来代替java的HashSet。相对于HashSet，ArraySet在对内存的使用方面做了优化，使得ArraySet在Android这种低内存（相对PC）的设备上表现得比HashSet要好。
首先来看下HashSet的问题，因为HashSet内部是使用HashMap来存储的，所以我们直接分析HashMap就可以。HashMap的容量由容量阈值和加载因子两个属性来控制的，构造方法如下：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
// 这是我们最常用的一个构造方法，这里只初始化了加载因子（loadFactor ）
// 容量阈值会在初始化内部数组和每次扩容的时候进行设置
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
// 初始化HashMap的时候指定了容量，加载因子使用默认值（0.75）
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量边界值检查
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 加载因子的范围检查
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
// 设置阈值，这里的tableSizeFor方法主要是将我们传入的容量值转换成2的冥
// 比如initialCapacity为10，则转换后的值为16（2的4次方）
this.threshold = tableSizeFor(initialCapacity);
}
当HashMap的容量不够时就会进行扩容，使用的是resize()方法，源码如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果oldCap大于0说明当前已经存在数组，本次属于扩容，否则说明当前还不存在数组，本次属于新建数组
if (oldCap > 0) {
// 如果已经达到了最大容量则不再进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将容量扩大为以前容量的两倍（oldCap << 1也就是oldCap * 2）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果以前的阈值不大于0，则将新的容量设置为该阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 如果阈值也没有初始化，则容量使用默认值，并初始化阈值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 重新计算新的阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
...
}
对于HashMap每次扩容都扩大一倍这种实现，在Android这种内存不高的设备上来说不是一个好的设计。另外，HashMap在删除数据的时候没有进行收缩容量来释放内存，这样对内存的利用率也不高。
ArraySet就是为了解决上面这两个问题而重新设计的一种数据结构。功能和HashSet一样，存储的元素唯一且无序。
ArraySet内部使用了两个数组（一个存储元素的hash值，一个存储元素本身）来代替HashSet中的HashMap。它有几个特点：
- 初始容量为4（HashSet的初始容量为16）;
- 每次扩容都是原来的1.5倍（HashSet扩容是原来的两倍）；
- 当删除元素时，如果当前使用的容量不到总容量的1/3，则收缩容量，减小内存的占用；
- ArraySet会对不再使用的一倍基础容量和二倍基础容量两种数组进行缓存；
先来解释下源码中的几个重要字段：
// 该数组用于存放元素的hash值，注意：该数组中可能会存在多个相同的hash值，原因见mArray字段的注释
int[] mHashes;
// 该数组用于存放元素本身。
// 原则上一个元素的hash值在mHashes数组里的索引位置也应该是它在mArray数组里的位置，
// 但是为了解决hash碰撞的问题，这里的索引关系稍微有些复杂。
// 举个添加元素的例子来说明下（假设某个元素A的hash值为100，且该hash值已存在）：
// 第一步：ArraySet通过对mHashes数组进行二分查找，找到该hash值在数组中的索引是5；
// 第二步：查看mArray数组中的第5个元素和元素A是否是同一个元素，如果是则返回false，表示已经存在相同元素，如果不是则从该位置分别向上和向下对mArray进行遍历，查找是否有相同的元素，如果有则返回false；
// 第三步：上面的查找结果会返回一个新的位置该位置的前一个或后一个位置元素的hash值和当前元素的hash值必然相同（后面解析），将新的元素插入到这个位置，使得具有相同hash值的元素都是挨着一起的。
Object[] mArray;
// 基础数组长度
private static final int BASE_SIZE = 4;
// 缓存数据数量
private static final int CACHE_SIZE = 10;
// sBaseCache用来缓存数组长度是基础数组长度的数组（同时对一组mHashes和mArray进行缓存）。
// 缓存步骤：
// 第一步：将当前sBaseCache指向的对象赋值给mArray的第0个元素（存储以前的缓存数组）；
// 第二步：将本次要缓存的mHashes数组赋值给mArray的第1个元素（存储本次的mHashes数组）；
// 第三步：将数组mArray从第三个位置到最后位置进行清空操作；
// 第四步：将sBaseCache指向mArray。
//
// sBaseCache整体看起来像是一个链表，mArray作为链表的节点，mArray[0]指向下一个节点，mArray[1]存放本节点的数据（mHashes数组）
static Object[] sBaseCache;
// 当前缓存的数量
static int sBaseCacheSize;
// sTwiceBaseCache用来缓存数组长度是基础数组长度两倍的数组（结构同sBaseCache）
static Object[] sTwiceBaseCache;
// 当前缓存的数量
static int sTwiceBaseCacheSize;
看完对这几个字段的解释，相信大家已经基本明白ArraySet的实现原理了。如果还有些迷糊，我们继续来看下它的实现方法：
public boolean add(E value) {
final int hash;
int index;
// 这里主要是计算元素的hash值以及查找该元素在mArray数组上的位置
if (value == null) {
hash = 0;
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(value) : value.hashCode();
index = indexOf(value, hash);
}
// 如果index>=0表示该元素在mArray数组上已经存在，则返回false来表示是一个重复元素
if (index >= 0) {
return false;
}
// indexOf方法在查找位置的时候如果发现没有相同元素时会返回最后一次查找的位置目的是为了将新元素插入到这个位置
// 但是为了和是否有这个元素做区分，返回值不能大于0，所以在返回之前对结果值进行了取反，让其变成一个负数
// 这里对该值再次取反，让其重新变成正数
index = ~index;
// 判断是否需要扩容
if (mSize >= mHashes.length) {
// 如果mSize大于两倍基础大小，则扩容为现在的1.5倍（mSize >> 1等价于 mSize / 2）
// 如果mSize在技术大小的一倍到两倍之间，则扩容为基础大小的两倍
// 如果 mSize小于基础大小，则扩容为基础大小
final int n = mSize >= (BASE_SIZE * 2) ? (mSize + (mSize >> 1))
: (mSize >= BASE_SIZE ? (BASE_SIZE * 2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "add: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// 重新创建两个数组，并赋值给mHashes和mArray
allocArrays(n);
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "add: copy 0-" + mSize + " to 0");
// 将以前数组中的值复制到新数组中
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
// 释放旧数组，如果缓存数量还没有达到最大值，且旧数组的大小为一倍或两倍基础大小，则将其缓存起来
freeArrays(ohashes, oarray, mSize);
}
// 如果要插入的元素位置在数组中间，则将从该插入位置开始的元素往后移动一位
if (index < mSize) {
if (DEBUG) {
Log.d(TAG, "add: move " + index + "-" + (mSize - index) + " to " + (index + 1));
}
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index, mArray, index + 1, mSize - index);
}
// 插入新元素
mHashes[index] = hash;
mArray[index] = value;
mSize++;
return true;
}
private int indexOf(Object key, int hash) {
final int N = mSize;
// 如果当前还没有元素，则对0取反并返回，
// 注意位运算法则：~0的结果为-1，所以上面add方法中的if (index >= 0)判断是不成立的
if (N == 0) {
return ~0;
}
// 对mHashes使用二分查找算法查找hash值的位置
// binarySearch返回的是最后查找的位置，如果没有找到，同样对返回值进行了取反操作
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
// 如果不存在这个hash值，则直接返回负数的index
if (index < 0) {
return index;
}
// 判断在mArray数组中该位置的元素和当前要插入的元素是否是同一个元素
// 如果是则返回该元素的在数组中的index，表示存在相同元素
if (key.equals(mArray[index])) {
return index;
}
// Search for a matching key after the index.
int end;
// 从该位置开始往后查找是否有与当前元素相同的的元素
// 注意查询的条件mHashes[end] == hash，表示只会查询和当前位置元素hash值相同的元素，
// 一但有不相同的元素则停止查询（不会遍历后面所有的元素）
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end])) return end;
}
// Search for a matching key before the index.
// 从该位置开始往前遍历，逻辑和上面一样
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i])) return i;
}
// 如果都没找到，此时end为最后一次遍历的位置，取反后返回
return ~end;
}
最后再来看看分配数组和释放数组的两个方法：
// 释放数组，如果要释放的数组正好是基础尺寸的一倍或二倍大小，则将其缓存起来
// 注意这种缓存时静态的，也就是所有ArraySet对象都可以使用
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
// 判断尺寸是否是基础尺寸的二倍大小
if (hashes.length == (BASE_SIZE * 2)) {
synchronized (ArraySet.class) {
// 判断是否达到了缓存上线
if (sTwiceBaseCacheSize < CACHE_SIZE) {
// array[0]用来存放当前的缓存数组引用（类似于链表中的next，array则相当于链表中的一个节点）
array[0] = sTwiceBaseCache;
// array[1]用来存放本次缓存的hash数组hashes（类似于链表节点中的数据部分）
array[1] = hashes;
// 将其他位置清空
for (int i = size - 1; i >= 2; i--) {
array[i] = null;
}
// 让sTwiceBaseCache重新指向array
sTwiceBaseCache = array;
sTwiceBaseCacheSize++;
if (DEBUG) {
Log.d(TAG, "Storing 2x cache " + array + " now have " + sTwiceBaseCacheSize + " entries");
}
}
}
}
// 判断尺寸是否是基础尺寸的一倍大小
else if (hashes.length == BASE_SIZE) {
synchronized (ArraySet.class) {
if (sBaseCacheSize < CACHE_SIZE) {
array[0] = sBaseCache;
array[1] = hashes;
for (int i = size - 1; i >= 2; i--) {
array[i] = null;
}
sBaseCache = array;
sBaseCacheSize++;
if (DEBUG) {
Log.d(TAG, "Storing 1x cache " + array + " now have " + sBaseCacheSize + " entries");
}
}
}
}
}
// 申请数组的时候优先使用缓存的数组，如果没有才新建数组
private void allocArrays(final int size) {
if (size == (BASE_SIZE * 2)) {
synchronized (ArraySet.class) {
if (sTwiceBaseCache != null) {
final Object[] array = sTwiceBaseCache;
try {
mArray = array;
sTwiceBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
array[0] = array[1] = null;
sTwiceBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 2x cache " + mHashes + " now have "
+ sTwiceBaseCacheSize + " entries");
}
return;
} catch (ClassCastException e) {
}
// Whoops! Someone trampled the array (probably due to not protecting
// their access with a lock). Our cache is corrupt; report and give up.
Slog.wtf(TAG, "Found corrupt ArraySet cache: [0]=" + array[0]
+ " [1]=" + array[1]);
sTwiceBaseCache = null;
sTwiceBaseCacheSize = 0;
}
}
} else if (size == BASE_SIZE) {
synchronized (ArraySet.class) {
if (sBaseCache != null) {
final Object[] array = sBaseCache;
try {
mArray = array;
sBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
array[0] = array[1] = null;
sBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 1x cache " + mHashes + " now have " +
sBaseCacheSize + " entries");
}
return;
} catch (ClassCastException e) {
}
// Whoops! Someone trampled the array (probably due to not protecting
// their access with a lock). Our cache is corrupt; report and give up.
Slog.wtf(TAG, "Found corrupt ArraySet cache: [0]=" + array[0]
+ " [1]=" + array[1]);
sBaseCache = null;
sBaseCacheSize = 0;
}
}
}
mHashes = new int[size];
mArray = new Object[size];
}
可见，ArraySet的主要索引方法是二分查找，这就导致它的效率要比HashMap低。官方建议是在元素不超过1000条的情况下使用，因为在这种数量级下效率相差不多的，但ArraySet对内存的使用更好。下面是一段官方注释：
Note that this implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashSet, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.
总结
综上所述，HashSet的元素是唯一无序的，TreeSet的元素是唯一有序的，ArraySet则是Android对HashSet在内存使用方便的一个优化版本，因为ArraySet效率比HashSet要低，所以建议在元素不超过1000条的情况下使用。另外，它们都不是线程安全的。
