java集合源码_java集合源码分析 - CSDN
精华内容
参与话题
  • Java集合源码剖析】Java集合框架

    万次阅读 多人点赞 2014-06-29 12:48:57
    Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:List列表、Set集合、Map映射、迭代器(Iterator、Enumeration...

    转载轻注明出处:http://blog.csdn.net/ns_code/article/details/35564663


        Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:List列表、Set集合、Map映射、迭代器(Iterator、Enumeration)、工具类(Arrays、Collections)。

        Java集合类的整体框架如下:

     

        从上图中可以看出,集合类主要分为两大类:Collection和Map。

        Collection是List、Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主要又分为两大部分:List和Set。

        List接口通常表示一个列表(数组、队列、链表、栈等),其中的元素可以重复,常用实现类为ArrayList和LinkedList,另外还有不常用的Vector。另外,LinkedList还是实现了Queue接口,因此也可以作为队列使用。

        Set接口通常表示一个集合,其中的元素不允许重复(通过hashcode和equals函数保证),常用实现类有HashSet和TreeSet,HashSet是通过Map中的HashMap实现的,而TreeSet是通过Map中的TreeMap实现的。另外,TreeSet还实现了SortedSet接口,因此是有序的集合(集合中的元素要实现Comparable接口,并覆写Compartor函数才行)。

        我们看到,抽象类AbstractCollection、AbstractList和AbstractSet分别实现了Collection、List和Set接口,这就是在Java集合框架中用的很多的适配器设计模式,用这些抽象类去实现接口,在抽象类中实现接口中的若干或全部方法,这样下面的一些类只需直接继承该抽象类,并实现自己需要的方法即可,而不用实现接口中的全部抽象方法。

        Map是一个映射接口,其中的每个元素都是一个key-value键值对,同样抽象类AbstractMap通过适配器模式实现了Map接口中的大部分函数,TreeMap、HashMap、WeakHashMap等实现类都通过继承AbstractMap来实现,另外,不常用的HashTable直接实现了Map接口,它和Vector都是JDK1.0就引入的集合类。

        Iterator是遍历集合的迭代器(不能遍历Map,只用来遍历Collection),Collection的实现类都实现了iterator()函数,它返回一个Iterator对象,用来遍历集合,ListIterator则专门用来遍历List。而Enumeration则是JDK1.0时引入的,作用与Iterator相同,但它的功能比Iterator要少,它只能再Hashtable、Vector和Stack中使用。

        Arrays和Collections是用来操作数组、集合的两个工具类,例如在ArrayList和Vector中大量调用了Arrays.Copyof()方法,而Collections中有很多静态方法可以返回各集合类的synchronized版本,即线程安全的版本,当然了,如果要用线程安全的结合类,首选Concurrent并发包下的对应的集合类。


    展开全文
  • java集合源码详解

    2019-03-25 22:21:09
    分析的很清楚。 https://blog.csdn.net/yeyazhishang/article/category/8093220
    展开全文
  • Java集合源码学习

    2019-02-26 21:33:37
    Java集合工具包位于java.util包下,包含了很多数据结构。如数组、链表、栈、队列、集合、哈希表等。 Java集合框架大致分为5个部分:List列表、Set集合、Map映射、迭代器(Iterator, Enumeration)、工具类(Arrays, ...

    Java集合工具包位于java.util包下,包含了很多数据结构。如数组、链表、栈、队列、集合、哈希表等。

    Java集合框架大致分为5个部分:List列表、Set集合、Map映射、迭代器(Iterator, Enumeration)、工具类(Arrays, Collections)

    Java集合类的整体框架如下:
    在这里插入图片描述
    集合类可分为Collection和Map两大类。

    Collection又分为:
    1)List(有序可重复):数组、链表、栈、队列。
    实现类常用的有ArrayList, LinkedList, 不常用的有Vector。
    由于LinkedList还实现了Queue接口,因此也可以作为队列使用。

    2)Set(无序不可重复)
    常用实现有HashSet(基于HashMap实现), TreeSet(基于TreeMap实现)
    TreeSet还实现了SortedMap接口,因此是有序的集合.

    抽象类AbstractCollection、AbstractList、AbstractSet分别实现了Collection、List、Set接口,用这些抽象类去实现接口,在抽象类中实现接口中的若干或全部方法,这样在下面的一些类,只需要直接继承该抽象类,并实现自己需要的方法即可,而不用实现接口中的全部抽象方法。

    AbstractMap实现了Map接口的大部分方法,TreeMap, HashMap, WeakHashMap等类都继承自AbstractMap。而HashTable就直接实现了Map接口。

    Iterator是遍历集合的迭代器(不能遍历Map, 只能遍历Collection),Collection的实现类都现实了iterator()方法, 该方法返回一个Iterator对象,用来遍历集合。

    Arrays和Collections是用来操作数组、集合的两个工具类,例如ArrayList和Vector中大量调用了Arrays.copyOf()方法;而Collections中有很多静态方法可以返回各集合类的synchronized版本。

    一。ArrayList

    1. 概述
      ArrayList以数组实现,这样节约空间,但由于数组的长度有限, 超出时会增加50%的容量,用System.arraycopy()复制到新的数组,因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。

    按照数组下标访问元素:get(i), set(i)的性能非常高,这是数组的优势。

    直接在数组末尾加入元素add(e)性能也很高。但如果按下标插入、删除元素,如add(i, e), remove(i), remove(e), 则要用System.arraycopy()来移动部分受影响的元素,性能就变差了,这是数组的基本劣势。

    数组是简单的数据结构,最重要的一点事它的扩容。如下面的代码:
    ArrayList list = new ArrayList();
    list.add(“语文: 99”);
    list.add(“数学: 98”);
    list.add(“英语: 100”);
    list.remove(0);

    在执行这四句是,内存中的数据这么变化的:
    在这里插入图片描述
    2. add方法

    add方法会将元素放到数组的末尾,具体源码如下:
    public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
    }

    其中,ensureCapacityInternal方法是实现自动扩容的方法,其具体实现如下:

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

    也就是说,当增加数据的时候如果ArrayList已经不满足需求时,那么就扩容到原来的1.5倍,之后的操作就是把老的数组copy到新的数组中。例如,数组初始大小是10,在加入第11个元素时,会触发扩容:
    在这里插入图片描述
    3. set和get方法:先做index检查,再赋值

    public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
    

    }

    public E get(int index) {
    rangeCheck(index);

    return elementData(index);
    

    }

    1. remove方法

    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);
    // 把最后的置null
    elementData[--size] = null; // clear to let GC do its work
    
    return oldValue;
    

    }

    二。LinkedList

    1. 概述

    LinkedList以双向链表实现。链表无容量限制,但双向链表使用了更多空间,也需要额外的链表指针操作。

    按下标访问元素如get(i), set(i, e)要悲剧地遍历链表,将指针移动到位(使用双向链表是为了,如果i > 数组大小的一半,会从末尾向前查找)

    在插入、删除元素时,只需要修改节点的指针即可,但还是要遍历部分链表的指针才能移动到下标所指的位置,只有在链表两头的操作如add(), addFirst(), removeLast(), 或用iterator()上的remove()能省掉指针的移动。

    LinkedList是采用双向链表的简单的数据结构,如:
    LinkedList list = new LinkedList();
    list.add(“语文: 1”);
    list.add(“数学: 2”);
    list.add("英语: 3”);

    在这里插入图片描述
    2. set和get方法

    public E set(int index, E element) {
    checkElementIndex(index);
    Node x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
    }

    public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
    }

    这两个函数都调用了node方法,该函数以O(n/2)的性能去获取一个节点,具体实现代码如下:
    Node 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;
    }
    

    }

    即判断index在前半区还是后半区,如果在前半区就从前往后查找,如果在后半区就从后往前查找。这样,将节点的访问的复杂度由O(n)变为O(n/2)

    1. Stack:继承自Vector, 数组实现,线程安全,后进先出。
    展开全文
  • Java 集合框架 源码浅析 与理解

    千次阅读 多人点赞 2017-03-07 16:44:09
    Java集合框架 collection map set hashmap hashset queue

    最近在研究java源码,就是看一看别人写好的东西,也不算是研究。知根知底的对以后的学习会有很大的帮助,我先去了解一下java集合框架,从总体上对这个组织和操作数据的数据结构有个浅显得的了解。

    从网上看了很多资料,发现这一张图总结的还算不错就引用过来了。但是最上面的Map和Collection之间的关系应该是依赖,不是Produces。

    一、java集合框架概述

    从上面的集合框架图可以看到,Java集合框架主要包括两种类型的容器.

    一种是集合(Collection),存储一个元素集合,另一种是图(Map),存储键/值对映射。Collection接口又有3种子类型,List、Set和Queue,再下面是一些抽象类,最后是具体实现类,常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等.

    二、Collection接口

    首先看一下Collection的结构:

    Collection接口是处理对象集合的根接口,其中定义了很多对元素进行操作的方法,AbstractCollection是提供Collection部分实现的抽象类。上图展示了Collection接口中的全部方法。

    有几个比较常用的方法,比如方法:

    • add()添加一个元素到集合中,
    • addAll()将指定集合中的所有元素添加到集合中,
    • contains()方法检测集合中是否包含指定的元素,
    • toArray()方法返回一个表示集合的数组。

    Collection接口有三个子接口,下面详细介绍。

    1.List

    List接口扩展自Collection,它可以定义一个允许重复的有序集合,从List接口中的方法来看,List接口主要是增加了面向位置的操作,允许在指定位置上操作元素,同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator。AbstractList类提供了List接口的部分实现,AbstractSequentialList扩展自AbstractList,主要是提供对链表的支持。下面介绍List接口的两个重要的具体实现类,也是我们可能最常用的类,ArrayList和LinkedList。

    ArrayList

    通过查看ArrayList的源码,我们可以很清楚地看到里面的逻辑,它是用数组存储元素的,这个数组可以动态创建,如果元素个数超过了数组的容量,那么就创建一个更大的新数组(可以看出默认是10个),并将当前数组中的所有元素都复制到新数组中。假设第一次是集合没有任何元素,下面以插入一个元素为例看看源码的实现。

    1、方法add(int index, E element) 向集合中指定位置添加指定元素。
      public void add(int index, E element) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    2、此方法主要是确定将要创建的数组大小。
     private void ensureCapacityInternal(int minCapacity) {
            if (elementData == 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);
        }
    3、之后是创建数组,可以明显的看到先是确定了添加元素后的大小之后将元素复制到新数组中。
      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);
        }
    4、最后是处理数组,System.arraycopy()可以使用它来实现数组之间的复制,将元素复制到新数组中。
    /**
         * The char[] specialized version of arraycopy().
         *
         * @hide internal use only
         */
        public static void arraycopy(char[] src, int srcPos, char[] dst, int dstPos, int length) {
            if (src == null) {
                throw new NullPointerException("src == null");
            }
            if (dst == null) {
                throw new NullPointerException("dst == null");
            }
            if (srcPos < 0 || dstPos < 0 || length < 0 ||
                srcPos > src.length - length || dstPos > dst.length - length) {
                throw new ArrayIndexOutOfBoundsException(
                    "src.length=" + src.length + " srcPos=" + srcPos +
                    " dst.length=" + dst.length + " dstPos=" + dstPos + " length=" + length);
            }
            if (length <= ARRAYCOPY_SHORT_CHAR_ARRAY_THRESHOLD) {
                // Copy char by char for shorter arrays.
                if (src == dst && srcPos < dstPos && dstPos < srcPos + length) {
                    // Copy backward (to avoid overwriting elements before
                    // they are copied in case of an overlap on the same
                    // array.)
                    for (int i = length - 1; i >= 0; --i) {
                        dst[dstPos + i] = src[srcPos + i];
                    }
                } else {
                    // Copy forward.
                    for (int i = 0; i < length; ++i) {
                        dst[dstPos + i] = src[srcPos + i];
                    }
                }
            } else {
                // Call the native version for longer arrays.
                arraycopyCharUnchecked(src, srcPos, dst, dstPos, length);
            }
        }  

    LinkedList

    LinkedList是在一个链表中存储元素。

    在学习数据结构的时候,我们知道链表和数组的最大区别在于它们对元素的存储方式的不同导致它们在对数据进行不同操作时的效率不同,同样,ArrayList与LinkedList也是如此,实际使用中我们需要根据特定的需求选用合适的类,如果除了在末尾外不能在其他位置插入或者删除元素,那么ArrayList效率更高,如果需要经常插入或者删除元素,就选择LinkedList。

    2.Set

    Set接口扩展自Collection,它与List的不同之处在于,规定Set的实例不包含重复的元素。在一个规则集内,一定不存在两个相等的元素。AbstractSet是一个实现Set接口的抽象类,Set接口有三个具体实现类,分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。

    HashSet

    散列集HashSet是一个用于实现Set接口的具体类,可以使用它的无参构造方法来创建空的散列集,也可以由一个现有的集合创建散列集。在散列集中,有两个名词需要关注,初始容量和客座率。客座率是确定在增加规则集之前,该规则集的饱满程度,当元素个数超过了容量与客座率的乘积时,容量就会自动翻倍。

    下面看一个HashSet的例子。

    import java.util.HashSet;
    import java.util.Set;
    /**
     * @author ShanCanCan
     */
    public class HashSetTest {
        public static void main(String[] args) {
    
            Set<String> set = new HashSet<>();
    
            set.add("11111");
            set.add("22222");
            set.add("33333");
            set.add("44444");
            set.add("22222");
            set.add("99999");
            set.add("00000");
    
            System.out.println(set.size());
    
            for (String e : set) {
                System.out.println(e);
            }
    
        }
    }

    看一下输出结果:

    从输出结果我们可以看到,规则集里最后有6个元素,而且在输出时元素还是无序的。

    LinkedHashSet

    LinkedHashSet是用一个链表实现来扩展HashSet类,它支持对规则集内的元素排序。HashSet中的元素是没有被排序的,而LinkedHashSet中的元素可以按照它们插入规则集的顺序提取。

    TreeSet

    TreeSet扩展自AbstractSet,并实现了NavigableSet,AbstractSet扩展自AbstractCollection,树形集是一个有序的Set,其底层是一颗树,这样就能从Set里面提取一个有序序列了。在实例化TreeSet时,我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。

    下面是一个TreeSet的例子。

    import java.util.TreeSet;
      /**
      * @author ShanCanCan
      */
    public class TreeSetTest {
        public static void main(String[] args) {
    
            TreeSet<Integer> set = new TreeSet<>();
    
            set.add(1111);
            set.add(2222);
            set.add(3333);
            set.add(4444);
            set.add(5555);
    
            System.out.println(set.first()); // 输出第一个元素
            System.out.println(set.lower(3333)); // 小于3333的最大元素
            System.out.println(set.higher(2222)); // 大于2222的最大元素
            System.out.println(set.floor(3333)); // 不大于3333的最大元素
            System.out.println(set.ceiling(3333)); // 不小于3333的最大元素
    
            System.out.println(set.pollFirst()); // 删除第一个元素
            System.out.println(set.pollLast()); // 删除最后一个元素
            System.out.println(set);
        }
    }

    看一下输出结果:

    3.Queue

    队列是一种先进先出的数据结构,元素在队列末尾添加,在队列头部删除。Queue接口扩展自Collection,并提供插入、提取、检验等操作。

    上图中,方法offer表示向队列添加一个元素,poll()与remove()方法都是移除队列头部的元素,两者的区别在于如果队列为空,那么poll()返回的是null,而remove()会抛出一个异常。方法element()与peek()主要是获取头部元素,不删除。

    接口Deque,是一个扩展自Queue的双端队列,它支持在两端插入和删除元素,因为LinkedList类实现了Deque接口,所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列,优先队列中元素被赋予优先级,拥有高优先级的先被删除。

    下面是一个Queue的例子。

    import java.util.LinkedList;
    import java.util.Queue;
    /**
     * @author ShanCanCan
     */
    public class QueueTest {
        public static void main(String[] args) {
    
            Queue<String> queue = new LinkedList<>();
    
            queue.offer("aaaa");
            queue.offer("bbbb");
            queue.offer("cccc");
            queue.offer("dddd");
            queue.offer("eeee");
            queue.offer("ffff");
    
            while (queue.size() > 0) {
                System.out.println(queue.remove() + "");
            }
        }
    }

    看一下输出结果:

    三、Map接口

    Map,图,是一种存储键值对映射的容器类,在Map中键可以是任意类型的对象,但不能有重复的键,每个键都对应一个值,真正存储在图中的是键值构成的条目。

    下面是接口Map的类结构。

    从上面这张图中我们可以看到接口Map提供了很多查询、更新和获取存储的键值对的方法,更新包括方法clear()、put()、putAll()、remove()等等,查询方法包括containsKey、containsValue等等。Map接口常用的有三个具体实现类,分别是HashMap、LinkedHashMap、TreeMap。

    1.HashMap

    HashMap是基于哈希表的Map接口的非同步实现,继承自AbstractMap,AbstractMap是部分实现Map接口的抽象类。在平时的开发中,HashMap的使用还是比较多的。我们知道ArrayList主要是用数组来存储元素的,LinkedList是用链表来存储的,那么HashMap的实现原理是什么呢?先看下面这张图:

    在之前的版本中,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当链表中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

    下面主要通过源码介绍一下它的实现原理。

    HashMap存储元素的数组

    transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
    

    数组的元素类型是HashMapEntry

    /** @hide */  // Android added.
        static class HashMapEntry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            HashMapEntry<K,V> next;
            int hash;
    
            /**
             * Creates new entry.
             */
            HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
    
            public final K getKey() {
                return key;
            }
    
            public final V getValue() {
                return value;
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry e = (Map.Entry)o;
                Object k1 = getKey();
                Object k2 = e.getKey();
                if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                    Object v1 = getValue();
                    Object v2 = e.getValue();
                    if (v1 == v2 || (v1 != null && v1.equals(v2)))
                        return true;
                }
                return false;
            }
    
            public final int hashCode() {
                return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
            }

    接下来我们看下HashMap的put操作。

        /**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
            int i = indexFor(hash, table.length);
            for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }
         /**
         * Offloaded version of put for null keys
         */
        private V putForNullKey(V value) {
            for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }
    

    接下来我们看下HashMap的get操作。

     /**
         * Returns the value to which the specified key is mapped,
         * or {@code null} if this map contains no mapping for the key.
         *
         * <p>More formally, if this map contains a mapping from a key
         * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
         * key.equals(k))}, then this method returns {@code v}; otherwise
         * it returns {@code null}.  (There can be at most one such mapping.)
         *
         * <p>A return value of {@code null} does not <i>necessarily</i>
         * indicate that the map contains no mapping for the key; it's also
         * possible that the map explicitly maps the key to {@code null}.
         * The {@link #containsKey containsKey} operation may be used to
         * distinguish these two cases.
         *
         * @see #put(Object, Object)
         */
        public V get(Object key) {
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
    
            return null == entry ? null : entry.getValue();
        }
    
        /**
         * Offloaded version of get() to look up null keys.  Null keys map
         * to index 0.  This null case is split out into separate methods
         * for the sake of performance in the two most commonly used
         * operations (get and put), but incorporated with conditionals in
         * others.
         */
        private V getForNullKey() {
            if (size == 0) {
                return null;
            }
            for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }
    
        /**
         * Returns <tt>true</tt> if this map contains a mapping for the
         * specified key.
         *
         * @param   key   The key whose presence in this map is to be tested
         * @return <tt>true</tt> if this map contains a mapping for the specified
         * key.
         */
        public boolean containsKey(Object key) {
            return getEntry(key) != null;
        }
    
        /**
         * Returns the entry associated with the specified key in the
         * HashMap.  Returns null if the HashMap contains no mapping
         * for the key.
         */
        final Entry<K,V> getEntry(Object key) {
            if (size == 0) {
                return null;
            }
    
            int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
            for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }

    到这里HashMap的大致实现原理应该很清楚了,有几个需要关注的重点是:HashMap存储元素的方式以及根据Hash值确定映射在数组中的位置还有JDK 1.8之后加入的红黑树的。

    在HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用hash(int h)方法所计算得到的hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中,(n - 1) & hash 用于计算对象应该保存在table数组的哪个索引处。HashMap底层数组的长度总是2的n次方,当数组长度为2的n次幂的时候,(n - 1) & hash 算得的index相同的几率较小,数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

    2.LinkedHashMap

    LinkedHashMap继承自HashMap,它主要是用链表实现来扩展HashMap类,HashMap中条目是没有顺序的,但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序,也可以按它们最后一次被访问的顺序排序。

    3.TreeMap

    TreeMap基于红黑树数据结构的实现,键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap,同时实现了接口NavigableMap,而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口,使用它可以确保图中的条目是排好序的。

    在实际使用中,如果更新图时不需要保持图中元素的顺序,就使用HashMap,如果需要保持图中元素的插入顺序或者访问顺序,就使用LinkedHashMap,如果需要使图按照键值排序,就使用TreeMap。

    四、其它集合类

    上面主要对Java集合框架作了详细的介绍,包括Collection和Map两个接口及它们的抽象类和常用的具体实现类,下面主要介绍一下其它几个特殊的集合类,Vector、Stack、HashTable、ConcurrentHashMap以及CopyOnWriteArrayList。

    1.Vector

    前面我们已经提到,Java设计者们在对之前的容器类进行重新设计时保留了一些数据结构,其中就有Vector。用法上,Vector与ArrayList基本一致,不同之处在于Vector使用了关键字synchronized将访问和修改向量的方法都变成同步的了,所以对于不需要同步的应用程序来说,类ArrayList比类Vector更高效。

    2.Stack

    Stack,栈类,是Java2之前引入的,继承自类Vector。

    3.HashTable

    HashTable和前面介绍的HashMap很类似,它也是一个散列表,存储的内容是键值对映射,不同之处在于,HashTable是继承自Dictionary的,HashTable中的函数都是同步的,这意味着它也是线程安全的,另外,HashTable中key和value都不可以为null。

    上面的三个集合类都是在Java2之前推出的容器类,可以看到,尽管在使用中效率比较低,但是它们都是线程安全的。下面介绍两个特殊的集合类。

    4.ConcurrentHashMap

    Concurrent,并发,从名字就可以看出来ConcurrentHashMap是HashMap的线程安全版。同HashMap相比,ConcurrentHashMap不仅保证了访问的线程安全性,而且在效率上与HashTable相比,也有较大的提高。关于ConcurrentHashMap的设计,我将会在下一篇关于并发编程的博客中介绍,敬请关注。

    5.CopyOnWriteArrayList

    CopyOnWriteArrayList,是一个线程安全的List接口的实现,它使用了ReentrantLock锁来保证在并发情况下提供高性能的并发读取。

    五、总结

    到这里,对于Java集合框架的总结就结束了,还有很多集合类没有在这里提到,更多的还是需要大家自己去查去用。通过阅读源码,查阅资料,收获很大。

    • Java集合框架主要包括Collection和Map两种类型。其中Collection又有3种子类型,分别是List、Set、Queue。Map中存储的主要是键值对映射。

    • 规则集Set中存储的是不重复的元素,线性表中存储可以包括重复的元素,Queue队列描述的是先进先出的数据结构,可以用LinkedList来实现队列。效率上,规则集比线性表更高效。

    • ArrayList主要是用数组来存储元素,LinkedList主要是用链表来存储元素,HashMap的底层实现主要是借助数组+链表+红黑树来实现。

    • Vector、HashTable等集合类效率比较低但都是线程安全的。包java.util.concurrent下包含了大量线程安全的集合类,效率上有较大提升。

    本文引用了简书文章,但是对里面的内容做了很多更新,源码均来自jdk1.8.0_121。可以给你带来更新,更好的理解。

    展开全文
  • Java集合源码详解

    2017-09-06 17:57:59
    http://www.cnblogs.com/skywang12345/p/3323085.html  点击打开链接
  • java源码整理包-集合

    2020-07-29 14:20:07
    java源码整理包:list,map,ArrayList,HashMap,HashSet,Hashtable,TreeMap,TreeSet,Vector等源码包分享
  • Java 集合源码解析(1):Iterator

    万次阅读 多人点赞 2016-10-19 00:34:49
    Java, Android 开发也有段时间了,当初为了早点学 Android,Java 匆匆了解个大概... 这段时间就开始 Java 集合源码学习。 Java 提供的 集合类都在 Java.utils 包下,其中包含了很多 List, Set, Map, Queue… 它们的关
  • java集合源码分析(一)---整体

    千次阅读 2018-10-07 22:41:13
    这个月要把java集合好好重新看下了,把上个月没看的补上,突然发现自己写了这么久的安卓,集合那块都忘的差不多了,自己看了下自己当时写的集合的博客,写的真心烂唉。 自己当时学的时候的博客 主要的目的是搞清楚...
  • Java集合源码剖析-Java集合框架

    千次阅读 2019-05-28 13:34:25
    Hi大家好,我是清和二七,今天我们来聊聊《Java集合源码剖析-Java集合框架》 一.层次关系 Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合...
  • java_集合体系之总体目录——00

    千次阅读 多人点赞 2013-12-27 15:00:00
    摘要: java集合系列目录、不断更新中、、、、水平有限、总有不足、误解的地方、请多包涵、也希望多提意见、多多讨论 ^_^
  • 史上最全Java集合关系图

    万次阅读 多人点赞 2016-01-24 22:57:29
    说是史上最全,或许有点吸引眼球的嫌疑了,但我在网上确实也没有找到更全的,这图也是我对照Java源码挨个分析,画出了较为常见的关系图,及其重要特性。 图中部分集合的使用事例可以参见我的github(点击访问),...
  • Java8容器源码-目录

    千次阅读 2018-03-02 16:00:28
    本专栏从了解到使用再到源码,详细深入地讲解Java容器(集合)。 本专栏主要参考《Think In Java》一书,还有网上的一些技术文章。主要讲解Java容器的使用、源码、优缺点。个人能力有限,难免有考虑不到的地方,...
  • Java面试之集合

    千次阅读 2020-04-29 00:38:58
    Java面试之集合篇 篇章 个人博客链接 集合基础篇
  • java集合框架总结以及源码分析(一)

    万次阅读 2018-08-25 13:53:44
    一、集合框架总体架构图分析 1、首先我们先来看看一个集合框架的总图,有一个清晰的脉络机构,非常重要,因为不管我们学习那知识点,思路很重要。下面这张张图是我从网上博客摘取的,在此谢谢你精心的绘制。说明一下...
  • 《深入理解Java集合框架》系列文章

    千次阅读 2016-09-11 23:20:19
    关于C++标准模板库(Standard Template Library, STL)的书籍和资料有很多,关于Java集合框架(Java Collections Framework, JCF)的资料却很少,甚至很难找到一本专门介绍它的书籍,这给Java学习者们带
  • Java常用集合源码级深度解析

    千次阅读 2019-10-24 21:47:58
    Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:List列表、Set集合、Map映射、迭代器(Iterator、Enumeration...
  • Java集合框架(一):大纲

    千次阅读 多人点赞 2019-08-25 13:06:42
    Java集合框架之简述 Java集合框架之Collection Java集合框架之Iterator Java集合框架之HashSet Java集合框架之TreeSet Java集合框架之LinkedHashSet Java集合框架之...
  • Java Set集合详解及Set与List的区别

    万次阅读 2019-08-08 08:41:11
    Java中的Set集合是继承Collection的接口,是一个不包含重复元素的集合。 下图是Set集合源码。 Set和List都是以接口的形式来进行声明。Set主要包含三种存放数据类型都变量,分别是HashSet,LinkedHashSet,...
  • 给大家分享本人收集整理的16款Java小游戏源码,大部分是applet小程序,下面把每个游戏做个截图,最下面会有下载地址: 目录结构: 下载地址:...
  • 最近因为elasticsearch数据结构设计,设计一种需要字符串数组中的所有组合。...它的MathUtil类里面的方法都很好,请自行看源码,里面都是中文注释,能符合大部分的需求,各种组合排列,我在它的基础上封装了一个...
1 2 3 4 5 ... 20
收藏数 161,558
精华内容 64,623
关键字:

java集合源码