欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java 集合(一)

程序员文章站 2024-03-15 09:21:53
...

集合类介绍

  • ArrayList(非线程安全)

    • ArrayList底层采用数组存放数据

    • 创建时可以指定初始容量的大小,若不指定则默认是10.

    • ArrayList扩容是1.5倍的增长

    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //将数组内容拷贝到新创建的数组中,并返回新创建数组的引用
    elementData = Arrays.copyOf(elementData, newCapacity);
    • arrayList不是线程安全的容器

    • 当数组元素已经达到数组容量时才会发生扩容

  • Vector(线程安全)

    • Vector与ArrayList实现基本相同,当时Vector是线程安全的,每个操作方法中加了synchronized关键字,属于线程安全的容器

    • 创建Vector时可以指定初始容量,也可以指定发生扩容时扩容的大小。若没指定初始容量大小默认是10;若没有指定扩容的大小,默认是两倍增长,否则

    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                             capacityIncrement : oldCapacity);
  • LinkedList(非线程安全)

    • LinkedList底层实现是通过链表,每个元素是一个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;
            }
        }
    • 定义两个变量first、last分别指向链表的头结点和尾结点

    • 实现了Queue 接口

      1. offer(E e) 操作调用add方法,将元素插入队列的尾部

        Java 集合(一)

        添加元素e之后,last会紧接着指向新添加的元素e

        Java 集合(一)

      2. poll操作删除队列头元素,删除的是first结点

      3. element操作返回队列头结点,即first结点,如果first==null 抛出异常

      4. peek操作返回队列头结点,即first结点,如果first==null 则返回null

    • 实现了Stack功能

      1. push添加元素,注意是在链表的头结点处插入元素

        Java 集合(一)

      2. pop 操作是删除链表的头结点

      3. peek 操作返回链表的头结点

  • HashMap(非线程安全)

    • HashMap底层由一个EntrySet数组构成,每个EntrySet都是一个链表
        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;
            }
             ……
        }

    Java 集合(一)

    • loadFactor,加载因子,默认值是0.75。当map中的元素个数size>=table.length*loadFactor时,hashMap 会进行扩容。如果loadFactor过小,则空间浪费比较严重;若loadFactor过大,则hashmap冲突的概率会加大,造成一些EntrySet链表过长。

    • 创建hashMap时可以指定初始容量和加载因子,默认初始容量为16,加载因子为0.75

    • 计算元素o 在table数组中的下标,其中h是根据o.key计算的hash值,length是指数组的长度

      static int indexFor(int h, int length) {
            return h & (length-1);
        }
    • hashMap中的key和value都可以为null,当key==null时,该元素会放在table下标为0的位置上。
    if (key == null)
        return putForNullKey(value);
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                //如果map中原来已经存在key值为null的元素,则更新value值
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            // hash值为0,key=null  value=value  在table中位置index=0
            addEntry(0, null, value, 0);
            return null;
    }
    • map中添加新元素时,是将元素添加在链表头。
        void addEntry(int hash, K key, V value, int bucketIndex) {
            //threshold = table.length * loadFactor  判断是否需要扩容
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
            createEntry(hash, key, value, bucketIndex);
        }
        //创建一个新的结点,插入链表头。即创建新元素时是插入链表头的。
        void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            //table[bucketIndex]表示的是链表头,链表头指向了新建的结点,同时新节点的next指针指向          了原来的链表头结点。
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
        }   
    • map扩容是原来table长度的2倍。扩容时,需要遍历原来的map,将每个元素重新计算hash值和在新table的中位置,再放入新的table中。
    void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    //计算元素在新table中的位置
                    int i = indexFor(e.hash, newCapacity);
                    //newTable[i]是其中一个链表的链表头
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }

集合类继承关系图 和常用API

Java 集合(一)

常用的API:

ArrayList:

//List尾部添加元素
boolean add(E e);
//在index位置添加元素
public void add(int index,E element);
//移除元素o
boolean remove(Object o);
//移除下标index的元素
public E remove(int index);
//清空列表
public void clear();
//添加集合中的全部元素
public boolean addAll(Collection<? extends E> c);
//返回list的遍历
public Iterator<E> iterator();
//是否包含元素
public boolean contains(Object o);
//将下标为index元素替换
public E set(int index,E element)

Queue:

//添加元素
boolean add(E e);
//获取并移除队列头,此队列为空时将抛出一个异常。
E remove();
//获取并移除此队列的头,如果此队列为空,则返回 null。
E poll();
//获取,但是不移除此队列的头。此方法与 peek 唯一的不同在于:此队列为空时将抛出一个异常。
E element();
//获取但不移除此队列的头;如果此队列为空,则返回 null。
E peek();

Set:

//添加元素
boolean add(E e);
//移除元素
boolean remove(Object o);
//添加所有集合元素
boolean addAll(Collection<? extends E> c);
//清空集合
void clear();
//返回set的迭代器
Iterator<E> iterator();

Stack: 继承自vector,是线程安全的

//把项压入堆栈顶部。
public E push(E item);
//移除栈顶元素
public E pop();
//返回栈顶元素,但是不删除
public E peek();
//测试栈是否为空
public boolean empty();
//返回元素在栈中的位置,以1为基数,-1表示不存在
public int search(Object o);

Map集合继承关系图:

Java 集合(一)