Arraylist

底层数据结构

1	private Object[] elementData; //元素数据底层数组实现

默认构造函数

public MyArrayList(){
        //数组默认大小
        elementData = new Object[10];
        size = 0;
    }

简单实现增删改查方法

// add方法
public void add(T t){
    elementData[size++] = t;
}

// get方法
public Object get(int index){

    if(index > size){
        throw new RuntimeException("数组没有"+index+"这个元素");
    }

    return elementData[index];
}

// remove
public void remove(int moveNum){
    // 获取删除元素后的元素数量
    int lastes = size - moveNum - 1;

    // 核心将删除索引后的元素赋值到前面
    if(moveNum > 0){
        // 删除索引的后一位开始复制数组到原数组的删除索引，复制大小为lastes
        System.arraycopy(elementData,moveNum+1,elementData,moveNum,lastes);
    }
}

// set
public String set(int index,String newValue){
    // 判断索引是否存在
   if(index >= size){
       throw new RuntimeException("索引越界");
   }
   String oldValue = (String)elementData[index];
   elementData[index] = newValue;
   return oldValue;
}

扩容核心

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    // 新容量为老容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
    	// 新容量大于最大值时的处理
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}

与Vector的比较

与Arraylist相似，除了添加了synchronized保证线成安全，扩容自定义

// 在add方法上添加了synchronizated
public synchronized boolean add(E e) {
    ++this.modCount;
    this.add(e, this.elementData, this.elementCount);
    return true;
}
// 扩容 用户可在初始化阶段指定capacityIncrement的大小
// 没指定就扩容原来的2倍
int newCapacity = oldCapacity + (this.capacityIncrement > 0 ? this.capacityIncrement : oldCapacity);

LinkedList

底层数据结构

// 被transient修饰的成员变量不参与序列化过程。
transient int size;
transient LinkedList.Node<E> first; // 记录第一个节点
transient LinkedList.Node<E> last;  // 记录最后一个节点
// 构造函数
private static class Node<E> {
    E item;
    // 底层为双向链表
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;

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

简单实现增删改查方法

//add
public void add(E e){
    Node l = last; // 保存最后节点
    MyLinkedList.Node<E> newNode = new MyLinkedList.Node(l, e, null);
    this.last = newNode;
    if(l == null) // 集合中没有数据
        first = newNode;
    else
        l.next = newNode;
    size++;
}
//set
public E set(int index, E element) {
    // 判断index的合理性
    if(0 >= index || index >= size){
        throw new RuntimeException("不存元素");
    }
    MyLinkedList.Node<E> x = this.get(index); // 获取当前索引节点
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
// get
public MyLinkedList.Node<E> get(int index){
    // 判断index的合理性
    if(0 >= index || index >= size){
        throw new RuntimeException("不存元素");
    }

    MyLinkedList.Node x;
    int i;
    if(index < size >> 1){ //判断索引在前半部分还是后半部分
        x = this.first;
        for(i = 0; i < index; i++){
            x = x.next;
        }
    }else{
        x = this.last;
        for(i = size; i > index; i--){
            x = x.prev;
        }
    }
    return x;
}
// remove
public E remove(int index){
    // 判断index的合理性
    if(0 >= index || index >= size){
        throw new RuntimeException("不存元素");
    }
    // 通过get方法得到该节点
    Node<E> x = get(index);
    // 保存该节点的信息
    E element = x.item;
    MyLinkedList.Node<E> next = x.next;
    MyLinkedList.Node<E> prev = x.prev;

    if(prev == null){
        this.first = next;
    }else{
    	// 让当前节点的前一个节点的下一个节点指向当前节点的下一个节点
    	// 1 <-> 2 <-> 3 删除2
    	// 1 -> 3
        prev.next = next;
        x.prev = null;
    }

    if(next == null){
        this.last = prev;
    }else{
    	// 让当前节点的后一个节点的前一个节点指向当前节点的前一个节点
    	// 1 <-> 2 <-> 3 删除2
    	// 1 <- 3
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    --this.size;
    return element;
}

HashMap

底层数据结构

//底层是 数组和链表和红黑树 结合在一起使用也就是 链表散列。
final int hash;
final K key;
V value;
HashMap.Node<K, V> next;
//HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个

对 putVal 方法添加元素的分析如下：

HashSet

底层数据结构

// 底层数据为hashMap
private transient HashMap<E, Object> map;
// HashSet的所有元素的Value值
private static final Object PRESENT = new Object();

简单实现增删改查方法

读集合源码

Arraylist

与Vector的比较

LinkedList

HashMap

HashSet