Java集合框架中Set接口有哪些实现?
1. Set接口详解
1.1. Set接口有哪些实现?
2. HashSet详解
2.1. HashSet是如何设计的?
HashSet
内部组合了一个HashMap
,利用了HashMap
的键不能重复的特性。
2.2. HashSet是如何添加元素的?
当HashSet
添加元素时,会调用HashMap
的put
方法。新元素作为键值对的键,PRESENT
对象作为键值对的值添加到内部组合的HashMap
中。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
2.3. HashSet是如何查询元素的?
当HashSet
查询元素时,会调用HashMap
的containsKey
方法。
public boolean contains(Object o) {
return map.containsKey(o);
}
2.4. HashSet是如何删除元素的?
当HashSet
删除元素时,会调用HashMap
的remove
方法。使用PRESENT
对象作为键值对的值的目的是在移除键时会返回对应的值,以判断是否包含该键。
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
3. LinkedHashSet详解
3.1. LinkedHashSet是如何设计的?
LinkedHashSet
内部组合了一个LinkedHashMap
,利用了LinkedHashMap
的键不能重复且有序的特性。
3.2. LinkedHashSet是如何实现有序的?
利用了LinkedHashMap
有序的特性。创建LinkedHashSet
时,会调用父类HashSet
中的构造器来创建一个LinkedHashMap
。
public LinkedHashSet() {
super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
4. TreeSet详解
4.1. TreeSet是如何设计的?
TreeSet
内部组合了一个TreeMap
,利用了TreeMap
的键不能重复且有序的特性。
4.2. TreeSet是如何实现有序的?
利用了TreeMap
有序的特性。创建TreeSet
时,会调用构造器来创建一个TreeMap
。
public TreeSet() {
this(new TreeMap<E,Object>());
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
5. EnumSet详解
5.1. EnumSet有哪些实现?
EnumSet
的实现有RegularEnumSet
和JumboEnumSet
两种。当枚举中枚举项的个数不大于64时使用RegularEnumSet
,否则使用JumboEnumSet
。
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
throw new ClassCastException(elementType + " not an enum");
if (universe.length <= 64)
// 当枚举中枚举项的个数不大于64时
return new RegularEnumSet<>(elementType, universe);
else
// 当枚举中枚举项的个数大于64时
return new JumboEnumSet<>(elementType, universe);
}
public static <E extends Enum<E>> EnumSet<E> of(E e) {
EnumSet<E> result = noneOf(e.getDeclaringClass());
result.add(e);
return result;
}
5.2. RegularEnumSet是如何设计的?
RegularEnumSet
内部维护了一个long
类型变量,占用了8个字节,即64位,每一位的0或1代表对应的枚举值是否存在,故其用于枚举项的个数不大于64的枚举。RegularEnumSet
通过位运算实现Set
的功能。
public boolean add(E e) {
typeCheck(e);
long oldElements = elements;
// 指定位为1,|位运算赋值为1;指定位为0,|位运算赋值为1
elements |= (1L << ((Enum<?>)e).ordinal());
return elements != oldElements;
}
public boolean contains(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
// 指定位为1,&位运算返回不为0;指定位为0,&位运算返回为0
return (elements & (1L << ((Enum<?>)e).ordinal())) != 0;
}
5.3. JumboEnumSet是如何设计的?
相比于RegularEnumSet
,JumboEnumSet
内部维护了一个long
类型数组变量,每个long
的每一位的0或1代表对应的枚举值是否存在。JumboEnumSet
通过位运算实现Set
的功能。
public boolean add(E e) {
typeCheck(e);
int eOrdinal = e.ordinal();
int eWordNum = eOrdinal >>> 6;
// 右移先找到对应的long字段
long oldElements = elements[eWordNum];
elements[eWordNum] |= (1L << eOrdinal);
boolean result = (elements[eWordNum] != oldElements);
if (result)
size++;
return result;
}
public boolean contains(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
int eOrdinal = ((Enum<?>)e).ordinal();
// 右移先找到对应的long字段
return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0;
}