Java中數據結構的示例分析

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

1.1.1.       增量內存分配

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


在一個數組中有若干個對象，對象的類型都是 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 類型的變量中。

實現代碼 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());

}

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

讓我們來看看 ArrayList 類的實現 ：

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 內部是使用數組保存的數據， Java 中的數組是固定大小的，要想改變數組的大小，就要重新開辟一個新的大小的內存區域，把原先的數據復制到新內存區域中，這就是增量性數組。由于需要重新開辟內存區域并進行數據的復制，因此改變數組的大小是非常耗時的，我們要盡量避免改變數組的大小。

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

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

實現代碼 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());

}

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

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

選用合適的類

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

正如 4.5.1 中闡述的那樣， ArrayList 內部是使用數組保存的數據，而 LinkedList 則使用鏈表保存的數據。數組方式和鏈表方式儲存數據的優缺點比較如下 ：

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

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

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

選用合適的數據結構

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

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

實現代碼 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(" 數據重復 ");

        return;

    }

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

}

運行結果 ：

數據重復

     

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

實現代碼 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(" 數據重復 ");

        return;

    }

    set.add(data[i]);

}

運行結果 ：

數據重復

     

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

關于返回值

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

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

（ 1 ）數組，一定不能返回 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中數據結構的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。