Java中的容器

老付     2017-11-12   5082   14min  

容器的种类

为什么要使用容器? 因为数组不能够满足日常的开发需求,数组有以下弊端:

  1. 长度难以扩充
  2. 数据的类型必须相同
  3. 数组无法获得有多少个真实的数据,只能获得数组的长度。

在Java中有常用的三种类型的容器,分别是List 、Map、Set,基于这个三个基本的类型,派生出很多其它的类型,具体关系如下:

Relation

三者的区别:

  • Set(集):与list都是有Collection类的派生出来, 分辨各个元素的标识是HashCode,所以元素不能有重复
  • List(列表):是一个有序的列表,元素如果有重复,也会一一列出来。
  • Map(映射): Map是我们常说的键值对,有key和Value两个元素

使用方法:

 @Test
public void ContainerTest() {
    String string[] = {"i", "am", "am", "xiao", "ming"};

    List<String> list = new ArrayList<String>();
    for (String s : string) {
        list.add(s);
    }
    System.out.println("List执行结果:");
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }

    //
    Set<String> set = new HashSet<String>();
    for (String s : string) {
        set.add(s);
    }
    Iterator iterator = set.iterator();
    System.out.println("===================");
    System.out.println("Set 执行结果:");
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

运行结果:

List执行结果:
i
am
am
xiao
ming
===================
Set 执行结果:
ming
xiao
i
am

三者的区别可以表示如下图:

ListMapSet

各个容器的说明和使用


List


ArrayList

ArrayList是List一个派生类,非线安全,是基于Object数组实现的可动态扩展的容器,在调用Add的时候会判断当前的长度是否已经超过了Size.对应的Add方法:

  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    } 

 private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}
 private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkList与ArrayList区别是LinkList 是基于链表的结构设计 ,插入和删除的性能要高于ArrayList,查询的效率低于LinkList,使用方法基本一致,也是非线安全,下面看下性能测试代码:

 @Test
public void ListAdd() {
    System.out.println("ArrayList ADD耗时:" + AddList(new ArrayList()));
    System.out.println("LinkedList ADD耗时:" + AddList(new LinkedList()));

    //测试Edit
    final int N = 50000;
    Integer vals[] = new Integer[N];
    Random r = new Random();
    for (int i = 0, currval = 0; i < N; i++) {
        currval += r.nextInt(100) + 1;
        vals[i] = new Integer(currval);
    }
    List lst = Arrays.asList(vals);
    System.out.println("ArrayList Search耗时:" + SearchList(new ArrayList(lst)));
    System.out.println("LinkedList Search耗时:" + SearchList(new LinkedList(lst)));
}
long AddList(List list) {
    final int N = 50000;
    long start = System.currentTimeMillis();
    Object o = new Object();
    for (int i = 0; i < N; i++)
        list.add(0, o);
    return System.currentTimeMillis() - start;
}

long SearchList(List lst) {
    final int N = 50000;
    long start = System.currentTimeMillis();
    for (int i = 0; i < N; i++) {
        int index = Collections.binarySearch(lst, lst.get(i));
        if (index != i)
            System.out.println("***错误***");
    }
    return System.currentTimeMillis() - start;
}

运行结果:

ArrayList ADD耗时:396
LinkedList ADD耗时:9 

ArrayList Search耗时:20
LinkedList Search耗时:8330
Vector

比arraylist多了个同步化机制(线程安全),用法相同,但效率比较低,不建议使用。

Map


HashMap 和 HashTable

二者在使用上功能差不多,区别是HashMap是线程不安全,允许多线程去同时访问,允许插入空值。 而HashTable是相反的,对于HapMap的使用,可以参考下面代码:

 Map map=new HashMap();
 map.put("key","abc");
 map.put("key1","abc1");
 map.put("key2","abc2");
 System.out.println(map.get("key"));
 
 map.remove("key");
 System.out.println(map.values());
 System.out.println(map.keySet());
 System.out.println(map.entrySet());

运行结果如下:

abc
[abc1, abc2]
[key1, key2]
[key1=abc1, key2=abc2]

TreeMap

是一个有顺序的HaspMap

手工实现容器ArrayList

根据上面的分析,我们可以手工实现一个ArrayList 代码如下:

public class MyArrayList {

    private Object[] _arr;
    private int _size;

    public MyArrayList() {
        _arr = new Object[10];
        this._size = 0;
    }

    public void Add(Object obj) {
        if (this._size >= this._arr.length) {
            Object[] newArray = new Object[2 * this._size + 1];

            for (int i = 0; i < this._size; i++) {
                newArray[i] = this._arr[i];
            }
            this._arr = newArray;
            this._arr[this._size] = obj;
            this._size++;
        } else {
            this._arr[this._size] = obj;
            this._size++;
        }
    }

    public int Size() {
        return this._size;
    }

    public Object get(int index) {
        if (index > this._size) {
            throw new IndexOutOfBoundsException("索引超出界限");
        }
        return this._arr[index];
    }
}

使用方法:


@Test
public void PrintMyArr(){
    MyArrayList list=new MyArrayList();
    for (int i=0;i<10000;i++){
        list.Add(i);
    }

    System.out.println(list.Size());
    System.out.println(list.get(503));
    System.out.println(list);
}
 
(本文完)

作者:老付

如果觉得对您有帮助,可以下方的订阅,或者选择右侧捐赠作者,如果有问题,请在捐赠后咨询,谢谢合作

如有任何知识产权、版权问题或理论错误,还请指正。

自由转载-非商用-非衍生-保持署名,请遵循:创意共享3.0许可证

交流请加群113249828: 点击加群   或发我邮件 laofu_online@163.com