Java中數(shù)據(jù)結構的示例分析

這篇文章將為大家詳細講解有關Java中數(shù)據(jù)結構的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

1.1.1.       增量內(nèi)存分配

ArrayList 、 HashMap 、 Vector 等類都允許我們向其中加入任意多的對象，從而進行處理的，我們在享受它們帶來的便利的同時也要注意一定的性能問題。以 ArrayList 為例，我們來看一下在很多情況下是如何編寫出低性能的代碼的：


在一個數(shù)組中有若干個對象，對象的類型都是 PersonInfo ， PersonInfo 的類結構如下：

public class PersonInfo

{

    // 身份證號碼

    private String id;

    // 姓名

    private String name;

    // 年齡

    private int age;

    public PersonInfo(String id, String name, int age)

    {

        super();

        this.id = id;

        this.name = name;

        this.age = age;

    }

 

    public int getAge()

    {

        return age;

    }

 

    public String getId()

    {

        return id;

    }

 

    public String getName()

    {

        return name;

    }

}

請將所有這些 PersonInf 的身份證號碼，也就是 id 屬性，提取出來，放到另一個 List 類型的變量中。

實現(xiàn)代碼 1 ：

PersonInfo[] persons = new PersonInfo[] {

        new PersonInfo("00001", "Tom", 20),

        new PersonInfo("00002", "Tim", 23),

        new PersonInfo("00003", "Sally", 26),

        new PersonInfo("00005", "Lily", 20),

        new PersonInfo("00006", "Lucy", 30),

        new PersonInfo("00008", "Kitty", 20),

        new PersonInfo("00011", "Smith", 20),

        new PersonInfo("00031", "Ketty", 22),

        new PersonInfo("00051", "Melly", 20),

        new PersonInfo("00022", "Blues", 20),

        new PersonInfo("00033", "Tid", 18),

        new PersonInfo("00101", "Duoliaos", 30),

        new PersonInfo("00201", "Yang", 26),

        new PersonInfo("03001", "King", 20),

        new PersonInfo("05001", "Lee", 20),

        new PersonInfo("10001", "Wang", 20),

        new PersonInfo("06001", "Pizza", 60) };

 

List list = new ArrayList();

for (int i = 0, n = persons.length; i < n; i++)

{

    PersonInfo pInfo = persons[i];

    list.add(pInfo.getId());

}

程序運行正常，好像沒有出現(xiàn)任何問題。程序也確實真的不會出現(xiàn)問題，因為其邏輯如此簡單，不會但來問題。但是這個程序性能是最優(yōu)的嗎？

讓我們來看看 ArrayList 類的實現(xiàn) ：

public class ArrayList extends AbstractList implements List, RandomAccess,

        Cloneable, java.io.Serializable

{

    ……

    private transient Object elementData[];

    ……

    public ArrayList(int initialCapacity)

    {

        super();

        if (initialCapacity < 0)

             throw new IllegalArgumentException("Illegal Capacity: "

                      + initialCapacity);

        this.elementData = new Object[initialCapacity];

    }

    public ArrayList()

    {

        this(10);

    }

    ……

    public void ensureCapacity(int minCapacity)

    {

        modCount++;

        int oldCapacity = elementData.length;

        if (minCapacity > oldCapacity)

        {

             Object oldData[] = elementData;

             int newCapacity = (oldCapacity * 3) / 2 + 1;

             if (newCapacity < minCapacity)

                  newCapacity = minCapacity;

             elementData = new Object[newCapacity];

             System.arraycopy(oldData, 0, elementData, 0, size);

        }

    }    

 

    public boolean add(Object o)

    {

        ensureCapacity(size + 1);

        elementData[size++] = o;

        return true;

    }

}

正如其名字所暗示的， ArrayList 內(nèi)部是使用數(shù)組保存的數(shù)據(jù)， Java 中的數(shù)組是固定大小的，要想改變數(shù)組的大小，就要重新開辟一個新的大小的內(nèi)存區(qū)域，把原先的數(shù)據(jù)復制到新內(nèi)存區(qū)域中，這就是增量性數(shù)組。由于需要重新開辟內(nèi)存區(qū)域并進行數(shù)據(jù)的復制，因此改變數(shù)組的大小是非常耗時的，我們要盡量避免改變數(shù)組的大小。

從 ArrayList 的內(nèi)部實現(xiàn)我們可以發(fā)現(xiàn)， ArrayList 中儲存數(shù)據(jù)用的數(shù)組的默認大小為 10 ，當調(diào)用 add 方法向其中增加數(shù)據(jù)的時候，如果數(shù)據(jù)已經(jīng)超過了數(shù)組的大小， ArrayList 就要增加數(shù)組的大小以便容納更多的數(shù)據(jù)。在我們的這個人例子中，由于數(shù)據(jù)已經(jīng)超過 10 條，當增加到第 11 條的時候， ArrayList 就會進行一次“擴容”，這是一個非常耗時的操作，因此我們必須想方設法避免。

我們注意到 ArrayList 有一個帶參數(shù)的構造函數(shù)： public ArrayList(int initialCapacity) ，這里的 initialCapacity 代表構造此 ArrayList 的時候，數(shù)組的大小。我們可以使用此構造函數(shù)來避免“擴容”。

實現(xiàn)代碼 2 ：

PersonInfo[] persons = new PersonInfo[] {

        new PersonInfo("00001", "Tom", 20),

        new PersonInfo("00002", "Tim", 23),

        new PersonInfo("00003", "Sally", 26),

        new PersonInfo("00005", "Lily", 20),

        new PersonInfo("00006", "Lucy", 30),

        new PersonInfo("00008", "Kitty", 20),

        new PersonInfo("00011", "Smith", 20),

        new PersonInfo("00031", "Ketty", 22),

        new PersonInfo("00051", "Melly", 20),

        new PersonInfo("00022", "Blues", 20),

        new PersonInfo("00033", "Tid", 18),

        new PersonInfo("00101", "Duoliaos", 30),

        new PersonInfo("00201", "Yang", 26),

        new PersonInfo("03001", "King", 20),

        new PersonInfo("05001", "Lee", 20),

        new PersonInfo("10001", "Wang", 20),

        new PersonInfo("06001", "Pizza", 60) };

 

List list = new ArrayList(persons.length);

for (int i = 0, n = persons.length; i < n; i++)

{

    PersonInfo pInfo = persons[i];

    list.add(pInfo.getId());

}

我們已經(jīng)知道了 list 將放置 persons.length 條數(shù)據(jù)，因此我們就使 list 中數(shù)組的默認大小設置為 persons.length ，這樣系統(tǒng)的性能就好了很多。

不僅是 ArrayList ，我們在使用 Vector 、 HashMap 等類的同時，同樣要注意這個問題。

選用合適的類

List 接口最常用的實現(xiàn)類有兩個： ArrayList 、 LinkedList ，我們一般都是通過 List 接口來調(diào)用這些類的實現(xiàn)方法，所以它們的使用方式是幾乎相同的，其區(qū)別就在于其實現(xiàn)方式。

正如 4.5.1 中闡述的那樣， ArrayList 內(nèi)部是使用數(shù)組保存的數(shù)據(jù)，而 LinkedList 則使用鏈表保存的數(shù)據(jù)。數(shù)組方式和鏈表方式儲存數(shù)據(jù)的優(yōu)缺點比較如下 ：

數(shù)組中的數(shù)據(jù)是順序排列的，因此要向數(shù)組中插入數(shù)據(jù)或者從數(shù)組中刪除數(shù)據(jù)，就必須對其他數(shù)據(jù)進行位置的改變，因此效率是非常低的；但是由于數(shù)組的數(shù)據(jù)是按下標讀取的，所以從數(shù)組中檢索數(shù)據(jù)是非?？斓?。

鏈表中的數(shù)據(jù)是通過指針連在一起的，向鏈表中插入數(shù)據(jù)或者從鏈表中刪除數(shù)據(jù)只需要斷開指針關系即可，效率非常高；但是從鏈表中檢索數(shù)據(jù)的時候，必須從鏈表頭向后遍歷，效率非常低 。

因此 ArrayList 適合于保存很少插入、刪除，但是經(jīng)常讀取的場合，而 LinkedList 適合于經(jīng)常插入、刪除，但是很少讀取的場合。合理的使用這兩個類，將會提高系統(tǒng)的效率。

選用合適的數(shù)據(jù)結構

很多程序員都意識到了 Map 的方便性和實用性，因此也造成了 Map 的濫用。比如：

一個數(shù)組中有若干字符串，請驗證，這些字符串是否有重復。

實現(xiàn)代碼 1 ：

String[] data = { "11", "22", "33", "55", "11", "66" };

Map map = new HashMap();

for (int i = 0, n = data.length; i < n; i++)

{

    if (map.containsKey(data[i]))

    {

        System.out.println(" 數(shù)據(jù)重復 ");

        return;

    }

    map.put(data[i], "");

}

運行結果 ：

數(shù)據(jù)重復

     

這段代碼利用了 Map 中鍵不能重復的特性，實現(xiàn)了要求的效果，但是看起來怪怪的，因為 Map 中的數(shù)據(jù)是“鍵 - 值對”，而這里只用到了“鍵”，對于“值”則只是簡單的塞了一個空字符串進去應付差事。顯然這對 Map 來說是誤用。

實現(xiàn)代碼 2 ：

String[] data = { "11", "22", "33", "55", "11", "66" };

Set set = new HashSet();

for (int i = 0, n = data.length; i < n; i++)

{

    if (set.contains(data[i]))

    {

        System.out.println(" 數(shù)據(jù)重復 ");

        return;

    }

    set.add(data[i]);

}

運行結果 ：

數(shù)據(jù)重復

     

JDK 中的 Set 接口代表中數(shù)學中的“集合”（注意和 JDK 中的 Collection 區(qū)分開），即不重復的數(shù)據(jù)項的容器。顯然使用 Set 接口就完全能滿足我們的要求，同時我們又使用了采用哈希算法的 HashSet ，這就保證了判斷數(shù)據(jù)重復時的效率。案例系統(tǒng)中的 PermissionServiceImpl 類（包 com.cownew.PIS.base.permission.bizLayer 下）就是用 Set 來完成權限項名稱重復驗證的；類 ServerUserContext （包 com.cownew.PIS.framework.server.sessionMgr 下）的 getPermissonNameSet 方法返回 Set 類型的意義也在于此 。

關于返回值

經(jīng)常需要使用 List 、 Map 、 Set 等類做為方法返回值以返回多個數(shù)據(jù)，但是 JDK1.5 之前是不支持泛型的，我們只能看到方法返回一個 List 、 Map 或者 Set 類型的返回值，至于這些容器內(nèi)存放著什么類型的數(shù)據(jù)則無法得知，只能通過查手冊才能得知。在讀取數(shù)據(jù)的時候又要進行類型轉換。這給系統(tǒng)留下了很多不確定性因素。在 JDK1.5 之前唯一能在編譯器就確定容器中數(shù)據(jù)的類型的 Java 結構就是數(shù)組，因此如果在返回數(shù)據(jù)的時候能夠確定數(shù)據(jù)的類型以及大小，并且確定調(diào)用者只是讀取返回值，那么我們就應該盡量使用數(shù)組來返回數(shù)據(jù)，這樣程序的可讀性就增強了，而且也減少了很多不確定性因素。

在使用返回值的時候還要注意一些慣用法。

（ 1 ）數(shù)組，一定不能返回 NULL

Object[] fooBar()

{

   //do something

   return null;

}

極少有人這樣使用此方法：

Object[] objArray = fooBar();

if (objArray != null)

{

   for (int i = 0; i < objArray.Length; ++i)

   {

       //do something

   }

}

應該這樣寫 fooBar 方法：

Object[] fooBar()

{

   //do something

   return new Object[0];

}

（ 2 ）集合，同樣不能返回 NULL

Set fooBar()

{

   //do something

   return null;

}

應該這樣寫：

Set fooBar()

{

   //do something

   return new HashSet(0);

}

關于“Java中數(shù)據(jù)結構的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。