Arraylist

底层数据结构

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

默认构造函数

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

简单实现增删改查方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 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;
}

扩容核心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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保证线成安全,扩容自定义
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 在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

    底层数据结构

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 被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;
    }
    }

    简单实现增删改查方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    //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

    底层数据结构

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

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

    1

    HashSet

    底层数据结构

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

    简单实现增删改查方法

    1