Skip to content

Latest commit

 

History

History
423 lines (322 loc) · 9.29 KB

9. Collection.md

File metadata and controls

423 lines (322 loc) · 9.29 KB

9. Collection

java.util

  1. Collection可以自动调整容量 2）只能放对象

List三个子类：

==ArrayList==底层实现是数组（线程不安全，效率高，查询快，插入修改慢）；==LinkedList==（线程不安全，效率高，查询慢，插入修改快）底层实现是链表；==Vector==线程安全，效率低；

package com.alexanderli95.collections;

import java.util.ArrayList;

import java.util.Date;
import java.util.List;

/**
 * 测试List
 */
public class TestCollection {
    public static void main(String[] args) {
        List list=new ArrayList();
        list.add("aaaaa");
        list.add(new Date());
        list.add(new Dog());
        list.add(1234);

        System.out.println(list.size());
        list.remove("aaaaa");
        System.out.println(list.size());
        System.out.println(list.isEmpty());

        List list2=new ArrayList();
        list2.add("aaa");
        list2.add("bbb");
        list.add(list2);
        System.out.println(list.size());

        //String s=(String)list.get(0);
        //System.out.println(s);
        list.add(1,"c");
        System.out.println(list);
    }
}

class Dog{

}

链表类的实现：

package com.alexanderli95.collections;


public class AlexLinkedList {  //双向链表
    private Node first;
    private Node last;
    private int size=0;

    public void add(Object obj){
        if(first==null){
            Node n=new Node();
            n.setPrevious(null);
            n.setData(obj);
            n.setNext(null);

            first=n;
            last=n;
        }else{
            //在最后增加节点
            Node n=new Node();
            n.setPrevious(last);
            n.setData(obj);
            n.setNext(null);

            last.setNext(n);

            last=n;
        }
        size++;
    }

    public int size(){
        return size;
    }

    public Object get(int index){

        if(first!=null && index>=0 && index<=size){  //检查index是否越界
            Node temp=first;
            for(int i=0;i<index;i++){
                temp=temp.getNext();
            }
            return temp.getData();
        }else if(index<0 || index>size){
            System.out.println("下标越界");
        }
        return null;

    }


    public void remove(int index){
        Node temp=null;
        if(first!=null && index>=0 && index<=size){  //检查index是否越界

            temp=first;
            for(int i=0;i<index;i++){
                temp=temp.getNext();
            }
        }else if(index<0 || index>size){
            System.out.println("下标越界");
        }

        if(temp!=null) {
            Node up = temp.getPrevious();
            Node down = temp.getNext();

            up.setNext(down);
            down.setPrevious(up);
            size--;
        }
    }

    public void add(int index,Object obj){
        Node temp=null;
        if(first!=null && index>=0 && index<=size){  //检查index是否越界

            temp=first;
            for(int i=0;i<index;i++){
                temp=temp.getNext();
            }
        }else if(index<0 || index>size){
            System.out.println("下标越界");
        }

        Node newNode=new Node();
        newNode.setData(obj);

        if(temp!=null){
            Node up=temp.getPrevious();
            up.setNext(newNode);
            newNode.setPrevious(up);

            newNode.setNext(temp);
            temp.setPrevious(newNode);
        }

        size++;

    }


    public static void main(String[] args) {
        AlexLinkedList alexLinkedList=new AlexLinkedList();
        alexLinkedList.add(123);
        alexLinkedList.add(456);
        alexLinkedList.add(123456);
        alexLinkedList.add(2,"addtest");
        System.out.println(alexLinkedList.size());
        System.out.println(alexLinkedList.get(1));

        alexLinkedList.remove(1);
        System.out.println(alexLinkedList.get(1));
    }

}

class Node{
    private Node previous;
    private Object data;
    private Node next;

    public  Node(){

    }

    public Node(Node previous, Object data, Node next) {
        this.previous = previous;
        this.data = data;
        this.next = next;
    }

    public Node getPrevious() {
        return previous;
    }

    public void setPrevious(Node previous) {
        this.previous = previous;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

Map:键值对

==两个包==：java.util.Map; java.util.HashMap

==底层实现==：数组+链表，数组中存放的是链表对象

==常用的子类==：HashMap（线程不安全，效率高）和Hashtable（线程安全，效率低）;用法相同

==注==：键不能重复，如果重复了，后put的键值对会将原来的键值对覆盖

package com.alexanderli95.collections;

import java.util.HashMap;
import java.util.Map;

/**
 * 测试Map
 */
public class TestMap {
    public static void main(String[] args) {
        Map map=new HashMap();
        map.put("a",new Wife("1"));  //put(Key,Value); 增加或删除都是成对的操作
        map.put("b",new Wife("2"));

        Wife w=(Wife)map.get("a");

        System.out.println(w.getName());

        map.remove("b");
        //Wife w2=(Wife)map.get("b");

    }
}

class Wife{
    private String name;
    public Wife(String name){
        this.name=name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

Map类的实现（version: 0.1）：

package com.alexanderli95.collections;

/**
 * Map类的实现
 */
public class AlexMap {

    AlexEntry[] arr=new AlexEntry[1000];
    int size;

    public void put(Object key,Object value){
        AlexEntry e=new AlexEntry(key,value);

        for(int i=0;i<size;i++){
            if(arr[i].getKey().equals(key)){
                arr[i].setValue(value);
                return ;
            }
        }

        arr[size++]=e;
    }

    public Object get(Object key){
        for(int i=0;i<size;i++){
            if(arr[i].getKey().equals(key)){
                return arr[i].getValue();
            }
        }
        return null;
    }

    public boolean containsKey(Object key){
        for(int i=0;i<size;i++){
            if(arr[i].getKey().equals(key)){
                return true;
            }
        }
        return false;
    }

    public boolean containsValue(Object value){
        for(int i=0;i<size;i++){
            if(arr[i].getValue().equals(value)){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        AlexMap map=new AlexMap();
        map.put("1",new Wife("a"));
        map.put("2",new Wife("b"));
        Wife w=(Wife)map.get("1");

        System.out.println(w.getName());
    }
}

class AlexEntry{
    private Object key;
    private Object value;

    public AlexEntry(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    public Object getKey() {
        return key;
    }

    public void setKey(Object key) {
        this.key = key;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }
}

Map类的实现（version 0.2）：

package com.alexanderli95.collections;

import java.util.LinkedList;

/**
 * Map类的实现
 * 1.提高查询的效率
 */
public class AlexMap02 {
    LinkedList[] arr=new LinkedList[1000];
    int size;

    public void put(Object key,Object value){
        AlexEntry e=new AlexEntry(key,value);
        int a=key.hashCode()%arr.length;
        if(arr[a]==null){

            LinkedList list=new LinkedList();
            list.add(e);
            arr[a]=list;

        }else{

            //键值重复直接覆盖
            LinkedList list=arr[a];
            for(int i=0;i<list.size();i++){
                AlexEntry entry=(AlexEntry) list.get(i);
                if(entry.getKey().equals(key)){
                    entry.setValue(value);
                    return ;
                }

            }

            arr[a].add(e);
        }
    }

    public Object get(Object key){
        int a=key.hashCode()%arr.length;
        if(arr[a]!=null){
            LinkedList list=arr[a];
            for(int i=0;i<list.size();i++){
                AlexEntry entry=(AlexEntry) list.get(i);
                if(entry.getKey().equals(key)){
                    return entry.getValue();
                }

            }
        }
        return null;

    }

    public static void main(String[] args) {
        AlexMap02 map=new AlexMap02();
        map.put("1",new Wife("a"));
        map.put("2",new Wife("b"));
        Wife w=(Wife)map.get("1");

        System.out.println(w.getName());
    }
}