蔡妈看看

我们不是代码的搬运工,我们只生产代码

Java 集合框架类

Java 集合框架类

标签(空格分隔): Java


集合

Collection

List

  • ArrayList

    使用数组存储,当数组长度不够时,会构造一个新数组,长度为原数组的2倍,然后将原数组内容copy到新数组。

    • 数组存储关键代码
    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    • 扩容关键代码
    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
    }
    
  • Vector

    vector与ArrayList方法一致,只是在对数组操作的方法上加入了synchronized 从而保证线程安全。

    • 线程安全关键代码
    /**
     * Appends the specified element to the end of this Vector.
     *
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
  • LinkedList

    使用链表存储,默认add方法在最后端存储。

    • LinkedList 数据结构
    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;
        }
    }
    

Set

  • HashSet

    Hash的数据存储在HashMap中的key中,值都是Object对象,从而保证了数据不可重复。

    • HashSet数据结构
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
  • LinkedHashSet

Map

HashMap

采用“数组+链表”形式存储,下标使用了key的hashcode,当hashcide发生碰撞时则在数组后面形成链表,在链表过长时,使用红黑树优化索引

LinkedHashMap

存储原理与HashMap基本一致,LinkedHashMap的Entry加入了next,从而保证了LinkedHashMap 的有序结构

  • next 关键代码
    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        ......
    }

Hashtable

Hashtable 在操作的方法上添加了synchronized 保证线程安全,并且校验了value为空的情况。

关键代码

    /**
     * Maps the specified <code>key</code> to the specified
     * <code>value</code> in this hashtable. Neither the key nor the
     * value can be <code>null</code>. <p>
     *
     * The value can be retrieved by calling the <code>get</code> method
     * with a key that is equal to the original key.
     *
     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or <code>null</code> if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               <code>null</code>
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        ......
    }

TreeMap

TreeMap的key使用红黑树的存储结构,有序结构,当key为引用对象类型时,可以指定排序属性。

Properties

工具类

Arrays

Collections

我们能否让HashMap同步?
HashMap可以通过下面的语句进行同步:
Map m = Collections.synchronizeMap(hashMap);

XMind: ZEN – Trial Version

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注