精华内容
下载资源
问答
  • 主要介绍了Java集合框架源码分析之LinkedHashMap详解,内容包括了linkedhashmap的简介和源码剖析以及关于LinkedHashMap的源码总结,内容丰富,需要的朋友可以参考下。
  • 集合框架示图Collection接口和Map接口 方法API介绍Collection接口:boolean add(E e) :添加元素到集合中boolean addAll(Collection extends E> c) : 将指定 collection 中的所有元素都添加到此 collection 中...

    集合框架示图

    8ef5cb9e2be23841b43d2919ff3a397e.png

    Collection接口和Map接口 方法API介绍

    Collection接口:

    boolean add(E e) :添加元素到集合中

    boolean addAll(Collection extends E> c) : 将指定 collection 中的所有元素都添加到此 collection 中(可选操作)。

    void clear() : 移除此 collection 中的所有元素(可选操作)。

    boolean contains(Object o) :如果此 collection 包含指定的元素,则返回 true。

    boolean containsAll(Collection> c) : 如果此 collection 包含指定 collection 中的所有元素,则返回 true。

    boolean equals(Object o) : 比较此 collection 与指定对象是否相等。

    int hashCode() :返回此 collection 的哈希码值。

    boolean isEmpty() : 如果此 collection 不包含元素,则返回 true。

    Iteratoriterator() :返回在此 collection 的元素上进行迭代的迭代器。

    boolean remove(Object o) : 从此 collection 中移除指定元素的单个实例,如果存在的话(可选操作)。

    boolean removeAll(Collection> c):移除此 collection 中那些也包含在指定 collection 中的所有元素(可选操作)。

    boolean retainAll(Collection> c) :仅保留此 collection 中那些也包含在指定 collection 的元素(可选操作)。

    int size() :返回此 collection 中的元素数。

    Object[] toArray() :返回包含此 collection 中所有元素的数组。

    T[] toArray(T[] a) : 返回包

    default Spliteratorspliterator() :Creates a Spliterator over the elements in this collection. (jdk1.8)

    default Streamstream() :Returns a sequential Stream with this collection as its source. (jdk1.8)

    **Map接口:**

    void clear() :从此映射中移除所有映射关系(可选操作)。

    boolean containsKey(Object key) :如果此映射包含指定键的映射关系,则返回 true。

    boolean containsValue(Object value) :如果此映射将一个或多个键映射到指定值,则返回 true。

    Set> entrySet() :返回此映射中包含的映射关系的 Set 视图。

    boolean equals(Object o) :比较指定的对象与此映射是否相等。

    V get(Object key) :返回指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null。

    int hashCode() :返回此映射的哈希码值。

    boolean isEmpty() :如果此映射未包含键-值映射关系,则返回 true。

    SetkeySet() :返回此映射中包含的键的 Set 视图。

    V put(K key, V value) :将指定的值与此映射中的指定键关联(可选操作)。

    void putAll(Map extends K,? extends V> m) :从指定映射中将所有映射关系复制到此映射中(可选操作)。

    V remove(Object key) :如果存在一个键的映射关系,则将其从此映射中移除(可选操作)。

    int size() :返回此映射中的键-值映射关系数。

    常用集合

    List:ArrayList、LinkedList、Vector

    Map:TreeMap、CurrentHashMap、HashTable

    Set:HashSet、TreeSet

    集合原理详解

    List集合

    ArrayList

    说明:

    ArrayList底层基于对象数组来实现,默认的容量是10,超过该容量后会按照原来的1.5倍再加1来去扩容。

    特点:查询和更加速度快,删除添加慢,有序排列

    构造器:

    //对象数组

    private transient Object[] elementData;

    //默认构造器

    public ArrayList() {

    this(10); //默认容量为10

    }

    //指定容量构造器

    public ArrayList(int initialCapacity) {

    super();

    if (initialCapacity < 0){

    throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);

    }

    this.elementData = new Object[initialCapacity]; //生成一个长度为10的Object类型的数组

    }

    //集合复制构造器

    public ArrayList(Collection extends E> c) {

    elementData = c.toArray(); //返回包含此 collection 中所有元素的数组

    size = elementData.length; //得到该数组的长度

    if (elementData.getClass() != Object[].class){

    //如果elementData数组不是Object[].class类型,则进行复制操作,返回包含相同元素和长度的Object类型的数组

    elementData = Arrays.copyOf(elementData, size, Object[].class);

    }

    }

    add方法:

    //元素添加 size:初始化大小是一开始对象数组的长度,记录当前数组长度

    public boolean add(E e) {

    ensureCapacity(size + 1); //判断是否需要扩容

    elementData[size++] = e; //将元素添加到对象数组最后

    return true;

    }

    //将元素添加到指定位置

    public void add(int index, E element) {

    //如果指定的角标大于或者小于当前对象数组长度,抛出角标越界异常

    if (index > size || index < 0)

    throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    ensureCapacity(size+1); // 判断是否要扩容

    //将index这位置空出,index后面的元素全部后移一位

    System.arraycopy(elementData, index, elementData, index + 1,size - index);

    elementData[index] = element; //将要添加的元素放到指定的数组下标处

    size++;

    }

    //判断当前对象数组是否需要扩容,minCapacity当前对象数组最少应该有的容量值

    public void ensureCapacity(int minCapacity) {

    modCount++;

    int oldCapacity = elementData.length; //原数组的容量

    if (minCapacity > oldCapacity) {

    Object oldData[] = elementData;

    //定义新数组的容量,为原数组容量的1.5倍+1

    int newCapacity = (oldCapacity * 3)/2 + 1;

    //如果扩容后还是不够当前对象数组最少应该有的容量值,那么直接用该容量值作为新数组的容量值

    if (newCapacity < minCapacity)

    newCapacity = minCapacity;

    elementData = Arrays.copyOf(elementData, newCapacity); //复制指定的数组,返回新数组的容量为newCapacity

    }

    }

    get方法:

    //根据index获取元素

    public E get(int index) {

    RangeCheck(index); //检查传入的指定下标是否合法

    return (E) elementData[index]; //返回数组下标为index的数组元素

    }

    //判断指定的index是否越界

    private void RangeCheck(int index) {

    if (index >= size)

    throw new IndexOutOfBoundsException(

    "Index: "+index+", Size: "+size);

    }

    remove方法:

    //移除指定index元素并返回该元素

    public E remove(int index) {

    RangeCheck(index); //检查index是否越界

    modCount++;

    E oldValue = (E) elementData[index]; //获取指定index的数组元素

    int numMoved = size - index - 1; //要移动的元素个数

    if (numMoved > 0)

    //参数1:原数组 参数2:原数组初始角标 参数3:目标数组 参数4:目标数组的其实角标 参数5:复制的个数

    System.arraycopy(elementData, index+1, elementData, index, numMoved); //空出index位置,后面全部元素左移动一位

    elementData[--size] = null; //将引用置空,让gc进行回收

    return oldValue;

    }

    //移除指定的元素

    public boolean remove(Object o) {

    //插入的值为null时,移除数组中的null值元素

    if (o == null) {

    for (int index = 0; index < size; index++)

    if (elementData[index] == null) { //移除首次出现的null

    fastRemove(index);

    return true;

    }

    } else {

    for (int index = 0; index < size; index++)

    if (o.equals(elementData[index])) { //注意:Object的equals方法比较的是内存地址

    fastRemove(index);

    return true;

    }

    }

    return false;

    }

    //移除非null元素

    private void fastRemove(int index) { //移除指定位置的元素,实现方法类似remove(int i)

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

    //空出index位置,后面全部元素左移动一位

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    elementData[--size] = null; //将引用置空,让gc进行回收

    }

    clone方法-浅克隆:

    public Object clone() {

    try {

    ArrayList v = (ArrayList) super.clone(); //调用Object类的clone方法返回一个ArrayList对象

    v.elementData = Arrays.copyOf(elementData, size); //复制目标数组

    v.modCount = 0;

    return v;

    } catch (CloneNotSupportedException e) {

    // this shouldn't happen, since we are Cloneable

    throw new InternalError();

    }

    }

    LinkedList

    说明:

    LinkedList底层基于双向链表实现,可以实现双向链表,双端队列和栈等数据结构

    特点:删除添加快,查询和更加速度慢(不支持高效的随机元素访问),有序排列

    基本数据结构:

    //节点类

    //实现双向链表

    private static class Node {

    E item; //当前节点元素

    Node next; //下一个元素

    Node prev; //上一个元素

    Node(Node prev, E element, Node next) {

    this.item = element;

    this.next = next;

    this.prev = prev;

    }

    }

    //add get remove set方法 均基于该方法

    Node node(int index) {

    //二分法查找

    if (index < (size >> 1)) { //左边

    Node x = first;

    for (int i = 0; i < index; i++)

    x = x.next;

    return x;

    } else { //右边

    Node x = last;

    for (int i = size - 1; i > index; i--)

    x = x.prev;

    return x;

    }

    }

    add方法:

    transient int size = 0; //当前集合大小

    transient Node first; //链头

    transient Node last; //链尾

    //将元素添加到链头

    public void addFirst(E e) {

    linkFirst(e);

    }

    //将元素添加到链尾

    public void addLast(E e) {

    linkLast(e);

    }

    //将元素添加到链头实现

    private void linkFirst(E e) {

    final Node f = first; //获取到链头

    //参数1:上一个节点 参数2:当前节点元素 参数3:下一个节点

    final Node newNode = new Node<>(null, e, f);

    first = newNode; //将包含当前元素的节点设置为链头

    if (f == null)

    //如果这是f为null(表示这是集合是第一次添加元素),则当前节点即使链头也是链尾,前后节点都为null

    last = newNode;

    else

    //将新增的节点赋给链头的prev,即代替当前链头成为新的链头

    f.prev = newNode;

    size++;

    modCount++;

    }

    //将元素添加到链尾实现

    private void linkLast(E e) {

    final Node l = last; //获取到链尾

    final Node newNode = new Node<>(l, e, null); //当前节点

    last = newNode;

    if (l == null)

    //如果这是l为null(表示这是集合是第一次添加元素),则当前节点即使链头也是链尾,前后节点都为null

    first = newNode;

    else

    //将新增的节点赋给链尾的next,即代替当前链尾成为新的链尾

    l.next = newNode;

    size++;

    modCount++;

    }

    add方法 - jdk 1.6:

    //区别:添加成功返回boolean值

    public boolean offerFirst(E e) {

    addFirst(e);

    return true;

    }

    public boolean offerLast(E e) {

    addLast(e);

    return true;

    }

    get方法:

    //根据索引获取 : 二分查找

    public E get(int index) {

    checkElementIndex(index);

    return node(index).item;

    }

    //获取链头

    public E getFirst() {

    final Node f = first;

    if (f == null)

    throw new NoSuchElementException();

    return f.item;

    }

    //获取链尾

    public E getLast() {

    final Node l = last;

    if (l == null)

    throw new NoSuchElementException();

    return l.item;

    }

    get方法 - jdk 1.6:

    区别:如果获取的值为null则返回null不抛异常

    public E peekFirst() {

    final Node f = first;

    return (f == null) ? null : f.item;

    }

    public E peekLast() {

    final Node l = last;

    return (l == null) ? null : l.item;

    }

    remove方法:

    //移除链头节点并返回链头元素

    public E removeFirst() {

    final Node f = first;

    if (f == null)

    throw new NoSuchElementException();

    return unlinkFirst(f);

    }

    //移除链尾节点并返回链尾元素

    public E removeLast() {

    final Node l = last;

    if (l == null)

    throw new NoSuchElementException();

    return unlinkLast(l);

    }

    //移除链头节点并返回链头元素实现

    private E unlinkFirst(Node f) {

    final E element = f.item; //获取到链头中的元素对象

    final Node next = f.next; //获取到链头的next节点

    //置空引入,让gc回收对象

    f.item = null;

    f.next = null;

    //用当前链头的next节点来代替当前链头成为新的链头

    first = next;

    //next为null表示当前几个只有一个元素,即上下节点都为null

    if (next == null)

    last = null;

    else

    next.prev = null;

    size--;

    modCount++;

    return element;

    }

    //移除链尾节点并返回链尾元素实现

    private E unlinkLast(Node l) {

    final E element = l.item;

    final Node prev = l.prev;

    l.item = null;

    l.prev = null; // help GC

    last = prev;

    if (prev == null)

    first = null;

    else

    prev.next = null;

    size--;

    modCount++;

    return element;

    }

    remove方法 - jdk 1.6:

    区别:不抛异常返回null

    public E pollFirst() {

    final Node f = first;

    return (f == null) ? null : unlinkFirst(f);

    }

    public E pollLast() {

    final Node l = last;

    return (l == null) ? null : unlinkLast(l);

    }

    LinkedList实现Stack:

    //jdk 1.6

    public E pollFirst() {

    final Node f = first;

    return (f == null) ? null : unlinkFirst(f);

    }

    //jdk 1.6

    public E pollLast() {

    final Node l = last;

    return (l == null) ? null : unlinkLast(l);

    }

    public void push(E e) {

    addFirst(e);

    }

    public E pop() {

    return removeFirst();

    }

    Vector

    说明:

    Vector是jdk 1.0的容器,和ArrayList一样基于对象数组,初始容量同样默认为10,但不同的是扩容时会增加为原来的2倍,且每个方法都使用synchronize修饰,是一个同步的线程安全的容器

    特点:使用Enumeration遍历元素,有序排列

    Map集合

    HashMap 基于JDK 1.8

    说明:

    HashMap底层基于哈希表来实现(在Java中哈希表通过数组+链表来实现,称链表散列或拉链法)也称作关联数组,不记录元素插入顺序,默认的容量是16,扩容按照2的n次幂递增,但不能超过1<<30

    特点:key-value都能存null值,无序排列

    注意:在JDK 1.8中,HashMap加入了红黑树,当桶中的bin大于TREEIFY_THRESHOLD时将使用(数组+红黑树)来存储,

    少于TREEIFY_THRESHOLD将使用(数组+链表)

    数据结构实现图解(JDK 1.8):

    1f9a15e489156c979c5bd24b6dfa9aeb.png

    基本数据结构:

    //单向链表节点

    static class Node implements Map.Entry {

    final int hash; //当前节点Hash值

    final K key; //当前节点key值

    V value;//当前节点value值

    Node next; //当前节点的next节点

    Node(int hash, K key, V value, Node next) {

    this.hash = hash;

    this.key = key;

    this.value = value;

    this.next = next;

    }

    public final K getKey() { return key; }

    public final V getValue() { return value; }

    public final String toString() { return key + "=" + value; }

    public final V setValue(V newValue) {

    V oldValue = value;

    value = newValue;

    return oldValue;

    }

    public final int hashCode() {

    return Objects.hashCode(key) ^ Objects.hashCode(value);

    }

    public final boolean equals(Object o) {

    if (o == this)

    return true;

    if (o instanceof Map.Entry) {

    Map.Entry,?> e = (Map.Entry,?>)o;

    if (Objects.equals(key, e.getKey()) &&

    Objects.equals(value, e.getValue()))

    return true;

    }

    return false;

    }

    }

    //红黑树节点

    static final class TreeNode extends LinkedHashMap.Entry {

    TreeNode parent; //父亲节点

    TreeNode left;//左子节点

    TreeNode right; //右子节点

    TreeNode prev; //上一个节点

    boolean red;

    TreeNode(int hash, K key, V val, Node next) {

    super(hash, key, val, next);

    }

    /**

    * 返回root节点

    */

    final TreeNode root() {

    for (TreeNode r = this, p;;) {

    if ((p = r.parent) == null) //当一个节点没有父节点时该节点就是root节点

    return r;

    r = p;

    }

    }

    /**

    * Ensures that the given root is the first node of its bin.

    */

    static void moveRootToFront(Node[] tab, TreeNode root) {

    int n;

    if (root != null && tab != null && (n = tab.length) > 0) {

    int index = (n - 1) & root.hash;

    TreeNode first = (TreeNode)tab[index];

    if (root != first) {

    Node rn;

    tab[index] = root;

    TreeNode rp = root.prev;

    if ((rn = root.next) != null)

    ((TreeNode)rn).prev = rp;

    if (rp != null)

    rp.next = rn;

    if (first != null)

    first.prev = root;

    root.next = first;

    root.prev = null;

    }

    assert checkInvariants(root);

    }

    }

    //重置数组长度

    final Node[] resize() {

    //旧数组

    Node[] oldTab = table;

    //获取就数组的长度

    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    //获取初始化阈值

    int oldThr = threshold;

    //初始化新容量和新阈值 往后给新数组用

    int newCap, newThr = 0;

    if (oldCap > 0) {

    //就数组长度大于最大值限制时

    if (oldCap >= MAXIMUM_CAPACITY) {

    threshold = Integer.MAX_VALUE;

    return oldTab;

    }

    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)

    newThr = oldThr << 1; // double threshold

    }

    else if (oldThr > 0) // initial capacity was placed in threshold

    newCap = oldThr;

    else { // zero initial threshold signifies using defaults

    newCap = DEFAULT_INITIAL_CAPACITY;

    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    }

    if (newThr == 0) {

    float ft = (float)newCap * loadFactor;

    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

    (int)ft : Integer.MAX_VALUE);

    }

    threshold = newThr;

    @SuppressWarnings({"rawtypes","unchecked"})

    //创建新的数组

    Node[] newTab = (Node[])new Node[newCap];

    table = newTab;

    //将旧数组元素复制到新数组中

    if (oldTab != null) {

    for (int j = 0; j < oldCap; ++j) {

    Node e;

    if ((e = oldTab[j]) != null) {

    oldTab[j] = null;

    if (e.next == null)

    newTab[e.hash & (newCap - 1)] = e;

    else if (e instanceof TreeNode)

    ((TreeNode)e).split(this, newTab, j, oldCap);

    else { // preserve order

    Node loHead = null, loTail = null;

    Node hiHead = null, hiTail = null;

    Node next;

    do {

    next = e.next;

    if ((e.hash & oldCap) == 0) {

    if (loTail == null)

    loHead = e;

    else

    loTail.next = e;

    loTail = e;

    }

    else {

    if (hiTail == null)

    hiHead = e;

    else

    hiTail.next = e;

    hiTail = e;

    }

    } while ((e = next) != null);

    if (loTail != null) {

    loTail.next = null;

    newTab[j] = loHead;

    }

    if (hiTail != null) {

    hiTail.next = null;

    newTab[j + oldCap] = hiHead;

    }

    }

    }

    }

    }

    return newTab;

    }

    几个重要的属性:

    //默认容量值

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    //最大容量限制值

    static final int MAXIMUM_CAPACITY = 1 << 30;

    //默认加载因子:加载因子提高可以减少空间开销,但同时会增加查找某个条目的时间

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //底层实现,实质存储元素的就是该Node数组

    transient Node[] table;

    //Map.Entry的Set集合

    transient Set> entrySet;

    //元素个数

    transient int size;

    //由链表转换成树的阈值(又叫临界值,是指一个效应能够产生的最低值或最高值)

    //当桶中bin的数量【超过】TREEIFY_THRESHOLD时使用树来代替链表。默认值是8

    static final int TREEIFY_THRESHOLD = 8;

    //由树转换成链表的阈值

    //当执行resize操作时,当桶中bin的数量【少于】UNTREEIFY_THRESHOLD时使用链表来代替树。默认值是6

    static final int UNTREEIFY_THRESHOLD = 6;

    //当桶中的bin被树化时最小的hash表容量

    static final int MIN_TREEIFY_CAPACITY = 64;

    构造器:

    //默认构造器

    public HashMap() {

    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

    }

    //指定容量构造器

    public HashMap(int initialCapacity) {

    this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

    //指定初始化容量和加载因子构造器

    public HashMap(int initialCapacity, float loadFactor) {

    //初始化容量值少于0,抛异常

    if (initialCapacity < 0)

    throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

    //初始化容量大于最大容量限制值,则就依最大容量限制值来作容器为初始化大少

    if (initialCapacity > MAXIMUM_CAPACITY)

    initialCapacity = MAXIMUM_CAPACITY;

    //初始化加载因子小于或者等于0时,又或者不是一个数字时,抛异常

    if (loadFactor <= 0 || Float.isNaN(loadFactor))

    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    this.loadFactor = loadFactor;

    this.threshold = tableSizeFor(initialCapacity);

    }

    //根据一个Map创建一个HashMap 构造器

    public HashMap(Map extends K, ? extends V> m) {

    this.loadFactor = DEFAULT_LOAD_FACTOR;

    putMapEntries(m, false);

    }

    put方法:

    //存入键值对

    public V put(K key, V value) {

    return putVal(hash(key), key, value, false, true);

    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

    Node[] tab;

    Node p;

    int n, i;

    /** 当Node[] table为空时

    > 当前节点数组 tab = table

    > 当前节点数组的长度 n = tab.length

    */

    if ((tab = table) == null || (n = tab.length) == 0)

    n = (tab = resize()).length;

    /** 存储key-value的时候是以 (n - 1) & hash 作为节点数组的角标来存储的

    > hash:当前插入key值的hashCode

    > (n - 1):当前节点数组的最大角标

    */

    //如果添加的这个key在table对应的位置没有值,直接创建一个新节点添加到Node[] table中

    if ((p = tab[i = (n - 1) & hash]) == null)

    tab[i] = newNode(hash, key, value, null);

    /**

    在当前Node[] table中有对应 (n - 1) & hash 作为节点数组的角标值时(值是节点)

    */

    else {

    Node e;

    K k;

    //如果已经存在一样的key,那么就覆盖该key

    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

    e = p;

    else if (p instanceof TreeNode) //如果是节点数

    e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

    else {

    for (int binCount = 0; ; ++binCount) {

    if ((e = p.next) == null) {

    p.next = newNode(hash, key, value, null);

    if (binCount >= TREEIFY_THRESHOLD - 1) //当桶中bin的数量【超过】TREEIFY_THRESHOLD时使用树来代替链表

    treeifyBin(tab, hash);

    break;

    }

    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

    break;

    p = e;

    }

    }

    if (e != null) { // existing mapping for key

    V oldValue = e.value;

    if (!onlyIfAbsent || oldValue == null)

    e.value = value;

    afterNodeAccess(e);

    return oldValue;

    }

    }

    ++modCount;

    if (++size > threshold)

    resize();

    afterNodeInsertion(evict);

    return null;

    }

    get方法:

    //获取对应key的value

    public V get(Object key) {

    Node e;

    return (e = getNode(hash(key), key)) == null ? null : e.value;

    }

    final Node getNode(int hash, Object key) {

    Node[] tab;

    Node first, e;

    int n;

    K k;

    //容器必须有元素才能操作,否则返回null

    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {

    //如果first = tab[(n - 1) & hash]就是要获取的节点,直接返回

    if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))

    return first;

    //如果当前节点有下一个节点的信息

    if ((e = first.next) != null) {

    //如果当前节点是节点树形式存储的节点,调用节点数节点获取方法获取

    if (first instanceof TreeNode)

    return ((TreeNode)first).getTreeNode(hash, key);

    do {

    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

    return e;

    } while ((e = e.next) != null); //链表遍历获取

    }

    }

    return null;

    }

    get方法:

    //移除指定key的value

    public V remove(Object key) {

    Node e;

    return (e = removeNode(hash(key), key, null, false, true)) == null ?

    null : e.value;

    }

    final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {

    Node[] tab;

    Node p;

    int n, index;

    //容器必须有元素才能操作,否则返回null

    //当前数组长度:n = tab.length

    //该key的节点位于数组的位置的角标: index = (n - 1) & hash

    if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {

    Node node = null, e;

    K k;

    V v;

    //如果p = tab[(n - 1) & hash]就是要获取的节点,直接复制给node变量

    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

    node = p;

    //如果p = tab[(n - 1) & hash]不是要找的节点,那么循环查找

    else if ((e = p.next) != null) {

    //如果该节点是节点树的节点,那么调用节点树查找方法获取node节点

    if (p instanceof TreeNode) node = ((TreeNode)p).getTreeNode(hash, key);

    else {

    do {

    //如果遍历到了该key的节点

    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {

    node = e;

    break;

    }

    p = e; //记录主 key对应节点的上一个节点

    } while ((e = e.next) != null);

    }

    }

    //node != null表示经过上面的代码后找到了该key的节点

    if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {

    //如果该节点是节点树的节点,那么调用节点树移除方法移除节点

    if (node instanceof TreeNode)

    ((TreeNode)node).removeTreeNode(this, tab, movable);

    else if (node == p)

    tab[index] = node.next;

    else

    //p是node节点的上一个节点

    p.next = node.next; //将要删除的节点的next赋值给上一个节点的next

    ++modCount;

    --size;

    afterNodeRemoval(node);

    return node;

    }

    }

    return null;

    }

    clear方法:

    public void clear() {

    Node[] tab;

    modCount++;

    if ((tab = table) != null && size > 0) {

    size = 0;

    //循环将引用置空,让gc回收

    for (int i = 0; i < tab.length; ++i)

    tab[i] = null;

    }

    }

    entrySet方法:

    //依Set>形式返回Node[] table数组

    public Set> entrySet() {

    Set> es;

    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;

    }

    final class EntrySet extends AbstractSet> {

    public final int size() { return size; }

    public final void clear() { HashMap.this.clear(); }

    //返回迭代器

    public final Iterator> iterator() {

    return new EntryIterator();

    }

    public final boolean contains(Object o) {

    if (!(o instanceof Map.Entry))

    return false;

    Map.Entry,?> e = (Map.Entry,?>) o;

    Object key = e.getKey();

    Node candidate = getNode(hash(key), key);

    return candidate != null && candidate.equals(e);

    }

    //移除节点

    public final boolean remove(Object o) {

    if (o instanceof Map.Entry) {

    Map.Entry,?> e = (Map.Entry,?>) o;

    Object key = e.getKey();

    Object value = e.getValue();

    return removeNode(hash(key), key, value, true, true) != null;

    }

    return false;

    }

    public final Spliterator> spliterator() {

    return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);

    }

    public final void forEach(Consumer super Map.Entry> action) {

    Node[] tab;

    if (action == null)

    throw new NullPointerException();

    if (size > 0 && (tab = table) != null) {

    int mc = modCount;

    for (int i = 0; i < tab.length; ++i) {

    for (Node e = tab[i]; e != null; e = e.next)

    action.accept(e);

    }

    if (modCount != mc)

    throw new ConcurrentModificationException();

    }

    }

    }

    TreeMap

    说明:

    TreeMap底层基红黑树来实现,查看“键”或“键值对”时,它们会被排序(次序由Comparable或Comparator决定)。TreeMap的特点在于,所得到的结果是经过排序的。

    TreeMap是唯一的带有subMap()方法的Map,它可以返回一个子树

    特点:key不能为null,value可以,自然排序或比较器排序

    红黑树基本介绍:

    示意图:

    cfcd81f2803750e751b838a66fffb2d2.png

    红黑树需要满足的条件:

    每个节点不是红色就是黑色的;

    根节点总是黑色的;

    如果节点是红色的,则它的子节点必须是黑色的(反之不一定);

    从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度);

    在红-黑树中插入的节点都是红色的,这不是偶然的,因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小。

    原因是:插入黑色节点总会改变黑色高度(违背规则4),但是插入红色节点只有一半的机会会违背规则3。

    另外违背规则3比违背规则4要更容易修正

    基本数据结构:

    static final class Entry implements Map.Entry {

    K key; //key值

    V value; //value值

    Entry left; //左子节点

    Entry right; //右子节点

    Entry parent;//父节点

    boolean color = BLACK; //黑色,注意:红黑树很节点必须为黑色

    Entry(K key, V value, Entry parent) {

    this.key = key;

    this.value = value;

    this.parent = parent;

    }

    public K getKey() {

    return key;

    }

    public V getValue() {

    return value;

    }

    public V setValue(V value) {

    V oldValue = this.value;

    this.value = value;

    return oldValue;

    }

    public boolean equals(Object o) {

    if (!(o instanceof Map.Entry))

    return false;

    Map.Entry,?> e = (Map.Entry,?>)o;

    return valEquals(key,e.getKey()) && valEquals(value,e.getValue());

    }

    public int hashCode() {

    int keyHash = (key==null ? 0 : key.hashCode());

    int valueHash = (value==null ? 0 : value.hashCode());

    return keyHash ^ valueHash;

    }

    public String toString() {

    return key + "=" + value;

    }

    }

    //左旋

    private void rotateLeft(Entry p) {

    if (p != null) {

    Entry r = p.right;

    p.right = r.left;

    if (r.left != null)

    r.left.parent = p;

    r.parent = p.parent;

    if (p.parent == null)

    root = r;

    else if (p.parent.left == p)

    p.parent.left = r;

    else

    p.parent.right = r;

    r.left = p;

    p.parent = r;

    }

    }

    //右旋

    private void rotateRight(Entry p) {

    if (p != null) {

    Entry l = p.left;

    p.left = l.right;

    if (l.right != null) l.right.parent = p;

    l.parent = p.parent;

    if (p.parent == null)

    root = l;

    else if (p.parent.right == p)

    p.parent.right = l;

    else p.parent.left = l;

    l.right = p;

    p.parent = l;

    }

    }

    //插入变色

    private void fixAfterInsertion(Entry x) {

    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {

    if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {

    Entry y = rightOf(parentOf(parentOf(x)));

    if (colorOf(y) == RED) {

    setColor(parentOf(x), BLACK);

    setColor(y, BLACK);

    setColor(parentOf(parentOf(x)), RED);

    x = parentOf(parentOf(x));

    } else {

    if (x == rightOf(parentOf(x))) {

    x = parentOf(x);

    rotateLeft(x);

    }

    setColor(parentOf(x), BLACK);

    setColor(parentOf(parentOf(x)), RED);

    rotateRight(parentOf(parentOf(x)));

    }

    } else {

    Entry y = leftOf(parentOf(parentOf(x)));

    if (colorOf(y) == RED) {

    setColor(parentOf(x), BLACK);

    setColor(y, BLACK);

    setColor(parentOf(parentOf(x)), RED);

    x = parentOf(parentOf(x));

    } else {

    if (x == leftOf(parentOf(x))) {

    x = parentOf(x);

    rotateRight(x);

    }

    setColor(parentOf(x), BLACK);

    setColor(parentOf(parentOf(x)), RED);

    rotateLeft(parentOf(parentOf(x)));

    }

    }

    }

    root.color = BLACK;

    }

    //删除变色

    private void fixAfterDeletion(Entry x) {

    while (x != root && colorOf(x) == BLACK) {

    if (x == leftOf(parentOf(x))) {

    Entry sib = rightOf(parentOf(x));

    if (colorOf(sib) == RED) {

    setColor(sib, BLACK);

    setColor(parentOf(x), RED);

    rotateLeft(parentOf(x));

    sib = rightOf(parentOf(x));

    }

    if (colorOf(leftOf(sib)) == BLACK &&

    colorOf(rightOf(sib)) == BLACK) {

    setColor(sib, RED);

    x = parentOf(x);

    } else {

    if (colorOf(rightOf(sib)) == BLACK) {

    setColor(leftOf(sib), BLACK);

    setColor(sib, RED);

    rotateRight(sib);

    sib = rightOf(parentOf(x));

    }

    setColor(sib, colorOf(parentOf(x)));

    setColor(parentOf(x), BLACK);

    setColor(rightOf(sib), BLACK);

    rotateLeft(parentOf(x));

    x = root;

    }

    } else { // symmetric

    Entry sib = leftOf(parentOf(x));

    if (colorOf(sib) == RED) {

    setColor(sib, BLACK);

    setColor(parentOf(x), RED);

    rotateRight(parentOf(x));

    sib = leftOf(parentOf(x));

    }

    if (colorOf(rightOf(sib)) == BLACK &&

    colorOf(leftOf(sib)) == BLACK) {

    setColor(sib, RED);

    x = parentOf(x);

    } else {

    if (colorOf(leftOf(sib)) == BLACK) {

    setColor(rightOf(sib), BLACK);

    setColor(sib, RED);

    rotateLeft(sib);

    sib = leftOf(parentOf(x));

    }

    setColor(sib, colorOf(parentOf(x)));

    setColor(parentOf(x), BLACK);

    setColor(leftOf(sib), BLACK);

    rotateRight(parentOf(x));

    x = root;

    }

    }

    }

    setColor(x, BLACK);

    }

    几个重要的属性:

    //比较器,排序使用

    private final Comparator super K> comparator;

    //根节点

    private transient Entry root;

    //节点数

    private transient int size = 0;

    //修改标记

    private transient int modCount = 0;

    构造器:

    //默认构造器

    public TreeMap() {

    comparator = null;

    }

    //带有比较器的构造器

    public TreeMap(Comparator super K> comparator) {

    this.comparator = comparator;

    }

    //使用一个map集合创建一个TreeMap 构造器

    public TreeMap(Map extends K, ? extends V> m) {

    comparator = null; //无比较器

    putAll(m);

    }

    //使用一个SortedMap集合创建一个TreeMap 构造器

    public TreeMap(SortedMap m) {

    comparator = m.comparator();

    try {

    buildFromSorted(m.size(), m.entrySet().iterator(), null, null);

    } catch (java.io.IOException cannotHappen) {

    } catch (ClassNotFoundException cannotHappen) {

    }

    }

    put方法:

    //比较排序

    final int compare(Object k1, Object k2) {

    return comparator==null ? ((Comparable super K>)k1).compareTo((K)k2) : comparator.compare((K)k1, (K)k2);

    }

    public V put(K key, V value) {

    Entry t = root; //获取根节点

    if (t == null) {

    compare(key, key); // type (and possibly null) check

    //如果root为空,将第一个put如的key-value节点作为根节点

    root = new Entry<>(key, value, null);

    size = 1;

    modCount++;

    return null;

    }

    int cmp;

    Entry parent;

    //获取比较器

    Comparator super K> cpr = comparator;

    if (cpr != null) {

    //循环找位置将节点设入去

    do {

    parent = t;

    cmp = cpr.compare(key, t.key);

    if (cmp < 0) //放左边

    t = t.left;

    else if (cmp > 0) //放右边

    t = t.right;

    else

    return t.setValue(value); //替换

    } while (t != null);

    }

    else {

    if (key == null)

    throw new NullPointerException();

    @SuppressWarnings("unchecked")

    Comparable super K> k = (Comparable super K>) key;

    do {

    parent = t;

    cmp = k.compareTo(t.key);

    if (cmp < 0)

    t = t.left;

    else if (cmp > 0)

    t = t.right;

    else

    return t.setValue(value);

    } while (t != null);

    }

    Entry e = new Entry<>(key, value, parent);

    if (cmp < 0)

    parent.left = e;

    else

    parent.right = e;

    fixAfterInsertion(e);

    size++;

    modCount++;

    return null;

    }

    get方法:

    //获取到指定key的节点

    public V get(Object key) {

    Entry p = getEntry(key);

    return (p==null ? null : p.value);

    }

    //获取到指定key的节点实现

    final Entry getEntry(Object key) {

    //有比较器的时候

    if (comparator != null)

    return getEntryUsingComparator(key);

    //key为null的时候抛异常

    if (key == null)

    throw new NullPointerException();

    //

    @SuppressWarnings("unchecked")

    Comparable super K> k = (Comparable super K>) key; //向上转型

    Entry p = root;

    while (p != null) {

    int cmp = k.compareTo(p.key);

    if (cmp < 0)

    p = p.left;

    else if (cmp > 0)

    p = p.right; //k等于p.key,即找到该节点

    else

    return p;

    }

    return null;

    }

    final Entry getEntryUsingComparator(Object key) {

    @SuppressWarnings("unchecked")

    K k = (K) key;

    Comparator super K> cpr = comparator;

    if (cpr != null) {

    Entry p = root;

    while (p != null) {

    int cmp = cpr.compare(k, p.key);

    if (cmp < 0)

    p = p.left;

    else if (cmp > 0)

    p = p.right;

    else

    return p; //k等于p.key,即找到该节点

    }

    }

    return null;

    }

    remove方法:

    //移除指定的节点对象

    public boolean remove(Object o) {

    //当o不是Map.Entry的实例就返回false

    if (!(o instanceof Map.Entry))

    return false;

    //将o转为强转成Map.Entry对象

    Map.Entry,?> entry = (Map.Entry,?>) o;

    //获取该对象的值

    Object value = entry.getValue();

    //根据该对象的key值从红黑树中获取到对应的红黑树节点

    Entry p = getEntry(entry.getKey());

    /*

    对比传进来的这个对象的value,和利用该对象的key在红黑树中获得的节点的value进行对比

    如果相同,证明确实有这个节点,那么就记性删除,否者但会false

    */

    if (p != null && valEquals(p.getValue(), value)) {

    deleteEntry(p);

    return true;

    }

    return false;

    }

    //移除指定key的节点对象,并返回移除了的节点的value值

    public V remove(Object key) {

    //根据key在红黑树总查找到对应的节点

    Entry p = getEntry(key);

    if (p == null)

    return null;

    V oldValue = p.value;

    deleteEntry(p); //删除节点

    return oldValue;

    }

    //获取红黑树节点中指定key的节点

    final Entry getEntry(Object key) {

    //当有自定义比较器的时候

    if (comparator != null)

    return getEntryUsingComparator(key);

    if (key == null)

    throw new NullPointerException();

    @SuppressWarnings("unchecked")

    //将key强转成Comparable实例,这就是为什么TreeMap要么传入比较器,要么实现Comparable的原因

    Comparable super K> k = (Comparable super K>) key;

    //获取红黑树的根节点

    Entry p = root;

    //遍历红黑树来获取当前key的节点

    while (p != null) {

    //从根节点开始查找

    int cmp = k.compareTo(p.key);

    if (cmp < 0)

    p = p.left;

    else if (cmp > 0)

    p = p.right;

    else

    return p;

    }

    return null;

    }

    //删除指定节点实现,注意:是要删除的节点

    private void deleteEntry(Entry p) {

    modCount++;

    size--;

    if (p.left != null && p.right != null) {

    Entry s = successor(p);

    p.key = s.key;

    p.value = s.value;

    p = s;

    }

    // Start fixup at replacement node, if it exists.

    Entry replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {

    // Link replacement to parent

    replacement.parent = p.parent;

    if (p.parent == null)

    root = replacement;

    else if (p == p.parent.left)

    p.parent.left = replacement;

    else

    p.parent.right = replacement;

    // Null out links so they are OK to use by fixAfterDeletion.

    p.left = p.right = p.parent = null;

    // Fix replacement

    if (p.color == BLACK)

    fixAfterDeletion(replacement);

    } else if (p.parent == null) { // return if we are the only node.

    root = null;

    } else { // No children. Use self as phantom replacement and unlink.

    if (p.color == BLACK)

    fixAfterDeletion(p);

    if (p.parent != null) {

    if (p == p.parent.left)

    //如果当前是左节点,利用父节点来移除自己

    p.parent.left = null;

    else if (p == p.parent.right)

    //如果当前是右节点,利用父节点来移除自己

    p.parent.right = null;

    //移除父节点

    p.parent = null;

    }

    }

    }

    HashTable

    说明:

    基于散列(数组+链表)实现,操作方法都被synchronize修饰,所以是线程安全的容器

    特点:key不能为null,value不能为null,使用Enumeration遍历

    和HashMap的基本对比:

    e325e7f7f040c0ffbd4d01247d0bf76c.png

    ConcurrentHashTable

    说明:

    可以高效地支持并发操作,开源框架Spring的底层数据结构就是使用ConcurrentHashMap实现的;

    与同是线程安全的老大哥HashTable相比,它已经更胜一筹,因此它的锁更加细化,而不是像HashTable一样为几乎每个方法都添加了synchronized锁,这样的锁无疑会影响到性能;

    JDK8的版本,与JDK6的版本有很大的差异。实现线程安全的思想也已经完全变了,它摒弃了Segment(锁段)的概念,

    而是启用了一种全新的方式实现,利用CAS算法,它沿用了与它同时期的HashMap版本的思想,底层依然由“数组”+链表+红黑树的方式思想,

    但是为了做到并发,又增加了很多辅助的类,例如TreeBin,Traverser等对象内部类。

    注意:ConcurrentHashMap不允许key或value为null值

    Set集合

    HashSet

    说明:

    基于HashMap实现(散列),所以可以得出结论,值不能为重复,但可以为null,重复会被覆盖

    TreeSet

    说明:

    基于TreeMap实现,元素的顺序取决于元素自身的自然顺序或者在构造时提供的比较器

    注意:TreeMap的key不能为null,所以TreeSet的元素不能为null

    展开全文
  • Java集合框架源码学习-ArrayListjava集合框架体系结构ArrayList源码类变量方法实现初始化方法公共方法总结 java集合框架体系结构 java集合框架顶层接口为:Collection接口,然后List和Set接口实现了Collection接口。...

    java集合框架体系结构

    java集合框架顶层接口为:Collection接口,然后List和Set接口实现了Collection接口。其中,ArrayList和LinkedList具体实现了List接口,HashSet和TreeSet具体实现了Set接口,本文将尽可能仔细分析ArrayList的源代码(基于jdk1.8)。

    ArrayList源码

    类变量

    下面将介绍一些ArrayList的类变量:
    
    
        /**
         *默认容量为10,当不使用任何参数初始化ArrayList时的elementData的默认容量
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * 空的数组实例
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * 默认容量的空数组实例,当不使用参数初始化List时,将elementData数组指向本实例,
         * 再添加第一个元素时在扩充数组
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        /**
         *存储具体数据的数组,容量为初始化时指定容量或默认容量(初始化时为指定容量)
         */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         * 当前ArrayList中的存储的元素数量
         */
        private int size;
        /**
        *elementData数组长度的最大值
        */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    

    由以上代码可知,ArrayList的初始化时默认的容量大小为10,当不使用参数初始化ArrayList时,不会为elementData数组分配空间,只有当添加第一个元素对象是才会对elementData进行扩容。

    方法实现

    初始化方法

    ArrayList一共有3个初始化方法:

    • 无参方法:
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    

    直接将elementData 指向默认容量的空数组,不会对elementData 进行初始化;

    • 参数为一个整数(容量):
        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    

    参数为elementData 数组的·初始化容量,=0时指向空的element实例;<0时会抛出异常;>0时会对elementData 数组进行初始化。

    • 参数为一个集合
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray 可能 (不正确) 不会返回 Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                //调用Arrays.copyOf方法实现Object数组的复制。底层调用的是系统的Native方法
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // 用空数组替代.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }
    

    使用一个集合来对ArrayList进行初始化,首先将集合参数转化为一个Object数组,然后赋给elementData,同时如果两个对象指向同一个地址会造成修改混乱问题,因此需要对elementData重新声明一个新的地址空间,程序调用Arrays.copyOf方法实现Object数组的复制,而Arrays.copyO又调用了一个Native方法 System.arraycopy。

    公共方法

    • size()方法:获得ArrayList中元素的数量
    public int size() {
            return size;
        }
    

    直接返回size参数

    • isEmpty()方法:判断ArrayList是否为空
     public boolean isEmpty() {
            return size == 0;
        }
    

    直接判断size是否为0.

    • contains(Object o) 方法:判断ArrayList是否包含某个元素,参数为Object,因为java中Object类是所有类父类,使用Object类型可以兼容所有的对象。
    public boolean contains(Object o) {
            return indexOf(o) >= 0;
        }
    

    由源码可知,contains方法是通过调用indexOf方法实现的,返回值大于0时,证明包含该对象,下面我们来看indexOf方法。

    • indexOf(Object o) 方法:返回对象在ArrayList中的elementData数组的第一次出现的下标,若对象不存在则返回-1;
        public int indexOf(Object o) {
            if (o == null) {//判断o==null的原因,避免出现指针异常
            //o为空时,判断数组中是否存在空元素
                for (int i = 0; i < size; i++)
                    if (elementData[i]==null)
                        return i;
            } else {
            //数组不为空,则挨个对象比较
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            //不存在,返回空
            return -1;
        }
    

    从源码可知,o不为空时会调用equals()函数进行比较。同时由于要遍历整个数组,indexOf()方法和contains()方法的时间复杂度都为O(n)。
    注意:如果使用自定义对象为重载equals()函数,则Object的equals()函数默认比较的对象地址。

    • lastIndexOf(Object o) 方法:返回对象在ArrayList中的elementData数组最后一次出现的下标,不存在返回-1。
        public int lastIndexOf(Object o) {
           if (o == null) {
               for (int i = size-1; i >= 0; i--)
                   if (elementData[i]==null)
                       return i;
           } else {
               for (int i = size-1; i >= 0; i--)
                   if (o.equals(elementData[i]))
                       return i;
           }
           return -1;
       }
    

    时间复杂度同indexOf方法,为:O(n)。

    • toArray()方法共有两个,第一个:无参方法返回一个新的数组,第二个传入一个数组a,将elementData中元素拷贝进数组a中。
        public Object[] toArray() {
            return Arrays.copyOf(elementData, size);
        }
        public <T> T[] toArray(T[] a) {
            if (a.length < size)//如果a的长度小于size,则新建一个数组返回
                // 创建a类型的新数组,但数组内元素为elementData内的元素
                return (T[]) Arrays.copyOf(elementData, size, a.getClass());
            System.arraycopy(elementData, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }
    

    注意:拷贝时,数组中的对象的相互顺序不会改变。

    • get(int index) 方法·:返回数组中指数为index的对象。
       public E get(int index) {
           rangeCheck(index);
    
           return elementData(index);
       }
    

    其中 rangeCheck(index)方法:检查输入的index是否合法; elementData(index)这是获得 elementData数组中index为的对象。时间复杂度为:O(1);

    • set(int index, E element) 方法:将index位置的对象,替换为element,同时返回被替换的对象
        public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
    

    时间复杂度:O(1)

    • add(E e)方法:向ArrayList中添加一个对象,如果elementData数组没有多余空间时,则会进行扩容
      public boolean add(E e) {
           ensureCapacityInternal(size + 1);  // 判断是否需要扩容
           elementData[size++] = e;
           return true;
       }
       //扩容函数,每次扩容为之前容量的1.5倍或minCapacity;minCapacity为需求的最小容量
      private void grow(int minCapacity) {
           // 旧容量为elementData数组的长度,每次扩容时表示elementData已满
           int oldCapacity = elementData.length;
           //新容量为旧容量的1.5倍
           int newCapacity = oldCapacity + (oldCapacity >> 1);
           //如果小于最小容量,则扩容至最小容量
           if (newCapacity - minCapacity < 0)
               newCapacity = minCapacity;
             //判断新容量是否大于最大容量的限制
           if (newCapacity - MAX_ARRAY_SIZE > 0)
           //大于则将新容量设置为 MAX_ARRAY_SIZE或 Integer.MAX_VALUE
               newCapacity = hugeCapacity(minCapacity);
           //复制新数组
           elementData = Arrays.copyOf(elementData, newCapacity);
       }
      //在指定位置添加元素
       public void add(int index, E element) {
           rangeCheckForAdd(index);
    
           ensureCapacityInternal(size + 1);  // Increments modCount!!
           System.arraycopy(elementData, index, elementData, index + 1,
                            size - index);
           elementData[index] = element;
           size++;
       }
    

    由以上代码可知,使用add()方法扩容时,每次扩容一般扩展为之前容量的1.5倍或之前容量加1(初始容量为1时),时间复杂度:O(n)

    • remove(int index)和remove(Object o)方法:移除ArrayList中的一个元素对象,并返回该元素对象。
        //移除指定位置上的对象
        public E remove(int index) {
            rangeCheck(index);
    
            modCount++;//多线程环境下,判断是否存在并发修改,记录修改得次数
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
        //移除第一个与o相同的对象对象
        public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
            //遍历数组,寻找与o相同的对象
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                    //fastRemove作用将index之后的元素前移一位
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    

    从以上源代码可知,移除元素就相当于将index之后的分别元素前移一位,从而将index位置的元素覆盖掉,因此时间复杂度为:O(n);

    • clear() 方法:清空ArrayList中的全部元素,将elementData数组中的元素赋值为null
        public void clear() {
            modCount++;
    
            // 
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }
    

    时间复杂度:O(n)

    • addAll()方法添加一个集合
       public boolean addAll(Collection<? extends E> c) {
       //转化为Object数组
            Object[] a = c.toArray();
            int numNew = a.length;
            //判断当前elementData数组容量是否充足,若容量不够则进行扩容
            ensureCapacityInternal(size + numNew);  
            //将a数组拷贝进elementData数组中
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            //如果输入数组为空返回false,否则返回true
            return numNew != 0;
        }
        public boolean addAll(int index, Collection<? extends E> c) {
        	//判断index的范围是否符合条件
            rangeCheckForAdd(index);
    		//其余同addAll的单参数方法
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
    
            int numMoved = size - index;
            //进行两次复制,第一次将index之后的数据
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                                 numMoved);
    
            System.arraycopy(a, 0, elementData, index, numNew);
            size += numNew;
            return numNew != 0;
        }
    
    • removeAll(Collection<?> c) 方法:清除与c中元素相同的元素
    	public boolean removeAll(Collection<?> c) {
           	Objects.requireNonNull(c);
           	return batchRemove(c, false);
       }
    

    对elementData中的每个元素依次判断是否存在于c,存在则删除,否则保留,删除采取覆盖方式,第一个保留的元素放在elementData[0],第二个放在elementData[1],以此类推时间复杂度:O(nm)

    • retainAll(Collection<?> c) 方法:保留ArrayList与c中元素相同的元素
        public boolean retainAll(Collection<?> c) {
            Objects.requireNonNull(c);
            return batchRemove(c, true);
        }
    
    

    实现方法同removeAll(Collection<?> c),时间复杂度:O(nm)

    总结

    ArrayList的实现相对而言比较简单,同时通过index读取数据和在结尾添加数据(不考虑扩容)的时间复杂度为O(1),删除元素和得到元素位置等操作的时间复杂度都为O(n)。

    展开全文
  • 1. ArrayList概述:ArrayList是List接口的可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。...

    1. ArrayList概述:

    ArrayList是List接口的可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。

    每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造ArrayList时指定其容量。在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

    注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。

    2. ArrayList的实现:

    对于ArrayList而言,它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。下面我们来分析ArrayList的源代码:

    1) 底层使用数组实现:

    private transient Object[] elementData;

    2) 构造方法:

    ArrayList提供了三种方式的构造器,可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的。

    1 publicArrayList() {2 this(10);3 }4

    5 public ArrayList(intinitialCapacity) {6 super();7 if (initialCapacity < 0)8 throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);9 this.elementData = newObject[initialCapacity];10 }11

    12 public ArrayList(Collection extends E>c) {13 elementData =c.toArray();14 size =elementData.length;15 //c.toArray might (incorrectly) not return Object[] (see 6260652)

    16 if (elementData.getClass() != Object[].class)17 elementData = Arrays.copyOf(elementData, size, Object[].class);18 }

    3) 存储:

    ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection extends E> c)、addAll(int index, Collection extends E> c)这些添加元素的方法。下面我们一一讲解:

    1 //用指定的元素替代此列表中指定位置上的元素,并返回以前位于该位置上的元素。

    2 public E set(intindex, E element) {3 RangeCheck(index);4

    5 E oldValue =(E) elementData[index];6 elementData[index] =element;7 returnoldValue;8 }

    1 //将指定的元素添加到此列表的尾部。

    2 public booleanadd(E e) {3 ensureCapacity(size + 1);4 elementData[size++] =e;5 return true;6 }

    1 //将指定的元素插入此列表中的指定位置。2 //如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。

    3 public void add(intindex, E element) {4 if (index > size || index < 0)5 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);6 //如果数组长度不足,将进行扩容。

    7 ensureCapacity(size+1); //Increments modCount!!8 //将 elementData中从Index位置开始、长度为size-index的元素,9 //拷贝到从下标为index+1位置开始的新的elementData数组中。10 //即将当前位于该位置的元素以及所有后续元素右移一个位置。

    11 System.arraycopy(elementData, index, elementData, index + 1, size -index);12 elementData[index] =element;13 size++;14 }

    1 //按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此列表的尾部。

    2 public boolean addAll(Collection extends E>c) {3 Object[] a =c.toArray();4 int numNew =a.length;5 ensureCapacity(size + numNew); //Increments modCount

    6 System.arraycopy(a, 0, elementData, size, numNew);7 size +=numNew;8 return numNew != 0;9 }

    1 //从指定的位置开始,将指定collection中的所有元素插入到此列表中。

    2 public boolean addAll(int index, Collection extends E>c) {3 if (index > size || index < 0)4 throw newIndexOutOfBoundsException(5 "Index: " + index + ", Size: " +size);6

    7 Object[] a =c.toArray();8 int numNew =a.length;9 ensureCapacity(size + numNew); //Increments modCount

    10

    11 int numMoved = size -index;12 if (numMoved > 0)13 System.arraycopy(elementData, index, elementData, index +numNew, numMoved);14

    15 System.arraycopy(a, 0, elementData, index, numNew);16 size +=numNew;17 return numNew != 0;18 }

    4) 读取:

    1 //返回此列表中指定位置上的元素。

    2 public E get(intindex) {3 RangeCheck(index);4

    5 return(E) elementData[index];6 }

    5) 删除:

    ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下:

    1 //移除此列表中指定位置上的元素。

    2 public E remove(intindex) {3 RangeCheck(index);4

    5 modCount++;6 E oldValue =(E) elementData[index];7

    8 int numMoved = size - index - 1;9 if (numMoved > 0)10 System.arraycopy(elementData, index+1, elementData, index, numMoved);11 elementData[--size] = null; //Let gc do its work

    12

    13 returnoldValue;14 }

    1 //移除此列表中首次出现的指定元素(如果存在)。这是应为ArrayList中允许存放重复的元素。

    2 public booleanremove(Object o) {3 //由于ArrayList中允许存放null,因此下面通过两种情况来分别处理。

    4 if (o == null) {5 for (int index = 0; index < size; index++)6 if (elementData[index] == null) {7 //类似remove(int index),移除列表中指定位置上的元素。

    8 fastRemove(index);9 return true;10 }11 } else{12 for (int index = 0; index < size; index++)13 if(o.equals(elementData[index])) {14 fastRemove(index);15 return true;16 }17 }18 return false;19 }

    注意:从数组中移除元素的操作,也会导致被移除的元素以后的所有元素的向左移动一个位置。

    6) 调整数组容量:

    从上面介绍的向ArrayList中存储元素的代码中,我们看到,每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前,我也可以使用ensureCapacity来手动增加ArrayList实例的容量,以减少递增式再分配的数量。

    1 public void ensureCapacity(intminCapacity) {2 modCount++;3 int oldCapacity =elementData.length;4 if (minCapacity >oldCapacity) {5 Object oldData[] =elementData;6 int newCapacity = (oldCapacity * 3)/2 + 1;7 if (newCapacity

    10 elementData =Arrays.copyOf(elementData, newCapacity);11 }12 }

    从上述代码中可以看出,数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造ArrayList实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

    ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下:

    1 public voidtrimToSize() {2 modCount++;3 int oldCapacity =elementData.length;4 if (size

    7) Fail-Fast机制:

    ArrayList也采用了快速失败的机制,通过记录modCount参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

    展开全文
  • 一:简述List集合代表一个有序集合集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素,可以通过索引来访问指定位置的集合元素。List接口继承于Collection接口,它可以定义一个允许重复的有序集合。...
  • 阅读本节内容需要读者对 HashMap 、HashSet 和 LinkedHashMap 的源码有所了解,因为 ...如果你想多了解下这三个容器类,可以从这里获得:Java集合框架源码解析 LinkedHashSet 的所有源码如下所示 package j...
  • 注:博主java集合框架源码剖析系列的源码全部基于JDK1.8.0版本。本博客将从源码角度带领大家学习关于HashSet的知识。 一HashSet的定义: public class HashSet<E> extends AbstractSet<E> ...
  • 注:博主java集合框架源码剖析系列的源码全部基于JDK1.8.0版本。本博客将从源码角度带领大家学习关于TreeMap的知识。 一TreeMap的定义: public class TreeMap<K,V> extends AbstractMap<K,V>...
  • 集合框架源码分析

    2020-10-07 10:13:46
    1. Java集合总体框架 Java集合中List,Set以及Map等集合体系详解 Java 集合系列01之 总体框架 Java集合工具包在java.util.*下,他们的继承关系如下图所示 Java集合主要可以划分为4个部分:List列表、Set集合、Map...
  • Vector 和 ArrayList 类似,都是基于数组来实现的。但是 Vector 是线程同步(Synchronized)的,所以它也是线程安全的,而...ArrayList 可以参考: Java集合框架源码——ArrayList解析 public class Vector&lt;...
  • 注:博主java集合框架源码剖析系列的源码全部基于JDK1.8.0版本。 在实际项目中LinkedList也是使用频率非常高的一种集合,本博客将从源码角度带领大家学习关于LinkedList的知识。 一LinkedList类的定义: public ...
  • 注:博主java集合框架源码剖析系列的源码全部基于JDK1.8.0版本。 本博客将从源码角度带领大家学习关于ArrayList的知识。 一ArrayList类的定义: public class ArrayList extends AbstractList implements List, ...
  • 导语:我们平时编程使用过很多的JDK工具类,但是学习不能...集合框架简介java的集合框架定义了对集合操作的方法,框架集合代表了对于集合的增删改查定义了一套完整的规范,使得使用具体操作与实现进行解耦。主要理念用
  • 035:Java8十大新特性1 Java8集合框架源码分析课程介绍2 Jdk1.8新特性概念课程介绍3 Jdk1.8新特性中接口默认关键字4 Jdk1.8函数接口基本概念定义5 Jdk1.8新特性Lambda基本的使用6 实际项目中使用Lambda简化代码7 Jdk...
  • Jdk1.6 集合框架源码解析汇总   非并发:  Jdk1.6 Collections Framework源码解析(1)-ArrayList  描述:动态扩容的数组。    Jdk1.6 Collections Framework源码解析(2)-LinkedList  描述:双向链表。...
  • 集合框架介绍  Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:List列表、Set集合、Map映射、迭代器...
  • 前言:之所以打算写java集合框架源码剖析系列博客是因为自己反思了一下阿里内推一面的失败(估计没过,因为写此博客已距阿里巴巴一面一个星期),当时面试完之后感觉自己回答的挺好的,而且据面试官最后说的这几天...
  • 在前面的博文(Java集合框架源码(一)——hashMap)中我们详细讲了HashMap的原理,对于HashSet而言,它是基于HashMap来实现的,底层采用HashMap来保存元素。 一、定义 1 public class HashSet<E> 2 ...
  • HashMap 是Java 集合框架中重要的组成部分,也是平常使用频率很高的一个集合类,典型使用方式如下: Map map=new HashMap(); map.put(1,"Java EE"); map.put(2,"Android"); ...1234 它的类继承层级结构如下。 类...
  • 总体介绍  前面以Java ArrayDeque为例讲解了Stack和Queue,其实还有一种特殊的队列叫做PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值小的(Java的优先队列每次取小元素,C++的...
  • 总体介绍  LinkedList同时实现了List接口和Deque接口,也是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直是个全能。当你需要使用栈或者...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,894
精华内容 1,557
关键字:

集合框架源码