容器集合

简述;记录一下Java的容器集合和数据结构的应用

目录(Catalog)

泛型
Collection接口
List常用方法
ArrayList特点
LinkedList底层实现
Map接口
HashMap和HashTable
红黑树/二叉树/TreeMap
Set接口
总结

泛型

泛型的概念

泛型的本质就是“数据类型的参数化”。我们可以把“泛型”理解为规定容器数据类型的接口，告诉编译器，在调用泛型时必须传入实际类型。

泛型类的声明

在下面的第一个例子中E表示泛型，有时也可用T来表示。第二个例子是泛型的使用过程,”String”就是实际传入的数据类型,加了泛型，直接返回String类型，不用强制转换,简单来说也就避免了强制转型带来的麻烦。

exp1:

 class MyCollection<E> {
    Object[] objs = new Object[5];
 
    public E get(int index) {
        return (E) objs[index];
    }
    public void set(E e, int index) {
        objs[index] = e;
    }
}

exp2:

public static void main(String[] args) {
		ArrayList<String> s =  new ArrayList<String>();
		s.add("I am");
		s.add("a handsome boy !");
		System.out.println(s);
	}

Collection接口

说明一下各集合之间的关系：

Collection (接口这个接口extends自Iterable接口)
- List (接口代表有序，可重复的集合。列表）
  - ArreyList (Class 数组，随机访问，没有同步，线程不安全)
  - ector (Class 数组同步线程全)
  - inkedList (Class 链表插入删除没有同步线程不安全)
  - tack (Class)
- Set（接口不能含重复的元素。仅接收一次并做内部排序，集）
- HashSet
- LinkedHashSet
- TreeSet
Map(接口映射集合)
- ashMap (Class 不同步，线程不安全。除了不同和允许使用null 键值之外，与Hashtable大致相同)
- Hashtable (Class 同步，线程安全。不允许实施null 键值)
- SortedMap 接口
- reeMap (Class)
- WeakHashMap (Class)

放张图说明一下：

Collection包含List和Set两个子接口，有包含集合的以上。

以下是Collection的常用方法；List、Set是Collection的子接口，所有List、Set的实现类都有下面的方法。

List

List是有序、可重复的容器。
List中每个元素都有索引标记。可以根据元素的索引标记(在List中的位置)访问元素，从而精确控制这些元素。
List允许加入重复的元素。更确切地讲，List通常允许满足 e1.equals(e2) 的元素重复加入容器。

下表是List增加的一些常用方法：

ArrayList

数组长度是有限的，而ArrayList是可以存放任意数量的对象，长度不受限制。
ArrayList相比于数组的使用更为灵活。

ArrayList之所以不需要事先考虑储存长度是由于其类方法中考虑到了扩容操作，看下面的代码：

 private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

这里写了一些ArrayList常用的方法操作：

public static void main(String[] args) {
		//定义接口类型
		ArrayList<Integer> mylist = new ArrayList<Integer>();
		ArrayList<Integer> testAdd = new ArrayList<Integer>();
		System.out.println("ArrayList的大小为："+mylist.size());
		for(int i=0;i<10;i++) {
			mylist.add(i);
			testAdd.add(-i);
		}
		System.out.println("ArrayList的大小为："+mylist.size());
		System.out.println("ArrayList包含:"+mylist);
		System.out.println("ArrayList是否包含整形6："+mylist.contains(6));
		System.out.println("ArrayList的第六个元素："+mylist.get(5));
		System.out.println("ArrayList中整形5的下标为："+mylist.indexOf(5));
		mylist.remove(2);
		System.out.println("ArrayList移除元素2后剩下："+mylist);
		mylist.set(0, 9);
		System.out.println("将ArrayList中的第一个元素改为9之后："+mylist);
		mylist.addAll(2, testAdd);
		System.out.println("将testAdd添加到ArrayList第三个元素之后:"+mylist);
		mylist.clear();
		System.out.println("ArrayList清除之后还有："+mylist);
		
	}

控制台的输出：

ArrayList的大小为：0
ArrayList的大小为：10
ArrayList包含:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
ArrayList是否包含整形6：true
ArrayList的第六个元素：5
ArrayList中整形5的下标为：5
ArrayList移除元素2后剩下：[0, 1, 3, 4, 5, 6, 7, 8, 9]
将ArrayList中的第一个元素改为9之后：[9, 1, 3, 4, 5, 6, 7, 8, 9]
将testAdd添加到ArrayList第三个元素之后:[9, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, 3, 4, 5, 6, 7, 8, 9]
ArrayList清除之后还有：[]

如果要更好地了解ArrayList,可以看ArrayList的源码

LinkedList

LinkedList底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。
双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。
ArrayList和LinkedList区别
- ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于链表的数据结构；
- 对于添加和删除操作add，remove，LinkedList要比ArrayList快，因为ArrayList要移动数据。
- 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针.

一些LinkedList的常用方法代码，与ArrayList类似：

public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		for(int i=0;i<10;i++) {
			list.add(i, i);
		}
		System.out.println("list里的元素有"+list);
		System.out.println("list的大小："+list.size());
		System.out.println("判断list是否为空:"+list.isEmpty());
		for(int i=0;i<10;i++) {
			list.set(list.get(i), -i);
		}
		System.out.println("将list的元素更改："+list);
		list.removeAll(list);
		System.out.println("移除所有元素后的list："+list);
	}

控制台输出：

list里的元素有[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list的大小：10
判断list是否为空:false
将list的元素更改：[0, -1, -2, -3, -4, -5, -6, -7, -8, -9]
移除所有元素后的list：[]

LinkedList的源码比ArrayList的更难读懂一些.

Vector特性

底层是用数组实现的List。
相关的方法都加了同步检查，线程安全，效率低。
如何选用ArrayList\LinkedList\Vector
- 需要线程安全时，首选Vector
- 不考虑线程安全问题时，查找较多用ArrayList。
- 不考虑线程安全问题时，增删较多用LinkedList。

Map接口

Map是一个接口，不能直接实现，和Collection接口一样。
Map类中存储的“键值对”通过键来标识，其“键对象”不能重复。<key,value>
Map 接口的实现类有HashMap、TreeMap、HashTable、Properties等。

Map接口中的一些方法：

HashMap和HashTable

HashMap采用哈希算法实现，是Map接口最常用的实现类.
键值如果发生重复，新的键值对会替换旧的键值对。
HashMap在查找、删除、修改方面都有非常高的效率。
HashTable类和HashMap用法几乎一样，但HashTable类的实现方法添加了同步(synchronized)关键字。
使用区别：
- HashMap:线程不安全，效率高。允许key或value为null。
- HashTable线程安全，效率低。不允许key或value为null。

具体实例：

public static void main(String[] args) {
			Map<Integer, String> m1 = new HashMap<Integer, String>();
			for(int i=0;i<10;i++) {
				m1.put(i,"aa");
			}
			System.out.println(m1);
			System.out.println(m1.get(5));
			m1.put(5, "bb");
			System.out.println(m1);
			m1.clear();
			System.out.println(m1);
		}

控制台输出：

{0=aa, 1=aa, 2=aa, 3=aa, 4=aa, 5=aa, 6=aa, 7=aa, 8=aa, 9=aa}
aa
{0=aa, 1=aa, 2=aa, 3=aa, 4=aa, 5=bb, 6=aa, 7=aa, 8=aa, 9=aa}
{}

红黑树/二叉树/TreeMap

红黑树二叉树原理概述以及其Java实现
- Java 实现二叉树的构造以及遍历过程
- 红黑树深入剖析及Java实现
TreeMap

我们看到TreeMap的源码中的private transient Entry<K,V> root;,进入Entry<K,V>。

    private static final boolean RED   = false;
    private static final boolean BLACK = true;

    /**
     * Node in the Tree.  Doubles as a means to pass key-value pairs back to
     * user (see Map.Entry).
     */

    static final class Entry<K,V> implements Map.Entry<K,V> {
	K key;
	V value;
	Entry<K,V> left;
	Entry<K,V> right;
	Entry<K,V> parent;
	boolean color = BLACK;

可以看到里面存储了本身数据、左节点、右节点、父节点、以及节点颜色。
TreeMap是红黑树的经典实现。

Set接口

继承自Collection,方法和Collection保持完全一致。
无序、不可重复；Set中的元素没有索引，我们只能遍历查找;不允许加入重复的元素。
其实现类有：HashSet、TreeSet等。
HashSet的使用方法与前面类似。
TreeSet通过TreeMap来实现，放入TreeSet中的类要实现Comparable接口，且放入元素不能为null。

总结

容器集合系列比较通俗，并没有很好地深入了解底层的原理。
只能作为一个全面的知识点框架图使用。

容器集合

关于java中的常用集合类collection\map\list的记录

容器集合

目录(Catalog)

泛型

Collection接口

List

ArrayList

LinkedList

Vector特性

Map接口

HashMap和HashTable

红黑树/二叉树/TreeMap

Set接口

总结

CATALOG

FEATURED TAGS

FRIENDS