三歪教你学Java集合

前言一、学习指南一、Java集合学习指南1.1学习一项技术之前，必须知道为什么要学它！1.2如何入门学习Java集合1.3 集合进阶与面试二、Collection一、集合(Collection)介绍1.1为什么需要Collection1.2数组和集合的区别1.3Collection的由来与功能二、迭代器(Iterator)介绍三、List集合介绍3.1List集合常用子类四、Set集合介绍4.1Set集合常用子类三、List集合一、ArrayList解析1.1构造方法1.2Add方法1.2.1add(E e)1.2.2add(int index, E element)1.3 get方法1.4 set方法1.5remove方法1.6细节再说明二、Vector与ArrayList区别三、LinkedList解析3.1构造方法3.2add方法3.3remove方法3.4get方法3.5set方法四、List集合总结四、Map集合一、Map介绍1.1为什么需要Map1.2Map与Collection的区别1.3Map的功能二、散列表介绍2.1散列表工作原理三、红黑树介绍3.1回顾二叉查找树3.2知新2-3树3.3从2-3树到红黑树3.4红黑树基础知识五、HashMap一、HashMap剖析1.1HashMap构造方法1.2put方法1.3get方法1.4remove方法二、HashMap与Hashtable对比三、HashMap总结六、LinkedHashMap一、LinkedHashMap1.1LinkedHashMap的域1.2LinkedHashMap重写的方法1.3构造方法1.4put方法1.5get方法1.6remove方法1.7遍历的方法二、LinkedHashMap总结七、TreeMap一、TreeMap剖析1.1TreeMap的域1.2TreeMap构造方法1.3put方法1.4get方法1.5remove方法1.6遍历方法二、TreeMap总结九、Set一、HashSet剖析二、TreeSet剖析三、LinkedHashSet剖析四、Set集合总结十、CopyOnWriteArrayList一、Vector和SynchronizedList1.1回顾线程安全的Vector和SynchronizedList1.2Vector和SynchronizedList可能会出现的问题二、CopyOnWriteArrayList(Set)介绍2.1CopyOnWriteArrayList实现原理2.1.1看一下CopyOnWriteArrayList基本的结构2.1.2常见方法的实现2.1.3剖析为什么遍历时不用调用者显式加锁2.1.4CopyOnWriteArrayList缺点2.1.5CopyOnWriteSet十一、Java集合面试题一、ArrayList和Vector的区别二、HashMap和Hashtable的区别三、List和Map的区别四、Set里的元素是不能重复的，那么用什么方法来区分重复与否呢? 是用=还是equals()?五、Collection和Collections的区别六、说出ArrayList,LinkedList的存储性能和特性6.1扩展：七、Enumeration和Iterator接口的区别八、ListIterator有什么特点九、并发集合类是什么？十、Java中HashMap的key值要是为类对象则该类需要满足什么条件？十一、与Java集合框架相关的有哪些最好的实践十二、ArrayList集合加入1万条数据，应该怎么提高效率前言这个文档的内容纯手打，如果想要看更多的干货文章，关注我的公众号：Java3y。有更多的原创技术文章和干货！目前疯狂处于疯狂更新PDF中，只要是Java后端的知识，都会有！欢迎来我公众号催更！微信搜索：Java3y如果文档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！公众号有我的联系方式 Java精美脑图 Java学习路线 开发常用工具 精美电子书、文档在公众号下回复888即可获取！学习不能盲目，跟着我，会让你事半功倍文档允许随意传播，但不能修改任何内容。电子书的整理也是挺不容易，如果你觉得有帮助，想要打赏作者，那么可以通过这个收款码打赏我，金额不重要，心意最重要。主要是我可以通过这个打赏情况来预计大家对这本电子书的评价，嘻嘻一、学习指南一、Java集合学习指南本文会提出很多可能新手会想到的问题，但不会一一解答，只会往大方向去说明白。本文的内容偏向于指南，而非技术教程讲解。如果想要得到具体的答案，可以翻阅我曾经写过的资料：/ZhongFuCheng3y/3y，或者加入人才交流群跟众多开发者讨论，前面的Github链接有我的联系方式。1.1学习一项技术之前，必须知道为什么要学它！Q: 我们得知道为什么要学习Java集合，学到Java集合的时候已经学过了数组了，为什么我不用数组反而用Java集合。数组和Java集合有什么区别？A:Java是一门面向对象的语言，就免不了处理对象，为了方便操作多个对象，那么我们就得把这多个对象存储起来，想要存储多个对象(变量),很容易就能想到一个容器(集合)来装载总的来说：就是Java给我们提供了工具方便我们去操作多个Java对象。1.2如何入门学习Java集合Q: 从上面我们已经知道了为什么要学Java集合，下面我们就该知道Java集合的基本用法，以及从它整体的知识点去了解它是什么A： 我们学习Java集合实际上就是为了方便操作多个对象，而Java给我们提供一系列的API(方法)供我们去操作。所以在初学Java集合的时候我们更多的是学习这些API(方法)分别是什么意思。Q： 对Java集合的API使用有一定的了解之后，我们就应该从面向对象的角度去理解它。为什么会抽象出多个接口，以及每个接口的有什么特性。A: 我们可以总结出几个常用的实现类，这几个常用的实现类我们必须要知道它的数据结构是什么，什么时候使用这个类。需要学习和了解的数据结构：到这里，我们简单了解各个实现类的数据结构以后，我们可能会简单记住下面的结论： 如果是集合类型，有List和Set供我们选择。List的特点是插入有序的，元素是可重复的。Set的特点是插入无序的，元素不可重复的。至于选择哪个实现类来作为我们的存储容器，我们就得看具体的应用场景。是希望可重复的就得用List，选择List下常见的子类。是希望不可重复，选择Set下常见的子类。 如果是Key-Value型，那我们会选择Map。如果要保持插入顺序的，我们可以选择LinkedHashMap，如果不需要则选择HashMap，如果要排序则选择TreeMap。 总之：学完常见实现类的数据结构之后，你对它的使用场景就有一个清楚的认知了。1.3 集合进阶与面试如果我们在写代码的时候懂得选择什么样的集合作为我们的容器，那已经是入门了。但要知道的是，如果去面试之前，你懂的不应该只有这么少。（如果还在初学或者零基础的同学我建议可以跳过这一部分，在网上有可能很多言论，比如：“如果你Java基础扎实的话，那你以后找工作就不愁了。在学Java基础的时候一定要把基础学好，看源码！”。但我认为，这一块是建立在有一定的编码/项目或者是去找工作的时候才成立的，一个刚入门学Java的，就不应该看源码，这很容易把自己劝退了）我的观点是：如果刚入门学Java，首先你要十分清楚知道为什么要学这个，这个到底有什么用，用在哪些地方，以及熟悉常用的方法，就足够了。即便你花了两周左右时间去看源码实现了，可能看懂了。但是，你相信我，你大概率会忘掉。Java集合是面试的重点，我在面试的时候几乎每家公司都会问集合的问题，从基础到源码，一步一步深入。Java集合面试的知识点就不限于基本的用法了。可能面试官会问你： HashMap的数据结构是什么？他是怎么扩容的？底层有没有用红黑树？取Key Hash值是JDK源码是怎么实现的？为什么要这样做？ HashMap是线程安全的吗？什么是线程安全？有什么更好的解决方案？那线程安全的HashMap是怎么实现的？ HashSet是如何判断Key是重复的？ .很多很多总的来说，入门Java集合并不难，归根到底我认为就是三件事： 了解为什么要学习Java集合 学习Java集合的各个接口以及常用的实现类用法 学习常用实现类的数据结构是什么，能在写代码的时候选择一个合适的实现类装载自己的对象。零基础入门不需要阅读源码，面试前一定要回顾和阅读源码（这是面试必考的知识点）！如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y二、Collection一、集合(Collection)介绍1.1为什么需要Collection1. Java是一门面向对象的语言，就免不了处理对象2. 为了方便操作多个对象，那么我们就得把这多个对象存储起来3. 想要存储多个对象(变量),很容易就能想到一个容器4. 常用的容器我们知道有-StringBuffered,数组(虽然有对象数组，但是数组的长度是不可变的！)5. 所以，Java就为我们提供了集合(Collection)1.2数组和集合的区别接下来，我们可以对数组和集合的区别来分析一下：数组和集合的区别: 1:长度的区别 数组的长度固定 集合的长度可变 2:内容不容 数组存储的是同一种类型的元素 集合可以存储不同类型的元素(但是一般我们不这样干.) 3:元素的数据类型 数组可以存储基本数据类型,也可以存储引用类型 集合只能存储引用类型(你存储的是简单的int，它会自动装箱成Integer)1.3Collection的由来与功能Collection的由来： 集合可以存储多个元素,但我们对多个元素也有不同的需求 多个元素,不能有相同的 多个元素,能够按照某个规则排序 针对不同的需求：java就提供了很多集合类，多个集合类的数据结构不同。但是，结构不重要，重要的是能够存储东西,能够判断,获取 把集合共性的内容不断往上提取,最终形成集合的继承体系-CollectionCollection的大致结构体系是这样的：但是，一般我们要掌握的并不需要那么多，只需要掌握一些常用的集合类就行了。下面我圈出来的那些：再次精减：Collection的基础功能：二、迭代器(Iterator)介绍我们可以发现Collection的源码中继承了Iterable，有iterator()这个方法.点进去看了一下，Iterable是一个接口：它有iterator()这个方法，返回的是Iterator再来看一下，Iterator也是一个接口，它只有三个方法： hasNext() next() remove()可是，我们没能找到对应的实现方法，只能往Collection的子类下找找了，于是我们找到了-ArrayList(该类后面会说)于是，我们在ArrayList下找到了iterator实现的身影：它是在ArrayList以内部类的方式实现的！并且，从源码可知：Iterator实际上就是在遍历集合所以说：我们遍历集合(Collection)的元素都可以使用Iterator，至于它的具体实现是以内部类的方式实现的！如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y三、List集合介绍从上面已经可以看到了，Collection主要学习集合的类型两种：Set和List，这里主要讲解List！我们来看一下List接口的方法，比Collection多了一点点： List集合的特点就是：有序(存储顺序和取出顺序一致),可重复Collection返回的是Iterator迭代器接口，而List中又有它自己对应的实现-ListIterator接口该接口比普通的Iterator接口多了几个方法：从方法名就可以知道：ListIterator可以往前遍历，添加元素，设置元素3.1List集合常用子类List集合常用的子类有三个： ArrayList 底层数据结构是数组。线程不安全 LinkedList 底层数据结构是链表。线程不安全 Vector 底层数据结构是数组。线程安全现在知道有三个常用的集合类即可，后面会开新的文章来讲解的四、Set集合介绍从Set集合的方法我们可以看到：方法没有比Collection要多 Set集合的特点是：元素不可重复4.1Set集合常用子类 HashSet集合 A:底层数据结构是哈希表(是一个元素为链表的数组) TreeSet集合 A:底层数据结构是红黑树(是一个自平衡的二叉树) B:保证元素的排序方式 LinkedHashSet集合 A:：底层数据结构由哈希表和链表组成。如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y三、List集合现在这篇主要讲List集合的三个子类： ArrayList 底层数据结构是数组。线程不安全 LinkedList 底层数据结构是链表。线程不安全 Vector 底层数据结构是数组。线程安全这篇主要来看看它们比较重要的方法是如何实现的，需要注意些什么，最后比较一下哪个时候用哪个一、ArrayList解析首先，我们来讲解的是ArrayList集合，它是我们用得非常非常多的一个集合首先，我们来看一下ArrayList的属性：根据上面我们可以清晰的发现：ArrayList底层其实就是一个数组，ArrayList中有扩容这么一个概念，正因为它扩容，所以它能够实现“动态”增长1.1构造方法我们来看看构造方法来印证我们上面说得对不对：1.2Add方法add方法可以说是ArrayList比较重要的方法了，我们来总览一下：1.2.1add(E e)步骤： 检查是否需要扩容 插入元素首先，我们来看看这个方法： public boolean add(E e) ensureCapacityInternal(size + 1); / Increments modCount! elementDatasize+ = e; return true; 该方法很短，我们可以根据方法名就猜到他是干了什么： 确认list容量，尝试容量加1，看看有无必要 添加元素接下来我们来看看这个小容量(+1)是否满足我们的需求：随后调用ensureExplicitCapacity()来确定明确的容量，我们也来看看这个方法是怎么实现的：所以，接下来看看grow()是怎么实现的进去看copyOf()方法：到目前为止，我们就可以知道add(E e)的基本实现了： 首先去检查一下数组的容量是否足够 足够：直接添加 不足够：扩容 扩容到原来的1.5倍 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。1.2.2add(int index, E element)步骤： 检查角标 空间检查，如果有需要进行扩容 插入元素我们来看看插入的实现：我们发现，与扩容相关ArrayList的add方法底层其实都是arraycopy()来实现的看到arraycopy()，我们可以发现：该方法是由C/C+来编写的，并不是由Java实现：总的来说：arraycopy()还是比较可靠高效的一个方法。1.3 get方法 检查角标 返回元素/ 检查角标private void rangeCheck(int index) if (index = size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index);/ 返回元素E elementData(int index) return (E) elementDataindex;1.4 set方法步骤： 检查角标 替代元素 返回旧值1.5remove方法步骤： 检查角标 删除元素 计算出需要移动的个数，并移动 设置为null，让Gc回收1.6细节再说明 ArrayList是基于动态数组实现的，在增删时候，需要数组的拷贝复制。 ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍 删除元素时不会减少容量，若希望减少容量则调用trimToSize() 它不是线程安全的。它能存放null值。如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y二、Vector与ArrayList区别Vector是jdk1.2的类了，比较老旧的一个集合类。Vector底层也是数组，与ArrayList最大的区别就是：同步(线程安全)Vector是同步的，我们可以从方法上就可以看得出来在要求非同步的情况下，我们一般都是使用ArrayList来替代Vector的了如果想要ArrayList实现同步，可以使用Collections的方法：List list = Collections.synchronizedList(new ArrayList(.);，就可以实现同步了还有另一个区别： ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。、三、LinkedList解析LinkedList底层是双向链表如果对于链表不熟悉的同学可先看看我的单向链表(双向链表的练习我还没做)【Java实现单向链表】理解了单向链表，双向链表也就不难了。从结构上，我们还看到了LinkedList实现了Deque接口，因此，我们可以操作LinkedList像操作队列和栈一样LinkedList变量就这么几个，因为我们操作单向链表的时候也发现了：有了头结点，其他的数据我们都可以获取得到了。(双向链表也同理)3.1构造方法LinkedList的构造方法有两个：3.2add方法如果做过链表的练习，对于下面的代码并不陌生的 add方法实际上就是往链表最后添加元素 public boolean add(E e) linkLast(e); return true; void linkLast(E e) final Node l = last; final Node newNode = new Node(l, e, null); last = newNode; if (l = null) first = newNode; else l.next = newNode; size+; modCount+; 3.3remove方法实际上就是下面那个图的操作：3.4get方法可以看到get方法实现就两段代码： public E get(int index) checkElementIndex(index); return node(index).item; 我们进去看一下具体的实现是怎么样的：3.5set方法set方法和get方法其实差不多，根据下标来判断是从头遍历还是从尾遍历 public E set(int index, E element) checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = element; return oldVal; 四、List集合总结其实集合的源码看起来并不是很困难，遇到问题可以翻一翻，应该是能够看懂的ArrayList、LinkedList、Vector算是在面试题中比较常见的的知识点了。下面我就来做一个简单的总结：ArrayList： 底层实现是数组 ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍 在增删时候，需要数组的拷贝复制(navite 方法由C/C+实现)LinkedList： 底层实现是双向链表双向链表方便实现往前遍历Vector： 底层是数组，现在已少用，被ArrayList替代，原因有两个： Vector所有方法都是同步，有性能损失。 Vector初始length是10 超过length时 以100%比率增长，相比于ArrayList更多消耗内存。总的来说：查询多用ArrayList，增删多用LinkedList。ArrayList增删慢不是绝对的(在数量大的情况下，已测试)： 如果增加元素一直是使用add()(增加到末尾)的话，那是ArrayList要快 一直删除末尾的元素也是ArrayList要快【不用复制移动位置】 至于如果删除的是中间的位置的话，还是ArrayList要快！但一般来说：增删多还是用LinkedList，因为上面的情况是极端的如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y四、Map集合一、Map介绍1.1为什么需要Map前面我们学习的Collection叫做集合，它可以快速查找现有的元素。而Map在Core Java中称之为-映射.映射的模型图是这样的：那为什么我们需要这种数据存储结构呢？举个例子 作为学生来说，我们是根据学号来区分不同的学生。只要我们知道学号，就可以获取对应的学生信息。这就是Map映射的作用！生活中还有很多这样的例子：只要你掏出身份证(key)，那就可以证明是你自己(value)1.2Map与Collection的区别1.3Map的功能下面我们来看看Map的源码：简单常用的Map功能有这么一些：下面用红色框框圈住的就是Map值得关注的子类：二、散列表介绍无论是Set还是Map，我们会发现都会有对应的-HashSet,HashMap首先我们也先得回顾一下数据和链表： 链表和数组都可以按照人们的意愿来排列元素的次序，他们可以说是有序的(存储的顺序和取出的顺序是一致的) 但同时，这会带来缺点：想要获取某个元素，就要访问所有的元素，直到找到为止。 这会让我们消耗很多的时间在里边，遍历访问元素而还有另外的一些存储结构：不在意元素的顺序，能够快速的查找元素的数据 其中就有一种非常常见的：散列表2.1散列表工作原理散列表为每个对象计算出一个整数，称为散列码。根据这些计算出来的整数(散列码)保存在对应的位置上！在Java中，散列表用的是链表数组实现的，每个列表称之为桶。【之前也写过桶排序就这么简单，可以回顾回顾】一个桶上可能会遇到被占用的情况(hashCode散列码相同，就存储在同一个位置上)，这种情况是无法避免的，这种现象称之为：散列冲突 此时需要用该对象与桶上的对象进行比较，看看该对象是否存在桶子上了如果存在，就不添加了，如果不存在则添加到桶子上 当然了，如果hashcode函数设计得足够好，桶的数目也足够，这种比较是很少的 在JDK1.8中，桶满时会从链表变成平衡二叉树如果散列表太满，是需要对散列表再散列，创建一个桶数更多的散列表，并将原有的元素插入到新表中，丢弃原来的表 装填因子(load factor)决定了何时对散列表再散列 装填因子默认为0.75，如果表中超过了75%的位置已经填入了元素，那么这个表就会用双倍的桶数自动进行再散列当然了， 在后面阅读源码的时候会继续说明的，现在简单了解一下即可如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y三、红黑树介绍上面散列表中已经提过了：如果桶数满的时候，JDK8是将链表转成红黑树的。并且，我们的TreeSet、TreeMap底层都是红黑树来实现的。所以，在这里学习一波红黑树到底是啥玩意。在未学习之前，我们可能是听过红黑树这么一个数据结构类型的，还有其他什么B/B+树等等，反正是比较复杂的数据结构了各种常见的树的用途：3.1回顾二叉查找树首先我们来回顾一下：利用二叉查找树的特性，我们一般来说可以很快地查找出对应的元素。可是二叉查找树也有个例(最坏)的情况(线性)：上面符合二叉树的特性，但是它是线性的，完全没树的用处树是要“均衡”才能将它的优点展示出来的，比如下面这种：因此，就有了平衡树这么一个概念红黑树就是一种平衡树，它可以保证二叉树基本符合矮矮胖胖(均衡)的结构3.2知新2-3树讲到了平衡树就不得不说最基础的2-3树，2-3树长的是这个样子：在二叉查找树上，我们插入节点的过程是这样的：小于节点值往右继续与左子节点比，大于则继续与右子节点比，直到某节点左或右子节点为空，把值插入进去。这样无法避免偏向问题而2-3树不一样：它插入的时候可以保持树的平衡！在2-3树插入的时可以简单总结为两个操作： 合并2-节点为3-节点，扩充将3-节点扩充为一个4-节点 分解4-节点为3-节点，节点3-节点为2-节点 .至使得树平衡合并分解的操作还是比较复杂的，要分好几种情况，代码量很大这里我就不介绍了，因为要学起来是一大堆的，很麻烦3.3从2-3树到红黑树由于2-3树为了保持平衡性，在维护的时候是需要大量的节点交换的！这些变换在实际代码中是很复杂的，大佬们在2-3树的理论基础上发明了红黑树(2-3-4树也是同样的道理，只是2-3树是最简单的一种情况，所以我就不说2-3-4树了)。 红黑树是对2-3查找树的改进，它能用一种统一的方式完成所有变换。红黑树是一种平衡二叉树,因此它没有3-节点。那红黑树是怎么将3-节点来改进成全都是二叉树呢？红黑树就字面上的意思，有红色的节点，有黑色的节点：我们可以将红色节点的左链接画平看看：一颗典型的二叉树：将红色节点的左链接画平之后：得到2-3平衡树:3.4红黑树基础知识前面已经说了，红黑树是在2-3的基础上实现的一种树，它能够用统一的方式完成所有变换。很好理解：红黑树也是平衡树的一种，在插入元素的时候它也得保持树的平衡，那红黑树是以什么的方式来保持树的平衡的呢？红黑树用的是也是两种方式来替代2-3树不断的节点交换操作： 旋转：顺时针旋转和逆时针旋转 反色：交换红黑的颜色 这个两个实现比2-3树交换的节点(合并，分解)要方便一些红黑树为了保持平衡，还有制定一些约束，遵守这些约束的才能叫做红黑树：1. 红黑树是二叉搜索树。2. 根节点是黑色。3. 每个叶子节点都是黑色的空节点（NIL节点）。4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(每一条树链上的黑色节点数量（称之为“黑高”）必须相等)。如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y五、HashMap一、HashMap剖析首先看看HashMap的顶部注释说了些什么：再来看看HashMap的类继承图：下面我们来看一下HashMap的属性：成员属性有这么几个：再来看一下hashMap的一个内部类Node：我们知道Hash的底层是散列表，而在Java中散列表的实现是通过数组+链表的再来简单看看put方法就可以印证我们的说法了：数组+链表-散列表我们可以简单总结出HashMap： 无序，允许为null，非同步 底层由散列表(哈希表)实现 初始容量和装载因子对HashMap影响挺大的，设置小了不好，设置大了也不好1.1HashMap构造方法HashMap的构造方法有4个：在上面的构造方法最后一行，我们会发现调用了tableSizeFor()，我们进去看看：看完上面可能会感到奇怪的是：为啥是将2的整数幂的数赋给threshold？ threshold这个成员变量是阈值，决定了是否要将散列表再散列。它的值应该是：capacity * load factor才对的。其实这里仅仅是一个初始化，当创建哈希表的时候，它会重新赋值的：至于别的构造方法都差不多，这里我就不细讲了：1.2put方法put方法可以说是HashMap的核心，我们来看看：我们来看看它是怎么计算哈希值的：为什么要这样干呢？我们一般来说直接将key作为哈希值不就好了吗，做异或运算是干嘛用的？我们看下来：我们是根据key的哈希值来保存在散列表中的，我们表默认的初始容量是16，要放到散列表中，就是0-15的位置上。也就是tabi = (n - 1) & hash。可以发现的是：在做&运算的时候，仅仅是后4位有效那如果我们key的哈希值高位变化很大，低位变化很小。直接拿过去做&运算，这就会导致计算出来的Hash值相同的很多。而设计者将key的哈希值的高位也做了运算(与高16位做异或运算，使得在做&运算时，此时的低位实际上是高位与低位的结合)，这就增加了随机性，减少了碰撞冲突的可能性！下面我们再来看看流程是怎么样的：新值覆盖旧值，返回旧值测试：接下来我们看看resize()方法，在初始化的时候要调用这个方法，当散列表元素大于capacity * load factor的时候也是调用resize()1.3get方法接下来我们看看getNode()是怎么实现的：1.4remove方法再来看看removeNode()的实现：二、HashMap与Hashtable对比从存储结构和实现来讲基本上都是相同的。它和HashMap的最大的不同是它是线程安全的，另外它不允许key和value为null。Hashtable是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换三、HashMap总结在JDK8中HashMap的底层是：数组+链表(散列表)+红黑树在散列表中有装载因子这么一个属性，当装载因子*初始容量小于散列表元素时，该散列表会再散列，扩容2倍！装载因子的默认值是0.75，无论是初始大了还是初始小了对我们HashMap的性能都不好 装载因子初始值大了，可以减少散列表再散列(扩容的次数)，但同时会导致散列冲突的可能性变大(散列冲突也是耗性能的一个操作，要得操作链表(红黑树)！ 装载因子初始值小了，可以减小散列冲突的可能性，但同时扩容的次数可能就会变多！初始容量的默认值是16，它也一样，无论初始大了还是小了，对我们的HashMap都是有影响的： 初始容量过大，那么遍历时我们的速度就会受影响 初始容量过小，散列表再散列(扩容的次数)可能就变得多，扩容也是一件非常耗费性能的一件事从源码上我们可以发现：HashMap并不是直接拿key的哈希值来用的，它会将key的哈希值的高16位进行异或操作，使得我们将元素放入哈希表的时候增加了一定的随机性。还要值得注意的是：并不是桶子上有8位元素的时候它就能变成红黑树，它得同时满足我们的散列表容量大于64才行的如果档中有任何的不懂的问题，都可以直接来找我询问，我乐意帮助你们！微信搜Java3y公众号有我的联系式。更多原创技术章可关注我的GitHub：/ZhongFuCheng3y/3y六、LinkedHashMap一、LinkedHashMap首先我们来看看类继承图：我简单翻译了一下顶部的注释(我英文水平渣，如果有错的地方请多多包涵欢迎在评论区下指正)从顶部翻译我们就可以归纳总结出LinkedHashMap几点： 底层是散列表和双向链表 允许为null，不同步 插入的顺序是有序的(底层链表致使有序) 装载因子和初始容量对LinkedHashMap影响是很大的同时也给我带了几个疑问： access-ordered和insertion-ordered具体的使用和意思 为什么说初始容量对遍历没有影响？希望可以在看源码的过程中可以解决掉我这两个疑问那接下来就开始吧1.1LinkedHashMap的域1.2LinkedHashMap重写的方法下面我列举就这两个比较重要的：这就印证了我们的LinkedHashMap底层确确实实是散列表和双向链表 在构建新节点时，构建的是LinkedHashMap.Entry 不再是Node.1.3构造方法可以发现，LinkedHashMap有5个构造方法：下面我们来看看构造方法的定义是怎么样的：从构造方法上我们可以知道的是：LinkedHashMap默认使用的是插入顺序1.4put方法原本我是想要找put方法，看看是怎么实现的，后来没找着，就奇了个怪再顿了一下，原来LinkedHashMap和HashMap的put方法是一样的！LinkedHashMap继承着HashMap，LinkedHashMap没有重写HashMap的put方法所以，LinkedHashMap的put方法和HashMap是一样的。当然了，在创建节点的时候，调用的是LinkedHashMap重写的方法1.5get方法get方法也是多了：判断是否为访问顺序讲到了这里，感觉我们可以简单测试一波了：首先我们来看看已插入顺序来进行插入和遍历： public static void insertOrder() / 默认是插入顺序 LinkedHashMap insertOrder = new LinkedHashMap(); String value = 关注公众号Java3y; int i = 0; insertOrder.put(i+, value); insertOrder.put(i+, value); insertOrder.put(i+, value); insertOrder.put(i+, value); insertOrder.put(i+, value); /遍历 Set set = insertOrder.keySet(); for (Integer s : set) String mapValue = insertOrder.get(s); System.out.println(s + - + mapValue); 测试一波：接着，我们来测试一下以访问顺序来进行插入和遍历： public static void accessOrder() / 设置为访问顺序的方式 LinkedHashMap accessOrder = new LinkedHashMap(16, 0.75f, true); String value = 关注公众号Java3y; int i = 0; accessOrder.put(i+, value); accessOrder.put(i+, value); accessOrder.put(i+, value); accessOrder.put(i+, value); accessOrder.put(i+, value); / 遍历 Set sets = accessOrder.keySet(); for (Integer key : sets) String mapValue = accessOrder.get(key); System.out.println(key + - + mapValue); 代码看似是没有问题，但是运行会出错的！前面在看源码注释的时候我们就发现了：在AccessOrder的情况下，使用get方法也是结构性的修改！为了简单看出他俩的区别，下面我就直接用key来进行看了以下是访问顺序的测试： public static void accessOrder() / 设置为访问顺序的方式 LinkedHashMap accessOrder = new LinkedHashMap(16, 0.75f, true); String value = 关注公众号Java3y; int i = 0; accessOrder.put(i+, value); accessOrder.put(i+, value); accessOrder.put(i+, value); accessOrder.put(i+, value); accessOrder.put(i+, value); / 访问一下key为3的元素再进行遍历 accessOrder.get(3); / 遍历 Set sets = access