本節介紹EnumSet,為什麼說它是處理枚舉類型資料的一把利器?它有哪些應用場景?如何使用?内部是如何實作的? ...
本系列文章經補充和完善,已修訂整理成書《Java程式設計的邏輯》,由機械工業出版社華章分社出版,于2018年1月上市熱銷,讀者好評如潮!各大網店和書店有售,歡迎購買,京東自營連結:http://item.jd.com/12299018.html
上節介紹了EnumMap,本節介紹同樣針對枚舉類型的Set接口的實作類EnumSet。與EnumMap類似,之是以會有一個專門的針對枚舉類型的實作類,主要是因為它可以非常高效的實作Set接口。
之前介紹的Set接口的實作類HashSet/TreeSet,它們内部都是用對應的HashMap/TreeMap實作的,但EnumSet不是,它的實作與EnumMap沒有任何關系,而是用極為精簡和高效的位向量實作的,位向量是計算機程式中解決問題的一種常用方式,我們有必要了解和掌握。
除了實作機制,EnumSet的用法也有一些不同。次外,EnumSet可以說是處理枚舉類型資料的一把利器,在一些應用領域,它非常友善和高效。
下面,我們先來看EnumSet的基本用法,然後通過一個場景來看EnumSet的應用,最後,我們分析EnumSet的實作機制。
基本用法
與TreeSet/HashSet不同,EnumSet是一個抽象類,不能直接通過new建立,也就是說,類似下面代碼是錯誤的:
EnumSet<Size> set = new EnumSet<Size>();
不過,EnumSet提供了若幹靜态工廠方法,可以建立EnumSet類型的對象,比如:
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType)
noneOf方法會建立一個指定枚舉類型的EnumSet,不含任何元素。建立的EnumSet對象的實際類型是EnumSet的子類,待會我們再分析其具體實作。
為友善舉例,我們定義一個表示星期幾的枚舉類Day,值從周一到周日,如下所示:
enum Day {
MONDAY, TUESDAY, WEDNESDAY,
THURSDAY, FRIDAY, SATURDAY, SUNDAY
}
可以這麼用noneOf方法:
Set<Day> weekend = EnumSet.noneOf(Day.class);
weekend.add(Day.SATURDAY);
weekend.add(Day.SUNDAY);
System.out.println(weekend);
weekend表示休息日,noneOf傳回的Set為空,添加了周六和周日,是以輸出為:
[SATURDAY, SUNDAY]
EnumSet還有很多其他靜态工廠方法,如下所示(省略了修飾public static):
// 初始集合包括指定枚舉類型的所有枚舉值
<E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType)
// 初始集合包括枚舉值中指定範圍的元素
<E extends Enum<E>> EnumSet<E> range(E from, E to)
// 初始集合包括指定集合的補集
<E extends Enum<E>> EnumSet<E> complementOf(EnumSet<E> s)
// 初始集合包括參數中的所有元素
<E extends Enum<E>> EnumSet<E> of(E e)
<E extends Enum<E>> EnumSet<E> of(E e1, E e2)
<E extends Enum<E>> EnumSet<E> of(E e1, E e2, E e3)
<E extends Enum<E>> EnumSet<E> of(E e1, E e2, E e3, E e4)
<E extends Enum<E>> EnumSet<E> of(E e1, E e2, E e3, E e4, E e5)
<E extends Enum<E>> EnumSet<E> of(E first, E... rest)
// 初始集合包括參數容器中的所有元素
<E extends Enum<E>> EnumSet<E> copyOf(EnumSet<E> s)
<E extends Enum<E>> EnumSet<E> copyOf(Collection<E> c)
可以看到,EnumSet有很多重載形式的of方法,最後一個接受的的是可變參數,其他重載方法看上去是多餘的,之是以有其他重載方法是因為可變參數的運作效率低一些。
應用場景
下面,我們通過一個場景來看EnumSet的應用。
想象一個場景,在一些工作中,比如醫生、客服,不是每個從業人員每天都在的,每個人可工作的時間是不一樣的,比如張三可能是周一和周三,李四可能是周四和周六,給定每個人可工作的時間,我們可能有一些問題需要回答,比如:
- 有沒有哪天一個人都不會來?
- 有哪些天至少會有一個人來?
- 有哪些天至少會有兩個人來?
- 有哪些天所有人都會來,以便開會?
- 哪些人周一和周二都會來?
使用EnumSet,可以友善高效地回答這些問題,怎麼做呢?我們先來定義一個表示從業人員的類Worker,如下所示:
class Worker {
String name;
Set<Day> availableDays;
public Worker(String name, Set<Day> availableDays) {
this.name = name;
this.availableDays = availableDays;
}
public String getName() {
return name;
}
public Set<Day> getAvailableDays() {
return availableDays;
}
}
為示範友善,将所有從業人員的資訊放到一個數組workers中,如下所示:
Worker[] workers = new Worker[]{
new Worker("張三", EnumSet.of(
Day.MONDAY, Day.TUESDAY, Day.WEDNESDAY, Day.FRIDAY)),
new Worker("李四", EnumSet.of(
Day.TUESDAY, Day.THURSDAY, Day.SATURDAY)),
new Worker("王五", EnumSet.of(
Day.TUESDAY, Day.THURSDAY)),
};
每個從業人員的可工作時間用一個EnumSet表示。有了這個資訊,我們就可以回答以上的問題了。
哪些天一個人都不會來?代碼可以為:
Set<Day> days = EnumSet.allOf(Day.class);
for(Worker w : workers){
days.removeAll(w.getAvailableDays());
}
System.out.println(days);
days初始化為所有值,然後周遊workers,從days中删除可工作的所有時間,最終剩下的就是一個人都不會來的時間,這實際是在求worker時間并集的補集,輸出為:
[SUNDAY]
有哪些天至少會有一個人來?就是求worker時間的并集,代碼可以為:
Set<Day> days = EnumSet.noneOf(Day.class);
for(Worker w : workers){
days.addAll(w.getAvailableDays());
}
System.out.println(days);
輸出為:
[MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY]
有哪些天所有人都會來?就是求worker時間的交集,代碼可以為:
Set<Day> days = EnumSet.allOf(Day.class);
for(Worker w : workers){
days.retainAll(w.getAvailableDays());
}
System.out.println(days);
[TUESDAY]
哪些人周一和周二都會來?使用containsAll方法,代碼可以為:
Set<Worker> availableWorkers = new HashSet<Worker>();
for(Worker w : workers){
if(w.getAvailableDays().containsAll(
EnumSet.of(Day.MONDAY,Day.TUESDAY))){
availableWorkers.add(w);
}
}
for(Worker w : availableWorkers){
System.out.println(w.getName());
}
張三
哪些天至少會有兩個人來?我們先使用EnumMap統計每天的人數,然後找出至少有兩個人的天,代碼可以為:
Map<Day, Integer> countMap = new EnumMap<>(Day.class);
for(Worker w : workers){
for(Day d : w.getAvailableDays()){
Integer count = countMap.get(d);
countMap.put(d, count==null?1:count+1);
}
}
Set<Day> days = EnumSet.noneOf(Day.class);
for(Map.Entry<Day, Integer> entry : countMap.entrySet()){
if(entry.getValue()>=2){
days.add(entry.getKey());
}
}
System.out.println(days);
[TUESDAY, THURSDAY]
了解了EnumSet的使用,下面我們來看它是怎麼實作的。
實作原理
位向量
EnumSet是使用位向量實作的,什麼是位向量呢?就是用一個位表示一個元素的狀态,用一組位表示一個集合的狀态,每個位對應一個元素,而狀态隻可能有兩種。
對于之前的枚舉類Day,它有7個枚舉值,一個Day的集合就可以用一個位元組byte表示,最高位不用,設為0,最右邊的位對應順序最小的枚舉值,從右到左,每位對應一個枚舉值,1表示包含該元素,0表示不含該元素。
比如,表示包含Day.MONDAY,Day.TUESDAY,Day.WEDNESDAY,Day.FRIDAY的集合,位向量圖示結構如下:
對應的整數是23。
位向量能表示的元素個數與向量長度有關,一個byte類型能表示8個元素,一個long類型能表示64個元素,那EnumSet用的長度是多少呢?
EnumSet是一個抽象類,它沒有定義使用的向量長度,它有兩個子類,RegularEnumSet和JumboEnumSet。RegularEnumSet使用一個long類型的變量作為位向量,long類型的位長度是64,而JumboEnumSet使用一個long類型的數組。如果枚舉值個數小于等于64,則靜态工廠方法中建立的就是RegularEnumSet,大于64的話就是JumboEnumSet。
内部組成
了解了位向量的基本概念,我們來看EnumSet的實作,同EnumMap一樣,它也有表示類型資訊和所有枚舉值的執行個體變量,如下所示:
final Class<E> elementType;
final Enum[] universe;
elementType表示類型資訊,universe表示枚舉類的所有枚舉值。
EnumSet自身沒有記錄元素個數的變量,也沒有位向量,它們是子類維護的。
對于RegularEnumSet,它用一個long類型表示位向量,代碼為:
private long elements = 0L;
它沒有定義表示元素個數的變量,是實時計算出來的,計算的代碼是:
public int size() {
return Long.bitCount(elements);
}
對于JumboEnumSet,它用一個long數組表示,有單獨的size變量,代碼為:
private long elements[];
private int size = 0;
靜态工廠方法
我們來看EnumSet的靜态工廠方法noneOf,代碼為:
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)
return new RegularEnumSet<>(elementType, universe);
else
return new JumboEnumSet<>(elementType, universe);
}
getUniverse的代碼與上節介紹的EnumMap是一樣的,就不贅述了。如果元素個數不超過64,就建立RegularEnumSet,否則建立JumboEnumSet。
RegularEnumSet和JumboEnumSet的構造方法為:
RegularEnumSet(Class<E>elementType, Enum[] universe) {
super(elementType, universe);
}
JumboEnumSet(Class<E>elementType, Enum[] universe) {
super(elementType, universe);
elements = new long[(universe.length + 63) >>> 6];
}
它們都調用了父類EnumSet的構造方法,其代碼為:
EnumSet(Class<E>elementType, Enum[] universe) {
this.elementType = elementType;
this.universe = universe;
}
就是給執行個體變量指派,JumboEnumSet根據元素個數配置設定足夠長度的long數組。
其他工廠方法基本都是先調用noneOf構造一個空的集合,然後再調用添加方法,我們來看添加方法。
添加元素
RegularEnumSet的add方法的代碼為:
public boolean add(E e) {
typeCheck(e);
long oldElements = elements;
elements |= (1L << ((Enum)e).ordinal());
return elements != oldElements;
}
主要代碼是按位或操作:
elements |= (1L << ((Enum)e).ordinal());
(1L << ((Enum)e).ordinal())将元素e對應的位設為1,與現有的位向量elements相或,就表示添加e了。從集合論的觀點來看,這就是求集合的并集。
JumboEnumSet的add方法的代碼為:
public boolean add(E e) {
typeCheck(e);
int eOrdinal = e.ordinal();
int eWordNum = eOrdinal >>> 6;
long oldElements = elements[eWordNum];
elements[eWordNum] |= (1L << eOrdinal);
boolean result = (elements[eWordNum] != oldElements);
if (result)
size++;
return result;
}
與RegularEnumSet的add方法的差別是,它先找對應的數組位置,eOrdinal >>> 6就是eOrdinal除以64,eWordNum就表示數組索引,有了索引之後,其他操作與RegularEnumSet就類似了。
對于其他操作,JumboEnumSet的思路是類似的,主要算法與RegularEnumSet一樣,主要是增加了尋找對應long位向量的操作,或者有一些循環處理,邏輯也都比較簡單,後文就隻介紹RegularEnumSet的實作了。
RegularEnumSet的addAll方法的代碼為:
public boolean addAll(Collection<? extends E> c) {
if (!(c instanceof RegularEnumSet))
return super.addAll(c);
RegularEnumSet es = (RegularEnumSet)c;
if (es.elementType != elementType) {
if (es.isEmpty())
return false;
else
throw new ClassCastException(
es.elementType + " != " + elementType);
}
long oldElements = elements;
elements |= es.elements;
return elements != oldElements;
}
類型正确的話,就是按位或操作。
删除元素
remove方法的代碼為:
public boolean remove(Object e) {
if (e == null)
return false;
Class eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
long oldElements = elements;
elements &= ~(1L << ((Enum)e).ordinal());
return elements != oldElements;
}
主要代碼是:
elements &= ~(1L << ((Enum)e).ordinal());
~是取反,該代碼将元素e對應的位設為了0,這樣就完成了删除。
從集合論的觀點來看,remove就是求集合的差,A-B等價于A∩B',B'表示B的補集。代碼中,elements相當于A,(1L << ((Enum)e).ordinal())相當于B,~(1L << ((Enum)e).ordinal())相當于B',elements &= ~(1L << ((Enum)e).ordinal())就相當于A∩B',即A-B。
檢視是否包含某元素
contains方法的代碼為:
public boolean contains(Object e) {
if (e == null)
return false;
Class eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
return (elements & (1L << ((Enum)e).ordinal())) != 0;
}
代碼也很簡單,按位與操作,不為0,則表示包含。
檢視是否包含集合中的所有元素
containsAll方法的代碼為:
public boolean containsAll(Collection<?> c) {
if (!(c instanceof RegularEnumSet))
return super.containsAll(c);
RegularEnumSet es = (RegularEnumSet)c;
if (es.elementType != elementType)
return es.isEmpty();
return (es.elements & ~elements) == 0;
}
最後的位操作有點晦澀。我們從集合論的角度解釋下,containsAll就是在檢查參數c表示的集合是不是目前集合的子集。一般而言,集合B是集合A的子集,即B⊆A,等價于A'∩B是空集∅,A'表示A的補集,如下圖所示:
上面代碼中,elements相當于A,es.elements相當于B,~elements相當于求A的補集,(es.elements & ~elements) == 0;就是在驗證A'∩B是不是空集,即B是不是A的子集。
隻保留參數集合中有的元素
retainAll方法的代碼為:
public boolean retainAll(Collection<?> c) {
if (!(c instanceof RegularEnumSet))
return super.retainAll(c);
RegularEnumSet<?> es = (RegularEnumSet<?>)c;
if (es.elementType != elementType) {
boolean changed = (elements != 0);
elements = 0;
return changed;
}
long oldElements = elements;
elements &= es.elements;
return elements != oldElements;
}
從集合論的觀點來看,這就是求集合的交集,是以主要代碼就是按位與操作,容易了解。
求補集
EnumSet的靜态工廠方法complementOf是求補集,它調用的代碼是:
void complement() {
if (universe.length != 0) {
elements = ~elements;
elements &= -1L >>> -universe.length; // Mask unused bits
}
}
這段代碼也有點晦澀,elements=~elements比較容易了解,就是按位取反,相當于就是取補集,但我們知道elements是64位的,目前枚舉類可能沒有用那麼多位,取反後高位部分都變為了1,需要将超出universe.length的部分設為0。下面代碼就是在做這件事:
elements &= -1L >>> -universe.length;
-1L是64位全1的二進制,我們在剖析Integer一節介紹過移動位數是負數的情況,上面代碼相當于:
elements &= -1L >>> (64-universe.length);
如果universe.length為7,則-1L>>>(64-7)就是二進制的1111111,與elements相與,就會将超出universe.length部分的右邊的57位都變為0。
實作原理小結
以上就是EnumSet的基本實作原理,内部使用位向量,表示很簡潔,節省空間,大部分操作都是按位運算,效率極高。
小結
本節介紹了EnumSet的用法和實作原理,用法上,它是處理枚舉類型資料的一把利器,簡潔友善,實作原理上,它使用位向量,精簡高效。
對于隻有兩種狀态,且需要進行集合運算的資料,使用位向量進行表示、位運算進行處理,是計算機程式中一種常用的思維方式。
至此,關于具體的容器類,我們就介紹完了。Java容器類中還有一些過時的容器類,以及一些不常用的類,我們就不介紹了。
在介紹具體容器類的過程中,我們忽略了一個實作細節,那就是,所有容器類其實都不是從頭建構的,它們都繼承了一些抽象容器類。這些抽象類提供了容器接口的部分實作,友善了Java具體容器類的實作。如果我們需要實作自定義的容器類,也應該考慮從這些抽象類繼承。
那,具體都有什麼抽象類?它們都提供了哪些基礎功能?如何進行擴充呢?讓我們下節來探讨。
----------------
未完待續,檢視最新文章,敬請關注微信公衆号“老馬說程式設計”(掃描下方二維碼),從入門到進階,深入淺出,老馬和你一起探索Java程式設計及計算機技術的本質。用心原創,保留所有版權。