Java学习笔记（3）

常用集合类以及实现原理。

1、ArrayList

ArrayList是我开发以来使用次数的最多的一个集合类了，它的内部其实就是一个数组，当我们往容器中添加元素的时候，首先检查该数组的大小是否足以加入新的元素，如果旧数组的大小不足的时候，将重新创建一个是原数组大小1.5倍的新数组（oldSize + (oldSize >> 1)），然后将就数组的数据复制到新数组中；见代码：

        ...
// overflow-conscious code

        if 
        (minCapacity - 
        elementData
        .
        length 
        > 
        0
        )

            grow(minCapacity);
...
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);
}

    

当我们移除容器中的某一位元素的时候，如果该元素不是数组中的最后一位，那么再使用System.arrayCopy()方法将该元素往后的元素copy至被移除元素的索引，然后将容器的最后一个元素索引的元素置为null。见代码：

        private void 
        fastRemove(
        int 
        index) {

            
        modCount
        ++;

            
        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

        }
    

显而易见的，数组的优势就是元素的内存位置是相连的，所以在查询元素的时候直接以索引为止查询，十分高效，而缺点也很明显，在增加和删除元素的时候可能会导致数组元素位置变化.

2、LinkList

LinkList是以链表的形式来存放元素的容器，同样是List接口的子类，具备相同的增删改查的方法。LinkList的实现方式是内部存放者开始与结束的节点，每个节点包含了该节点存放的元素以及前一个节点以及后一个节点的地址，这样容器中的哥哥元素在内存地址上不一定是相连的，但是又保存着联系。每次网容器末尾添加一个元素时，只需要修改原最末尾的节点信息以及新增一个新的节点信息即可，不会改变原容器的元素位置。

容器末尾添加元素，见代码：

        /**

         * Links e as last element.

         */

        void 
        linkLast(
        E 
        e) {

            
        final 
        Node<
        E
        > l = 
        last
        ;

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

            
        last 
        = newNode;

            
        if 
        (l == 
        null
        )

                
        first 
        = newNode;

            
        else

                
        l.
        next 
        = newNode;

            
        size
        ++;

            
        modCount
        ++;

        }
    

容器起始位置去除元素，见代码

        /**

         * Unlinks non-null first node f.

         */

        private 
        E 
        unlinkFirst(Node<
        E
        > f) {

            
        // assert f == first && f != null;

            
        final 
        E 
        element = f.
        item
        ;

            
        final 
        Node<
        E
        > next = f.
        next
        ;

            f.
        item 
        = 
        null
        ;

            f.
        next 
        = 
        null
        ; 
        // help GC

            
        first 
        = next;

            
        if 
        (next == 
        null
        )

                
        last 
        = 
        null
        ;

            
        else

                
        next.
        prev 
        = 
        null
        ;

            
        size
        --;

            
        modCount
        ++;

            
        return 
        element;

        }
    

所以LinkList的优点在于首位末尾的增加以及删除元素的时候，该并不会改变容器的其他元素位置，但是和ArrayList相比起来，其查找元素的能力就差了很多：

        /**

         * Returns the (non-null) Node at the specified element index.

         */

        Node<
        E
        > node(
        int 
        index) {

            
        // assert isElementIndex(index);

        
            

        
            
        if 
        (index < (
        size 
        >> 
        1
        )) {

                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;

            }

        }
    

这是个根据索引查找节点信息的方法，若索引在左，从起始节点找起，若索引在右，从末尾节点找起。在元素个数多的情况下，查找元素的效率不是很理想。

3、HashMap与HashTable

这两个容器都是用于储存键值对的，区别的地方有：

两者因为历史原因，HashTable继承于Dictionary，HashMap继承于AbstractMap,两者都实现了Map接口；

HashTable的键值不能有null，HashMap的键值可以为null；HashMap是线程不安全的，HashTable是线程安全的，效率上来说就比HashMap低了，如果想要使用线程安全的HashMap，可以使用Collections这个类去封装一下原Map；

对于HashMap内部实现网上有很多大神已经解析过了，这里我就只总结一下自己对它的认识吧。

当我们put(K,V)的时候，首先根据Key的hashCode去获取一个索引index，根据这个index去获取Entry的存放位置，该Entry存放了hash值，K，V对象还有一个Entry类型的next对象，若Entry为空，则新建一个包含hash值，K，V对象的Entry；拿到这个Entry之后，使用equals()对比参数K值和该Entry存放的K值，如果结果为true，则替换oldValue并返回这个oldValue，如果，对比结果为false，那么使用单链表的形式存放一个新的Entry。所以在使用HashMap的时候我们尽量使用不变的key值，即那些覆写了hashCode（）方法的对象，例如String和Integer这样的封装类。

HashMap中有两个参数对性能产生影响，一个是容量，一个是负载因子，一个HashMap的实际容量小于等于最大容量X负载因子，当超过这个值的时候，HashMap将扩容至原来的两倍，并且原来的数据将一个个的存放至新的内存位置中，这个过程就是resize（），使用HashMap时，赋予适当的初始容量有助于减少resize的次数，负载因子的初始值是0.75，负载因子越小，HashMap的实际容量与最大容量相差越差，浪费的空间就越多，内存的开销就相对加大，负载因子越大，HashMap的查询开销就会加大（我是这么理解的：hashmap中有一个数组，数组中每个元素都是一张链表的头元素，根据hash算法我们可以容易的找到这张链表的数组索引，然后再使用链表式的查询去查询Value值，相同个数的键值对，谁拆分的子链表越多，查询的速度越快，若果数组的长度只有1，那么这个map的查询和LinkList的查询也没有什么区别了，HashMap应该是有序与无序的结合，类似ArrayList和LinkList的结合），因此负载因子是时间与空间上的折中选择。

个人理解，如果不对谢谢指出。

原文：http://linwg.blog.51cto.com/9120692/1834808