Java集合

发表于 | 分类于 | | 浏览 次
字数统计: 494 字 | 阅读时长 ≈ 2 分钟

Java 集合类简介

Java 集合大致分为：Set 、 List 、 Queue 、 Map s四种体系

- Set 代表无无序、不可重复的集合
- List 代表有序、可重复的集合
- Map 代表具有映射关系的集合
- Queue Java 5 新增 代表队列集合的实现

  1. Java 集合与数组的区别

  2. Java 集合类之间的继承关系

  3. Collection 接口

ArrayList

  • 实现方式：数组
    • 优点：
      • 节约空间
      • 访问性能高（通过下标直接访问）
    • 缺点：
      • 数组容量限制，超出限制增加50%容量
      • 按下标remove 或者 添加元素时性能变低

  • 自动扩容机制

    public boolean add(E e) {
ensureCapacityInternal(size + 1);  // Increments modCount! 自动扩容
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++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩展为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩为1.5倍还不满足需求，直接扩为需求值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

另外， ArraryList 的 set 和 get 方法都有对 index进行检查 rangeCheck(int index)

此外，ArrayrList 的 remove 方法 使用的是 System.arraycopy()方法，完成复制后 下标减一 系统 GC

LinkedList

  • 实现方式: 双链表

    • 优点：容量无限制
    • 缺点：查表时需要指针从头/尾移动 性能较低

  • set 和 get 方法 都是使用 node(int index) 方法 该函数会以O(n/2)的性能去获取一个节点

    Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {  // 判断index是在链表的前半部还是后半部，决定从头还是从尾移指针
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

HashMap

hash值的计算：

char val[] = value;
for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
}
—— 结束 ——