体育php网站源码,wordpress能大网站主题,做阿里巴巴网站公司,广西建设网站一 数据结构剖析
我们举一个形象的例子来理解数据结构的作用#xff1a; 战场#xff1a;程序运行所需的软件、硬件环境 战术和策略#xff1a;数据结构 敌人#xff1a;项目或模块的功能需求 指挥官#xff1a;编写程序的程序员 士兵和装备#xff1a;一行一行的代码 …
一 数据结构剖析
我们举一个形象的例子来理解数据结构的作用 战场程序运行所需的软件、硬件环境 战术和策略数据结构 敌人项目或模块的功能需求 指挥官编写程序的程序员 士兵和装备一行一行的代码 上图没有战术打仗事倍功半 上图有战术打仗事半功倍
总结简单来说数据结构就是一种程序设计优化的方法论研究数据的逻辑结构和物理结构以及它们之间相互关系并对这种结构定义相应的运算目的是加快程序的执行速度、减少内存占用的空间。
具体研究对象如下
1.1 研究对象一数据间逻辑关系
数据的逻辑结构指反映数据元素之间的逻辑关系而与数据的存储无关是独立于计算机的。
集合结构数据结构中的元素之间除了“同属一个集合” 的相互关系外别无其他关系。集合元素之间没有逻辑关系。线性结构数据结构中的元素存在一对一的相互关系。比如排队。结构中必须存在唯一的首元素和唯一的尾元素。体现为一维数组、链表、栈、队列树形结构数据结构中的元素存在一对多的相互关系。比如家谱、文件系统、组织架构图形结构数据结构中的元素存在多对多的相互关系。比如全国铁路网、地铁图
1.2 研究对象二数据的存储结构或物理结构
数据的物理结构/存储结构包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言。
结构1顺序结构 顺序结构就是使用一组连续的存储单元依次存储逻辑上相邻的各个元素。 优点 只需要申请存放数据本身的内存空间即可支持下标访问也可以实现随机访问。 缺点 必须静态分配连续空间内存空间的利用率比较低。插入或删除可能需要移动大量元素效率比较低 结构2链式结构 不使用连续的存储空间存放结构的元素而是为每一个元素构造一个节点。节点中除了存放数据本身以外还需要存放指向下一个节点的指针。 优点不采用连续的存储空间导致内存空间利用率比较高克服顺序存储结构中预知元素个数的缺点。插入或删除元素时不需要移动大量的元素。 缺点需要额外的空间来表达数据之间的逻辑关系不支持下标访问和随机访问。 结构3索引结构 除建立存储节点信息外还建立附加的索引表来记录每个元素节点的地址。索引表由若干索引项组成。索引项的一般形式是关键字地址。 优点用节点的索引号来确定结点存储地址检索速度快。 缺点 增加了附加的索引表会占用较多的存储空间。在增加和删除数据时要修改索引表因而会花费较多的时间。 结构4散列结构 根据元素的关键字直接计算出该元素的存储地址又称为Hash存储。 优点检索、增加和删除结点的操作都很快。 缺点不支持排序一般比用线性表存储需要更多的空间并且记录的关键字不能重复。
1.3 研究对象三运算结构
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的指出运算的功能运算的实现是针对存储结构的指出运算的具体操作步骤。
分配资源建立结构释放资源插入和删除获取和遍历修改和排序
1.4 小结 二 一维数组
2.1 数组的特点
在Java中数组是用来存放同一种数据类型的集合注意只能存放同一种数据类型。
//只声明了类型和长度
数据类型[] 数组名称 new 数据类型[数组长度];//声明了类型初始化赋值大小由元素个数决定
数据类型[] 数组名称 {数组元素1数组元素2......}例如整型数组 例如对象数组 物理结构特点 申请内存一次申请一大段连续的空间一旦申请到了内存就固定了。不能动态扩展(初始化给大了浪费给小了不够用)插入快删除和查找慢。存储特点所有数据存储在这个连续的空间中数组中的每一个元素都是一个具体的数据或对象所有数据都紧密排布不能有间隔。 具体的如下图
2.2 自定义数组
class Array {private Object[] elementData;private int size;public Array(int capacity){elementData new Object[capacity];}/*** 添加元素* param value*/public void add(Object value){if(size elementData.length){throw new RuntimeException(数组已满不可添加);}elementData[size] value;size;}/*** 查询元素value在数组中的索引位置* param value* return*/public int find(Object value){for (int i 0; i size; i) {if(elementData[i].equals(value)){return i;}}return -1;}/*** 从当前数组中移除首次出现的value元素* param value* return*/public boolean delete(Object value){int index find(value);if(index -1){return false;}for(int i index;i size - 1;i){elementData[i] elementData[i 1];}elementData[size - 1] null;size--;return true;}/*** 将数组中首次出现的oldValue替换为newValue* param oldValue* param newValue* return*/public boolean update(Object oldValue,Object newValue){int index find(oldValue);if(index -1){return false;}elementData[index] newValue;return true;}/*** 遍历数组中所有数据*/public void print(){System.out.print({);for (int i 0; i size; i) {if(i size - 1){System.out.println(elementData[i] });break;}System.out.print(elementData[i] ,);}}
}//测试类
public class ArrayTest {public static void main(String[] args) {Array arr new Array(10);arr.add(123);arr.add(AA);arr.add(345);arr.add(345);arr.add(BB);arr.delete(345);arr.update(345,444);arr.print();}
}三 链表
3.1 链表的特点 逻辑结构线性结构 物理结构不要求连续的存储空间 存储特点链表由一系列结点node链表中每一个元素称为结点组成结点可以在代码执行过程中动态创建。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。 常见的链表结构有如下的形式 3.2 自定义链表
3.2.1 自定义单向链表 /*
单链表中的节点。
节点是单向链表中基本的单元。
每一个节点Node都有两个属性一个属性是存储的数据。另一个属性是下一个节点的内存地址。*/
public class Node {// 存储的数据Object data;// 下一个节点的内存地址Node next;public Node(){}public Node(Object data, Node next){this.data data;this.next next;}
}/*
链表类(单向链表)*/
public class LinkE {// 头节点Node header;private int size 0;public int size(){return size;}// 向链表中添加元素的方法向末尾添加public void add(E data){//public void add(Object data){// 创建一个新的节点对象// 让之前单链表的末尾节点next指向新节点对象。// 有可能这个元素是第一个也可能是第二个也可能是第三个。if(header null){// 说明还没有节点。// new一个新的节点对象作为头节点对象。// 这个时候的头节点既是一个头节点又是一个末尾节点。header new Node(data, null);}else {// 说明头不是空// 头节点已经存在了// 找出当前末尾节点让当前末尾节点的next是新节点。Node currentLastNode findLast(header);currentLastNode.next new Node(data, null);}size;}/*** 专门查找末尾节点的方法。*/private Node findLast(Node node) {if(node.next null) {// 如果一个节点的next是null// 说明这个节点就是末尾节点。return node;}// 程序能够到这里说明node不是末尾节点。return findLast(node.next); // 递归算法}/*// 删除链表中某个数据的方法public void remove(Object obj){//略}// 修改链表中某个数据的方法public void modify(Object newObj){//略}// 查找链表中某个元素的方法。public int find(Object obj){//略}*/
}3.2.2 自定义双向链表 /*
双向链表中的节点。*/
public class NodeE {Node prev;E data;Node next;Node(Node prev, E data, Node next) {this.prev prev;this.data data;this.next next;}
}/*** 链表类(双向链表)* author 尚硅谷-宋红康* create 15:05*/
public class MyLinkedListE implements IterableE{private Node first; //链表的首元素private Node last; //链表的尾元素private int total;public void add(E e){Node newNode new Node(last, e, null);if(first null){first newNode;}else{last.next newNode;}last newNode;total;}public int size(){return total;}public void delete(Object obj){Node find findNode(obj);if(find ! null){if(find.prev ! null){find.prev.next find.next;}else{first find.next;}if(find.next ! null){find.next.prev find.prev;}else{last find.prev;}find.prev null;find.next null;find.data null;total--;}}private Node findNode(Object obj){Node node first;Node find null;if(obj null){while(node ! null){if(node.data null){find node;break;}node node.next;}}else{while(node ! null){if(obj.equals(node.data)){find node;break;}node node.next;}}return find;}public boolean contains(Object obj){return findNode(obj) ! null;}public void update(E old, E value){Node find findNode(old);if(find ! null){find.data value;}}Overridepublic IteratorE iterator() {return new Itr();}private class Itr implements IteratorE{private NodeE node first;Overridepublic boolean hasNext() {return node!null;}Overridepublic E next() {E value node.data;node node.next;return value;}}
}自定义双链表测试
public class MyLinkedListTest {public static void main(String[] args) {MyLinkedListString my new MyLinkedList();my.add(hello);my.add(world);my.add(null);my.add(null);my.add(java);my.add(java);my.add(atguigu);System.out.println(一共有 my.size());System.out.println(所有元素);for (String s : my) {System.out.println(s);}System.out.println(-------------------------------------);System.out.println(查找java,null,haha的结果);System.out.println(my.contains(java));System.out.println(my.contains(null));System.out.println(my.contains(haha));System.out.println(-------------------------------------);System.out.println(替换java,null后);my.update(java,JAVA);my.update(null,songhk);System.out.println(所有元素);for (String s : my) {System.out.println(s);}System.out.println(-------------------------------------);System.out.println(删除helloJAVA,nullatguigu后);my.delete(hello);my.delete(JAVA);my.delete(null);my.delete(atguigu);System.out.println(所有元素);for (String s : my) {System.out.println(s);}}
}四 栈
4.1 栈的特点
栈Stack又称为堆栈或堆叠是限制仅在表的一端进行插入和删除运算的线性表。栈按照先进后出(FILO,first in last out)的原则存储数据先进入的数据被压入栈底最后的数据在栈顶。每次删除退栈的总是删除当前栈中最后插入进栈的元素而最先插入的是被放在栈的底部要到最后才能删除。 核心类库中的栈结构有Stack和LinkedList。 Stack就是顺序栈它是Vector的子类。LinkedList是链式栈。 体现栈结构的操作方法 peek()方法查看栈顶元素不弹出pop()方法弹出栈push(E e)方法压入栈 时间复杂度: 索引: O(n)搜索: O(n)插入: O(1)移除: O(1) 图示
4.2 Stack使用举例
public class TestStack {/** 测试Stack* */Testpublic void test1(){StackInteger list new Stack();list.push(1);list.push(2);list.push(3);System.out.println(list list);System.out.println(list.peek() list.peek());System.out.println(list.peek() list.peek());System.out.println(list.peek() list.peek());/*System.out.println(list.pop() list.pop());System.out.println(list.pop() list.pop());System.out.println(list.pop() list.pop());System.out.println(list.pop() list.pop());//java.util.NoSuchElementException
*/while(!list.empty()){System.out.println(list.pop() list.pop());}}/** 测试LinkedList* */Testpublic void test2(){LinkedListInteger list new LinkedList();list.push(1);list.push(2);list.push(3);System.out.println(list list);System.out.println(list.peek() list.peek());System.out.println(list.peek() list.peek());System.out.println(list.peek() list.peek());/*System.out.println(list.pop() list.pop());System.out.println(list.pop() list.pop());System.out.println(list.pop() list.pop());System.out.println(list.pop() list.pop());//java.util.NoSuchElementException
*/while(!list.isEmpty()){System.out.println(list.pop() list.pop());}}
}4.3 自定义栈
public class MyStack {// 向栈当中存储元素我们这里使用一维数组模拟。存到栈中就表示存储到数组中。// 为什么选择Object类型数组因为这个栈可以存储java中的任何引用类型的数据private Object[] elements;// 栈帧永远指向栈顶部元素// 那么这个默认初始值应该是多少。注意最初的栈是空的一个元素都没有。//private int index 0; // 如果index采用0表示栈帧指向了顶部元素的上方。//private int index -1; // 如果index采用-1表示栈帧指向了顶部元素。private int index;/*** 无参数构造方法。默认初始化栈容量10.*/public MyStack() {// 一维数组动态初始化// 默认初始化容量是10.this.elements new Object[10];// 给index初始化this.index -1;}/*** 压栈的方法* param obj 被压入的元素*/public void push(Object obj) throws Exception {if(index elements.length - 1){//方式1//System.out.println(压栈失败栈已满);//return;//方式2throw new Exception(压栈失败栈已满);}// 程序能够走到这里说明栈没满// 向栈中加1个元素栈帧向上移动一个位置。index;elements[index] obj;System.out.println(压栈 obj 元素成功栈帧指向 index);}/*** 弹栈的方法从数组中往外取元素。每取出一个元素栈帧向下移动一位。* return*/public Object pop() throws Exception {if (index 0) {//方式1//System.out.println(弹栈失败栈已空);//return;//方式2throw new Exception(弹栈失败栈已空);}// 程序能够执行到此处说明栈没有空。Object obj elements[index];System.out.print(弹栈 obj 元素成功);elements[index] null;// 栈帧向下移动一位。index--;return obj;}// set和get也许用不上但是你必须写上这是规矩。你使用IDEA生成就行了。// 封装第一步属性私有化第二步对外提供set和get方法。public Object[] getElements() {return elements;}public void setElements(Object[] elements) {this.elements elements;}public int getIndex() {return index;}public void setIndex(int index) {this.index index;}
}五 队列 队列Queue是只允许在一端进行插入而在另一端进行删除的运算受限的线性表。 队列是逻辑结构其物理结构可以是数组也可以是链表。 队列的修改原则队列的修改是依先进先出FIFO的原则进行的。新来的成员总是加入队尾即不允许加塞每次离开的成员总是队列头上的不允许中途离队即当前最老的成员离队。 图示
六 树与二叉树
6.1 树的理解 专有名词解释
结点树中的数据元素都称之为结点
根节点最上面的结点称之为根一颗树只有一个根且由根发展而来从另外一个角度来说每个结点都可以认为是其子树的根
父节点结点的上层结点如图中结点K的父节点是E、结点L的父节点是G
子节点节点的下层结点如图中节点E的子节点是K节点、节点G的子节点是L节点
兄弟节点具有相同父节点的结点称为兄弟节点图中F、G、H互为兄弟节点
结点的度数每个结点所拥有的子树的个数称之为结点的度如结点B的度为3
树叶度数为0的结点也叫作终端结点图中D、K、F、L、H、I、J都是树叶
非终端节点或分支节点树叶以外的节点或度数不为0的节点。图中根、A、B、C、E、G都是
树的深度或高度树中结点的最大层次数图中树的深度为4
结点的层数从根节点到树中某结点所经路径上的分支树称为该结点的层数根节点的层数规定为1其余结点的层数等于其父亲结点的层数1
同代在同一棵树中具有相同层数的节点
6.2 二叉树的基本概念
二叉树Binary tree是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式二叉树的存储结构及其算法都较为简单因此二叉树显得特别重要。 6.3 二叉树的遍历 前序遍历中左右根左右 即先访问根结点再前序遍历左子树最后再前序遍历右子 树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。 中序遍历左中右左根右 即先中前序遍历左子树然后再访问根结点最后再中序遍 历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。 后序遍历左右中左右根 即先后序遍历左子树然后再后序遍历右子树最后访问根 结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。
前序遍历ABDHIECFG
中序遍历HDIBEAFCG
后序遍历HIDEBFGCA
6.4 经典二叉树 满二叉树 除最后一层无任何子节点外每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方总的结点个数是2的n次方-1 完全二叉树 叶结点只能出现在最底层的两层且最底层叶结点均处于次底层叶结点的左侧。 二叉排序/查找/搜索树即为BST (binary search/sort tree)。满足如下性质 1若它的左子树不为空则左子树上所有结点的值均小于它的根节点的值 2若它的右子树上所有结点的值均大于它的根节点的值 3它的左、右子树也分别为二叉排序/查找/搜索树。 对二叉查找树进行中序遍历得到有序集合。便于检索。 平衡二叉树Self-balancing binary search treeAVL首先是二叉排序树此外具有以下性质 1它是一棵空树或它的左右两个子树的高度差的绝对值不超过1 2并且左右两个子树也都是一棵平衡二叉树 3不要求非叶节点都有两个子结点 平衡二叉树的目的是为了减少二叉查找树的层次提高查找速度。平衡二叉树的常用实现有红黑树、AVL、替罪羊树、Treap、伸展树等。 红黑树即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色可以是红(Red)或黑(Black)。 红黑树是一种自平衡二叉查找树是在计算机科学中用到的一种数据结构它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的但它的操作有着良好的最坏情况运行时间并且在实践中是高效的它可以在 O(log n)时间内做查找插入和删除 这里的 n 是树中元素的数目。
红黑树的特性
每个节点是红色或者黑色根节点是黑色每个叶子节点NIL是黑色。注意这里叶子节点是指为空(NIL或NULL)的叶子节点每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点确保没有一条路径会比其他路径长出2倍 当我们插入或删除节点时可能会破坏已有的红黑树使得它不满足以上5个要求那么此时就需要进行处理使得它继续满足以上的5个要求
1、recolor 将某个节点变红或变黑
2、rotation 将红黑树某些结点分支进行旋转左旋或右旋 红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据它的时间复杂度是O(logN)效率非常之高。 6.5 二叉树及其结点的表示
普通二叉树
public class BinaryTreeE{private TreeNode root; //二叉树的根结点private int total;//结点总个数private class TreeNode{//至少有以下几个部分TreeNode parent;TreeNode left;E data;TreeNode right;public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {this.parent parent;this.left left;this.data data;this.right right;}}
}TreeMap红黑树
public class TreeMapK,V {private transient EntryK,V root;private transient int size 0;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;/*** Make a new cell with given key, value, and parent, and with* {code null} child links, and BLACK color.*/Entry(K key, V value, EntryK,V parent) {this.key key;this.value value;this.parent parent;}}
}七 List接口分析
7.1 List接口特点
List集合所有的元素是以一种线性方式进行存储的例如存元素的顺序是11、22、33。那么集合中元素的存储就是按照11、22、33的顺序完成的。它是一个元素存取有序的集合。即元素的存入顺序和取出顺序有保证。它是一个带有索引的集合通过索引就可以精确的操作集合中的元素与数组的索引是一个道理。集合中可以有重复的元素通过元素的equals方法来比较是否为重复的元素。 注意 List集合关心元素是否有序而不关心是否重复请大家记住这个原则。例如“张三”可以领取两个号。 List接口的主要实现类 ArrayList动态数组Vector动态数组LinkedList双向链表Stack栈
7.2 动态数组ArrayList与Vector
Java的List接口的实现类中有两个动态数组的实现ArrayList 和 Vector。
7.2.1 ArrayList与Vector的区别
它们的底层物理结构都是数组我们称为动态数组。
ArrayList是新版的动态数组线程不安全效率高Vector是旧版的动态数组线程安全效率低。动态数组的扩容机制不同ArrayList默认扩容为原来的1.5倍Vector默认扩容增加为原来的2倍。数组的初始化容量如果在构建ArrayList与Vector的集合对象时没有显式指定初始化容量那么Vector的内部数组的初始容量默认为10而ArrayList在JDK 6.0 及之前的版本也是10JDK8.0 之后的版本ArrayList初始化为长度为0的空数组之后在添加第一个元素时再创建长度为10的数组。原因 用的时候再创建数组避免浪费。因为很多方法的返回值是ArrayList类型需要返回一个ArrayList的对象例如后期从数据库查询对象的方法返回值很多就是ArrayList。有可能你要查询的数据不存在要么返回null要么返回一个没有元素的ArrayList对象。
7.2.2 ArrayList部分源码分析
JDK1.7.0_07中
//属性
private transient Object[] elementData; //存储底层数组元素
private int size; //记录数组中存储的元素的个数//构造器
public ArrayList() {this(10); //指定初始容量为10
}public ArrayList(int initialCapacity) {super();//检查初始容量的合法性if (initialCapacity 0)throw new IllegalArgumentException(Illegal Capacity: initialCapacity);//数组初始化为长度为initialCapacity的数组this.elementData new Object[initialCapacity];
}//方法add()相关方法
public boolean add(E e) {ensureCapacityInternal(size 1); //查看当前数组是否够多存一个元素elementData[size] e; //将元素e添加到elementData数组中return true;
}private void ensureCapacityInternal(int minCapacity) {modCount;// 如果if条件满足则进行数组的扩容if (minCapacity - elementData.length 0)grow(minCapacity);
}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity elementData.length; //当前数组容量int newCapacity oldCapacity (oldCapacity 1); //新数组容量是旧数组容量的1.5倍if (newCapacity - minCapacity 0) //判断旧数组的1.5倍是否够newCapacity minCapacity;//判断旧数组的1.5倍是否超过最大数组限制if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);//复制一个新数组elementData Arrays.copyOf(elementData, newCapacity);
}//方法remove()相关方法
public E remove(int index) {rangeCheck(index); //判断index是否在有效的范围内modCount; //修改次数加1//取出[index]位置的元素[index]位置的元素就是要被删除的元素用于最后返回被删除的元素E oldValue elementData(index); int numMoved size - index - 1; //确定要移动的次数//如果需要移动元素就用System.arraycopy移动元素if (numMoved 0)System.arraycopy(elementData, index1, elementData, index, numMoved);//将elementData[size-1]位置置空让GC回收空间元素个数减少elementData[--size] null; return oldValue;
}private void rangeCheck(int index) {if (index size) //index不合法的情况throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}E elementData(int index) { //返回指定位置的元素return (E) elementData[index];
}//方法set()方法相关
public E set(int index, E element) {rangeCheck(index); //检验index是否合法//取出[index]位置的元素[index]位置的元素就是要被替换的元素用于最后返回被替换的元素E oldValue elementData(index);//用element替换[index]位置的元素elementData[index] element;return oldValue;
}//方法get()相关方法
public E get(int index) {rangeCheck(index); //检验index是否合法return elementData(index); //返回[index]位置的元素
}//方法indexOf()
public int indexOf(Object o) {//分为o是否为空两种情况if (o null) {//从前往后找for (int i 0; i size; i)if (elementData[i]null)return i;} else {for (int i 0; i size; i)if (o.equals(elementData[i]))return i;}return -1;
}//方法lastIndexOf()
public int lastIndexOf(Object o) {//分为o是否为空两种情况if (o null) {//从后往前找for (int i size-1; i 0; i--)if (elementData[i]null)return i;} else {for (int i size-1; i 0; i--)if (o.equals(elementData[i]))return i;}return -1;
}jdk1.8.0_271中
//属性
transient Object[] elementData;
private int size;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};//构造器
public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //初始化为空数组
}//方法:add()相关方法
public boolean add(E e) {//查看当前数组是否够多存一个元素ensureCapacityInternal(size 1); // Increments modCount!!//存入新元素到[size]位置然后size自增1elementData[size] e;return true;
}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private static int calculateCapacity(Object[] elementData, int minCapacity) {//如果当前数组还是空数组if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}//查看是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {modCount; //修改次数加1//如果需要的最小容量比当前数组的长度大即当前数组不够存就扩容if (minCapacity - elementData.length 0)grow(minCapacity);
}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity elementData.length; //当前数组容量int newCapacity oldCapacity (oldCapacity 1); //新数组容量是旧数组容量的1.5倍//看旧数组的1.5倍是否够if (newCapacity - minCapacity 0)newCapacity minCapacity;//看旧数组的1.5倍是否超过最大数组限制if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);//复制一个新数组elementData Arrays.copyOf(elementData, newCapacity);
}7.2.3 ArrayList相关方法图示
ArrayList采用数组作为底层实现 ArrayList自动扩容过程 ArrayList的add(E e)方法 ArrayList的add(int index,E e)方法
7.2.4 Vector部分源码分析
jdk1.8.0_271中
//属性
protected Object[] elementData;
protected int elementCount;//构造器
public Vector() {this(10); //指定初始容量initialCapacity为10
}public Vector(int initialCapacity) {this(initialCapacity, 0); //指定capacityIncrement增量为0
}public Vector(int initialCapacity, int capacityIncrement) {super();//判断了形参初始容量initialCapacity的合法性if (initialCapacity 0)throw new IllegalArgumentException(Illegal Capacity: initialCapacity);//创建了一个Object[]类型的数组this.elementData new Object[initialCapacity];//增量默认是0如果是0后面就按照2倍增加如果不是0后面就按照你指定的增量进行增量this.capacityIncrement capacityIncrement;
}//方法add()相关方法
//synchronized意味着线程安全的
public synchronized boolean add(E e) {modCount;//看是否需要扩容ensureCapacityHelper(elementCount 1);//把新的元素存入[elementCount]存入后elementCount元素的个数增1elementData[elementCount] e;return true;
}private void ensureCapacityHelper(int minCapacity) {//看是否超过了当前数组的容量if (minCapacity - elementData.length 0)grow(minCapacity); //扩容
}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity elementData.length; //获取目前数组的长度//如果capacityIncrement增量是0新容量 oldCapacity的2倍//如果capacityIncrement增量是不是0新容量 oldCapacity capacityIncrement增量;int newCapacity oldCapacity ((capacityIncrement 0) ?capacityIncrement : oldCapacity);//如果按照上面计算的新容量还不够就按照你指定的需要的最小容量来扩容minCapacityif (newCapacity - minCapacity 0)newCapacity minCapacity;//如果新容量超过了最大数组限制那么单独处理if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);//把旧数组中的数据复制到新数组中新数组的长度为newCapacityelementData Arrays.copyOf(elementData, newCapacity);
}//方法remove()相关方法
public boolean remove(Object o) {return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {modCount;//查找obj在当前Vector中的下标int i indexOf(obj);//如果i0说明存在删除[i]位置的元素if (i 0) {removeElementAt(i);return true;}return false;
}//方法indexOf()
public int indexOf(Object o) {return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {if (o null) {//要查找的元素是null值for (int i index ; i elementCount ; i)if (elementData[i]null)//如果是null值用null判断return i;} else {//要查找的元素是非null值for (int i index ; i elementCount ; i)if (o.equals(elementData[i]))//如果是非null值用equals判断return i;}return -1;
}//方法removeElementAt()
public synchronized void removeElementAt(int index) {modCount;//判断下标的合法性if (index elementCount) {throw new ArrayIndexOutOfBoundsException(index elementCount);}else if (index 0) {throw new ArrayIndexOutOfBoundsException(index);}//j是要移动的元素的个数int j elementCount - index - 1;//如果需要移动元素就调用System.arraycopy进行移动if (j 0) {//把index1位置以及后面的元素往前移动//index1的位置的元素移动到index位置依次类推//一共移动j个System.arraycopy(elementData, index 1, elementData, index, j);}//元素的总个数减少elementCount--;//将elementData[elementCount]这个位置置空用来添加新元素位置的元素等着被GC回收elementData[elementCount] null; /* to let gc do its work */
}7.3 链表LinkedList
Java中有双链表的实现LinkedList它是List接口的实现类。
LinkedList是一个双向链表如图所示
7.3.1 链表与动态数组的区别
动态数组底层的物理结构是数组因此根据索引访问的效率非常高。但是非末尾位置的插入和删除效率不高因为涉及到移动元素。另外添加操作时涉及到扩容问题就会增加时空消耗。
链表底层的物理结构是链表因此根据索引访问的效率不高即查找元素慢。但是插入和删除不需要移动元素只需要修改前后元素的指向关系即可所以插入、删除元素快。而且链表的添加不会涉及到扩容问题。
7.3.2 LinkedList源码分析
jdk1.8.0_271中
//属性
transient NodeE first; //记录第一个结点的位置
transient NodeE last; //记录当前链表的尾元素
transient int size 0; //记录最后一个结点的位置//构造器
public LinkedList() {
}//方法add()相关方法
public boolean add(E e) {linkLast(e); //默认把新元素链接到链表尾部return true;
}void linkLast(E e) {final NodeE l last; //用 l 记录原来的最后一个结点//创建新结点final NodeE newNode new Node(l, e, null);//现在的新结点是最后一个结点了last newNode;//如果lnull说明原来的链表是空的if (l null)//那么新结点同时也是第一个结点first newNode;else//否则把新结点链接到原来的最后一个结点的next中l.next newNode;//元素个数增加size;//修改次数增加modCount;
}//其中Node类定义如下
private static class NodeE {E item; //元素数据NodeE next; //下一个结点NodeE prev; //前一个结点Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}
//方法获取get()相关方法
public E get(int index) {checkElementIndex(index);return node(index).item;
} //方法插入add()相关方法
public void add(int index, E element) {checkPositionIndex(index);//检查index范围if (index size)//如果indexsize连接到当前链表的尾部linkLast(element);elselinkBefore(element, node(index));
}NodeE node(int index) {// assert isElementIndex(index);/*index (size 1)采用二分思想先将index与长度size的一半比较如果indexsize/2就只从位置0往后遍历到位置index处而如果indexsize/2就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历。*///如果indexsize/2就从前往后找目标结点if (index (size 1)) {NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {//否则从后往前找目标结点NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}
}//把新结点插入到[index]位置的结点succ前面
void linkBefore(E e, NodeE succ) {//succ是[index]位置对应的结点// assert succ ! null;final NodeE pred succ.prev; //[index]位置的前一个结点//新结点的prev是原来[index]位置的前一个结点//新结点的next是原来[index]位置的结点final NodeE newNode new Node(pred, e, succ);//[index]位置对应的结点的prev指向新结点succ.prev newNode;//如果原来[index]位置对应的结点是第一个结点那么现在新结点是第一个结点if (pred null)first newNode;elsepred.next newNode;//原来[index]位置的前一个结点的next指向新结点size;modCount;
}//方法remove()相关方法
public boolean remove(Object o) {//分o是否为空两种情况if (o null) {//找到o对应的结点xfor (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);//删除x结点return true;}}} else {//找到o对应的结点xfor (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);//删除x结点return true;}}}return false;
}
E unlink(NodeE x) {//x是要被删除的结点// assert x ! null;final E element x.item;//被删除结点的数据final NodeE next x.next;//被删除结点的下一个结点final NodeE prev x.prev;//被删除结点的上一个结点//如果被删除结点的前面没有结点说明被删除结点是第一个结点if (prev null) {//那么被删除结点的下一个结点变为第一个结点first next;} else {//被删除结点不是第一个结点//被删除结点的上一个结点的next指向被删除结点的下一个结点prev.next next;//断开被删除结点与上一个结点的链接x.prev null;//使得GC回收}//如果被删除结点的后面没有结点说明被删除结点是最后一个结点if (next null) {//那么被删除结点的上一个结点变为最后一个结点last prev;} else {//被删除结点不是最后一个结点//被删除结点的下一个结点的prev执行被删除结点的上一个结点next.prev prev;//断开被删除结点与下一个结点的连接x.next null;//使得GC回收}//把被删除结点的数据也置空使得GC回收x.item null;//元素个数减少size--;//修改次数增加modCount;//返回被删除结点的数据return element;
}public E remove(int index) { //index是要删除元素的索引位置checkElementIndex(index);return unlink(node(index));
}7.3.3 LinkedList相关方法图示
只有1个元素的LinkedList 包含4个元素的LinkedList add(E e)方法 add(int index,E e)方法 remove(Object obj)方法 remove(int index)方法
八 Map接口分析
8.1 哈希表的物理结构
HashMap和Hashtable底层都是哈希表也称散列表其中维护了一个长度为2的幂次方的Entry类型的数组table数组的每一个索引位置被称为一个桶(bucket)你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象放到某个table[index]桶中。
使用数组的目的是查询和添加的效率高可以根据索引直接定位到某个table[index]。
8.2 HashMap中数据添加过程
8.2.1 JDK7中过程分析
// 在底层创建了长度为16的Entry[] table的数组
HashMap map new HashMap(); map.put(key1,value1);
/*
分析过程如下将(key1,value1)添加到当前hashmap的对象中。首先会调用key1所在类的hashCode()方法计算key1的哈希值1
此哈希值1再经过某种运算(hash())得到哈希值2。此哈希值2再经过某种运算(indexFor())确定在底层table数组中的索引位置i。1如果数组索引为i上的数据为空则(key1,value1)直接添加成功 ------位置12如果数组索引为i上的数据不为空有(key2,value2)则需要进一步判断判断key1的哈希值2与key2的哈希值是否相同3 如果哈希值不同则(key1,value1)直接添加成功 ------位置2如果哈希值相同则需要继续调用key1所在类的equals()方法将key2放入equals()形参进行判断4 equals方法返回false : 则(key1,value1)直接添加成功 ------位置3equals方法返回true : 默认情况下value1会覆盖value2。位置1直接将(key1,value1)以Entry对象的方式存放到table数组索引i的位置。
位置2、位置3(key1,value1) 与现有的元素以链表的方式存储在table数组索引i的位置新添加的元素指向旧添加的元素。...
在不断的添加的情况下满足如下条件的情况下会进行扩容:
if ((size threshold) (null ! table[bucketIndex])) :
默认情况下当要添加的元素个数超过12(即数组的长度 * loadFactor得到的结果)时就要考虑扩容。补充jdk7源码中定义的
static class EntryK,V implements Map.EntryK,V
*/map.get(key1);
/*
① 计算key1的hash值用这个方法hash(key1)② 找index table.length-1 hash;③ 如果table[index]不为空那么就挨个比较哪个Entry的key与它相同就返回它的value
*/
map.remove(key1);
/*
① 计算key1的hash值用这个方法hash(key1)② 找index table.length-1 hash;③ 如果table[index]不为空那么就挨个比较哪个Entry的key与它相同就删除它把它前面的Entry的next的值修改为被删除Entry的next
*/8.2.2 JDK8中过程分析
下面说明是JDK8相较于JDK7的不同之处
/*
①
使用HashMap()的构造器创建对象时并没有在底层初始化长度为16的table数组。②
jdk8中添加的key,value封装到了HashMap.Node类的对象中。而非jdk7中的HashMap.Entry。③
jdk8中新增的元素所在的索引位置如果有其他元素。在经过一系列判断后如果能添加则是旧的元素指向新的元素。而非jdk7中的新的元素指向旧的元素。“七上八下”④
jdk7时底层的数据结构是数组单向链表。 而jdk8时底层的数据结构是数组单向链表红黑树。
红黑树出现的时机当某个索引位置i上的链表的长度达到8且数组的长度超过64时此索引位置上的元素要从单向链表改为红黑树。
如果索引i位置是红黑树的结构当不断删除元素的情况下当前索引i位置上的元素的个数低于6时要从红黑树改为单向链表。*/8.3 HashMap源码剖析
8.3.1 JDK1.7.0_07中源码 8.3.1.1 Entry
key-value被封装为HashMap.Entry类型而这个类型实现了Map.Entry接口。
public class HashMapK,V{transient EntryK,V[] table;static class EntryK,V implements Map.EntryK,V {final K key;V value;EntryK,V next;int hash;/*** Creates new entry.*/Entry(int h, K k, V v, EntryK,V n) {value v;next n;key k;hash h;}//略}
}8.3.1.2 属性
//table数组的默认初始化长度
static final int DEFAULT_INITIAL_CAPACITY 16;
//哈希表
transient EntryK,V[] table;
//哈希表中key-value的个数
transient int size;
//临界值、阈值扩容的临界值
int threshold;
//加载因子
final float loadFactor;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR 0.75f;8.3.1.3 构造器
public HashMap() {//DEFAULT_INITIAL_CAPACITY默认初始容量16//DEFAULT_LOAD_FACTOR默认加载因子0.75this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}public HashMap(int initialCapacity, float loadFactor) {//校验initialCapacity合法性if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);//校验initialCapacity合法性 if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;//校验loadFactor合法性if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);//计算得到table数组的长度保证capacity是2的整次幂int capacity 1;while (capacity initialCapacity)capacity 1;//加载因子初始化为0.75this.loadFactor loadFactor;// threshold 初始为默认容量threshold (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1);//初始化table数组table new Entry[capacity];useAltHashing sun.misc.VM.isBooted() (capacity Holder.ALTERNATIVE_HASHING_THRESHOLD);init();
}8.3.1.4 put()方法
public V put(K key, V value) {//如果key是null单独处理存储到table[0]中如果有另一个key为nullvalue覆盖if (key null)return putForNullKey(value);//对key的hashCode进行干扰算出一个hash值/*hashCode值 xxxxxxxxxxtable.length-1 000001111hashCode值 xxxxxxxxxx 无符号右移几位和原来的hashCode值做^运算使得hashCode高位二进制值参与计算也发挥作用降低index冲突的概率。*/int hash hash(key);//计算新的映射关系应该存到table[i]位置//i hash table.length-1可以保证i在[0,table.length-1]范围内int i indexFor(hash, table.length);//检查table[i]下面有没有key与我新的映射关系的key重复如果重复替换valuefor (EntryK,V e table[i]; e ! null; e e.next) {Object k;if (e.hash hash ((k e.key) key || key.equals(k))) {V oldValue e.value;e.value value;e.recordAccess(this);return oldValue;}}modCount;//添加新的映射关系addEntry(hash, key, value, i);return null;
}//如果key是null直接存入[0]的位置
private V putForNullKey(V value) {//判断是否有重复的key如果有重复的就替换valuefor (EntryK,V e table[0]; e ! null; e e.next) {if (e.key null) {V oldValue e.value;e.value value;e.recordAccess(this);return oldValue;}}modCount;//把新的映射关系存入[0]的位置而且key的hash值用0表示addEntry(0, null, value, 0);return null;
}final int hash(Object k) {int h 0;if (useAltHashing) {if (k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h hashSeed;}h ^ k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^ (h 20) ^ (h 12);return h ^ (h 7) ^ (h 4);
}static int indexFor(int h, int length) {return h (length-1);
}void addEntry(int hash, K key, V value, int bucketIndex) {//判断是否需要库容//扩容1size达到阈值2table[i]正好非空if ((size threshold) (null ! table[bucketIndex])) {//table扩容为原来的2倍并且扩容后会重新调整所有key-value的存储位置resize(2 * table.length); //新的key-value的hash和index也会重新计算hash (null ! key) ? hash(key) : 0;bucketIndex indexFor(hash, table.length);}//存入table中createEntry(hash, key, value, bucketIndex);
}void createEntry(int hash, K key, V value, int bucketIndex) {EntryK,V e table[bucketIndex];//原来table[i]下面的映射关系作为新的映射关系nexttable[bucketIndex] new Entry(hash, key, value, e);//个数增加size;
}8.3.2 JDK1.8.0_271中源码
8.3.2.1 Node
key-value被封装为HashMap.Node类型或HashMap.TreeNode类型它俩都直接或间接的实现了Map.Entry接口。
存储到table数组的可能是Node结点对象也可能是TreeNode结点对象它们也是Map.Entry接口的实现类。即table[index]下的映射关系可能串起来一个链表或一棵红黑树。
public class HashMapK,V{transient NodeK,V[] table;//Node类static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}// 其它结构略}//TreeNode类static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {TreeNodeK,V parent;TreeNodeK,V left;TreeNodeK,V right;TreeNodeK,V prev;boolean red; //是红结点还是黑结点TreeNode(int hash, K key, V val, NodeK,V next) {super(hash, key, val, next);}}//....
}8.3.3.2 属性
static final int DEFAULT_INITIAL_CAPACITY 1 4; // 默认的初始容量 16
static final int MAXIMUM_CAPACITY 1 30; //最大容量 1 30
static final float DEFAULT_LOAD_FACTOR 0.75f; //默认加载因子
static final int TREEIFY_THRESHOLD 8; //默认树化阈值8当链表的长度达到这个值后要考虑树化
static final int UNTREEIFY_THRESHOLD 6;//默认反树化阈值6当树中结点的个数达到此阈值后要考虑变为链表//当单个的链表的结点个数达到8并且table的长度达到64才会树化。
//当单个的链表的结点个数达到8但是table的长度未达到64会先扩容
static final int MIN_TREEIFY_CAPACITY 64; //最小树化容量64transient NodeK,V[] table; //数组
transient int size; //记录有效映射关系的对数也是Entry对象的个数
int threshold; //阈值当size达到阈值时考虑扩容
final float loadFactor; //加载因子影响扩容的频率8.3.3.3 构造器
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted (其他字段都是默认值)
}8.3.3.4 put()方法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {int h;//如果key是nullhash是0//如果key非null用key的hashCode值 与 key的hashCode值高16进行异或// 即就是用key的hashCode值高16位与低16位进行了异或的干扰运算/*index hash table.length-1如果用key的原始的hashCode值 与 table.length-1 进行按位与那么基本上高16没机会用上。这样就会增加冲突的概率为了降低冲突的概率把高16位加入到hash信息中。*/return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; //数组NodeK,V p; //一个结点int n, i; //n是数组的长度 i是下标//tab和table等价//如果table是空的if ((tab table) null || (n tab.length) 0){n (tab resize()).length;/*tab resize();n tab.length;*//*如果table是空的resize()完成了①创建了一个长度为16的数组②threshold 12n 16*/}//i (n - 1) hash 下标 数组长度-1 hash//p tab[i] 第1个结点//if(pnull) 条件满足的话说明 table[i]还没有元素if ((p tab[i (n - 1) hash]) null){//把新的映射关系直接放入table[i]tab[i] newNode(hash, key, value, null);//newNode方法就创建了一个Node类型的新结点新结点的next是null}else {NodeK,V e; K k;//p是table[i]中第一个结点//if(table[i]的第一个结点与新的映射关系的key重复)if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;//用e记录这个table[i]的第一个结点else if (p instanceof TreeNode){ //如果table[i]第一个结点是一个树结点//单独处理树结点//如果树结点中有key重复的就返回那个重复的结点用e接收即e!null//如果树结点中没有key重复的就把新结点放到树中并且返回null即enulle ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);}else {//table[i]的第一个结点不是树结点也与新的映射关系的key不重复//binCount记录了table[i]下面的结点的个数for (int binCount 0; ; binCount) {//如果p的下一个结点是空的说明当前的p是最后一个结点if ((e p.next) null) {//把新的结点连接到table[i]的最后p.next newNode(hash, key, value, null);//如果binCount8-1达到7个时if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//要么扩容要么树化treeifyBin(tab, hash);break;}//如果key重复了就跳出for循环此时e结点记录的就是那个key重复的结点if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;//下一次循环ep.next就类似于ee.next往链表下移动}}//如果这个e不是null说明有key重复就考虑替换原来的valueif (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e); //什么也没干return oldValue;}}modCount;//元素个数增加//size达到阈值if (size threshold)resize(); //一旦扩容重新调整所有映射关系的位置afterNodeInsertion(evict); //什么也没干return null;
}final NodeK,V[] resize() {NodeK,V[] oldTab table; //oldTab原来的table//oldCap原来数组的长度int oldCap (oldTab null) ? 0 : oldTab.length;//oldThr原来的阈值int oldThr threshold;//最开始threshold是0//newCap新容量//newThr新阈值int newCap, newThr 0;if (oldCap 0) { //说明原来不是空数组if (oldCap MAXIMUM_CAPACITY) { //是否达到数组最大限制threshold Integer.MAX_VALUE;return oldTab;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)//newCap 旧的容量*2 新容量最大数组容量限制//新容量32,64...//oldCap 初始容量16//新阈值重新算 2448 ....newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY; //新容量是默认初始化容量16//新阈值 默认的加载因子 * 默认的初始化容量 0.75*16 12newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr; //阈值赋值为新阈值1224.。。。//创建了一个新数组长度为newCap1632,64.。。SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) { //原来不是空数组//把原来的table中映射关系倒腾到新的table中for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {//e是table下面的结点oldTab[j] null; //把旧的table[j]位置清空if (e.next null) //如果是最后一个结点newTab[e.hash (newCap - 1)] e; //重新计算e的在新table中的存储位置然后放入else if (e instanceof TreeNode) //如果e是树结点//把原来的树拆解放到新的table((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;//把原来table[i]下面的整个链表重新挪到了新的table中do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}NodeK,V newNode(int hash, K key, V value, NodeK,V next) {//创建一个新结点return new Node(hash, key, value, next);
}final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;//MIN_TREEIFY_CAPACITY最小树化容量64//如果table是空的或者 table的长度没有达到64if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();//先扩容else if ((e tab[index (n - 1) hash]) ! null) {//用e记录table[index]的结点的地址TreeNodeK,V hd null, tl null;/*do...while把table[index]链表的Node结点变为TreeNode类型的结点*/do {TreeNodeK,V p replacementTreeNode(e, null);if (tl null)hd p;//hd记录根结点else {p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);//如果table[index]下面不是空if ((tab[index] hd) ! null)hd.treeify(tab);//将table[index]下面的链表进行树化}
} 小结
8.4 LinkedHashMap源码剖析
8.4.1 源码
内部定义的Entry如下
static class EntryK,V extends HashMap.NodeK,V {EntryK,V before, after;Entry(int hash, K key, V value, NodeK,V next) {super(hash, key, value, next);}
}LinkedHashMap重写了HashMap中的newNode()方法
NodeK,V newNode(int hash, K key, V value, NodeK,V e) {LinkedHashMap.EntryK,V p new LinkedHashMap.EntryK,V(hash, key, value, e);linkNodeLast(p);return p;
}TreeNodeK,V newTreeNode(int hash, K key, V value, NodeK,V next) {TreeNodeK,V p new TreeNodeK,V(hash, key, value, next);linkNodeLast(p);return p;
}8.4.2 图示 九 Set接口分析
9.1 Set集合与Map集合的关系
Set的内部实现其实是一个MapSet中的元素存储在HashMap的key中。即HashSet的内部实现是一个HashMapTreeSet的内部实现是一个TreeMapLinkedHashSet的内部实现是一个LinkedHashMap。
9.2 源码剖析
9.2.1 HashSet源码
//构造器
public HashSet() {map new HashMap();
}public HashSet(int initialCapacity, float loadFactor) {map new HashMap(initialCapacity, loadFactor);
}public HashSet(int initialCapacity) {map new HashMap(initialCapacity);
}//这个构造器是给子类LinkedHashSet调用的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {map new LinkedHashMap(initialCapacity, loadFactor);
}//add()方法
public boolean add(E e) {return map.put(e, PRESENT)null;
}
//其中
private transient HashMapE,Object map;
private static final Object PRESENT new Object();//iterator()方法
public IteratorE iterator() {return map.keySet().iterator();
}9.2.2 LinkedHashSet源码
//构造器
public LinkedHashSet() {super(16, .75f, true);
}
public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);//调用HashSet的某个构造器
}
public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);//调用HashSet的某个构造器
} 9.2.3 TreeSet源码
public TreeSet() {this(new TreeMapE,Object());
}TreeSet(NavigableMapE,Object m) {this.m m;
}
//其中
private transient NavigableMapE,Object m;//add()方法
public boolean add(E e) {return m.put(e, PRESENT)null;
}
//其中
private static final Object PRESENT new Object();十 【拓展】HashMap的相关问题
10.1 说说你理解的哈希算法
hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法它将任意大小的数据映射到一个固定大小的序列上这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的唯一性是指相同的“对象”产生的hash code永远是一样的。
10.2 Entry中的hash属性为什么不直接使用key的hashCode()返回值呢
不管是JDK1.7还是JDK1.8中都不是直接用key的hashCode值直接与table.length-1计算求下标的而是先对key的hashCode值进行了一个运算JDK1.7和JDK1.8关于hash()的实现代码不一样但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果尽量的均匀分布。
JDK1.7 final int hash(Object k) {int h hashSeed;if (0 ! h k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^ k.hashCode();h ^ (h 20) ^ (h 12);return h ^ (h 7) ^ (h 4);}JDK1.8
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}虽然算法不同但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或然高位二进制参与到index的计算中。
为什么要hashCode值的二进制的高位参与到index计算呢
因为一个HashMap的table数组一般不会特别大至少在不断扩容之前那么table.length-1的大部分高位都是0直接用hashCode和table.length-1进行运算的话就会导致总是只有最低的几位是有效的那么就算你的hashCode()实现的再好也难以避免发生碰撞这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征显著减少了碰撞冲突的发生。
10.3 HashMap是如何决定某个key-value存在哪个桶的呢
因为hash值是一个整数而数组的长度也是一个整数有两种思路
①hash 值 % table.length会得到一个[0,table.length-1]范围的值正好是下标范围但是用%运算效率没有位运算符高。
②hash 值 (table.length-1)任何数 (table.length-1)的结果也一定在[0, table.length-1]范围。 JDK1.7
static int indexFor(int h, int length) {// assert Integer.bitCount(length) 1 : length must be a non-zero power of 2;return h (length-1); //此处h就是hash
}JDK1.8
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null) // i (n - 1) hashtab[i] newNode(hash, key, value, null);//....省略大量代码
}10.4 为什么要保持table数组一直是2的n次幂呢
因为如果数组的长度为2的n次幂那么table.length-1的二进制就是一个高位全是0低位全是1的数字这样才能保证每一个下标位置都有机会被用到。
举例1
hashCode值是
table.length是10
table.length-1是9 ????????
9 00001001
_____________00000000 [0]00000001 [1]00001000 [8]00001001 [9]一定[0]~[9]举例2
hashCode值是
table.length是16
table.length-1是15 ????????
15 00001111
_____________00000000 [0]00000001 [1]00000010 [2]00000011 [3]...00001111 [15]范围是[0,15]一定在[0,table.length-1]范围内10.5 解决[index]冲突问题
虽然从设计hashCode()到上面HashMap的hash()函数都尽量减少冲突但是仍然存在两个不同的对象返回的hashCode值相同或者hashCode值就算不同通过hash()函数计算后得到的index也会存在大量的相同因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办
JDK1.8之间使用数组链表的结构。 JDK1.8之后使用数组链表/红黑树的结构。 即hash相同或hash(table.lengt-1)的值相同那么就存入同一个“桶”table[index]中使用链表或红黑树连接起来。
10.6 为什么JDK1.8会出现红黑树和链表共存呢
因为当冲突比较严重时table[index]下面的链表就会很长那么会导致查找效率大大降低而如果此时选用二叉树可以大大提高查询效率。
但是二叉树的结构又过于复杂占用内存也较多如果结点个数比较少的时候那么选择链表反而更简单。所以会出现红黑树和链表共存。
10.7 加载因子的值大小有什么关系
如果太大threshold就会很大那么如果冲突比较严重的话就会导致table[index]下面的结点个数很多影响效率。
如果太小threshold就会很小那么数组扩容的频率就会提高数组的使用率也会降低那么会造成空间的浪费。
10.8 什么时候树化什么时候反树化
static final int TREEIFY_THRESHOLD 8;//树化阈值
static final int UNTREEIFY_THRESHOLD 6;//反树化阈值
static final int MIN_TREEIFY_CAPACITY 64;//最小树化容量当某table[index]下的链表的结点个数达到8并且table.length64那么如果新Entry对象还添加到该table[index]中那么就会将table[index]的链表进行树化。当某table[index]下的红黑树结点个数少于6个此时 当继续删除table[index]下的树结点最后这个根结点的左右结点有null或根结点的左结点的左结点为null会反树化当重新添加新的映射关系到map中导致了map重新扩容了这个时候如果table[index]下面还是小于等于6的个数那么会反树化
public class MyKey{int num;public MyKey(int num) {super();this.num num;}Overridepublic int hashCode() {if(num20){return 1;}else{final int prime 31;int result 1;result prime * result num;return result;}}Overridepublic boolean equals(Object obj) {if (this obj)return true;if (obj null)return false;if (getClass() ! obj.getClass())return false;MyKey other (MyKey) obj;if (num ! other.num)return false;return true;}}public class TestHashMapMyKey {Testpublic void test1(){//这里为了演示的效果我们造一个特殊的类这个类的hashCode方法返回固定值1//因为这样就可以造成冲突问题使得它们都存到table[1]中HashMapMyKey, String map new HashMap();for (int i 1; i 11; i) {map.put(new MyKey(i), valuei);//树化演示}}Testpublic void test2(){HashMapMyKey, String map new HashMap();for (int i 1; i 11; i) {map.put(new MyKey(i), valuei);}for (int i 1; i 11; i) {map.remove(new MyKey(i));//反树化演示}}Testpublic void test3(){HashMapMyKey, String map new HashMap();for (int i 1; i 11; i) {map.put(new MyKey(i), valuei);}for (int i 1; i 5; i) {map.remove(new MyKey(i));}//table[1]下剩余6个结点for (int i 21; i 100; i) {map.put(new MyKey(i), valuei);//添加到扩容时反树化}}
}
10.9 key-value中的key是否可以修改
key-value存储到HashMap中会存储key的hash值这样就不用在每次查找时重新计算每一个Entry或NodeTreeNode的hash值了因此如果已经put到Map中的key-value再修改key的属性而这个属性又参与hashcode值的计算那么会导致匹配不上。
这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。
10.10 JDK1.7中HashMap的循环链表是怎么回事如何解决
避免HashMap发生死循环的常用解决方案
多线程环境下使用线程安全的ConcurrentHashMap替代HashMap推荐多线程环境下使用synchronized或Lock加锁但会影响性能不推荐多线程环境下使用线程安全的Hashtable替代性能低不推荐
HashMap死循环只会发生在JDK1.7版本中主要原因头插法链表多线程并发扩容。
在JDK1.8中HashMap改用尾插法解决了链表死循环的问题。
