购物网站开发流程,全网软文推广,网站建设域名服务器,专业设计网站推荐目录
集合源码详解
一、常见数据结构讲解
1. 线性数据结构
1.1 数组
1.2 队列
1.3 链表
1.3.1 单向链表
1.3.2 双向链表
1.4 栈
2. 非线性数据结构
2.1 树
2.2 二叉树
2.2.1 概念介绍
2.2.2 遍历操作
2.2.3 删除节点
2.2.4 查找局限性
2.2.5 AVL#xff08; …目录
集合源码详解
一、常见数据结构讲解
1. 线性数据结构
1.1 数组
1.2 队列
1.3 链表
1.3.1 单向链表
1.3.2 双向链表
1.4 栈
2. 非线性数据结构
2.1 树
2.2 二叉树
2.2.1 概念介绍
2.2.2 遍历操作
2.2.3 删除节点
2.2.4 查找局限性
2.2.5 AVL 高度平衡树
2.3 2-3-4树
1 概念介绍
2 生成的过程
3 和红黑树的等价关系
3.1 2节点
3.2 3节点
3.3 4节点
3.4 裂变状态
4 转换为红黑树
2.4 红黑树
1 旋转操作
1.1 概念讲解
1.2 代码实现
2 新增节点
2.1 新增节点示例
2.2 新增代码实现
2.3 插入节点
3.红黑树删除节点
1.删除节点
2.删除后的平衡调整
2.5 B树和B树
2.5.1 B树
2.5.2 B树
二、集合API源码分析
1. 集合概述
2. ArrayList详解
2.1 类图结构
2.2 源码分析
2.2.1 声明的属性
2.2.2 构造方法
2.2.3 添加方法
3. Vector
3.1 类图结构
3.2 和ArrayList的区别
4. HashSet
4.1 类图结构
4.2 HashSet的本质
5.TreeSet
5.1 类图结构
5.2 TreeSet的本质
6.TreeMap
6.1 类图结构
6.2 源码分析
6.2.1 成员变量
6.2.2 put方法
7. HashMap
7.1 设计原理
7.1.1 JDK1.7
7.1.2 JDK1.8
7.1.3 扩容
7.2 源码分析
7.2.1 成员变量
7.2.2 构造方法
7.2.3 put方法
7.2.4 treeifyBin()
7.2.5 扩容方法
7.2.6 remove方法
7.2.7 get方法
7.3 面试相关 集合源码详解
一、常见数据结构讲解
1. 线性数据结构 线性表:顾名思义线性表就是数据排成像一条线的结构。每个线性表上的数据最多只有前和后两个方向。线性表结构数组、链表、队列、栈
1.1 数组 数组Array是一种线性表数据结构。它用一组连续的内存空间来存储一组具有相同类型的数据。
// 动态初始化初始化时由程序员只指定数组长度由系统为数组元素分配初始值
char c1[] new char[5];
// 静态初始化 初始化时由程序员显示置顶每个数组的初始值由系统决定数组长度
char c2[] new char[]{E,D,U,Y,U};
char c3[] {E,D,U,Y,U};
具有如下的特点 内存地址连续 可以通过下标的成员访问,下标访问的性能高 增删操作带来更大的性能消耗(保证数据越界的问题,需动态扩容) 1.2 队列 队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。 队列中数据的特点先进先出后进后出。
队列的操作允许插入的一端称为队尾允许删除的一端称为队头。我们可以将其想象成一个链表队头就是这个链表中的第一个节点队尾就是这个链表中的最后一个节点然而我们只能对这个链表进行 尾插、头删操作。 数据结构演示地址Data Structure Visualization 入队列 出队列 Java代码测试实现 public static void main(String[] args) {QueueInteger queue new LinkedList();queue.offer(3);//尾插queue.offer(6);queue.offer(9);queue.offer(12);System.out.println(queue);System.out.println(queue.peek());//访问队列头元素System.out.println(queue);System.out.println(queue.poll());//删除队列头元素System.out.println(queue);}
输出结果
[3, 6, 9, 12]
3
[3, 6, 9, 12]
3
[6, 9, 12]
1.3 链表 链表也是线性的顺序存储数据。只是在内存地址上不是连续的每一个节点里存到下一个节点的指针(Pointer).
1.3.1 单向链表 单向链表(单链表)是链表的一种它由节点组成每个节点都包含下一个节点的指针下图就是一个单链表表头为空表头的后继节点是结点10(数据为10的结点)“节点10的后继结点是节点20”(数据为20的结点) 然后我们来看下删除链表的操作比如删除30这个节点 在上面的结构基础上我们再来添加一个节点到链表中 1.3.2 双向链表 双向链表(双链表)是链表的一种。和单链表一样双链表也是由节点组成它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 双链表的示意图如下 双向链表的具体实现可以参考: static final class Node {// 前一个节点volatile Node prev;// 后一个节点volatile Node next;// 链表节点存储的具体数据volatile Thread thread;}
我们看看双向链表删除节点的操作比如说下面这个双向链表中我们要删除节点30。
删除之前“节点20的后继节点为节点30”“节点30” 的前继节点为节点20。“节点30的后继节点为节点40”“节点40” 的前继节点为节点30。
删除之后“节点20的后继节点为节点40”“节点40” 的前继节点为节点20。 我们再来看看双向链表添加节点的操作比如说下面这个双向链表在节点10与节点20之间添加节点15
添加之前“节点10的后继节点为节点20”“节点20” 的前继节点为节点10。
添加之后“节点10的后继节点为节点15”“节点15” 的前继节点为节点10。“节点15的后继节点为节点20”“节点20” 的前继节点为节点15。 1.4 栈 栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说表尾端称为栈顶top表头端称为栈低bottom。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除所以栈又被称为后进先出的线性表简称LIFO:Last in, First out.结构。 2. 非线性数据结构 非线性表:与线性表对立在非线性表之中数据之间并不是简单的前后关系。非线性表结构二叉树、堆、图等。
2.1 树 树[Tree]是nn0)个结点的有限集。n0时称为空树。在任意一颗非空树中 有且仅有一个特定的节点称为根[Root]的结点 当n1时其余结点可分为m(m0)个互不相交的有限集T1、T2、…、Tn其中每一个集合本身又是一棵树并且称为根的子树。 此外树的定义还需要强调以下两点 根结点是唯一的不可能存在多个根结点数据结构中的树只能有一个根结点。 子树的个数没有限制但它们一定是互不相交的。
如图是一棵普通树 度数结点拥有的子树的 数目称为结点的 度 。 节点关系 孩子结点 双亲结点 兄弟结点
节点层次 从根开始定义起根为第一层根的孩子为第二层以此类推。 树的深度树中结点的最大层次如上图深度为4 2.2 二叉树
2.2.1 概念介绍 二叉树 每个子节点只有两个子节点的树每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)并且二叉树的子树有左右之分其次序不能任意颠倒。 二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质 任意节点左子树不为空,则左子树的值均小于根节点的值 任意节点右子树不为空,则右子树的值均大于于根节点的值 任意节点的左右子树也分别是二叉查找树 没有键值相等的节点
二叉树又分为 完美二叉树 完全二叉树 完满二叉树
完美二叉树又称为 满二叉树 除了叶子节点之外的每一个节点都有两个孩子节点每层都被完全填充 完全二叉树:除了最后一层之外的其他每一层都被完全填充并且所有的节点都保持向左对齐 完满二叉树除了叶子节点之外的每一个节点都有两个孩子节点。 2.2.2 遍历操作
二叉树中的遍历规则有如下三种
中序遍历所谓的中序遍历就是先访问左节点再访问根节点最后访问右节点即左-根-右遍历
先序遍历所谓的前序遍历就是先访问根节点再访问左节点最后访问右节点即根-左-右遍历(前序)
后序遍历所谓的后序遍历就是先访问左节点再访问右节点最后访问根节点。即左-右-根遍历 查找最小值沿着根节点的左子树一路查找直到最后一个不为空的节点该节点就是当前这个树的最小节点
查找最大值沿着根节点的右子树一路查找直到最后一个不为空的节点该节点就是当前这个树的最大节点
查找前驱节点 小于当前节点的最大值
查找后继节点 大于当前节点的最小值 2.2.3 删除节点 二叉树中的删除节点本质上是找前驱节点或者后继节点来替代 叶子节点直接删除 只有一个子节点的用子节点替代(本质上就是找的前驱节点或者后继节点左节点就是前驱节点右节点就是后继节点) 有两个子节点的需要找到替代节点(替代节点就是前驱节点或者后继节点)
2.2.4 查找局限性 一个二叉查找树是由n个节点随机构成,所以对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图: 2.2.5 AVL 高度平衡树 BST存在的问题是树在插入的时候会导致倾斜不同的插入顺序会导致数的高度不一样而树的高度直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上这样树的高度为N。基于BST存在的问题平衡查找二叉树Balanced BST产生了。平衡树的插入和删除的时候会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树高度平衡树具备二叉搜索树的全部特性而且左右子树高度差不超过1和红黑树。 AVL树是如何实现平衡的呢具体是通过左旋或者右旋来实现的。具体如下图 过程细节如下 虽然AVL可以解决二叉树所存在的问题但是AVL树要求太过严格左旋和右旋的开销会比较大这时出现了红黑树只要求黑色节点(具有子节点的节点)平衡即可不用那么要求所有节点都平衡。 2.3 2-3-4树
1 概念介绍 2-3-4树是四阶的 B树(Balance Tree)他属于一种多路查找树它的结构有以下限制 所有叶子节点都拥有相同的深度。 节点只能是 2-节点、3-节点、4-节点之一。 2-节点包含 1 个元素的节点有 2 个子节点 3-节点包含 2 个元素的节点有 3 个子节点 4-节点包含 3 个元素的节点有 4 个子节点 所有节点必须至少包含1个元素 元素始终保持排序顺序整体上保持二叉查找树的性质即父结点大于左子结点小于右子结点 而且结点有多个元素时每个元素必须大于它左边的和它的左子树中元素。
下图是一个典型的 2-3-4树
2 生成的过程 接下来我们通过演示来看看2-3-4树生成的过程 第一次插入---2节点值为2 的节点
插入第二个节点--3节点这里指值为3 的节点 合并
插入第三个节点---4节点这里指值为4 的节点 合并
插入第4个节点---因为最多的是三个节点所以需要分裂
插入6
插入7
插入8 插入9
插入10
插入11 3 5 7 9 变成四个了提一个为父节点
插入12 最后我们插入1来看看效果 到这儿相信大家对于2-3-4树应该有了个直观的认知了。
3 和红黑树的等价关系 红黑树起源于2-3-4树它的本质就是2-3-4树。
3.1 2节点 一个2节点对应的红黑树节点就是一个黑色节点 3.2 3节点 一个三节点可以有两种情况的红黑树节点一种是右倾一种是左倾所以一个2-3-4树可以有多个红黑树
原则上黑下红
3.3 4节点 一个四节点转换的情况只有一种中间节点黑色左右节点红色
3.4 裂变状态 还有就是在2-3-4树中存在的裂变状态。转换为红黑树后会先变色(不能有两个相邻的红色节点)。
4 转换为红黑树 接下来具体看看一个2-3-4树是如何转换为对应的红黑树的
原始的2-3-4树 按照右倾规则来转换为 转换后满足黑色节点平衡的要求 按照左倾规则来转换为
2.4 红黑树 红黑树Red-Black Tree 「RBT」是一个自平衡(随着添加节点的不同它自己去维护自身黑节点的平衡不用个人为外部去干预处理当然不是绝对的平衡)的二叉查找树(BST)树上的每个节点都遵循下面的规则: 每个节点要么是黑色要么是红色。 根节点是黑色。 每个叶子节点是黑色。 每个红色结点的两个子结点一定都是黑色。 任意一结点到每个叶子结点的路径都包含数量相同的黑结点即黑节点的自平衡。 红黑树能自平衡它靠的是什么三种操作左旋、右旋和变色
操作描述左旋以某个结点作为支点(旋转结点)其右子结点变为旋转结点的父结点 右子结点的左子结点变为旋转结点的右子结点左子结点保持不变。右旋以某个结点作为支点(旋转结点)其左子结点变为旋转结点的父结点 左子结点的右子结点变为旋转结点的左子结点右子结点保持不变。变色结点的颜色由红变黑或由黑变红。
1 旋转操作
1.1 概念讲解 左旋以某个节点作为旋转点其右子节点变为旋转节点的父节点右子节点的左子节点变为旋转节点的右子节点左子节点保持不变。 右旋以某!个节点作为旋转点其左子节点变为旋转节点的父节点左子节点的右子节点变为旋转节点的左子节点右子节点保持不变。
1.2 代码实现 先进行类结构定义
package com.bobo.util.treemap;public class BRTree {private static final boolean RED false;private static final boolean BLACK true;private RBNode root;public RBNode getRoot() {return root;}public void setRoot(RBNode root) {this.root root;}/*** 表示 节点* param K* param V*/static class RBNodeK extends ComparableK,V{// 节点是双向的private RBNode parent;private RBNode left;private RBNode right;private boolean color;private K key;private V value;public RBNode() {}public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {this.parent parent;this.left left;this.right right;this.color color;this.key key;this.value value;}public RBNode getParent() {return parent;}public void setParent(RBNode parent) {this.parent parent;}public RBNode getLeft() {return left;}public void setLeft(RBNode left) {this.left left;}public RBNode getRight() {return right;}public void setRight(RBNode right) {this.right right;}public boolean isColor() {return color;}public void setColor(boolean color) {this.color color;}public K getKey() {return key;}public void setKey(K key) {this.key key;}public V getValue() {return value;}public void setValue(V value) {this.value value;}}
}左旋代码实现 /*** 围绕p左旋* p pr(r)* / | / \* pl pr(r) p rr* / \ / \* rl rr pl rl** 左旋的时候* p-pl 和 pr-rr的关系不变* pr-rl 要变为 p-rl* 也就是 rl要变为 p的右子节点* 同时 p要成为 rl 的父节点* 还有就是要判断 p 是否有父节点* 如果没有* r 变为 root 节点* 如果有* r.parent p.parent* 还要设置 r为 p.parent 的子节点(可能左也可能右)* 如果 p.parent.left p* p.parent.left r;* 否则* p.parent.right r;* 最后* p.parent r;* r.left p;* param p*/private void leftRotate(RBNode p){if(p ! null){RBNode r p.right;// 1.设置 pr-rl 要变为 p-rl// 把rl设置到p的右子节点p.right r.left;if(r.left ! null){// 设置rl的父节点为pr.left.parent p;}// 2.判断p的父节点情况r.parent p.parent; // 不管 p是否有父节点都把这个父节点设置为 r的父节点if(p.parent null){root r; // p没有父节点 则r为root节点}else if(p.parent.left p){p.parent.left r; // 如果p为 p.parent的左子节点 则 r 也为 p.parent的左子节点}else{p.parent.right r; // 反之设置 r 为 p.parent的右子节点}// 最后 设置 p 为 r 的左子节点r.left p;p.parent r;}}
右旋实现 /*** 围绕p右旋* param p*/public void rightRotate(RBNode p){if(p ! null){RBNode r p.left;p.left r.right;if(r.right ! null){r.right.parent p;}r.parent p.parent;if(p.parent null){root r;}else if(p.parent.left p){p.parent.left r;}else{p.parent.right r;}r.right p;p.parent r;}}
2 新增节点 未命名文件| ProcessOn免费在线作图,在线流程图,在线思维导图 2-3-4树中结点添加需要遵守以下规则 插入都是向最下面一层插入 升元将插入结点由 2-结点升级成 3-结点或由 3-结点升级成 4-结点 向 4-结点插入元素后需要将中间元素提到父结点升元原结点变成两个 2-结点再把元素插入2-结点中如果父结点也是 4-结点则递归向上层升元至到根结点后将树高加1 而将这些规则对应到红黑树里就是 新插入的结点颜色为 红色 这样才可能不会对红黑树的高度产生影响。 2-结点对应红黑树中的单个黑色结点插入时直接成功对应 2-结点升元。 3-结点对应红黑树中的 黑红 子树插入后将其修复成 红黑红 子树对应 3-结点升元 4-结点对应红黑树中的 红黑红 子树插入后将其修复成 红色祖父黑色父叔红色孩子 子树然后再把祖父结点当成新插入的红色结点递归向上层修复直至修复成功或遇到 root 结点 公式红黑树新增一个节点红色对等的2-3-4树新增一个节点
2.1 新增节点示例 我们通过新增2-3-4树的过程来映射对应的红黑树的节点新增
2-3-4树的新增全部在叶子节点完成
1.新增一个节点2 节点
2.新增一个节点与2节点合并直接合并
3.新增一个节点与3节点合并直接合并
插入的值的位置会有3种情况
对应的红黑树为
4.新增一个节点与4节点合并此时需要分裂
插入值的位置可能是
对应的红黑树的结构为
2.2 新增代码实现 红黑树的新增规则我们理清楚了接下来就可以通过Java代码来具体的实现了。
先实现插入节点这就是一个普通的二叉树的插入 /*** 新增节点* param key* param value*/public void put(K key , V value){RBNode t this.root;if(t null){// 说明之前没有元素现在插入的元素是第一个root new RBNode(key , value null ? key : value,null);return ;}int cmp ;// 寻找插入位置// 定义一个双亲指针RBNode parent;if(key null){throw new NullPointerException();}// 沿着跟节点找插入位置do{parent t;cmp key.compareTo((K)t.key);if(cmp 0){// 左侧找t t.left;}else if(cmp 0){// 右侧找t t.right;}else{// 插入节点的值比较的节点。值替换t.setValue(valuenull?key:value);return;}}while (t ! null);// 找到了插入的位置 parent指向 t 的父节点 t为null// 创建要插入的节点RBNodeK, Object e new RBNode(key, value null ? key : value, parent);// 然后判断要插入的位置 是 parent的 左侧还是右侧if(cmp 0){parent.left e;}else{parent.right e;}// 调整 变色 旋转fixAfterPut(e);}
然后再根据红黑树的特点来实现调整(旋转变色)
private boolean colorOf(RBNode node){return node null ? BLACK:node.color;}private RBNode parentOf(RBNode node){return node ! null ? node.parent:null;}private RBNode leftOf(RBNode node){return node ! null ? node.left:null;}private RBNode rightOf(RBNode node){return node ! null ? node.right:null;}private void setColor(RBNode node ,boolean color){if(node ! null){node.setColor(color);}}/*** 插入节点后的调整处理* 1. 2-3-4树 新增元素 2节点添加一个元素将变为3节点 直接合并节点中有两个元素* 红黑树新增一个红色节点这个红色节点会添加在黑色节点下(2节点) --- 这种情况不需要调整* 2. 2-3-4树 新增元素 3节点添加一个元素变为4节点合并 节点中有3个元素* 这里有6中情况( 根左左 根左右 根右右 根右左)这四种要调整 (左中右的两种)不需要调整* 红黑树新增红色节点 会添加到 上黑下红的节点中 排序后中间节点是黑色两边节点是红色** 3. 2-3-4树新增一个元素 4节点添加一个元素需要裂变中间元素升级为父节点新增元素与剩下的其中一个合并* 红黑树新增节点是红色爷爷节点是黑色父亲节点和叔叔节点为红色 调整为* 爷爷节点变红色父亲和叔叔节点变为黑色如果爷爷节点为root节点则调整为黑色* param x*/private void fixAfterPut(RBNodeK, Object x) {x.color RED;// 本质上就是父节点是黑色的就不需要调整对应的 2 3的情况while(x ! null x ! root x.parent.color RED){// 1. x 的父节点是爷爷的 左孩子if(parentOf(x) parentOf(parentOf(x)).left){// 获取当前节点的叔叔节点RBNode y rightOf(parentOf(parentOf(x)));// 情况3if(colorOf(y) RED){// 说明是 上3的情况 变色处理// 父亲节点和叔叔节点设置为黑色setColor(parentOf(x),BLACK);setColor(y,BLACK);// 爷爷节点设置为 红色setColor(parentOf(parentOf(x)),RED);// 递归处理x parentOf(parentOf(x));}else{// 情况 2if(x parentOf(x).right){// 如果x是父节点的右节点那么我们需要先根据 父节点 左旋x parentOf(x);leftRotate(x);}// 叔叔节点为空 对应于 上面的情况2// 将父节点变为黑色setColor(parentOf(x),BLACK);// 将爷爷节点变为红色setColor(parentOf(parentOf(x)),RED);// 右旋转 根据爷爷节点右旋转rightRotate(parentOf(parentOf(x)));}}else{// x 的父节点是爷爷是右孩子// 获取父亲的叔叔节点RBNode y leftOf(parentOf(parentOf(x)));if(colorOf(y) RED){// 情况3setColor(parentOf(x),BLACK);setColor(y,BLACK);setColor(parentOf(parentOf(x)),RED);x parentOf(parentOf(x));}else{// 情况2if( x parentOf(x).left){x parentOf(x);rightRotate(x);}setColor(parentOf(x),BLACK);setColor(parentOf(parentOf(x)),RED);leftRotate(parentOf(parentOf(x)));}}}root.color BLACK;}
2.3 插入节点 不通过2-3-4树来实现添加节点的分析看大家是否能理解哦 插入的场景
插入场景1红黑树为空树
最简单的一种情景直接把插入结点作为根结点就行但注意根据红黑树性质2根节点是黑色。还需要把插入结点设为黑色。处理把插入结点作为根结点并把结点设置为黑色。 插入场景2插入结点的父结点为黑结点 由于插入的结点是红色的且父节点为黑色节点并不会影响红黑树的平衡直接插入即可无需做自平衡。 处理直接插入。
插入场景3插入结点的父结点为红结点 再次回想下红黑树的性质2根结点是黑色。如果插入的父结点为红结点那么该父结点不可能为根结点所以插入结点总是存在祖父结点。这点很重要因为后续的旋转操作肯定需要祖父结点的参与。
插入场景3.1叔叔结点存在并且为红结点 从红黑树性质4可以祖父结点肯定为黑结点因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是黑红红。显然最简单的处理方式是把其改为红黑红。
实际案例
祖父节点为根节点红黑黑 祖父节点不为根节点 插入场景3.2叔叔结点不存在或为黑结点并且插入结点的父亲结点是祖父结点的左子结点 单纯从插入前来看也即不算情景3.1自底向上处理时的情况叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点而父结点为红结点那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了这不满足红黑树的性质5。后续情景同样如此不再多做说明了。
前文说了需要旋转操作时肯定一边子树的结点多了或少了需要租或借给另一边。插入显然是多的情况那么把多的结点租给另一边子树就可以了。
插入场景3.2.1插入结点是其父结点的左子结点 插入场景3.2.2叔叔结点不存在或为黑结点并且插入结点的父亲结点是祖父结点的右子结点 3.红黑树删除节点 红黑树的节点的删除其实也分为两步 先删除节点(这步和普通的二叉树删除是一样的) 然后再调整
1.删除节点 要删除这个节点先需要找到这个节点找到节点就是普通的二分查找具体代码如下 private RBNode getNode(K key){RBNode node this.root;while (node ! null ){int cmp key.compareTo((K) node.key);if(cmp 0){// 在左子树node node.left;}else if(cmp 0){// 右子树node node.right;}else{return node;}}return null;} 在整理红黑树节点的删除操作时我们需要先理解清楚红黑树删除和2-3-4树删除的等价关系这样理解起来才会比较容易 核心理论红黑树删除操作的本质其实就是删除2-3-4树的叶子节点 情况一
情况2删除的是非情况1的节点根据我们前面介绍的删除的规则会找到对应的前驱和后继节点那么最终删除的还是叶子节点
首先删除节点的代码为
/*** 删除节点* param key* return*/public V remove(K key){// 先找到这个节点RBNode node getNode(key);if(node null){return null;}// 把值存起来 删除后 返回V oldValue (V) node.value;deleteNode(node);return oldValue;}/*** 删除节点* 3种情况* 1.删除叶子节点直接删除* 2.删除的节点有一个子节点那么用子节点来替代* 3.如果删除的节点右两个子节点此时需要找到前驱节点或者后继节点来替代* 可以转换为 1、2的情况* param node*/private void deleteNode(RBNode node){// 3.node节点有两个子节点if(node.left !null node.right ! null){// 找到要删除节点的后继节点RBNode successor successor(node);// 然后用后继节点的信息覆盖掉 要删除节点的信息node.key successor.key;node.value successor.value;// 然后我们要删除的节点就变为了 后继节点node successor;}// 2.删除有一个子节点的情况RBNode replacement node.left ! null ? node.left : node.right;if(replacement ! null){// 替代者的父指针指向原来 node 的父节点replacement.parent node.parent;if(node.parent null){// 说明 node 是root节点root replacement;}else if(node node.parent.left){// 双向绑定node.parent.left replacement;}else{node.parent.right replacement;}// 将node的左右孩子指针和父指针都指向null node等待GCnode.left node.right node.parent null;// 替换完成后需要调整平衡if(node.color BLACK){// fixAfterRemove(replacement)}}else if(node.parent null){// 说明要删除的是root节点root null;}else{// 1. node节点是叶子节点 replacement为null// 先调整if(node.color BLACK){// fixAfterRemove(node)}// 再删除if(node.parent ! null){if(node node.parent.left){node.parent.left null;}else{node.parent.right null;}node null;}}}
然后就是需要调整红黑树的平衡了。
2.删除后的平衡调整
删除节点的调整操作
1.情况一自己能搞定的对应叶子节点是3节点和4节点
2.情况二自己搞不定需要兄弟借但是兄弟不借找父亲借父亲下来然后兄弟找一个人去代替父亲当家
这种情况就是兄弟节点是3节点或者4节点
找兄弟节点 如果找到的兄弟节点是红色其实还要调整
执行如下调整先,先变色然后左旋
找兄弟节点借 然后沿着7节点左旋 3.情况三跟兄弟借兄弟也没有情同手足同时自损
兄弟节点是2节点同时当前节点的父节点是红色节点的情况 删除后直接变色就可以了
兄弟节点是2节点同时当前节点的父节点是黑色节点 变更操作为如下如果继续有父节点那么还要递归处理
分析清楚了删除的3中情况我们就可以撸处删除的调整的代码了 /*** 2-3-4树删除操作* 1.情况一自己能搞定的对应叶子节点是3节点和4节点* 2.情况二自己搞不定需要兄弟借但是兄弟不借找父亲借父亲下来然后兄弟找一个人去代替父亲当家* 3.情况三跟兄弟借兄弟也没有* param x*/private void fixAfterRemove(RBNode x){// 情况2、3while(x ! root colorOf(x) BLACK){// 这种情况才需要调整// x 是左孩子的情况if(x leftOf(parentOf(x))){// 找兄弟节点RBNode rNode rightOf(parentOf(x));// 判断此时的兄弟节点是否是真正的兄弟节点 兄弟是红色的情况要调整if(colorOf(rNode) RED){ // 2-3-4树的 3节点 交换颜色然后左旋一次就可以了setColor(rNode,BLACK);setColor(parentOf(x),RED);leftRotate(parentOf(x)); // 左旋一次rNode rightOf(parentOf(x)); // 找到真正的兄弟节点}// 情况3 找兄弟借 没得借if(colorOf(leftOf(rNode)) BLACK colorOf(rightOf(rNode)) BLACK){// 情况复杂setColor(rNode,RED);xparentOf(x); // 向上递归}else{// 情况2 找兄弟借 有借// 兄弟节点是 3节点或者4节点if(colorOf(rightOf(rNode)) BLACK){// 右孩子为空则左孩子肯定不为空// 兄弟节点 先要左一次右旋setColor(rNode,RED);setColor(leftOf(rNode),BLACK);rightRotate(rNode);// 重新调整叔叔节点的位置rNode rightOf(parentOf(x));}// 变色 兄弟节点是 3节点还是4节点 都旋转一次setColor(rNode, colorOf(parentOf(x)));setColor(parentOf(x),BLACK);setColor(rightOf(rNode),BLACK);// 左旋leftRotate(parentOf(x));x root; // 结束循环 递归 针对的是 情况3}}else{// 找兄弟节点RBNode rNode leftOf(parentOf(x));// 判断此时的兄弟节点是否是真正的兄弟节点 兄弟是红色的情况要调整if(colorOf(rNode) RED){ // 2-3-4树的 3节点 交换颜色然后左旋一次就可以了setColor(rNode,BLACK);setColor(parentOf(x),RED);rightRotate(parentOf(x)); // 左旋一次rNode leftOf(parentOf(x)); // 找到真正的兄弟节点}// 情况3 找兄弟借 没得借if(colorOf(rightOf(rNode)) BLACK colorOf(leftOf(rNode)) BLACK){// 情况复杂setColor(rNode,RED);xparentOf(x); // 向上递归}else{// 情况2 找兄弟借 有借// 兄弟节点是 3节点或者4节点if(colorOf(leftOf(rNode)) BLACK){// 右孩子为空则左孩子肯定不为空// 兄弟节点 先要左一次右旋setColor(rNode,RED);setColor(leftOf(rNode),BLACK);leftRotate(rNode);// 重新调整叔叔节点的位置rNode leftOf(parentOf(x));}// 变色 兄弟节点是 3节点还是4节点 都旋转一次setColor(rNode, colorOf(parentOf(x)));setColor(parentOf(x),BLACK);setColor(leftOf(rNode),BLACK);// 左旋rightRotate(parentOf(x));x root; // 结束循环 递归 针对的是 情况3}}}// 情况1替代节点是红色直接染黑 在情况3的情况下 补偿删除的黑色节点这样红黑树依然保存平衡setColor(x,BLACK);}
2.5 B树和B树
2.5.1 B树 Balanced Tree 这个就是我们的多路平衡查找树叫做B-TreeB代表平衡。 跟AVL树一样B树在枝节点和叶子节点存储键值、数据地址、节点引用。 它有一个特点分叉数路数永远比关键字数多1。比如我们画的这棵树每个节点存储两个关键字那么就会有三个指针指向三个子节点。 B Tree的查找规则是什么样的呢 比如我们要在这张表里面查找15。 因为15小于17走左边。 因为15大于12走右边。 在磁盘块7里面就找到了15只用了3次IO。 这个是不是比AVL 树效率更高呢 那B Tree又是怎么实现一个节点存储多个关键字还保持平衡的呢跟AVL树有什么区别 Data Structure Visualization 比如Max Degree路数是3的时候我们插入数据1、2、3在插入3的时候本来应该在第一个磁盘块但是如果一个节点有三个关键字的时候意味着有4个指针子节点会变成4路所以这个时候必须进行分裂其实就是BTree。把中间的数据2提上去把1和3变成2的子节点。 如果删除节点会有相反的合并的操作。 注意这里是分裂和合并跟AVL树的左旋和右旋是不一样的。 我们继续插入4和5B Tree又会出现分裂和合并的操作。 从这个里面我们也能看到在更新索引的时候会有大量的索引的结构的调整所以解释了为什么我们不要在频繁更新的列上建索引或者为什么不要更新主键。 节点的分裂和合并其实就是InnoDB页page的分裂和合并。
2.5.2 B树 加强版多路平衡查找树 因为B Tree的这种特性非常适合用于做索引的数据结构所以很多文件系统和数据库的索引都是基于B Tree的。 但是实际上MySQL里面使用的是B Tree的改良版本叫做BTree加强版多路平衡查找树。
B树的存储结构 MySQL中的BTree有几个特点 它的关键字的数量是跟路数相等的 BTree的根节点和枝节点中都不会存储数据只有叶子节点才存储数据。InnoDB 中 B 树深度一般为 1-3 层它就能满足千万级的数据存储。搜索到关键字不会直接返回会到最后一层的叶子节点。比如我们搜索id28虽然在第一层直接命中了但是全部的数据在叶子节点上面所以我还要继续往下搜索一直到叶子节点。 BTree的每个叶子节点增加了一个指向相邻叶子节点的指针它的最后一个数据会指向下一个叶子节点的第一个数据形成了一个有序链表的结构。 总结一下 BTree的特点带来的优势 它是B Tree的变种B Tree能解决的问题它都能解决。B Tree解决的两大问题是什么每个节点存储更多关键字路数更多 扫库、扫表能力更强如果我们要对表进行全表扫描只需要遍历叶子节点就可以了不需要遍历整棵BTree拿到所有的数据 BTree的磁盘读写能力相对于B Tree来说更强根节点和枝节点不保存数据区所以一个节点可以保存更多的关键字一次磁盘加载的关键字更多 排序能力更强因为叶子节点上有下一个数据区的指针数据形成了链表 效率更加稳定BTree永远是在叶子节点拿到数据所以IO次数是稳定的
二、集合API源码分析
程序数据结构算法
1. 集合概述
集合是存储数据的容器 2. ArrayList详解
2.1 类图结构
首先我们来看下ArrayList的类图结构 2.2 源码分析
2.2.1 声明的属性
属性作用DEFAULT_CAPACITY默认的数组容量EMPTY_ELEMENTDATA用于共享的空实例数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA也是一个空的实例数组elementData这个是ArrayList中真实存储数据的容器size记录集合中的元素的个数
2.2.2 构造方法
public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(int initialCapacity) {if (initialCapacity 0) {this.elementData new Object[initialCapacity];} else if (initialCapacity 0) {this.elementData EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}
}public ArrayList(Collection? extends E c) {// 将传递的集合转换为数组 然后赋值给了 elementDataelementData c.toArray();if ((size elementData.length) ! 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() ! Object[].class)elementData Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData EMPTY_ELEMENTDATA;}
}
都很简单就不一一的记录描述了。
2.2.3 添加方法
方法名描述public boolean add(E e)将指定的元素追加到此列表的末尾。public void add(int index, E element)在此列表中的指定位置插入指定的元素。public boolean addAll(Collection? c )按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。public boolean addAll(i nt index,Collection? extends E c)将指定集合中的所有元素插入到此列表中从指定的位置开始。
add(E e) public boolean add(E e) {// 校验内部容量ensureCapacityInternal(size 1); // Increments modCount!!elementData[size] e;return true;} private void ensureCapacityInternal(int minCapacity) {// calculateCapacity计算容量// ensureExplicitCapacity 继续校验ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}
calculateCapacity方法 private static int calculateCapacity(Object[] elementData, int minCapacity) {// 判断集合存数据的数组是否等于空容量的数组if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 通过最小容量和默认容量 求出较大值 (用于第一次扩容)return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}
ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) { //实际修改集合次数 (在扩容的过程中没用,主要是用于迭代器中) modCount; //判断最小容量 - 数组长度是否大于 0 if (minCapacity - elementData.length 0) //将第一次计算出来的容量传递给 核心扩容方法 grow(minCapacity);
}
private void grow(int minCapacity) { //记录数组的实际长度,此时由于木有存储元素,长度为0 int oldCapacity elementData.length; //核心扩容算法 原容量的1.5倍 int newCapacity oldCapacity (oldCapacity 1); //判断新容量 - 最小容量 是否小于 0, 如果是第一次调用add方法必然小于 if (newCapacity - minCapacity 0) //还是将最小容量赋值给新容量 newCapacity minCapacity; //判断新容量-最大数组大小 是否0,如果条件满足就计算出一个超大容量 if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); // 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementData elementData Arrays.copyOf(elementData, newCapacity);
}
add(int index, E element) public void add(int index, E element) {// 检查index的合法性rangeCheckForAdd(index);// 校验内部容量ensureCapacityInternal(size 1); // Increments modCount!!// index 3// [1,2,3,4,5] -- [1,2,3, ,4,5]// 将 elementData index3后的元素复制到 elementData 的 index14后的位置// 也就是空出来了 index 的位置System.arraycopy(elementData, index, elementData, index 1,size - index);elementData[index] element;size;}
addAll(Collection? c )
public boolean addAll(Collection? extends E c) {//把集合的元素转存到Object类型的数组中Object[] a c.toArray();//记录数组的长度int numNew a.length;//调用方法检验是否要扩容,且让增量ensureCapacityInternal(size numNew); // Increments modCount//调用方法将a数组的元素拷贝到elementData数组中System.arraycopy(a, 0, elementData, size, numNew);//集合的长度a数组的长度size numNew;//只要a数组的长度不等于0,即说明添加成功return numNew ! 0;
}
addAll(i nt index,Collection? extends E c) public boolean addAll(int index, Collection? extends E c) {// 校验index是否合法rangeCheckForAdd(index);// 传递进来的集合转换为数组Object[] a c.toArray();// 记录数组的长度int numNew a.length;// 校验是否要扩容ensureCapacityInternal(size numNew); // Increments modCount// 计算 数组要插入到 集合的index 下标int numMoved size - index;if (numMoved 0)// 调整 elementData 中的数据的位置 给新插入的数据流出空间System.arraycopy(elementData, index, elementData, index numNew,numMoved);// 将数据中的数据插入到新的数组对应的位置中即可System.arraycopy(a, 0, elementData, index, numNew);// 集合容量增加size numNew;return numNew ! 0;}
其他方法的实现都很简单请自行查阅。
3. Vector
3.1 类图结构 3.2 和ArrayList的区别
本质上也是通过数组的形式来实现的只是在每个实现的方法中都添加了一个synchronized关键字所以Vector是数据安全的。 4. HashSet
4.1 类图结构 4.2 HashSet的本质
HashSet的本质其实就是HashMap这个我们可以通过HashSet的构造方法可以看到 所以我们要搞清楚HashSet本质上搞清楚了HashMap就可以了所以此处我们不过多讲解。重点是后面的HashMap。
5.TreeSet
5.1 类图结构 5.2 TreeSet的本质
和HashSet一样TreeSet的功能也不是自己来实现的而是借助TreeMap来实现的在TreeSet的构造方法中我们可以看到 6.TreeMap
6.1 类图结构 6.2 源码分析
通过前面红黑树的介绍其实大家已经对红黑树的节点的添加删除都很清楚而且TreeMap实现的本质就是红黑树所以TreeMap的源码大家应该很容易看懂。具体如下
6.2.1 成员变量 // 比较器private final Comparator? super K comparator;// 根节点 Entry 相当于之前的 RBNode 类型private transient EntryK,V root;/*** The number of entries in the tree*/private transient int size 0;/*** The number of structural modifications to the tree.*/private transient int modCount 0;
Entry的具体声明 static final class EntryK,V implements Map.EntryK,V {K key;V value;EntryK,V left;EntryK,V right;EntryK,V parent;boolean color BLACK;}
6.2.2 put方法 public V put(K key, V value) {// 1.查找插入的位置EntryK,V t root;// 第一次插入 插入的节点设置为 root 节点if (t null) {compare(key, key); // type (and possibly null) checkroot new Entry(key, value, null);size 1; // 记录集合中的元素个数modCount; // 记录操作的次数return null;}int cmp; // 比较的值EntryK,V parent; // 记录插入节点的父节点// split comparator and comparable pathsComparator? super K cpr comparator;if (cpr ! null) { // 比较器不为空// 遍历找到插入的位置do {parent t;cmp cpr.compare(key, t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;else// 插入的值在容器中有相同的值 直接覆盖return t.setValue(value);} while (t ! null);}else {if (key null)throw new NullPointerException();// 比较器为空就创建一个比较器SuppressWarnings(unchecked)Comparable? super K k (Comparable? super K) key;// 找到插入的位置do {parent t;cmp k.compareTo(t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;elsereturn t.setValue(value);} while (t ! null);}// 需要插入的 k v 对封装为 Entry对象EntryK,V e new Entry(key, value, parent);if (cmp 0)parent.left e;elseparent.right e;// 变色和调整操作fixAfterInsertion(e);size;modCount;return null;}
fixAfterInsertion(e)方法 private void fixAfterInsertion(EntryK,V x) {// 插入节点 默认就是红色节点x.color RED;// 只有 插入节点的 父节点是 黑色节点才需要 调整平衡while (x ! null x ! root x.parent.color RED) {if (parentOf(x) leftOf(parentOf(parentOf(x)))) {// 插入节点的 父亲节点是 爷爷节点的左节点// 获取叔叔节点EntryK,V y rightOf(parentOf(parentOf(x)));if (colorOf(y) RED) {// 存在叔叔节点// 父亲和叔叔节点 变为黑色setColor(parentOf(x), BLACK);setColor(y, BLACK);// 爷爷节点变为红色setColor(parentOf(parentOf(x)), RED);// 将插入节点调整为 爷爷节点 然后递归处理x parentOf(parentOf(x));} else {// 没有叔叔节点if (x rightOf(parentOf(x))) {// 插入节点是父节点的右子节点 需要先根据父亲节点左旋一次// 6 6// / /// 4 5// \ /// 5 4x parentOf(x);rotateLeft(x);}// 然后父亲节点设置为 黑色 爷爷节点设置为红色setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);// 右旋一次即可rotateRight(parentOf(parentOf(x)));}} else {// 和上面的情况刚好相反EntryK,V y leftOf(parentOf(parentOf(x)));if (colorOf(y) RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x parentOf(parentOf(x));} else {if (x leftOf(parentOf(x))) {x parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}// 将 root 节点设置为 黑色节点root.color BLACK;}
通过源码分析大家应该发现和我们在红黑树中的添加的代码是一模一样的。同样的大家可以自行看下左旋和右旋的代码。也很简单哦
7. HashMap
7.1 设计原理 HashMap 基于哈希表的 Map 接口实现是以 key-value 存储形式存在即主要用来存放键值对。HashMap 的实现不是同步的这意味着它不是线程安全的。它的 key、value 都可以为 null此外HashMap 中的映射不是有序的。 jdk1.8 之前 HashMap 由 数组 链表 组成数组是 HashMap 的主体链表则是主要为了解决哈希冲突两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用而存在的“拉链法”解决冲突。jdk1.8 以后在解决哈希冲突时有了较大的变化当链表长度大于阈值或者红黑树的边界值默认为 8 并且当前数组的长度大于 64 时此时此索引位置上的所有数据改为使用红黑树存储。
补充将链表转换成红黑树前会判断即便阈值大于 8但是数组长度小于 64此时并不会将链表变为红黑树而是选择逬行数组扩容。 这样做的目的是因为数组比较小尽量避开红黑树结构这种情况下变为红黑树结构反而会降低效率因为红黑树需要逬行左旋右旋变色这些操作来保持平衡。同时数组长度小于64时搜索时间相对要快些。所以结上所述为了提高性能和减少搜索时间底层阈值大于8并且数组长度大于64时链表才转换为红黑树具体可以参考 treeifyBin() 方法。 当然虽然增了红黑树作为底层数据结构结构变得复杂了但是阈值大于 8 并且数组长度大于 64 时链表转换为红黑树时效率也变的更高效。
HashMap 特点 存储无序的。 键和值位置都可以是 null但是键位置只能存在一个 null。 键位置是唯一的是底层的数据结构控制的。 jdk1.8 前数据结构是链表数组jdk1.8 之后是链表数组红黑树。 阈值边界值 8 并且数组长度大于 64才将链表转换为红黑树变为红黑树的目的是为了高效的查询。
7.1.1 JDK1.7 7.1.2 JDK1.8 7.1.3 扩容 7.2 源码分析
7.2.1 成员变量 serialVersionUID
序列化版本号
DEFAULT_INITIAL_CAPACITY
集合的初始化容量必须是 2 的 n 次幂
// 默认的初始容量是16 1 4 相当于 1*2的4次方
static final int DEFAULT_INITIAL_CAPACITY 1 4;
DEFAULT_LOAD_FACTOR
默认的负载因子默认值 0.75
static final float DEFAULT_LOAD_FACTOR 0.75f;
MAXIMUM_CAPACITY
集合最大容量
static final int MAXIMUM_CAPACITY 1 30; // 2的30次幂
TREEIFY_THRESHOLD
当链表的值超过8则会转为红黑树jdk1.8新增
// 当桶bucket上的结点数大于这个值时会转为红黑树
static final int TREEIFY_THRESHOLD 8;
UNTREEIFY_THRESHOLD
当链表的值小于 6 则会从红黑树转回链表
// 当桶bucket上的结点数小于这个值树转为链表
static final int UNTREEIFY_THRESHOLD 6;
MIN_TREEIFY_CAPACITY
当 Map 里面的数量超过这个值时表中的桶才能进行树形化否则桶内元素太多时会扩容而不是树形化为了避免进行扩容、树形化选择的冲突这个值不能小于4*TREEIFY_THRESHOLD(8)
// 桶中结构转化为红黑树对应的数组长度最小的值
static final int MIN_TREEIFY_CAPACITY 64;
table
table 用来初始化必须是二的n次幂(重点)
// 存储元素的数组
transient NodeK,V[] table;
在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构其中 table 就是 HashMap 中的数组jdk8 之前数组类型是 EntryK,V 类型。从 jdk1.8 之后是 NodeK,V 类型。只是换了个名字都实现了一样的接口Map.EntryK,V。负责存储键值对数据的。
entrySet
用来存放缓存
// 存放具体元素的集合
transient SetMap.EntryK,V entrySet;
size
HashMap 中存放元素的个数(重点)
// 存放元素的个数注意这个不等于数组的长度transient int size;
size 为 HashMap 中 K-V 的实时数量不是数组 table 的长度。
modCount
用来记录 HashMap 的修改次数
// 每次扩容和更改 map 结构的计数器transient int modCount;
threshold
用来调整大小下一个容量的值计算方式为容量*负载因子
// 临界值 当实际大小容量*负载因子超过临界值时会进行扩容
int threshold;
loadFactor
哈希表的负载因子(重点)
// 负载因子
final float loadFactor;
7.2.2 构造方法
HashMap()
构造一个空的HashMap默认初始容量16和默认负载因子0.75
public HashMap() {// 将默认的负载因子0.75赋值给loadFactor并没有创建数组this.loadFactor DEFAULT_LOAD_FACTOR;
}
HashMap(int initialCapacity)
构造一个具有指定的初始容量和默认负载因子0.75HashMap 。 // 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}HashMap(int initialCapacity, float loadFactor)
构造一个具有指定的初始容量和负载因子的 HashMap。
/*指定“容量大小”和“负载因子”的构造函数initialCapacity指定的容量loadFactor:指定的负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {// 判断初始化容量initialCapacity是否小于0if (initialCapacity 0)// 如果小于0则抛出非法的参数异常IllegalArgumentExceptionthrow new IllegalArgumentException(Illegal initial capacity: initialCapacity);// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITYif (initialCapacity MAXIMUM_CAPACITY)// 如果超过MAXIMUM_CAPACITY会将MAXIMUM_CAPACITY赋值给initialCapacityinitialCapacity MAXIMUM_CAPACITY;// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值if (loadFactor 0 || Float.isNaN(loadFactor))// 如果满足上述其中之一则抛出非法的参数异常IllegalArgumentExceptionthrow new IllegalArgumentException(Illegal load factor: loadFactor);// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactorthis.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);}
// 最后调用了tableSizeFor来看一下方法实现/*返回比指定初始化容量大的最小的2的n次幂*/static final int tableSizeFor(int cap) {int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16;return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;}HashMap(Map? extends K, ? extends V m)
包含另一个 “Map” 的构造函数
// 构造一个映射关系与指定 Map 相同的新 HashMap。
public HashMap(Map? extends K, ? extends V m) {// 负载因子loadFactor变为默认的负载因子0.75this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}
最后调用了 putMapEntries()来看一下方法实现
final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {//获取参数集合的长度int s m.size();if (s 0) {//判断参数集合的长度是否大于0说明大于0if (table null) { // 判断table是否已经初始化// 未初始化s为m的实际元素个数float ft ((float)s / loadFactor) 1.0F;int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 计算得到的t大于阈值则初始化阈值if (t threshold)threshold tableSizeFor(t);}// 已初始化并且m元素个数大于阈值进行扩容处理else if (s threshold)resize();// 将m中的所有元素添加至HashMap中for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue();putVal(hash(key), key, value, false, evict);}}
}注意
float ft ((float)s / loadFactor) 1.0F; 这一行代码中为什么要加 1.0F
s/loadFactor 的结果是小数加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量更大的容量能够减少 resize 的调用次数。所以 1.0F 是为了获取更大的容量。
例如原来集合的元素个数是 6 个那么 6/0.75 是8是 2 的n次幂那么新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了这样会导致在存储元素的时候容量不够还得继续扩容那么性能降低了而如果 1 呢数组长度直接变为16了这样可以减少数组的扩容。
7.2.3 put方法
put方法的实现文字说明 先通过 hash 值计算出 key 映射到哪个桶 如果桶上没有碰撞冲突则直接插入 如果出现碰撞冲突了则需要处理冲突 a 如果该桶使用红黑树处理冲突则调用红黑树的方法插入数据 b 否则采用传统的链式方法插入。如果链的长度达到临界值则把链转变为红黑树 如果桶中存在重复的键则为该键替换新值 value 如果 size 大于阈值 threshold则进行扩容
put方法的源码说明
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
/*** hashkey 的 hash 值* key原始 key* value要存放的值* onlyIfAbsent如果 true 代表不更改现有的值* evict如果为false表示 table 为创建状态*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;/*1transient NodeK,V[] table; 表示存储Map集合中元素的数组。2(tab table) null 表示将空的table赋值给tab然后判断tab是否等于null第一次肯定是null。3(n tab.length) 0 表示将数组的长度0赋值给n然后判断n是否等于0n等于0由于if判断使用双或满足一个即可则执行代码 n (tab resize()).length; 进行数组初始化并将初始化好的数组长度赋值给n。4执行完n (tab resize()).length数组tab每个空间都是null。*/if ((tab table) null || (n tab.length) 0)n (tab resize()).length;/*1i (n - 1) hash 表示计算数组的索引赋值给i即确定元素存放在哪个桶中。2p tab[i (n - 1) hash]表示获取计算出的位置的数据赋值给结点p。3) (p tab[i (n - 1) hash]) null 判断结点位置是否等于null如果为null则执行代码tab[i] newNode(hash, key, value, null);根据键值对创建新的结点放入该位置的桶中。小结如果当前桶没有哈希碰撞冲突则直接把键值对插入空间位置。*/ if ((p tab[i (n - 1) hash]) null)// 创建一个新的结点存入到桶中tab[i] newNode(hash, key, value, null);else {// 执行else说明tab[i]不等于null表示这个位置已经有值了NodeK,V e; K k;/*比较桶中第一个元素(数组中的结点)的hash值和key是否相等1p.hash hash p.hash表示原来存在数据的hash值 hash表示后添加数据的hash值 比较两个hash值是否相等。说明p表示tab[i]即 newNode(hash, key, value, null)方法返回的Node对象。NodeK,V newNode(int hash, K key, V value, NodeK,V next) {return new Node(hash, key, value, next);}而在Node类中具有成员变量hash用来记录着之前数据的hash值的。2(k p.key) key p.key获取原来数据的key赋值给k key 表示后添加数据的key比较两个key的地址值是否相等。3key ! null key.equals(k)能够执行到这里说明两个key的地址值不相等那么先判断后添加的key是否等于null如果不等于null再调用equals方法判断两个key的内容是否相等。*/if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))/*说明两个元素哈希值相等并且key的值也相等将旧的元素整体对象赋值给e用e来记录*/ e p;// hash值不相等或者key不相等判断p是否为红黑树结点else if (p instanceof TreeNode)// 放入树中e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);// 说明是链表结点else {/*1)如果是链表的话需要遍历到最后结点然后插入2)采用循环遍历的方式判断链表中是否有重复的key*/for (int binCount 0; ; binCount) {/*1)e p.next 获取p的下一个元素赋值给e。2)(e p.next) null 判断p.next是否等于null等于null说明p没有下一个元素那么此时到达了链表的尾部还没有找到重复的key,则说明HashMap没有包含该键将该键值对插入链表中。*/if ((e p.next) null) {/*1创建一个新的结点插入到尾部p.next newNode(hash, key, value, null);NodeK,V newNode(int hash, K key, V value, NodeK,V next) {return new Node(hash, key, value, next);}注意第四个参数next是null因为当前元素插入到链表末尾了那么下一个结点肯定是null。2这种添加方式也满足链表数据结构的特点每次向后添加新的元素。*/p.next newNode(hash, key, value, null);/*1)结点添加完成之后判断此时结点个数是否大于TREEIFY_THRESHOLD临界值8如果大于则将链表转换为红黑树。2int binCount 0 表示for循环的初始化值。从0开始计数。记录着遍历结点的个数。值是0表示第一个结点1表示第二个结点。。。。7表示第八个结点加上数组中的的一个元素元素个数是9。TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7如果binCount的值是7(加上数组中的的一个元素元素个数是9)TREEIFY_THRESHOLD - 1也是7此时转换红黑树。*/if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st// 转换为红黑树treeifyBin(tab, hash);// 跳出循环break;}/*执行到这里说明e p.next 不是null不是最后一个元素。继续判断链表中结点的key值与插入的元素的key值是否相等。*/if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))// 相等跳出循环/*要添加的元素和链表中的存在的元素的key相等了则跳出for循环。不用再继续比较了直接执行下面的if语句去替换去 if (e ! null) */break;/*说明新添加的元素和当前结点不相等继续查找下一个结点。用于遍历桶中的链表与前面的e p.next组合可以遍历链表*/p e;}}/*表示在桶中找到key值、hash值与插入元素相等的结点也就是说通过上面的操作找到了重复的键所以这里就是把该键的值变为新的值并返回旧值这里完成了put方法的修改功能*/if (e ! null) { // 记录e的valueV oldValue e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue null)// 用新值替换旧值// e.value 表示旧值 value表示新值 e.value value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 修改记录次数modCount;// 判断实际大小是否大于threshold阈值如果超过则扩容if (size threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;
}上面的源码中使用到了hash方法我们来看下hash方法的源码
static final int hash(Object key) {int h;/*1如果key等于null返回的是0.2如果key不等于null首先计算出key的hashCode赋值给h然后与h无符号右移16位后的二进制进行按位异或得到最后的hash值*/return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
从上面可以得知 HashMap 是支持 key 为空的而 HashTable 是直接用 Key 来获取hashCode 所以 key 为空会抛异常。
(n - 1) hash 的实现介绍 key.hashCode()返回散列值也就是 hashcode假设随便生成的一个值。 n 表示数组初始化的长度是 16。 按位与运算运算规则相同的二进制数位上都是 1 的时候结果为 1否则为0。 ^按位异或运算运算规则相同的二进制数位上数字相同结果为 0不同为 1。 7.2.4 treeifyBin()
结点添加完成之后判断此时结点个数是否大于 TREEIFY_THRESHOLD 临界值 8如果大于则将链表转换为红黑树转换红黑树的方法 treeifyBin整体代码如下
if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//转换为红黑树 tab表示数组名 hash表示哈希值treeifyBin(tab, hash);treeifyBin 方法如下所示
/*替换指定哈希表的索引处桶中的所有链接结点除非表太小否则将修改大小。NodeK,V[] tab tab 数组名int hash hash表示哈希值
*/
final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;/*如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY 64)就去扩容。而不是将结点变为红黑树。目的如果数组很小那么转换红黑树然后遍历效率要低一些。这时进行扩容那么重新计算哈希值链表长度有可能就变短了数据会放到数组中这样相对来说效率高一些。*/if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)//扩容方法resize();else if ((e tab[index (n - 1) hash]) ! null) {/*1执行到这里说明哈希表中的数组长度大于阈值64开始进行树形化2e tab[index (n - 1) hash]表示将数组中的元素取出赋值给ee是哈希表中指定位置桶里的链表结点从第一个开始*/// hd红黑树的头结点 tl红黑树的尾结点TreeNodeK,V hd null, tl null;do {// 新创建一个树的结点内容和当前链表结点e一致TreeNodeK,V p replacementTreeNode(e, null);if (tl null)hd p; // 将新创键的p结点赋值给红黑树的头结点else {p.prev tl; // 将上一个结点p赋值给现在的p的前一个结点tl.next p; // 将现在结点p作为树的尾结点的下一个结点}tl p;/*e e.next 将当前结点的下一个结点赋值给e如果下一个结点不等于null则回到上面继续取出链表中结点转换为红黑树*/} while ((e e.next) ! null);/*让桶中的第一个元素即数组中的元素指向新建的红黑树的结点以后这个桶里的元素就是红黑树而不是链表数据结构了*/if ((tab[index] hd) ! null)hd.treeify(tab);}
}小结 根据哈希表中元素个数确定是扩容还是树形化。 如果是树形化遍历桶中的元素创建相同个数的树形结点复制内容建立起联系。 然后让桶中的第一个元素指向新创建的树根结点替换桶的链表内容为树形化内容。
7.2.5 扩容方法
扩容机制
什么时候才需要扩容 当 HashMap 中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时就会进行数组扩容loadFactor 的默认值是 0.75。
HashMap 的扩容是什么 进行扩容会伴随着一次重新 hash 分配并且会遍历 hash 表中所有的元素是非常耗时的。在编写程序中要尽量避免 resize。HashMap 在进行扩容时使用的 rehash 方式非常巧妙因为每次扩容都是翻倍与原来计算的 (n - 1) hash 的结果相比只是多了一个 bit 位所以结点要么就在原来的位置要么就被分配到 “原位置 旧容量” 这个位置。
例如我们从 16 扩展为 32 时具体的变化如下所示 因此元素在重新计算 hash 之后因为 n 变为 2 倍那么 n - 1 的标记范围在高位多 1bit(红色)因此新的 index 就会发生这样的变化。 说明
5 是假设计算出来的原来的索引。这样就验证了上述所描述的扩容之后所以结点要么就在原来的位置要么就被分配到 “原位置 旧容量” 这个位置。
因此我们在扩充 HashMap 的时候不需要重新计算 hash只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了是 0 的话索引没变是 1 的话索引变成 “原位置 旧容量” 。可以看看下图为 16 扩充为 32 的 resize 示意图 正是因为这样巧妙的 rehash 方式既省去了重新计算 hash 值的时间而且同时由于新增的 1bit 是 0 还是 1 可以认为是随机的在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数保证了 rehash 之后不会出现更严重的 hash 冲突均匀的把之前的冲突的结点分散到新的桶中了。
resize源码分析
final NodeK,V[] resize() {// 得到当前数组NodeK,V[] oldTab table;// 如果当前数组等于null长度返回0否则返回当前数组的长度int oldCap (oldTab null) ? 0 : oldTab.length;//当前阀值点 默认是12(16*0.75)int oldThr threshold;int newCap, newThr 0;// 如果老的数组长度大于0// 开始计算扩容后的大小if (oldCap 0) {// 超过最大值就不再扩充了就只好随你碰撞去吧if (oldCap MAXIMUM_CAPACITY) {// 修改阈值为int的最大值threshold Integer.MAX_VALUE;return oldTab;}/*没超过最大值就扩充为原来的2倍1) (newCap oldCap 1) MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量2oldCap DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16*/else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)// 阈值扩大一倍newThr oldThr 1; // double threshold}// 老阈值点大于0 直接赋值else if (oldThr 0) // 老阈值赋值给新的数组长度newCap oldThr;else { // 直接使用默认值newCap DEFAULT_INITIAL_CAPACITY;//16newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新的resize最大上限if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 新的阀值 默认原来是12 乘以2之后变为24threshold newThr;// 创建新的哈希表SuppressWarnings({rawtypes,unchecked})//newCap是新的数组长度--》32NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;// 判断旧数组是否等于空if (oldTab ! null) {// 把每个bucket都移动到新的buckets中// 遍历旧的哈希表的每个桶重新计算桶里元素的新位置for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {// 原来的数据赋值为null 便于GC回收oldTab[j] null;// 判断数组是否有下一个引用if (e.next null)// 没有下一个引用说明不是链表当前桶上只有一个键值对直接插入newTab[e.hash (newCap - 1)] e;//判断是否是红黑树else if (e instanceof TreeNode)// 说明是红黑树来处理冲突的则调用相关方法把树分开((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // 采用链表处理冲突NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;// 通过上述讲解的原理来计算结点的新位置do {// 原索引next e.next;// 这里来判断如果等于true e这个结点在resize之后不需要移动位置if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}// 原索引oldCapelse {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);// 原索引放到bucket里if (loTail ! null) {loTail.next null;newTab[j] loHead;}// 原索引oldCap放到bucket里if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}7.2.6 remove方法 删除方法就是首先先找到元素的位置如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除树小于 6 的时候要转链表。
// remove方法的具体实现在removeNode方法中所以我们重点看下removeNode方法
public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ?null : e.value;}
removeNode() 方法
final NodeK,V removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {NodeK,V[] tab; NodeK,V p; int n, index;// 根据hash找到位置 // 如果当前key映射到的桶不为空if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,V node null, e; K k; V v;// 如果桶上的结点就是要找的key则将node指向该结点if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))node p;else if ((e p.next) ! null) {// 说明结点存在下一个结点if (p instanceof TreeNode)// 说明是以红黑树来处理的冲突则获取红黑树要删除的结点node ((TreeNodeK,V)p).getTreeNode(hash, key);else {// 判断是否以链表方式处理hash冲突是的话则通过遍历链表来寻找要删除的结点do {if (e.hash hash ((k e.key) key ||(key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);}}// 比较找到的key的value和要删除的是否匹配if (node ! null (!matchValue || (v node.value) value ||(value ! null value.equals(v)))) {// 通过调用红黑树的方法来删除结点if (node instanceof TreeNode)((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p)// 链表删除tab[index] node.next;elsep.next node.next;// 记录修改次数modCount;// 变动的数量--size;afterNodeRemoval(node);return node;}}return null;
}
7.2.7 get方法
查找方法通过元素的 key 找到 value这个方法就比较好理解了
public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}
get 方法主要调用的是 getNode 方法代码如下
final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;// 如果哈希表不为空并且key对应的桶上不为空if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {/* 判断数组元素是否相等根据索引的位置检查第一个元素注意总是检查第一个元素*/if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;// 如果不是第一个元素判断是否有后续结点if ((e first.next) ! null) {// 判断是否是红黑树是的话调用红黑树中的getTreeNode方法获取结点if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);do {// 不是红黑树的话那就是链表结构了通过循环的方法判断链表中是否存在该keyif (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;
}
7.3 面试相关 HashMap 中 hash 函数是怎么实现的还有哪些hash函数的实现方式 答对于 key 的 hashCode 做 hash 操作无符号右移 16 位然后做异或运算。还有平方取中法伪随机数法和取余数法。这三种效率都比较低。而无符号右移 16 位异或运算效率是最高的。 当两个对象的 hashCode 相等时会怎么样 答会产生哈希碰撞。若 key 值内容相同则替换旧的 value不然连接到链表后面链表长度超过阈值 8 就转换为红黑树存储。 什么是哈希碰撞如何解决哈希碰撞 答只要两个元素的 key 计算的哈希码值相同就会发生哈希碰撞。jdk8 之前使用链表解决哈希碰撞。jdk8之后使用链表 红黑树解决哈希碰撞。 如果两个键的 hashCode 相同如何存储键值对 答通过 equals 比较内容是否相同。相同则新的 value 覆盖之前的 value。不相同则将新的键值对添加到哈希表中
