JAVA的數(shù)據(jù)結(jié)構(gòu)

昵稱22369024 2015-04-01

展開全文

一、List接口,，有序的Collection接口,，能夠精確地控制每個元素插入的位置，允許有相同的元素

1.鏈表,，LinkedList實現(xiàn)了List接口,，允許null元素，提供了get(),、remove(),、insert()方法,，沒有同步方法

[java]view plaincopy
public void add() {                                      
        LinkedList List = new LinkedList();                
        List.add("link1");  
        List.add("link2");  
        List.add("link3");  
        Iterator it = List.iterator();                     
        while (it.hasNext()) {  
            System.out.println(it.next());  
        }  
        it.remove();                                          
        Iterator it1 = List.iterator();                       
        for (int i = 0; i < List.size(); i++) {  
            System.out.println(it1.next());  
        }  
    }  

2.數(shù)組列表，ArrayList,可以動態(tài)變化容量的數(shù)組,，非同步的

數(shù)組列表中存放的是Object類型,，因此在數(shù)組列表中存放的對象類型,，以其原型的父類代替，提取其中的元素時要進行類型轉(zhuǎn)換

[java]view plaincopy
public static void main(String[] args)  
    {  
        ArrayList al=new ArrayList();                        
        al.add("name");  
        al.add("value");  
        al.add("number");  
        for(int i=0;i<al.size();i++)  
        {  
            System.out.println(al.get(i));  
        }  
}  

二、Set接口,，不包含重復元素的Collection接口
1.散列集,，HashSet,實現(xiàn)了Set接口，非線性同步
與鏈表和數(shù)組列表幾乎類似,，但在數(shù)據(jù)處理時,，比使用鏈表進行數(shù)據(jù)處理花費時間更短，處理大數(shù)據(jù)時通常使用散列集

[java]view plaincopy
public static void main(String[] args)  
   {  
       long time=0;  
       HashSet hs=new HashSet();  
       ArrayList al=new ArrayList();  
       long starttime=System.currentTimeMillis();  
       for(int i=0;i<10000;i++)  
       {  
           hs.add(new Integer(i));  
       }  
       System.out.println(System.currentTimeMillis()-starttime);  
       for(int i=0;i<10000;i++)  
       {  
           al.add(new Integer(i));  
       }  
       System.out.println(System.currentTimeMillis()-starttime);     
   }  

2.樹集,，TreeSet,實現(xiàn)了Set接口,，實現(xiàn)了排序功能，該集合中的元素默認按升序排列元素
使用樹集數(shù)據(jù)結(jié)構(gòu)的對象,，需要實現(xiàn)Comparable接口,，樹集輸出的數(shù)據(jù)都是經(jīng)過排序的

三、Map接口,，沒有繼承Collection接口,，其提供key到value的映射，Map中不能包含相同的key,，每個key只能映射一個value,。
1.散列表類，HashTable,，繼承了Map接口,，非空（non-null）的對象都可作為key或value，是同步的
添加數(shù)據(jù)：put(key,value);
取出數(shù)據(jù)：get(key);
特點：無序的,，因此可以快速查找特定的元素

[java]view plaincopy
public static void TableTest(){  
        Hashtable ht = new Hashtable();  
        ht.put("key1", "value1");  
        ht.put("key2", "value2");  
        String value1=(String)ht.get("key2");  
        System.out.println(value1);  
    }  

構(gòu)造函數(shù)：Hashtable(),，初始容量11，負載因子0.75,，即散列表中已經(jīng)有75%的位置被放滿,，則進行再散列。
負載因子越高（越接近1）,，則內(nèi)存使用率越高,，元素的尋找時間越長，反之,，則內(nèi)存浪費越多,，尋找時間越短
key的對象將通過計算散函數(shù)確定與之對應的value位置，因此key的對象需要實現(xiàn)hashCode()和equals()方法,。
兩個對象相同,，則它們的hashCode必須相同；兩個對象不同,，則它們的hashCode不一定不同,。
沖突：不同對象的hashCode相同,，則稱為沖突，沖突將導致操作散列表的時間開銷增大,。因此要同時復寫equals()和hashCode()方法
2.散列映射類,，HashMap,與HashTable類似，不是HashMap是非同步的,，且允許null

[java]view plaincopy
public static void Maptest(){  
        Map<string string=""> map=new HashMap<string string="">();  
        map.put("key1", "value1");  
        map.put("key2", "value2");  
        map.put("key3", "value3");  
        for(Map.Entry<string string=""> entry:map.entrySet()){  
            System.out.println(entry.getKey());  
            System.out.println(entry.getValue());  
        }  
        String value1=(String)map.get("key1");  
        System.out.println(value1);  
    }  
</string></string></string>  