java 集合的数据结构

1、Collection集合

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2、Map集合

 

 * 图片中略掉抽象类

 

  1）Collection继承接口Iterable，所以其子类都可通过迭代器遍历元素。为了保证速度ArrayList适合用

        for循环，LinkedList适合用迭代器

    public static <T> void method(List<? super T> list) {
        int size = list.size();
        //RandomAccess标记接口，由此标记，最好用for循环遍历
        if ( list instanceof RandomAccess) {
            for (int i=0; i<size; i++){
            	//....
            }
        } else {
            ListIterator<? super T> itr = list.listIterator();
            for (int i=0; i<size; i++) {
            	itr.next();
            	//....
            }
        }
    }

  

  2）Map 可以通过entrySet()、keySet()方法，得到一个Set集合进行迭代器遍历。

  3）ListIterator可以向前和向后进行迭代

 

 

1）ArrayList<E>

 

数据结构：数组（线性序列）

适合操作：根据数据结构，善于随机访问元素，但是在其中间插入和移除元素时较慢

基本介绍：初始化时可设置数组容量大小，当实际元素个数size大于数组容量，对其进行扩容。因为其数

                 据结构是数组，每次查询可根据下标直接查到元素。删除一个元素时，后面元素统一向前移

                 一位。

 

 

 

2）LinkedList<E>

 

数据结构：双向链表   

适合操作：根据数据结构，不善于随机访问元素，但是在其中间插入和移除元素时较快

基本介绍：每个元素都是一个Node，除了元素值位，还有一个指向左右的引用。每次增删Node，只需要改

                 变左右的引用指向即可，不用移动元素 

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

 

 

 

 3）Vector<E>

 

数据结构：跟ArrayList的数据结构一样（数组）

适合操作：跟ArrayList一样，因同步的，所以没有ArrayList快

基本介绍：其方法与ArrayList也基本相同，只是在增、删、改、查等方法前加了synchronized关键字。

                 单线程中不需使用，即使使用后台的编译期也会进行对其进行优化，消除同步代码。多线程中

                 一般也很少使用，因为速度比较慢，而且组合操作（如果存在删除）无法实现线程安全。

          

              

 

 4）Stack<E>栈

 

数据结构：继承Vector （数组）  ，可用LinkedList链表实现。

适合操作：“栈”，先进后出的容器，只有一个口，一端放入元素，同一端取出元素

应用：1）平衡符号：栈中：｛｛【｛（   站外：）｝】｝｝ ，从栈中向外弹出元素做比较。

          2）后缀表达式: 表达式a+b*c+(d*e+f)*g 转成后缀：abc*+de*f+g*+ ,先将abc压栈，遇到*，bc出栈做

               乘法,结果x=b*c继续压入栈中，然后遇到+弹出ax做加法,,,,,,,

基本介绍： LinkedList能够直接实现栈的所有功能的方法，因此可以直接将LinkedList作为栈使用。

public class StackLinked<T> {	
	private LinkedList<T> linked = new LinkedList<T>();
	
	public T peek(){ return linked.getFirst(); }
	
	public T pop(){ return linked.removeFirst(); }

	public void push(T t){ linked.addFirst(t); }
	
	public boolean isEntry(){ return linked.isEmpty(); }
	
	@Override
	public String toString() {return linked.toString();}

}

 

 

 

 5）Queue<E> 队列

 

数据结构：数组（ArrayDeque）、链表（LinkedList）

适合操作：队列，先进先出的容器，从容器的一端放入事物， 从另一端取出

应用：并发，只是说思想，具体应用这里不介绍

基本介绍：放入顺序与取出顺序相同。

		Queue<String> queueLinked = new LinkedList<String>();
		Queue<String> queueArray = new ArrayDeque<String>();

  

 

 

 6）PriorityQueue<E> 优先队列

 

数据结构：堆（数组）。   

适合操作：优先队列，声明下一个弹出的元素是最需要的元素（最大值/最小值具有最高优先级）

基本介绍： 根据堆的性质，每次在[0]位置的都是最大或最小的元素。因为要进 行排序所以元素要实现接

                   口Comparator<T>。堆排介绍

	public static void main(String[] args) {
		Queue<Integer> queue = new PriorityQueue<Integer>(Arrays.asList(1, 3,
				5, 4, 6));
		while (!queue.isEmpty()) {
			System.err.println(queue.remove());// 1 3 4 5 6
		}
	}

 

 

 

7）Deque<E> 双向队列

 

数据结构：数组（ArrayDeque）、链表（LinkedList）

适合操作：双向队列，可以在任何一端添加或删除元素

基本介绍：因为ArrayDeque、LinkedList都实现了Deque接口，所以可以通过向上转型使用Deque

		Deque<String> dequeLinked = new LinkedList<String>();
		Deque<String> dequeArray = new ArrayDeque<String>();

 

 

 

 8）HashMap<K,V>  

 

数据结构：散列（数组+单向链表）   

适合操作：当get()时使用线性搜索，执行速度会很慢，而HashMap通过散列码可以很快定位元素位置。

基本介绍：1）每个元素都是一个Entry<K,V>对象，其底层通过Entry<K,V>数组来存储元素，每

                       个Entry<K,V>对象中会有一个next属性来实现单向链表

                  2）通过hash算法（利用K的hashCode）为每个Entry的K生成一个hash值，然后根据hash值

                       和数组length算出Entry在数组中的位置。

                  3）不同的K可能生成相同的hash值，即会存储在数组的同一个位置，这时通过for循环用

                        equals比较当前位置的链表元素，如果是false将新插入的值放入计算出来的位置，

                        然后next指向oldEntry，如果是false，则替换value

                  4) 装(负)载因子默认是075，即当数组75%的位置都有值时，对数组进行扩容length*2，然后重新

                      计算每个元素在数组中的位置。                  

 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        void recordAccess(HashMap<K,V> m) {
        }

        void recordRemoval(HashMap<K,V> m) {
        }
    }

 

 

9）HashSet<E> 

 

数据结构：散列

适合操作：无重复元素，可以快速超找到对象。

基本介绍：HashSet的元素可以看作是HashMap的key没有重复元素，查找块。所以HashSet的底层实现就

                 是HashMap

 

 

10）LinkedHashMap<K,V>   

 

数据结构：散列，双向链表

适合操作：具有HashMap的查询速度，内部使用双向链表维护顺序（插入次序），迭代遍历按插入顺序显

                  示，因为使用链表维护内部顺序，所以迭代访问很快。

基本介绍：继承自HashMap，每个元素Entry<K,V>多出两个指向两边元素的引用来维护顺序。

 private static class Entry<K,V> extends HashMap.Entry<K,V> {
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

        private void remove() {
            before.after = after;
            after.before = before;
        }

        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

 

 

 

11）LinkedHashSet<E> 

 

数据结构：散列，双向链表

适合操作：无重复元素，可以快速超找到对象。迭代遍历按插入顺序显示

基本介绍：LinkedHashSet的元素可以看作是LinkedHashMap的key没有重复的有序元素，

                 所以LinkedHashSet的底层实现就是LinkedHashMap

 

 

 

12）TreeMap<K,V>  

 

数据结构：红黑树

适合操作：对元素自动排序

基本介绍：下面是Entry<K,V>的属性。TreeMap会对K自动排序，次序由Comparable或Comparator决定，  

                  TreeMap中的元素都是有序的，如果键被用于TreeMap，那么必须实现Comparable。

 

红黑树：一种自平衡的二叉树。在实践中是高效的，它可以在O(log n)时间内做查找，插入和删除，

              这里的n是树中元素的数目。

学习红黑树建议： 先学习二叉查找树，然后学习平衡（AVL）树，再然后是红黑树

介绍：红黑树是内排（内存排序）中非常完美的结构，因为每种操作增、删、改、查时间复杂度都是

          O(log n)，再继续扩展的话就是b树，这种结构一般用来将数据存储在硬盘中，可用在数据库中。

          对List集合排序可以用帮助类Collections.sort()，Arrays.sort()可对数组排序。

    K key; 
    V value;
    Entry<K,V> left = null; //左节点
    Entry<K,V> right = null;//右节点
    Entry<K,V> parent; //父节点
    boolean color = BLACK;

 

 

 

13）TreeSet<E> 

 

数据结构：红黑树

基本介绍：通过TreeMap实现，功能参照TreeMap

评论

1 楼 男人50 2015-02-13