JAVA集合框架中的常用集合及其特点和实现原理简介

发布时间：2021-08-30 09:51:58 作者：chen
来源：亿速云阅读：231

JAVA集合框架中的常用集合及其特点和实现原理简介

引言

Java集合框架是Java编程语言中非常重要的一部分，它提供了一套用于存储和操作数据的接口和类。集合框架的设计目标是提供一种统一的、高效的方式来处理数据集合，使得开发者能够更加方便地进行数据操作。本文将详细介绍Java集合框架中的常用集合类，包括它们的特点、实现原理以及使用场景。

集合框架概述

集合框架的层次结构

Java集合框架主要由以下几个部分组成：

接口：定义了集合的基本操作，如Collection、List、Set、Map等。
实现类：提供了接口的具体实现，如ArrayList、LinkedList、HashSet、HashMap等。
算法：提供了一些通用的算法，如排序、搜索等。

集合框架的核心接口

Java集合框架的核心接口包括：

Collection：是所有集合类的根接口，定义了集合的基本操作，如添加、删除、遍历等。
List：是一个有序的集合，允许重复元素。
Set：是一个不允许重复元素的集合。
Map：是一个键值对的集合，键不允许重复。

常用集合类

List接口及其实现类

ArrayList

ArrayList是List接口的一个实现类，它基于动态数组实现。ArrayList的特点是：

动态扩容：当元素数量超过当前容量时，ArrayList会自动扩容。
随机访问：由于基于数组实现，ArrayList支持通过索引快速访问元素。
非线程安全：ArrayList不是线程安全的，如果在多线程环境下使用，需要手动同步。

实现原理：

ArrayList内部维护了一个Object类型的数组elementData，用于存储元素。当添加元素时，如果当前数组容量不足，ArrayList会创建一个新的更大的数组，并将原数组中的元素复制到新数组中。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final int DEFAULT_CAPACITY = 10;
    private transient Object[] elementData;
    private int size;

    public ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保容量足够
        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++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  // 扩容1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

LinkedList

LinkedList是List接口的另一个实现类，它基于双向链表实现。LinkedList的特点是：

插入和删除效率高：由于基于链表实现，LinkedList在插入和删除元素时效率较高。
随机访问效率低：由于需要遍历链表，LinkedList在随机访问元素时效率较低。
非线程安全：LinkedList也不是线程安全的。

实现原理：

LinkedList内部维护了一个双向链表，每个节点包含前驱节点、后继节点和当前元素。当添加元素时，LinkedList会在链表尾部插入新节点。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    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;
        }
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
}

Vector

Vector是List接口的一个早期实现类，它基于动态数组实现，并且是线程安全的。Vector的特点是：

线程安全：Vector的所有方法都是同步的，因此可以在多线程环境下安全使用。
动态扩容：与ArrayList类似，Vector也会在容量不足时自动扩容。
性能较低：由于同步操作的开销，Vector的性能通常低于ArrayList。

实现原理：

Vector的实现与ArrayList类似，内部也维护了一个Object类型的数组elementData。不同之处在于，Vector的所有方法都使用了synchronized关键字进行同步。

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    protected Object[] elementData;
    protected int elementCount;
    protected int capacityIncrement;

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

    private void ensureCapacityHelper(int minCapacity) {
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

Set接口及其实现类

HashSet

HashSet是Set接口的一个实现类，它基于哈希表实现。HashSet的特点是：

不允许重复元素：HashSet中的元素是唯一的，不允许重复。
无序：HashSet中的元素是无序的，不保证元素的插入顺序。
非线程安全：HashSet不是线程安全的。

实现原理：

HashSet内部维护了一个HashMap实例，元素的存储和查找都是通过HashMap实现的。HashSet的元素作为HashMap的键，而值则是一个固定的PRESENT对象。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

TreeSet

TreeSet是Set接口的另一个实现类，它基于红黑树实现。TreeSet的特点是：

有序：TreeSet中的元素是有序的，默认按照自然顺序排序，也可以通过Comparator自定义排序规则。
不允许重复元素：TreeSet中的元素是唯一的，不允许重复。
非线程安全：TreeSet不是线程安全的。

实现原理：

TreeSet内部维护了一个TreeMap实例，元素的存储和查找都是通过TreeMap实现的。TreeSet的元素作为TreeMap的键，而值则是一个固定的PRESENT对象。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
}

LinkedHashSet

LinkedHashSet是HashSet的一个子类，它基于哈希表和链表实现。LinkedHashSet的特点是：

有序：LinkedHashSet中的元素是有序的，按照插入顺序排列。
不允许重复元素：LinkedHashSet中的元素是唯一的，不允许重复。
非线程安全：LinkedHashSet不是线程安全的。

实现原理：

LinkedHashSet内部维护了一个LinkedHashMap实例，元素的存储和查找都是通过LinkedHashMap实现的。LinkedHashSet的元素作为LinkedHashMap的键，而值则是一个固定的PRESENT对象。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    public LinkedHashSet() {
        super(16, .75f, true);
    }
}

Map接口及其实现类

HashMap

HashMap是Map接口的一个实现类，它基于哈希表实现。HashMap的特点是：

键值对存储：HashMap存储的是键值对，键不允许重复。
无序：HashMap中的键值对是无序的，不保证插入顺序。
非线程安全：HashMap不是线程安全的。

实现原理：

HashMap内部维护了一个Node数组table，每个Node包含键、值和指向下一个节点的指针。当插入键值对时，HashMap会根据键的哈希值计算出数组索引，并将键值对存储在对应的位置。如果发生哈希冲突，HashMap会使用链表或红黑树来解决冲突。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    transient Node<K,V>[] table;
    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;
        }
    }

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
}

TreeMap

TreeMap是Map接口的另一个实现类，它基于红黑树实现。TreeMap的特点是：

有序：TreeMap中的键值对是有序的，默认按照键的自然顺序排序，也可以通过Comparator自定义排序规则。
键不允许重复：TreeMap中的键是唯一的，不允许重复。
非线程安全：TreeMap不是线程安全的。

实现原理：

TreeMap内部维护了一个红黑树，每个节点包含键、值和指向左右子节点的指针。当插入键值对时，TreeMap会根据键的顺序将键值对插入到红黑树中，并保持树的平衡。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
    private final Comparator<? super K> comparator;
    private transient Entry<K,V> root;

    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;

        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }

    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
}

LinkedHashMap

LinkedHashMap是HashMap的一个子类，它基于哈希表和链表实现。LinkedHashMap的特点是：

有序：LinkedHashMap中的键值对是有序的，按照插入顺序或访问顺序排列。
键不允许重复：LinkedHashMap中的键是唯一的，不允许重复。
非线程安全：LinkedHashMap不是线程安全的。

实现原理：

LinkedHashMap内部维护了一个双向链表，用于保持键值对的插入顺序或访问顺序。当插入键值对时，LinkedHashMap会将键值对插入到链表的尾部。当访问键值对时，LinkedHashMap会将访问的键值对移动到链表的尾部（如果设置了访问顺序）。

”`java public class LinkedHashMap extends HashMap implements Map { static class Entry extends HashMap.Node { Entry before, after; Entry(int

JAVA集合框架中的常用集合及其特点和实现原理简介

JAVA集合框架中的常用集合及其特点和实现原理简介

目录

引言

集合框架概述

集合框架的层次结构

集合框架的核心接口

常用集合类

List接口及其实现类

ArrayList

LinkedList

Vector

Set接口及其实现类

HashSet

TreeSet

LinkedHashSet

Map接口及其实现类

HashMap

TreeMap

LinkedHashMap

相关阅读