美文网首页
ArrayList、LinkedList、HashMap区别

ArrayList、LinkedList、HashMap区别

作者: 泽林呗 | 来源:发表于2019-03-15 17:40 被阅读0次

    首先问的是ArrayList和LinkedList的区别。

    先看ArrayList的相关源码:

    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData;
    

    可以看出ArrayList底层是实现了一个Object数组,并且初始容量为10

    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            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);
        }
    

    可以看出ArrayList动态扩容是原本的1.5倍,而且扩容是把原本的数据复制到新的数组,这样很耗费时间,所以一般在建arraylist的时候,可以把数据长度定义为预想的1.5倍,这样就可以免去扩容导致的复制问题

    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++;
        }
    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;
        }
    

    在看ArrayList的插入和删除,都需要移动后面的元素,比较耗时

    再看LinkedList的代码

    public boolean add(E e) {
            linkLast(e);
            return true;
        }
    public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
     public boolean remove(Object o) {
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
    public int indexOf(Object o) {
            int index = 0;
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }
    

    可以看到LinkedList的插入和删除其实也是需要通过for循环查找到具体位置的,所以并不一定比ArrayList的删除插入快。

    再看HashMap的源码

    这题答得比较烂,其实是了解的,我们先来看源码

    DEFAULT_INITIAL_CAPACITY =16 默认容量为
    MAXIMUM_CAPACITY =1 << 30 最大容量为
    DEFAULT_LOAD_FACTOR = 0.75f 默认负载因子
    TREEIFY_THRESHOLD=8 链表转换红黑树的阀值
    UNTREEIFY_THRESHOLD=6 红黑树转换链表的阀值
    MIN_TREEIFY_CAPACITY=64 桶中bin最小hash容量,如果大于这个值会进行
    

    总结:

    1. 一个是数组实现,一个是链表实现。
    2. ArrayList可以快速查询,链表需要遍历。ArrayList插入删除需要移动元素,链表只需要改变节点指向就行
    3. ArrayList内存不足时需要动态扩容,每次是原来的1.5倍,LinkedList不需要动态扩容
    4. 这一题回答的时候,动态扩容以及插入删除的效率没有说出来

    相关文章

      网友评论

          本文标题:ArrayList、LinkedList、HashMap区别

          本文链接:https://www.haomeiwen.com/subject/njprmqtx.html