程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> 計算機程序的思維邏輯 (51),思維51

計算機程序的思維邏輯 (51),思維51

編輯:JAVA綜合教程

計算機程序的思維邏輯 (51),思維51


上節介紹了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編程及計算機技術的本質。用心原創,保留所有版權。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved