Java 容器源码

昨天已经学习了HashSet，今天开始学习TreeSet。TreeSet是依赖于TreeMap的NavigableSet接口的实现，实际上是个TreeMap的实例。如果对TreeMap源码很熟悉，那么学习TreeSet就会很简单了。TreeSet的特点是使用元素的自然顺序对元素进行排序，或者根据创建set时提供的Comparator进行排序。本文将从数据结构、实现原理、源码等多个方面详细讲解TreeSet。数据结构TreeSet是依赖于TreeMap的NavigableSet接口的实现。所以HashSet的数据结构也是红黑树。这点可以从源码中很清楚地看出来。privatetransientNa

今天开始学习HashSet。HashSet是依赖于HashMap的Set接口的实现，实际上是个HashMap的实例。如果对HashMap源码很熟悉，那么学习HashSet就会很简单了。HashSet的特点是不保证set的迭代顺序，特别是它不保证该顺序恒久不变，允许使用null元素。本文将从数据结构、实现原理、源码等多个方面详细讲解HashSet。数据结构HashSet是依赖于HashMap的。所以HashSet的数据结构也是哈希表+链表+红黑树。HashSet是依赖于HashMap的。这点可以从源码中很清楚地看出来。privatetransientHashMap<E,Object>

前面一段时间，我们已经对List和Map的实现类进行了学习和总结。接下来，我们开始学习Set。相信学习了Map之后，学习Set会容易很多。本文主要介绍Set的整体结构。Set的整体结构Set接口继承了Collection接口。特点是不保存重复的元素。AbstractSet是一个抽象类，它继承于AbstractCollection，实现了Set。AbstractCollection提供了Set接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。SortedSet进一步提供关于元素的总体排序的Set。这些元素使用其自然顺序进行排序，或者根据通常在创建有序set时提供的Comparator进行

Map的整体结构先来回顾下Map的整体结构。层次结构图Map是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。Map没有继承Collection接口。AbstractMap：实现了Map接口的抽象类。Map的基本实现，其他Map的实现类可以通过继承AbstractMap来减少编码量。SortedMap：继承Map。保证按照键的升序排列的映射，对entrySet、keySet和values方法返回的结果进行迭代时，顺序就会反映出来。NavigableMap：继承SortedMap，含有返回特定条件最近匹配的导航方法。HashMap：Map接口基于哈希表的实现，是使用频率最

TreeMap是Map接口基于红黑树的实现，键值对是有序的。本文主要讲解关于红黑树实现的部分。部分顶部注释ARed-BlacktreebasedNavigableMapimplementation.ThemapissortedaccordingtotheComparablenaturalorderingofitskeys,orbyaComparatorprovidedatmapcreationtime,dependingonwhichconstructorisused.TreeMap是基于NavigableMap的红黑树实现。TreeMap根据键的自然顺序进行排序，或者根据创建map时提供的C

LinkedHashMap继承了HashMap，是Map接口的哈希表和链接列表实现。哈希表的功能通过继承HashMap实现了。LinkedHashMap还维护着一个双重链接链表。此链表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。本文主要讲解双重链接链表的部分，看看它是如何实现有序性的。数据结构在分析LinkedHashMap源码之前，有必要了解LinkedHashMap的数据结构，否则很难理解下面的内容。从上图中可以很清楚的看到，HashMap的数据结构是数组+链表+红黑树（sinceJDK1.8）+双重链接列表。数组+链表+红黑树的部分请参考HashMap源码一文中关于数据结构的

WeakHashMap和HashMap相似，也是哈希表的实现，以键值对的形式存储数据，key和value都可以为null。不同的是WeakHashMap的键为“弱键”。什么是“弱键”？弱键会对WeakHashMap产生什么影响？“弱键”是如何实现的？本文会通过源码来一一解答。部分顶部注释HashtablebasedimplementationoftheMapinterface,withweakkeys.AnentryinaWeakHashMapwillautomaticallyberemovedwhenitskeyisnolongerinordinaryuse.Moreprecisely,th

相信大家对Hashtable已经有所了解了，Hashtable和HashMap，从存储结构和实现来讲基本上都是相同的。它和HashMap的最大的不同是它是线程安全的，另外它不允许key和value为null。Hashtable是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。但这并不是我们不去了解它的理由。最起码Hashtable和HashMap的面试题在面试中经常被问到。Hashtable是如何实现线程安全的的？Hashtable和HashMap的相同点和不同点？本文将分析Hashtable的

相信大家对HashMap的使用已经很熟悉了，它和List的最大的不同是它是以key-value的形式存储数据的。HashMap是如何保存和处理key-value键值对的？本文将分析HashMap的内部结构及实现原理，帮助大家更好的使用它。数据结构在分析HashMap源码之前，有必要了解HashMap的数据结构，否则很难理解下面的内容。从上图中可以很清楚的看到，HashMap的数据结构是数组+链表+红黑树（红黑树sinceJDK1.8）。我们常把数组中的每一个节点称为一个桶。当向桶中添加一个键值对时，首先计算键值对中key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已

前面已经学习了List的实现类并做了总结，接下来学习Map的实现类。原本想学习Set，可仔细一想，Set的某些实现类如HashSet实现是基于HashMap的，TreeSet的实现也依赖于TreeMap。所以就决定先学习Map。本文主要介绍Map的整体结构，并简单介绍结构中的接口和抽象类。Map的整体结构Map是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。Map没有继承Collection接口。AbstractMap：实现了Map接口的抽象类。Map的基本实现，其他Map的实现类可以通过继承AbstractMap来减少编码量。SortedMap：继承Map。保证按照

前面我们已经学习了ArrayList、Vector、LinkedList、Stack的源码，现在我们来对List做个简单的总结。List整体结构先来回顾一下List的整体结构List以线性方式存储元素，集合中可以存放重复对象，元素有序。最常用实现类：ArrayList：随机访问元素快，增删元素慢。Vector：Vector与ArrayList相似。但Vector的方法是线程安全的，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此ArrayList的性能比Vector好。LinkedList：随机访问元素慢，顺序访问快，增删元素快。Stack：栈，继承Vector，特点是先进后

学完了ArrayList、Vector、LinkedList的源码后，今天来学习Stack源码。参考的JDK版本为1.8。Stack继承了Vector，学习了Vector再来学习Stack就变得很简单。Stack，栈，特点是先进后出(FILO,FirstInLastOut)。Stack是如何实现先进后出的？本文将详细讲解这个问题。顶部注释TheStackclassrepresentsalast-in-first-out(LIFO)stackofobjects.ItextendsclassVectorwithfiveoperationsthatallowavectortobetreatedasa

迭代器模式(IteratorPattern)：提供一种方法来访问聚合对象中的各个元素，而不用暴露这个对象的内部表示。在Java中，LinkedList的迭代器有三种：Iterator、ListIterator、DescendingIterator。其中DescendingIterator与Iterator只能单向遍历，遍历的方向相反。而ListIterator可以双向遍历。DescendingIterator/***AdaptertoprovidedescendingiteratorsviaListItr.previous*/privateclassDescendingIteratorimpl

LinkedList和ArrayList与Vector同样实现了List接口，但它执行某些操作如插入和删除元素操作比ArrayList与Vector更高效，而随机访问操作效率低。除此之外，LinkedList还添加了可以使其用作栈、队列或双端队列的方法。LinkedList在实现方面与ArrayList与Vector有哪些不同呢？为什么它插入删除操作效率高？随机访问操作效率低？它是如何用作栈、队列或双端队列的？本文将分析LinkedList的内部结构及实现原理，帮助大家更好的使用它，并一一解答上述问题。顶部注释Doubly-linkedlistimplementationoftheListan

Enumeration的存在有什么意义？Iterator已经实现了对容器的遍历了，Enumeration的存在有什么意义呢？原因可能有很多种，个人了解有限，欢迎大家补充。Enumeration在JDK1.0就已经存在了，而Iterator是JDK2.0新加的接口。为了依赖JDK1.0写的代码能够正常运行，Enumeration是不能删的。相同点Iterator和Enumeration都可以对某些容器进行遍历。Iterator和Enumeration都是接口。欢迎大家补充。不同点Iterator有对容器进行修改的方法。而Enumeration只能遍历。Iterator支持fail-fast，而E

细心地朋友看Java容器源码时一定会发现在list()和listIterator()的注释中都有一句话：Theiteratorsreturnedbythisclass’siteratorandlistIteratormethodsarefail-fast.我看ArrayList源码没认真想fail-fast是什么意思，看Vector源码时又看到了这个词，而且在翻看Set实现类和Map实现类源码时也看到了这个词。fail-fast是什么？本篇文章以Vector为例来详细解说fail-fast。什么是fail-fast？**下面是Vector中源码的最上部的注释中关于fail-fast的介绍The

本文主要讲解迭代器模式在Vector源码中的使用。参考的JDK版本为1.8。迭代器模式(IteratorPattern)：提供一种方法来访问聚合对象中的各个元素，而不用暴露这个对象的内部表示。在Java中，Vector的迭代器有两种：Iterator和ListIterator。值得一提的是，elements()方法也能实现类似迭代器的效果。为什么已经有了迭代器，还特意在Vector中新增了elements()呢？在文章最后会作出解释。Iterator迭代器是一个用来遍历并选择序列中的对象。Java的Iterator的只能单向移动。例子在写如何实现之前，先看一个使用迭代器Iterator的小例子

相信大家对Vector的使用已经很熟悉了，它和ArrayList的最大的不同是它是线程安全的，这点在Vector源码中也有说明。Vector源码中注释有这么一句“Vectorissynchronized.Ifathread-safeimplementationisnotneeded,itisrecommendedtouseArrayListinplaceofVector”，意为“Vector是同步的。如果不需要线程安全的实现，推荐使用ArrayList代替Vector”。Vector是如何线程安全的？除了线程安全之外，它和ArrayList还有其他不同吗？本文将分析Vector的内部结构及实现

迭代器模式(IteratorPattern)：提供一种方法来访问聚合对象中的各个元素，而不用暴露这个对象的内部表示。在Java中，ArrayList的迭代器有两种：Iterator和ListIterator。Iterator迭代器是一个用来遍历并选择序列中的对象。Java的Iterator的只能单向移动。例子在写如何实现之前，先看一个使用迭代器Iterator的小例子：importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassTest{@org.junit.Testpublicvoidt

今天开始学习ArrayList源码。参考的JDK版本为1.8。相信大家对ArrayList的使用已经很熟悉了，但你真的了解ArrayList吗？ArrayList源码中注释的第一行是“Resizable-arrayimplementationoftheListinterface”，意为“List接口的可变长数组实现”。ArrayList是如何实现可变长的？ArrayList有哪些私有方法？它们对ArrayList的功能起到了什么作用？本文将从数据结构、实现原理、源码等角度分析ArrayList，帮助大家更好的使用它。数据结构如图所示，ArrayList底层通过数组实现。顶部注释List接口的大

为什么需要Java容器通常，程序总是在运行时才能确定要创建的对象的数量，甚至是对象的类型。为了解决这个问题，需要在任意时刻任意位置创建任意数量的对象。大多数语言都提供某种方法来解决这个问题，Java使用容器来解决这个问题。容器也称集合类，基本的类型是List、Set、Queue、Map，但由于Java类库中使用了Collection关键字来代表某一接口，所以一般用容器来称呼这些集合类。Java容器工具包位置是java.util.*。容器的整体结构图Java容器主要可以划分为5个部分：List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays