集合相关

Collection

  1. List

  2. Set

  3. Queue

ArrayList

顺序表，支持随机访问。

内部结构

数组Object[] elementData

扩容

默认容量是10。

当数组元素个数超过数组长度时，将数组容量扩大为之前的1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1);//扩大
elementData = Arrays.copyOf(elementData, newCapacity);//复制

add

1. 判断是否要扩容
2. elementData[size++] = e;//存入对象

remove

1. 将待删除的元素后的元素向前移动1位（通过复制来实现）
2. elementData[--size]=null;

Vector

与ArrayList相似，在操作数组的方法上使用synchronized关键字修饰。

LinkedList

内部结构

双向链表实现，维护头结点first和尾结点last

class Node {
    E item;
    Node next;
    Node prev;
}

HashMap

内部结构

哈希数组+链表+红黑树。

通过拉链法解决哈希冲突。其他方法还有开放定址法等。

Node<K, V>[] table;//哈希数组

class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    // 重写了equals&hashCode方法
    final int hashCode(){return Objects.hashCode(key)^Objects.hashCode(value);}//键和值的哈希值异或运算
    equals//判断两个对象的键的哈希码和值的哈希码是否相等
}

hash算法

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//键哈希值的高16位和低16位进行异或运算，使高位参与进来，减少冲突。
    }

扩容

默认容量是16；

几个重要参数

  1. int threshold，threshold = length * loadFactor

  2. final float loadFactor 默认是0.75

  3. size

当size > threshold的时候，进行resize()操作。

  1. 设置新的容量，newCap = oldCap << 1扩大两倍

  2. 创建新数组，将旧数组每个index上的元素转移到新数组中

    1. index上只有一个节点newTab[e.hash & (newCap-1)] = e

    2. index上是红黑树，split

    3. index上是链表，将链表根据e.hash & oldCap是否等于0分成两个链表

      1. 等于0，则是loHead，将其插入到新数组的原位置index上

      2. 不等于0，则 hiHead，并将hiHead插到新数组的index+oldCap的位置上

put操作

逻辑：

  1. 判断哈希数组是否初始化

  2. 判断元素对应数组下标是否为空

    1. 是，直接插入

    2. 否

      1. 若第一个元素是待插入元素，返回当前第一个元素

      2. 若第一个元素是树节点，返回插入后的元素

      3. 若第一个元素是链表，遍历链表上的元素

        1. 若链表上没有该插入元素，将其插入到链表尾部，并判断是否要树化

        2. 若链表上有插入元素，则返回之

      4. 如果返回的元素不为空，则更新它的value值

  3. 判断是否要扩容

优化

结构优化

当链表元素过长时，大于8个结点时，将其转化为红黑树

运算优化

容量始终是2的整数次幂的好处

  1. 计算数组对应下标时，通过位运算替代了模运算，index = e.hash & (capacity-1)

  2. 计算扩容后的数组下标时, newIndex = oldIndex + oldCap，节省了重新计算哈希的时间。

ConcurrentHashMap

内部结构

如何保证线程安全

LinkedHashMap

内部结构

继承了HashMap

  1. 双向链表：维护插入顺序或者LRU顺序

  2. 哈希数组

特别方法

afterNodeAccess节点被访问时调用，将结点移动尾部

afterNodeInsertion插入节点时调用，维护链表，可能会删除最旧的结点

PreviousJava基础NextSpring框架

Last updated

Was this helpful?