[toc]

Java 类库中的集合接口和迭代器

集合接口及迭代器


集合概览图

image-20181105132158288.png

具体的集合实现

ArrayList

简介

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.ArrayList<E>

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

特性

    // 将其包装成线程安全
    List list = Collections.synchronizedList(new ArrayList());

toArray()

    // toArray(T[] contents)调用方式一
public static Integer[] vectorToArray1(ArrayList<Integer> v) {
    Integer[] newText = new Integer[v.size()];
    v.toArray(newText);
    return newText;
}
// toArray(T[] contents)调用方式二。最常用!
public static Integer[] vectorToArray2(ArrayList<Integer> v) {
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);
    return newText;
}
// toArray(T[] contents)调用方式三
public static Integer[] vectorToArray3(ArrayList<Integer> v) {
    Integer[] newText = new Integer[v.size()];
    Integer[] newStrings = (Integer[])v.toArray(newText);
    return newStrings;
}

注意点

LinkedList

一种可以在任意位置进行高效插入及删除的操作的有序序列

简介

定义

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.AbstractSequentialList<E>
                     ↳     java.util.LinkedList<E>

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

特性

将LinkedList当作 LIFO(后进先出)的堆栈示例

    public static void useLinkedListAsLIFO() {
        System.out.println("\nuseLinkedListAsLIFO");
        // 新建一个LinkedList
        LinkedList stack = new LinkedList();

        // 将1,2,3,4添加到堆栈中
        stack.push("1");
        stack.push("2");
        stack.push("3");
        stack.push("4");
        // 打印“栈”
        System.out.println("stack:"+stack);

        // 删除“栈顶元素”
        System.out.println("stack.pop():"+stack.pop());

        // 取出“栈顶元素”
        System.out.println("stack.peek():"+stack.peek());

        // 打印“栈”
        System.out.println("stack:"+stack);
    }

将LinkedList当作 FIFO(先进先出)的队列

 public static void useLinkedListAsFIFO() {
        System.out.println("\nuseLinkedListAsFIFO");
        // 新建一个LinkedList
        LinkedList queue = new LinkedList();

        // 将10,20,30,40添加到队列。每次都是插入到末尾
        queue.add("10");
        queue.add("20");
        queue.add("30");
        queue.add("40");
        // 打印“队列”
        System.out.println("queue:"+queue);

        // 删除(队列的第一个元素)
        System.out.println("queue.remove():"+queue.remove());

        // 读取(队列的第一个元素)
        System.out.println("queue.element():"+queue.element());

        // 打印“队列”
        System.out.println("queue:"+queue);
    }

HashMap(JDK 1.7 及之前)

简介

HashMap 它是基于 hash 表的 Map 接口实现,以 key-value 的形式存在的,HashMap 总是以 key-value 的形式存在的,系统会通过计算 key 的 hash 值来定位 key-value 的存储位置的,我们可以快速的通过 key 来存取 value;

定义

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable

数据结构

关于 HashMap 的数据结构,底层的话还是数组的,只不过数组的每一项就是一个链表

image-20181105132158288.png

    public HashMap(int initialCapacity, float loadFactor) {
            //初始容量不能<0
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: "
                        + initialCapacity);
            //初始容量不能 > 最大容量值,HashMap的最大容量值为2^30
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            //负载因子不能 < 0
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: "
                        + loadFactor);

            // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;

            this.loadFactor = loadFactor;
            //设置HashMap的容量极限,当HashMap的容量达到该极限时就会进行扩容操作
            threshold = (int) (capacity * loadFactor);
            //初始化table数组
            table = new Entry[capacity];
            init();
        }

Entry 的源码

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

            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
            .......
        }

Entry 是 HashMap 的内部类,其中包含了 key,value 和 下一个 Entry,以及 hash 值,正因为有这下才构成了数组的项为一个列表。

容量、加载因子、临界值及哈希冲突

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

哈希冲突

在关键字的 hash 地址上已经有了记录,那么这就是哈希冲突

(3)将节点插入表头

    void addEntry(int hash, K key, V value, int bucketIndex) {
            //获取bucketIndex处的Entry
            Entry<K, V> e = table[bucketIndex];
            //将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry 
            table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
            //若HashMap中元素的个数超过极限了,则容量扩大两倍
            if (size++ >= threshold)
                resize(2 * table.length);
        }

存储步骤:

// Callbacks to allow LinkedHashMap post-actions
    // 访问元素之后
    void afterNodeAccess(Node<K,V> p) { }
    // 插入节点之后
    void afterNodeInsertion(boolean evict) { }
    // 删除节点之后
    void afterNodeRemoval(Node<K,V> p) { }

HashMap 和 HashTable 的区别

HashTable 和 HashMap 都实现了 Map 接口,他们的主要区别在于线程安全、速度。

HashSet

参考资料

数据结构之红黑树

LinkedHashSet

彻头彻尾理解 LinkedHashMap

LinkedList 的详细介绍

广州芦苇科技 APP 开发团队

芦苇科技-广州专业互联网软件服务公司

抓住每一处细节 ,创造每一个美好

关注我们的公众号,了解更多

想和我们一起奋斗吗?lagou搜索“ 芦苇科技 ”或者投放简历到 lanwuf@talkmoney.cn 加入我们吧