`
孙海友
  • 浏览: 24859 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

jdk源码解析之——java.util源码详解

阅读更多

jdk源码解析之——java.util源码详解

java.util的util自然指的就是utility(实用),就是说,这个包中定义的class和interface为我们提供了一些实用的工具可以辅助我们的开发。

那么这个包中最主要的以及最重要的就是collection框架,就是我们不管开发什么项目都会用到的”类集”。我们用类集来存放和提取数据,使我们的开发高效有序。

我们不太去赘述用法,而是通过源码来了解collection框架的基本实现,来使得我们更了解用法。

 

首先,我们来了解一下collection这个框架。

我们常常使用的集合,其实是分为两大类的:Collection<E>Map<K,V>

 

Collection<E>:

Collection 层次结构 中的根接口。Collection 表示一组对象,这些对象也称为 collection 的元素。

一些 collection 允许有重复的元素(如:List),而另一些则不允许(如:Set)。一些 collection 是有序的(如:SortedSet),而另一些则是无序的(如:ArrayList)。

Collection是没有构造函数的,它只是一个提供了通用方法的interface。

Collection<E>又根据是否有重复值分为两大类Set<E>与List<E>。Set<E>与List<E>同样是interface

 

Map<K,V>:

将键映射到值的对象。一个映射不能包含重复的键;每个键最多只能映射到一个值。

                           

 

下面,我们就从源码角度去看看collection的实现。(推荐使用IDE查看源代码,如:eclipse中的outline,对查看代码帮助很大)

 

一、List<E>:

List<E>接口的实现子类主要有两个:ArrayList<E>和LinkedList<E>。即List有顺序实现和链式实现。(写到这就默默想到,当时数据结构课上学习的C++STL很是类似)。

  (1)ArrayList<E>

    实现:通过成员变量和构造函数

    private static final int DEFAULT_CAPACITY = 10;
    private transient Object[] elementData;   //ArrayList维护的Object数组
    private int size;
    //指定初始长度的构造函数
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    //不带参数的构造函数
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
    //指定使用Collection初始化的构造函数
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

   ArrayList是由Object数组实现的,并且默认的长度是“DEFAULT_CAPACITY = 10”。当使用不带参数的构造函数时,底层默认是长度为10的Object[]。

   这时候就有一个问题了,当向ArrayList里面添加元素,使得Object数组不够用怎么办?

    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);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

   ArrayList在使用add方法时,会首先检查是否越界,如果越界,最终会使用grow方法。获得一个新长度的Object数组,将原数组拷贝到当中,再add新元素。

   获得新长度的算法是:

int newCapacity = oldCapacity + (oldCapacity >> 1);  //根据原数组的长度来确定新数组的长度

   看完ArrayList的实现,我们就不去看ArrayList的基本操作add()与remove()了,无非是一些数组的移位、拷贝操作。

    总结:

     1)ArrayList使用数组实现的,本质上,ArrayList是对象引用的一个变长数组。

     2)因此ArrayList又称为顺序表,正是因为是用数组实现的,对于随机存取比较方便;而插入和删除操作,需要移动大量的元素,缺点。

 

 

  (2)LinkedList<E>

   实现:链式表,顾名思义,是通过引用实现的,因此必然存在数据节点,以及对数据节点的引用。

/*LinkedList的内部类,数据节点Node<E>*/

private static class Node<E> {
        E item;
        Node<E> next;   //对后一个节点的引用
        Node<E> prev;   //对前一个节点的引用

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

  操作:LinkedList实现比较容易,操作的实现也就是引用的变化,不再赘述。

   总结:

    关于 ArrayList 与 LinkedList 的比较分析:

(a)ArrayList 底层采用数组实现,LinkedList 底层采用双向链表实现。

(b)当执行插入或者删除操作时,采用 LinkedList 比较好。

(c)当执行搜索操作时,采用 ArrayList 比较好。

 

二、Map<K,V>

  我们先看Map再看Set。Map使用两个基本操作:get( )和put( )

  Map最常用的实现子类时HashMap<K,V>

  实现:

   首先,我们看到的是:

 

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;    //存放元素的“数组”
    数组中存放的是Entry<K,V>

    Map中所有的键值都存放到了一个个的Entry中。相当于一个Bean。

 

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
}
   很类似与LinkedList,但是很奇怪,为什么要把节点放到数组中呢?为什么有了引用"Entry<K,V> next"还需要数组呢?为什么有个特殊的变量"int hash"呢?

 

   显然,HashMap的实现是数组与LinkedList的“结合”。(也就是数组与链表相结合的)

 

   看下面的代码:能够基本了解这种数据结构。

 

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);          //重新设置数组的大小
            hash = (null != key) ? hash(key) : 0;  //得到新的hash值
            bucketIndex = indexFor(hash, table.length);  //得到新的索引
        }

        createEntry(hash, key, value, bucketIndex);    //构建新的Entry
    }
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
    当addEntry时,可能会重新修改数组的大小,再将Entry存放到数组中。可是是怎么存放的呢? 
 Entry<K,V> e = table[bucketIndex];   //取出原来的Entry
 table[bucketIndex] = new Entry<>(hash, key, value, e); //将原来的Entry被引用到新的Entry的next,再讲新的Entry放到数组里面。

   1、先取出原来的Entry

   2、将原来的Entry被引用到新的Entry的next,再讲新的Entry放到数组里面

  于是图形如下:(盗用一下网上用的很多的这张图片:"拉链法"。来源:图片上有水印)

  
   

 

     现在只是知道的大致的数据结构是像上面那样的,但是HashMap如何通过一个“数组”来实现存取操作的呢?

 

   操作:

     put()操作:

 

    int hash = hash(key);
    int i = indexFor(hash, table.length);
    //put时,得到索引

    static int indexFor(int h, int length) {
        return h & (length-1);   //HashMap存取时,都需要计算当前key应该对应Entry[]数组哪个元素,即计算数组下标
    }
    当向 HashMap 中 put 一对键值时,它会根据 key 的 hashCode 值计算出一个位置,该位置就是此对象准备往数组中存放的位置。(如果Key相同,会覆盖成新的Value)

 

   具体操作:

   如果该位置没有对象存在,就将此对象直接放进数组当中;如果该位置已经有对象存在了,则顺着此存在的对象的链开始寻找(Entry 类有一个 Entry 类型的 next 成员变量,指向了该对象的下一个对象),如果此链上有对象的话,再去使用 equals 方法进行比较,如果对此链上的某个对象的 equals 方法比较为 false,则将该对象放到数组当中,然后将数组中该位置以前存在的那个对象链接到此对象的后面。

   get()操作类似,不再去解释了。

  

   我们再回过去看一下构造函数

   这是jdk1.6之前的实现:

public HashMap(int initialCapacity, float loadFactor) {
        .....
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }
   jdk1.7:(与1.6类似)
public HashMap(int initialCapacity, float loadFactor) {
        //........
        //........
        this.loadFactor = loadFactor;   //获得负载因子(根据负载因子的大小决定负载的能力)
        //装填因子 = key的个数 / 散列表的长度
        threshold = initialCapacity;   //threshold是再散列时的大小(capacity * load factor)
        init();
    }

 

   负载因子loadFactor的理解为:HashMap中的数据量/HashMap的总容量(initialCapacity),当loadFactor达到指定值或者0.75时候,HashMap的总容量自动扩展一倍,以此类推。

   下面就是总容量扩容的实现

 

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //...
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
 

 

 

 

三、Set<E>

   最后我们看一下Set<E>的常用子类HashSet<E>的实现。

   实现:还是先看构造函数和成员变量:

private transient HashMap<E,Object> map;
public HashSet() {
        map = new HashMap<>();
    }
    一目了然,原来HashSet使用HashMap来实现的,所以我们要先说Map再说Set。

 

   HashSet用HashMap来实现,将元素存放在Map的Key中,因此Map中存放的元素是不可以重复的。而Value当中存放的是默认的Object。

   相应的HashSet也给出了一个可以修改装载能力的构造函数:

public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
   最后是HashSet的操作:
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    实现也因此比较简单。

    那么Collection框架就介绍到这里了。

 

下一期继续进行jdk源代码详解。

 

-------------------------------------------------------------------------------------

3月23日更新:《杂七杂八》之——别当测试不重要(软件测试技术)

  • 大小: 10.6 KB
  • 大小: 18.2 KB
分享到:
评论
3 楼 孙海友 2014-03-24  
3月23号的博客,因为博主忙着参加面试,没能更新。好在面试过了,最近就不更新《杂七杂八》了。为了面试,主要复习设计模式以及Java源码了。
2 楼 ysr1023 2014-03-23  
支持一下。
1 楼 孙海友 2014-03-22  

相关推荐

    无法解析类型 java.util.Map$Entry。从必需的 .class 文件间接引用了它

    这是我在编写struts2中遇到的问题,整理出来,包括截图,希望可以帮到大家

    深入剖析jdk的java.util包

    jdk源码java.util包,所有类解析,包含整体架构及各个类详解

    Java源码解析——看优秀源码最能使人进步

    Java源码解析——看优秀源码最能使人进步 Java源码解析是一种深入了解JDK源码的方式,适合那些想深入了解JDK源码的人。通过对JDK源码的解析,可以让开发者更好地理解Java语言的底层逻辑,从而写出更加高效、稳定的...

    linux安装jdk(csdn)————程序.pdf

    这里,JAVA_HOME变量指定了JDK的安装位置,CLASSPATH变量指定了Java类库的路径,PATH变量指定了Java命令的路径。 三、让配置文件生效 修改配置文件后,需要让配置文件生效,可以使用以下命令: source /etc/...

    JDK7源码 包含rt.jar包下的 sun包源码 sun.security包等源码

    本压缩包提供了JDK7的源码,特别强调了`sun`包和`sun.security`包下的源代码,这对于深入理解Java内部机制和安全机制有着极大的帮助。 `rt.jar`是JDK中的核心类库,包含了Java标准API的实现。这个jar文件中的`sun`...

    JDK1.8 java.util.stream.Stream:Stream 代码示例

    java.util.stream.Stream:Stream 代码示例

    jdk1.6.0——13.tagz

    标题“jdk1.6.0——13.tagz”揭示了这是一个与Java开发工具包(Java Development Kit)相关的文件,具体版本为1.6.0的第13次更新。Java JDK是用于编写、编译和调试Java应用程序的基础软件包。它包含了Java虚拟机...

    jdk源码调试重编译rt.jar包

    关于调试jdk源码显示源码变量值的rt.jar重编译包

    JDK研究系列--》util.concurrent(java.util part3)

    合适研究底层研发员,但,一般程序员也必须掌握的要点 JDK研究系列--》util.concurrent(java.util part3)

    JDK1.5中的线程池(java.util.concurrent.ThreadPoolExecutor)使用简介.doc

    JDK1.5中的线程池(java.util.concurrent.ThreadPoolExecutor)使用简介

    jdk源码(完整版)

    **Java Development Kit (JDK) 源码详解** JDK,即Java Development Kit,是Java编程语言的核心组件,包含了编译器、运行时环境、工具集和其他必要的资源,用于开发和运行Java应用程序。这里提到的"jdk源码(完整版...

    jdk1.8 rt.jar 源码

    Java开发工具包(JDK)是Java编程语言的核心组件,其中包含了运行和开发Java应用程序所需的库和工具。在 JDK 1.8 版本中,`rt.jar` 是一个非常重要的文件,它包含了Java标准版(Java SE)的运行时类库。这个库包含了...

    JavaJDK@19——47198.exe

    JDK下载软件的宅槽信息系统以及配置需求安装文件信息详情

    各种系统java jdk安装步骤(csdn)————程序.pdf

    "Java JDK安装步骤详解" Java JDK是Java开发环境的基础组件之一,对于Java开发者来说,安装和配置JDK是非常重要的一步骤。下面我们将详细介绍在不同的系统平台上安装和配置JDK的步骤。 UOS(统信操作系统) 1. 解...

    JDK1.8下载 : jdk_8.0.1310.11_64.zip

    1.Java 8允许我们给接口添加一个非抽象的方法实现,只需要使用 default关键字即可。 2.新增lambda表达式 3.提供函数式接口 4.Java 8 允许你使用关键字来传递方法或者构造函数引用 5.我们可以直接在lambda表达式中...

    javajdk源码-java.util_source_learning:学习JDK源代码

    `java.util_source_learning`项目提供了对JDK源码的学习资源,帮助开发者深入探索这个包内的实现细节。 在JDK源码中,`java.util`包涵盖了许多关键类和接口,如ArrayList、LinkedList、HashMap、HashSet、Queue、...

    动画学习 java.util.concurrent并发工具包

    1.打开cmd,cd到jdk的path,本机是:cd C:\Java\jdk6\bin 2.资源javaConcurrentAnimated.jar放在D盘根目录 3.使用java -cp命令: java -cp D:\javaConcurrentAnimated.jar vgrazi.concurrent.samples.launcher....

    良葛格————JavaJDK5.0学习笔记PDF

    良葛格————JavaJDK5.0学良葛格————JavaJDK5.0学习笔记PDF.rar习笔记PDF.rar良葛格良葛格————JavaJDK5.0学习笔记PDF.rar————JavaJDK5.0学习笔记PDF.rar良葛格————JavaJDK5.0学习笔记PDF.rar良...

    java base64的jar包

    Java Base64是一个用于处理Base64编码的库,它为Java开发者提供了便捷的方式来编码和解码Base64数据。Base64是一种在网络上传输二进制数据时常用的编码方式,因为HTTP、电子邮件等协议主要处理ASCII字符,而Base64...

    JDK研究系列--》util实用类util实用类(java.util part2)

    合适研究底层研发员,但,一般程序员也必须掌握的要点 JDK研究系列--》util实用类util实用类(java.util part2)

Global site tag (gtag.js) - Google Analytics