-
编辑 删除
查找
基本概念仅存储数据而不获取数据是不可能的，这就是查找。查找的定义如下：查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。查找表（SearchTable）是由同一类型的数据元素（或记录）构成的集合。简单来说就是，在我们定义的数据结构中，查找位于某
-
编辑 删除
树与二叉树
早在分析Java集合源码时，我们对树和二叉树就有了基本的了解，部分知识可以查看Java集合源码分析之基础（三）：树与二叉树。本文在此基础上，介绍树和二叉树的存储、特性以及部分知识的Java参考代码。树的存储结构数据结构中定义的树，类似于下图：树示意图前面我们说过，计算机只能顺序或者链式存储数据，所以
-
编辑 删除
栈与队列
前言数组与链表结构能够解决很多一对一的线性表问题，但是在许多情况下，使用最原始的数据结构过于复杂，而且不够安全。数组和链表都可以在任意位置增加和删除数据，但在一些场景下这个机制并不适用。比如我们要做一个排队系统，如果人们可以随意插队，那么所有人都会不满吧？栈与队列，就是在一些场景下对数组或链表的包装
-
编辑 删除
线性表：数组与链表
前言线性表是指数据之间是一对一的关系，比如数组和链表都属于这一范畴。数组和链表又代表了两种存储方式：顺序存储和链式存储。部分知识在分析集合：Java集合源码分析之基础（一）：数组与链表中已有阐述，这里不再赘述，本文是对这些概念的补充，以及给出可参考的Java代码实现。顺序存储顺序存储在大多数语言中定
-
编辑 删除
数据结构与算法概述
初衷学习数据结构与算法的知识，并没有一个完备的理由。如果是作为一名算法工程师，这无可厚非，但对于我们大部分的开发者而言，算法对工作的影响甚微，甚至可能不需要任何算法就可以完成全部的工作。那么，我们为什么要学习数据结构与算法？我总结有以下几点：首先，算法是面试的常客。很多人会抱怨面试为何要问算法，工作
-
编辑 删除
Java集合源码分析之Set概述与总结
Java集合源码分析系列到此就结束了，关于Set的知识会在这里进行简单的总结，除此之外，则是学习之后的一些感受。Set概述Set是一个包含不可重元素的集合，也就是所有的元素都是唯一的。文档说明如下：Acollectionthatcontainsnoduplicateelements.Moreform
-
编辑 删除
Java集合源码分析之Map（五）：LinkedHashMap
LinkedHashMap是HashMap的子类，所以也具备HashMap的诸多特性。不同的是，LinkedHashMap还维护了一个双向链表，以保证通过Iterator遍历时顺序与插入顺序一致。除此之外，它还支持AccessOrder，即按照元素被访问的顺序来排序，我们熟知的LRUCache底层就
-
编辑 删除
Java集合源码分析之Map（四）：HashMap
HashMap可能是我们使用最多的键值对型的集合类了，它的底层基于哈希表，采用数组存储数据，使用链表来解决哈希碰撞。在JDK1.8中还引入了红黑树来解决链表长度过长导致的查询速度下降问题。以下是文档对它的介绍中我们重点关注的部分：HashtablebasedimplementationoftheMa
-
编辑 删除
Java集合源码分析之Map（三）：TreeMap
TreeMap是红黑树的java实现，对红黑树不太了解的可以查阅历史文章：Java集合源码分析之基础（六）：红黑树（RBTree）。红黑树能保证增、删、查等基本操作的时间复杂度为O(lgN)。本文将对TreeMap的源码进行分析。TreeMap结构图Entry定义staticfinalclassEn
-
编辑 删除
Java集合源码分析之Map（二）：SortedMap与NavigableMap
SortedMap由于乱序的数据对查找不利，例如无法使用二分法等降低算法的时间复杂度，如果数据在插入时就排好顺序，查找的性能就会提升很多。SortedMap接口就是为这种有序数据服务的。SortedMap接口需要数据的key支持Comparable，或者可以被指定的Comparator接受。Sort
-
编辑 删除
Java集合源码分析之Map（一）：超级接口Map
数组与链表在处理数据时各有优缺点，数组查询速度很快而插入很慢，链表在插入时表现优秀但查询无力。哈希表则整合了数组与链表的优点，能在插入和查找等方面都有不错的速度。我们之后要分析的HashMap就是基于哈希表实现的，不过在JDK1.8中还引入了红黑树，其性能进一步提升了。本文主要分析JDK中关于Map
-
编辑 删除
Java集合源码分析之LinkedList
分析完了List与Queue之后，终于可以看看LinkedList的实现了。LinkedList弥补了ArrayList增删较慢的问题，但在查找方面又逊色于ArrayList，所以在使用时需要根据场景灵活选择。对于这两个频繁使用的集合类，掌握它们的源码并正确使用，可以让我们的代码更高效。Linked
-
编辑 删除
Java集合源码分析之Queue（二）：ArrayDeque
在介绍了Queue与Deque概念之后，这是要进行分析的第一个实现类。ArrayDeque可能大家用的都比较少，但其实现里有许多亮点还是值得我们关注的。Deque的定义为doubleendedqueue，也就是允许在两侧进行插入和删除等操作的队列。这个定义看起来很简单，那么我们怎么实现它呢？我们最容
-
编辑 删除
Java集合源码分析之Queue（一）：Queue与Deque
在日常生活中，排队几乎随处可见，上地铁要排队，买火车票要排队，就连出门吃个大餐，也要排队。。。之前研究的ArrayList就像是一个缺乏管理的排队系统。大家虽然会排队，但一会走个人，大家向前挪一挪，一会插个人，大家向后挪一挪，碰到这样的队伍，一定让人痛苦万分吧？今天要介绍的Queue就不同了，它是一
-
编辑 删除
Java集合源码分析之List（二）：ArrayList
做了这么多准备，终于到了ArrayList了，ArrayList是我们使用最为频繁的集合类了，我们先看看文档是如何介绍它的：Resizable-arrayimplementationoftheListinterface.Implementsalloptionallistoperations,andp
-
编辑 删除
Java集合源码分析之List（一）：超级接口List
以下内容结合源码阅读，更舒适哦~List是Collection三大直接子接口之一，其中的数据可以通过位置检索，用户可以在指定位置插入数据。List的数据可以为空，可以重复。以下是其文档注释，只看前两段：Anorderedcollection(alsoknownasasequence).Theuser
-
编辑 删除
Java集合源码分析之超级接口：Collection
CollectionCollection是List、Queue和Set的超集，它直接继承于Iterable，也就是所有的Collection集合类都支持for-each循环。除此之外，Collection也是面向接口编程的典范，通过它可以在多种实现类间转换，这也是面向对象编程的魅力之一。方法定义在阅
-
编辑 删除
Java集合源码分析之Iterable概述
前言当我们想要遍历集合时，Java为我们提供了多种选择，通常有以下三种写法：写法1：for循环for(inti=,len=strings.size();i<len;i++){System.out.println(strings.get(i));}写法2：foreach循环for(Stringv
-
编辑 删除
Java集合源码分析之基础（六）：红黑树（RB Tree）
红黑树和AVL树的思想是类似的，都是在插入过程中对二叉排序树进行调整，从而提升性能，它的增删改查均可以在O(lgn)内完成。本文会从定义到实现一棵红黑树展开。定义红黑树是一棵二叉排序树。且满足以下特点：每个节点或者是黑色，或者是红色。根节点是黑色。每个叶子节点（NIL）是黑色。[注意：这里叶子节点，
-
编辑 删除
Java集合源码分析之基础（五）：平衡二叉树（AVL Tree）
二叉排序树很好的平衡了插入与查找的效率，但不平衡的二叉排序树效率大打折扣。今天介绍的AVL树就是一种解决此问题的方案。定义平衡二叉树(Self-BalancingBinarySearchTree或Height-BalancedBinarySearchTree)，是一种二叉排序树，其中每一个节点的左子
