推荐最新

cloud-atlas

### 《云图》这是一个不断迭代改进的开源技术分享项目，我想以每获得100个GitHub Star作为0.1版本的递进，不断完善这本技术书。请访问 readthedocs平台上的云图以便获得最佳阅读体验。 ### 这本书的目标大概在两年前，作者萌生了以开源技术构建自动化部署和交付数据中心的想法。通过开源技术来构建 one personal detacenter ，即一个人来实现完整的数据中心的构建和运维，实现IaaS，PaaS，SaaS。开源技术的迅速发展，已经赋能给全栈工程师，或许能以一己之力实现数据中心构建和维护。从存储、网络、虚拟化，从操作系统到数据库，从Web服务到消息中间件，只要是基础的服务，都应该通过自动化以及精心构建的架构来实现效率的最大化。作者写这本书是自己思考和实践的结合。为了能够模拟集群技术，作者采用了个人笔记本和二手服务器来构建实验环境，模拟构建IDC所使用的各种开源技术，力求能够将实践的方案无缝扩展成真实的数据中心。 ### 本书的特点本书的(几乎)所有文章都经过作者自己的实践验证，完整分享每个操作步骤，力求清晰、准确、可复现: 和很多(空洞的)PPT分享不同，作者的分享就是真实可复现的操作实践，没有隐藏和遗漏即使是翻译和综合，作者也会把自己的实践经验以及踩过的坑和解决方法融合到文章中，使Clous Atlas成为真正的实践指南

浏览量39

英勇黄铜

顺序表与ArrayList

线性表线性表就是有多个相同属性的数据元素的有限序列。线性表是一种在我们工作中广泛可以使用到的数据结构，常见的线性表：顺序表，链表，栈，队列……线性表在逻辑上是线性结构，是一条连续的直线。但是它在物理结构上可可能不是连续的。线性表在物理上存储时，一般是以数组和链式结构的方式存储。顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。简单顺序表的模拟实现大家可以移步到 Gitee 上看代码：structure_code/java2023.9.12/src/mylist · 彭子杰/数据结构 - 码云 - 开源中国 (gitee.com)集合框架java 集合框架，也称为容器，是定义在 java.util 包下的一组接口 interfaces 和其实现类 class 。它是要的作用是将多个元素 element 置于一个单元中，用于对这些元素进行快速，便捷的存储 store ，检索 retrieve ，管理 manipulate ，即平时我们说的增删查改。类与接口总览：ArrayList 介绍在 java 的集合框架（容器）中，ArrayList 就是一个顺序表，它是一个普通的类，实现了 List 接口，框架如下：注意：ArrayList 是以泛型方式实现的，使用时需要先实例化ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问ArrayList 实现了 cloneble 接口，表明 ArrayList 是可以 clone 的ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的和 Vector 不同，ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择 Vector 或者 CopyOnWriteArrayListArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表ArrayList 的使用ArrayList 的构造public class Test { public static void main(String[] args) { // ArrayList创建，推荐写法 // 构造一个空的列表 List<Integer> list1 = new ArrayList<>(); // 构造一个具有10个容量的列表 List<Integer> list2 = new ArrayList<>(10); list2.add(1); list2.add(2); list2.add(3); // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素 // list3构造好之后，与list中的元素一致 ArrayList<Integer> list3 = new ArrayList<>(list2); // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难 List list4 = new ArrayList(); list4.add("111"); list4.add(100); } }ArrayList 的基本方法 public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("JavaSE"); list.add("JavaWeb"); list.add("JavaEE"); list.add("JVM"); list.add("测试课程"); System.out.println(list); // 获取list中有效元素个数 System.out.println(list.size()); // 获取和设置index位置上的元素，注意index必须介于[0, size)间 System.out.println(list.get(1)); list.set(1, "JavaWEB"); System.out.println(list.get(1)); // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置 list.add(1, "Java数据结构"); System.out.println(list); // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置 list.remove("JVM"); System.out.println(list); // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常 list.remove(list.size()-1); System.out.println(list); } // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找 list.add("JavaSE"); System.out.println(list.indexOf("JavaSE")); System.out.println(list.lastIndexOf("JavaSE")); // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组 // List<String> ret = list.subList(0, 4); System.out.println(ret); list.clear(); System.out.println(list.size()); }ArrayList 的遍历ArrayList 可以使用三个方式来遍历： for 循环， foreach ，迭代器 public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); // 使用下标+for遍历 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + " "); } System.out.println(); // 借助foreach遍历 for (Integer integer : list) { System.out.print(integer + " "); } System.out.println(); // 使用迭代器遍历 Iterator<Integer> it = list.listIterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); }这里的迭代器是设计模式的一种。ArrayList 的扩容机制首选我们来看一段代码：public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < 100; i++) { list.add(i); } }我们知道，ArrayList 是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。我们可以看一下源码：Object[] elementData; // 存放元素的空间 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间 private static final int DEFAULT_CAPACITY = 10; // 默认容量大小 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[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) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private void grow(int minCapacity) { // 获取旧空间大小 int oldCapacity = elementData.length; // 预计按照1.5倍方式扩容 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果用户需要扩容大小超过原空间1.5倍，按照用户所需大小扩容 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 调用copyOf扩容 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { // 如果minCapacity小于0，抛出OutOfMemoryError异常 if (minCapacity < 0) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }画图分析【总结】检查是否真正需要扩容，如果是 g 调用了 row 准备扩容估计需要库容的大小初步按照 1.5 倍的大小扩容如果用户需要的大小超过1.5倍，则按照用户所需大小扩容真正扩容之前检查是否可以扩容成功，防止太大导致扩容失败使用 copyof 进行扩容ArrayList 的具体使用这里举一个简单的洗牌算法：public class Card { public int rank; // 牌面值 public String suit; // 花色 @Override public String toString() { return String.format("[%s %d]", suit, rank); } } import java.util.List; import java.util.ArrayList; import java.util.Random; public class CardDemo { public static final String[] SUITS = {"♠", "♥", "♣", "♦"}; // 买一副牌 private static List<Card> buyDeck() { List<Card> deck = new ArrayList<>(52); for (int i = 0; i < 4; i++) { for (int j = 1; j <= 13; j++) { String suit = SUITS[i]; int rank = j; Card card = new Card(); card.rank = rank; card.suit = suit; deck.add(card); } } return deck; } private static void swap(List<Card> deck, int i, int j) { Card t = deck.get(i); deck.set(i, deck.get(j)); deck.set(j, t); } private static void shuffle(List<Card> deck) { Random random = new Random(20190905); for (int i = deck.size() - 1; i > 0; i--) { int r = random.nextInt(i); swap(deck, i, r); } } public static void main(String[] args) { List<Card> deck = buyDeck(); System.out.println("刚买回来的牌:"); System.out.println(deck); shuffle(deck); System.out.println("洗过的牌:"); System.out.println(deck); // 三个人，每个人轮流抓 5 张牌 List<List<Card>> hands = new ArrayList<>(); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { hands.get(j).add(deck.remove(0)); } } System.out.println("剩余的牌:"); System.out.println(deck); System.out.println("A 手中的牌:"); System.out.println(hands.get(0)); System.out.println("B 手中的牌:"); System.out.println(hands.get(1)); System.out.println("C 手中的牌:"); System.out.println(hands.get(2)); } }顺序表 ArrayList 存储结构的优缺点优点不用为了表达清楚元素之间的关系而增加额外的存储空间。可以快速地存取表中的任意一个位置的元素缺点在任位置删除插入元素的时间复杂度为O(N)，所以需要移动大量的元素当顺序表长度变化较大时，难以确定存储空间的容量。容易造成存储空间的碎片，也就是浪费空间。

浏览量2174

英勇黄铜

String类对象的创建与字符串常量池的“神秘交易”

创建对象内的“那些事”话不多说，直接上代码：public static void main(String[] args) { String s1 = "hello"; String s2 = "hello"; String s3 = new String("hello"); String s4 = new String("hello"); System.out.println(s1 == s2); // true System.out.println(s1 == s3); // false System.out.println(s3 == s4); // false }上面这个代码我们发现创建的 String 对象的方式类似，但是结果 s1 和 s2 是同一个对象，但 s3 和 s4 却却不是？这就是要深究到 java 中的常量池了。在 java 中，“hello”，“1234” 等常量经常被频繁使用，java 为了让程序运行的速度更加快，跟节省内存，就为 8 种基本类型和 String 类提供了常量池。java 中引入了：Class 文件常量池：每个 Java 源文件编译后生成的 Class 文件中会保存当前类中的字面常量以及符号信息运行时常量池：在. Class 文件被加载时，Class 文件中的常量池被加载到内存中称为运行时常量池，运行时常量池每个类都会有一份"池" 是编程中的一种常见的, 重要的提升效率的方式, 我们会在遇到各种 "内存池", "线程池", "数据库连接池"字符串常量池字符串常量池在 JVM 中是一个 StringTable 类，实际是一固定大小的 HashTable，它是一种高效查找的数据结构，在不同的 JDK 版本下字符串常量池的位置以及默认大小是不同的：对 String 对象创建的具体分析直接使用字符串常量进行赋值public static void main(String[] args) { String str1 ="hello"; String str2 ="hello"; System.out.println(str1 == str2); } 这里直接通过画图分析：通过 new 创建 String 对象public static void main(String[] args) { String str1 = new String("hello"); String str2 = "hello"; System.out.println(str1 == str2); }这里我们得到一个结论：只要是 new 出来的对象，就是唯一的这里我们可以知道：使用常量串创建 String 类型对象的效率更高，更节省空间。用户也可以将创建的字符串对象通过 intern 方式添加进字符串常量池中intern 方法intern 方法的作用就是将创建的 String 对象添加到常量池中、public static void main(String[] args) { char[] ch = new char[]{'a', 'b', 'c'}; String s1 = new String(ch); // s1对象并不在常量池中 //s1.intern(); 调用之后，会将s1对象的引用放入到常量池中 String s2 = "abc"; // "abc" 在常量池中存在了，s2创建时直接用常量池中"abc"的引用 System.out.println(s1 == s2); }放开前返回的是 false，放开后返回 true：使用方法前，常量池中没有 “abc” ，导致 str2 自己重新创建了一份 “abc”使用方法后，常量池中有了 “abc” ， str2 直接拿过来用就可以了

浏览量2025

英勇黄铜

二叉树

树形结构什么是树形结构树是一种非线性的数据结构，它是由 n（ >= 0）个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一个根朝上，叶朝下的倒挂树。特点：有一个特殊的结点，称为根结点，根节点没有前驱结点除根结点外，其他结点被分为m个互不相交的集合树是递归定义的注意：树形结构中，子树是不能有交集的，否则就不是树形结构重要概念结点的度：一个结点含有子树的个数称为该结点的度树的度：一棵树中，所有结点度中的最大值为该树的度叶子结点：度为 0 的结点称为叶结点父结点：如果一个节点有子结点，则这个结点被称为父结点子结点：一个结点含有的子树的根结点称为该结点的子结点根结点：一课树中，没有父结点的结点结点的层次：从根结点开始定义起，根为第一层，根的子结点为第二层，依次类推树的高度或深度：树中结点的最大层次非终端结点或分支结点：度不为 0 的结点兄弟结点：具有相同父结点的结点互称为兄弟结点堂兄弟结点：双亲在同一层的结点互为堂兄弟结点的祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中任一结点都称为该结点的子孙森林：由 m（ m >= 0 ）棵互不相交的树组成的集合称为森林树的表示形式树的结构相对线性表比较复杂，要储存表示起来比较麻烦，实际中树有许多表示方法：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等。下面写一种最常用的孩子兄弟表示法。class Node { int value; // 树中存储的数据 Node firstChild; // 第一个孩子引用 Node nextBrother; // 下一个兄弟引用 } 树的应用一般我们文件系统管理就是用树形结构来处理的二叉树什么是二叉树一颗二叉树是结点的有限集合，这个集合：可能为空可能是由一个根结点加上两颗左子树和右子树的二叉树组成的注意：二叉树不存在度大于 2 的结点二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树二叉树有几种情况复合而成：二叉树的性质若根结点的层数为 1 ，则一颗非空的二叉树的第i层上最多有 2^( i-1 ) 个结点若规定只有根结点的二叉树的深度为 1，则深度为K的二叉树的最大结点数是 2^k - 1对任何一个二叉树，如果其叶结点个数为 n0 ，度为2的非叶结点的个数为 n2 ，则有 n0 = n2 + 1具有n个结点的完全二叉树的深度 K 为 log2(n+1) 向上取整对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：若 i>0，双亲序号：(i-1)/2 ；i=0 ，i 为根结点编号，无双亲结点若 2i+1<n ，左孩子序号：2i+1 ，否则无左孩子若 2i+2<n ，右孩子序号：2i+2 ，否则无右孩子二叉树的存储二叉树的存储结构分为：顺序存储和链式存储二叉树的链式存储是通过一个一个节点引用起来的，通常表示的方式有二叉和三叉表示方式// 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 } // 孩子双亲表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的根节点 } 二叉树的基本操作下面是二叉树一些基本功能的代码：public class BinaryTree { static class TreeNode { char val; TreeNode left; TreeNode right; public TreeNode(char val) { this.val = val; } } public TreeNode createTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } //前序遍历 public void preOrder(TreeNode root) { if(root == null) { return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } //中序遍历 public void inOrder(TreeNode root) { if(root == null) { return; } preOrder(root.left); System.out.print(root.val+" "); preOrder(root.right); } //后序遍历 public void lastOrder(TreeNode root) { if(root == null) { return; } preOrder(root.right); preOrder(root.left); System.out.print(root.val+" "); } //求tree的节点个数 int Treesize; public int size(TreeNode root) { if(root == null) { return 0; } Treesize++; size(root.left); size(root.right); return Treesize; } public int size1(TreeNode root) { if(root == null) { return 0; } return size1(root.left) + size1(root.right) + 1; } // 获取叶子节点的个数 int getLeafNodeCount(TreeNode root) { if(root == null) { return 0; } if(root.left == null && root.right == null) { return 1; } return getLeafNodeCount(root.left)+getLeafNodeCount(root.right); } // 获取第K层节点的个数 int getKLevelNodeCount(TreeNode root, int k) { if(root == null) { return 0; } if(k==1) { return 1; } return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1); } // 获取二叉树的高度 int getHeight(TreeNode root){ if(root == null) { return 0; } int a = getHeight(root.left); int b = getHeight(root.right); return a > b ? a+1 : b+1; } // 检测值为value的元素是否存在 TreeNode find(TreeNode root, char val) { if(root == null) { return null; } if(root.val == val) { return root; } TreeNode leftNode = find(root.left, val); if(leftNode != null) { return leftNode; } TreeNode rightNode = find(root.right, val); if(rightNode != null) { return rightNode; } return null; }二叉树的遍历前中后序遍历在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L 代表根节点的左子树，R 代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：NLR：前序遍历 (Preorder Traversal 亦称先序遍历) —— 访问根结点 ---> 根的左子树 ---> 根的右子树。LNR：中序遍历 (Inorder Traversal)—— 根的左子树 ---> 根节点 ---> 根的右子树。LRN：后序遍历 (Postorder Traversal) —— 根的左子树 ---> 根的右子树 ---> 根节点。具体代码：//前序遍历 public void preOrder(TreeNode root) { if(root == null) { return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } //中序遍历 public void inOrder(TreeNode root) { if(root == null) { return; } preOrder(root.left); System.out.print(root.val+" "); preOrder(root.right); } //后序遍历 public void lastOrder(TreeNode root) { if(root == null) { return; } preOrder(root.right); preOrder(root.left); System.out.print(root.val+" "); }层序遍历除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历具体代码：class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> array = new ArrayList<>(); if(root == null) { return array; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { List<Integer> tmp = new ArrayList<>(); int size = queue.size(); while(size != 0) { TreeNode x = queue.poll(); tmp.add(x.val); size--; if(x.left != null) { queue.offer(x.left); } if(x.right != null) { queue.offer(x.right); } } array.add(tmp); } return array; } }

浏览量2054

英勇黄铜

哈希表

什么是哈希表顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为 O(N)，平衡树中为树的高度，即 O( logN)，搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素向该结构中插入元素时：根据待插入的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素时：堆元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，按此位置取元素比较，若关键码相等，则查找成功这个方式就是哈希方法，哈希方法中使用的转换函数称为哈希函数，构造出来的结构称为哈希表，使用这个方法进行搜索不必进行多次的关键码的比价，使用搜索速度比较快，但是它有发生冲突的可能冲突冲突的概念不同的数据在通过同一个哈希函数的计算出相同的哈希地址的数据元素称为同义词，也就是发生冲突了。冲突的避免冲突的发生是无法避免的，因为我们哈希表的底层数组的容量往往是小于要存储的数据的数量的，这就导致冲突的发生是必然的，我们只能尽量的降低冲突率减少冲突的哈希函数引起哈希冲突的一个原因可能是：哈希函数设计不够合理。这里哈希函数的设计有一些原则：1 哈希函数的定义域必须包括需要存储的全部数据2 哈希函数计算出来的地址可以均匀分布在空间中3 哈希函数需要比较简单常见的哈希函数1. 直接定制法取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况面试题：字符串中第一个只出现一次字符2. 除留余数法设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址，Java 中的哈希函数就是使用的这3. 平方取中法假设关键字为 1234，对它平方就是 1522756，抽取中间的 3 位 227 作为哈希地址；再比如关键字为 4321，对它平方就是 8671041，抽取中间的 3 位 671 (或 710) 作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况这里要注意一点：哈希函数虽然设计的越巧妙，哈希冲突的可能性就越小，但是哈希冲突是无法避免的冲突避免的负载因子载荷因子定义为：a = 哈希表中放入元素个数 /哈希表的长度通过图我们可以发现，放冲突率到一个程度的时候，我们就需要通过降低负载因子来降低冲突率。我们知道哈希表放入的数据是不可以变的，那我们只能调整哈希表中的数组大小了。冲突的解决我们一般解决冲突有两种方法：闭散列和开散列闭散列闭散列也叫开放地址法，当发生哈希冲突的时候，如果哈希表没有被装满，那么可以将数据方法冲突位置的下一个空位置去。1. 线性探测比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为 4 ，因此 44 理论上应该插在该位置，但是该位置已经放了值为 4 的元素，即发生哈希冲突。线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。插入通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素 4，如果直接删除掉，44 查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素 2. 二次探测线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为 Hi = (H0 + i^2) % m , 其中：i = 1,2,3…，是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置，m 是表的大小.研究表明：当表的长度为质数且表装载因子 a 不超过 0.5 时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子 a 不超过 0.5，如果超出必须考虑增容。因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷开散列/哈希桶Java 中的 HashMap 和 HashSet 底层就是使用的哈希桶开散列法又叫链地址法 (开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。我们知道，桶中放的就是冲突的元素，开散列就是一个大集合中的搜索问题转化为在小集合中做搜索了。冲突严重中的解决方法刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：1. 每个桶的背后是另一个哈希表2. 每个桶的背后是一棵搜索树哈希桶的模拟实现 public class HashBucket { static class Node { int key; int val; Node next; public Node(int key, int val) { this.key = key; this.val = val; } } private Node[] array = new Node[10]; private int usedsize; private static final float DEFAULT_LOAD_FACTOR = 0.75f; public void put(int key, int val) { Node node = new Node(key, val); int Index = key % array.length; Node cur = array[Index]; while(cur != null) { if(cur.key == key) { cur.val = val; return; } cur = cur.next; } node.next = array[Index]; array[Index] = node; usedsize++; if(usedsize * 1.0f / array.length > DEFAULT_LOAD_FACTOR) { array = resize(array); } } private Node[] resize(Node[] array) { Node[] newArray = Arrays.copyOf(array, 2*array.length); for (int i = 0; i < array.length; i++) { Node cur = array[i]; while(cur != null) { int Index = cur.key % newArray.length; Node nextcur = cur.next; cur.next = newArray[Index]; newArray[Index] = cur; cur = nextcur; } } return newArray; } public int get(int key) { int Index = key % array.length; Node cur = array[Index]; while(cur != null) { if(cur.key == key) { return cur.val; } cur = cur.next; } return -1; } } 性能分析虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 哈希表与 Java 集合的关系1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set2. java 中使用的是哈希桶方式解决冲突的3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。

浏览量2026

英勇黄铜

链表与LinkedList

链表链表的概念与结构链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。大家可以把它理解为现实中的绿皮火车这里要注意：链式在逻辑上是连续的，但是在物理上不一定是连续的现实中的结点一般都是从堆上申请出来的从堆上申请的空间，是按照一定的策略来分配的，所以两次申请的空间可能连续，也可能不连续链表中的结构是多样的，根据情况来使用，一般使用一下结构：单向或双向带头和不带头循环和非循环这些结构中，我们需要重点掌握两种：无头单向非循环链表：结构简单，一般不会单独来存数据，实际上更多的是作为其他数据结构的子结构，如哈希桶，图的邻接表等。无头双向链表：在我们java的集合框架中LinkedList低层实现的就是无头双向循环链表。单向链表的模拟实现下面是单向链表需要实现的一些基本功能：// 1、无头单向非循环链表实现 public class SingleLinkedList { //头插法 public void addFirst(int data){ } //尾插法 public void addLast(int data){ } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ } //删除所有值为key的节点 public void removeAllKey(int key){ } //得到单链表的长度 public int size(){ return -1; } public void clear() { } public void display() {} }具体实现代码MyLinkedListpackage myLinkedList; import sun.awt.image.ImageWatched; import java.util.List; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-14 * Time: 10:38 */ public class MyLinkedList implements IList{ static class LinkNode { public int value; public LinkNode next; public LinkNode(int data) { this.value = data; } } LinkNode head; public void createNode() { LinkNode linkNode1 = new LinkNode(12); LinkNode linkNode2 = new LinkNode(23); LinkNode linkNode3 = new LinkNode(34); LinkNode linkNode4 = new LinkNode(56); LinkNode linkNode5 = new LinkNode(78); linkNode1.next = linkNode2; linkNode2.next = linkNode3; linkNode3.next = linkNode4; linkNode4.next = linkNode5; this.head = linkNode1; } @Override public void addFirst(int data) { //实例化一个节点 LinkNode firstNode = new LinkNode(data); if(this.head == null) { this.head = firstNode; return; } //将原第一个对象的地址给新节点的next，也就是将head给新next firstNode.next = this.head; //将新的对象的地址给head头 this.head = firstNode; } @Override public void addLast(int data) { //实例化一个节点 LinkNode lastNode = new LinkNode(data); //找到最后一个节点 LinkNode cur = this.head; while(cur.next!= null) { cur = cur.next; } cur.next = lastNode; //将最后一个节点的next记录插入节点的地址 } @Override public void addIndex(int index, int data) throws indexillgality { if(index < 0 || index > size()) { throw new indexillgality("index不合法"); } LinkNode linkNode = new LinkNode(data); if(this.head == null) { addFirst(data); return; } if(size() == index ) { addLast(data); return; } LinkNode cur = this.head; int count = 0; while(count != index - 1) { cur = cur.next; count++; } linkNode.next = cur.next; cur.next = linkNode; } @Override public boolean contains(int key) { LinkNode cur = this.head; while(cur != null) { if(cur.value == key) { return true; } cur = cur.next; } return false; } @Override public void remove(int key) { if(this.head.value == key) { this.head = this.head.next; return ; } //找前驱 LinkNode cur = findprev(key); //判断返回值 if(cur != null) { //删除 LinkNode del = cur.next; cur.next = del.next; //cur.next = cur.next.next; } } //找删除的前驱 private LinkNode findprev(int key) { LinkNode cur = head; while(cur.next != null) { if(cur.next.value == key) { return cur; } cur = cur.next; } return null; } @Override public void removeAllKey(int key) { if(size() == 0) { return ; } if(head.value == key) { head = head.next; } LinkNode cur = head.next; LinkNode prev = head; while(cur != null) { if(cur.value == key) { prev.next = cur.next; } prev = cur; cur = cur.next; } } @Override public int size() { LinkNode cur = head; int count = 0; while(cur != null) { count++; cur = cur.next; } return count; } @Override public void display() { LinkNode x = head; while(x != null) { System.out.print(x.value + " "); x = x.next; } System.out.println(); } @Override public void clear() { LinkNode cur = head; while(cur != null) { LinkNode curNext = cur.next; cur.next = null; cur = curNext; } head = null; } } indexillgality这时一个自定义异常package myLinkedList; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-14 * Time: 12:55 */ public class indexillgality extends RuntimeException { public indexillgality(String message) { super(message); } }LinkedListLinkedList 的模拟实现这相当于无头双向链表的实现，下面是它需要的基本功能：// 2、无头双向链表实现 public class MyLinkedList { //头插法 public void addFirst(int data){ } //尾插法 public void addLast(int data){} //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){} //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){} //删除第一次出现关键字为key的节点 public void remove(int key){} //删除所有值为key的节点 public void removeAllKey(int key){} //得到单链表的长度 public int size(){} public void display(){} public void clear(){} }MyLinkedListpackage myLinkedList; import java.util.List; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-20 * Time: 18:49 */ public class MyLinkedList implements IList { //单个节点 public static class ListNode { private int val; private ListNode prev; private ListNode next; public ListNode(int val) { this.val = val; } } ListNode head; ListNode last; @Override public void addFirst(int data) { ListNode cur = new ListNode(data); if(head == null) { cur.next = head; head = cur; last = cur; }else { cur.next = head; head.prev = cur; head = cur; } } @Override public void addLast(int data) { ListNode cur = new ListNode(data); if(head == null) { head = cur; last = cur; } else { last.next = cur; cur.prev = last; last = cur; } } @Override public void addIndex(int index, int data) throws Indexexception { ListNode cur = new ListNode(data); if(index < 0 || index > size()) { throw new Indexexception("下标越界"); } //数组为空时 if(head == null) { head = cur; last = cur; return ; } //数组只有一个节点的时候 if(head.next == null || index == 0) { head.prev = cur; cur.next = head; head = cur; return; } if(index == size()) { last.next = cur; cur.prev = last; return ; } //找到对应下标的节点 ListNode x = head; while(index != 0) { x = x.next; index--; } //头插法 cur.next = x; cur.prev = x.prev; x.prev.next = cur; x.prev = cur; } @Override public boolean contains(int key) { ListNode cur = head; while(cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; } @Override public void remove(int key) { if(head == null) { return; } ListNode cur = head; while(cur != null) { if(cur.val == key) { if(cur.next == null && cur.prev == null) { head = null; last = null; return; }else if(cur.next == null){ cur.prev.next = null; last = cur.prev; return; }else if(cur.prev == null) { head = cur.next; cur.next.prev = null; return ; }else { ListNode frone = cur.prev; ListNode curnext = cur.next; frone.next = curnext; curnext.prev = frone; return ; } } cur = cur.next; } } @Override public void removeAllKey(int key) { if(head == null) { return; } ListNode cur = head; while(cur != null) { if(cur.val == key) { if(cur.next == null && cur.prev == null) { head = null; last = null; } else if(cur.next == null){ cur.prev.next = null; last = cur.prev; }else if(cur.prev == null) { head = cur.next; cur.next.prev = null; }else { ListNode frone = cur.prev; ListNode curnext = cur.next; frone.next = curnext; curnext.prev = frone; } } cur = cur.next; } } @Override public int size() { int count = 0; ListNode cur = head; while(cur != null) { count++; cur = cur.next; } return count; } @Override public void display() { ListNode cur = head; while(cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } @Override public void clear() { if(head == null) { return; } ListNode cur = head.next; while(cur != null) { head = null; head = cur; cur = cur.next; } head = null; } }Indexexception这也是一个自定义异常package myLinkedList; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-21 * Time: 9:47 */ public class Indexexception extends RuntimeException{ public Indexexception(String message) { super(message); } }java 中的 LinkedListLinkedList 的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来。因为这样，在任意位置插入和删除元素时，是不需要搬移元素，效率比较高。在集合框架中， LinkedList 也实现了 List 接口：注意：LinkedList 实现了 List 接口LinkedList 的底层使用的是双向链表Linked 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问LinkedList 的随机位置插入和删除元素时效率较高，复杂度为 O(1)LinkedList 比较适合任意位置插入的场景LinkedList 的使用LinkedList 的构造：一般来说有两种方法：无参构造：List<Integer> list = new LinkedList<>();使用其他集合容器中的元素构造List：public LinkedList(Collection<? extends E> c)栗子：public static void main(String[] args) { // 构造一个空的LinkedList List<Integer> list1 = new LinkedList<>(); List<String> list2 = new java.util.ArrayList<>(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE"); // 使用ArrayList构造LinkedList List<String> list3 = new LinkedList<>(list2); }LinkedList 的基本方法：public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); // add(elem): 表示尾插 list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); System.out.println(list.size()); System.out.println(list); // 在起始位置插入0 list.add(0, 0); // add(index, elem): 在index位置插入元素elem System.out.println(list); list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst() list.removeFirst(); // removeFirst(): 删除第一个元素 list.removeLast(); // removeLast(): 删除最后元素 list.remove(1); // remove(index): 删除index位置的元素 System.out.println(list); // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false if(!list.contains(1)){ list.add(0, 1); } list.add(1); System.out.println(list); System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置 System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置 int elem = list.get(0); // get(index): 获取指定位置元素 list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem System.out.println(list); // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回 List<Integer> copy = list.subList(0, 3); System.out.println(list); System.out.println(copy); list.clear(); // 将list中元素清空 System.out.println(list.size()); }LinkedList 的多种遍历foreach：public static void main(String[] args) { List<Integer> list = new LinkedList<>(); list.add(1); list.add(3); list.add(5); list.add(2); list.remove(1); for (int x:list) { System.out.print(x + " "); } } 使用迭代器遍历： ListIterator<Integer> it = list.listIterator(); while(it.hasNext()) { System.out.println(it.next() + " "); } }ArrayList 与 LinkedList的区别

浏览量2055

英勇黄铜

时间复杂度和空间复杂度

引入这里提出一个问题，我们应该如何衡量一个算法的好坏？这里就要提到算法效率了。算法效率分为两种：一种为时间效率，一种为空间效率。时间效率为称为时间复杂度，空间效率被称为空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，空间复杂度衡量的是一个算法所需要的空间。在计算机的早期，因为计算机空间小，我们队空间复杂度很重视。但是在经过一段的时间的发展后，计算机的内存变得庞大起来后，我们就不太关注空间复杂度了，而是比较关心时间复杂度。时间复杂度时间复杂度的概念时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。大 O 的渐进表示法 void func1(int N){ int count = 0; for (int i = 0; i < N ; i++) { for (int j = 0; j < N ; j++) { count++; } } for (int k = 0; k < 2 * N ; k++) { count++; } int M = 10; while ((M--) > 0) { count++; } System.out.println(count); }通过简单的计算我们可以得到 func的时间复杂度为：n^2+2*n+10 但是在实际中我们计算时间复杂度的时候，我们其实并不一定要计算精确的执行次数，而只需要大概的执行次数，这里就是我们的大 O 渐进表达法。大 O 阶表达方式1 用常数1取代运行时间中的所有加法常数。2 在修改后的运行次数函数中，加法中只保留最高阶项3 如果最高阶存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶那么，我们使用大O阶的渐进表示法后，func1的时间复杂度就是 O(n^2)算法的时间复杂度是会存在最好，平均，最坏的情况：最坏：任意输入规模的最大运行次数平均：任意输入规模的期望运行次数最好：任意输入规模的最小运行次数一般情况下，我们关注的是最坏的运行情况常见的时间复杂度计算实例 1 void func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; k++) { count++; } int M = 10; while ((M--) > 0) { count++; } System.out.println(count); }实例一我们得到基本执行次数为 2*n+10 ,通过大 O 阶表示，func2 的时间复杂度为 O(n)实例 2 void func3(int N, int M) { int count = 0; for (int k = 0; k < M; k++) { count++; } for (int k = 0; k < N ; k++) { count++; } System.out.println(count); }func 3 基本执行次数为 m+n 次，又因为 m、n 都是未知数，时间复杂度为 O(n+m)实例 3 void func4(int N) { int count = 0; for (int k = 0; k < 100; k++) { count++; } System.out.println(count); }实例 3 基本操作执行了 100 次，通过推导大 O 阶方法，常数都为 1 得 func4 的复杂度为 1实例 4 void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { Swap(array, i - 1, i); sorted = false; } } if (sorted == true) { break; } } }实例 4 我们采用最坏的基本操作执行了 1/2*(n^2) ,大 O 阶推导就是 n^2实例 5 int binarySearch(int[] array, int value) { int begin = 0; int end = array.length - 1; while (begin <= end) { int mid = begin + ((end-begin) / 2); if (array[mid] < value) begin = mid + 1; else if (array[mid] > value) end = mid - 1; else return mid; } return -1; }实例5的最坏基本操作执行次数为 log2N，时间复杂度为 log2N实例 6 long factorial(int N) { return N < 2 ? N : factorial(N - 1) * N; }实例 6 的基本执行次数为 n 次，时间复杂度为 n实例 7 long factorial(int N) { return N < 2 ? N : factorial(N - 1) * N; }实例 7 的基本操作执行次数为 (1-2^N) / -1 , 时间复杂度为 2^n空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。常见的空间复杂度计算话不多说，我们直接上代码：实例1 void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { Swap(array, i - 1, i); sorted = false; } } if (sorted == true) { break; } }实例1使用了常数个空间，所以空间复杂度为 O(1)实例 2 long[] fibonacci(int n) { long[] fibArray = new long[n + 1]; fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; i++) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; }实例二它动态开辟了 n 个空间，时间复杂度为 O(n)实例 3long factorial(int N) { return N < 2 ? N : factorial(N-1)*N; }实例 3 递归调用了 n 次，所以空间复杂度为 O(n)

浏览量2098

英勇黄铜

搜索树与 Java集合框架中的Set，Map

什么是搜索树搜索树又名二叉搜索树，它是一颗完全二叉树，且：左树不为空的话，则左子树上的所有节点的值都小于根节点的值右树不为空的话，则右子树上的所有节点的值都大于根节点的值它的左右子树也是搜索树搜索树的模拟实现查找功能实现这个功能就可以利用它的性质，比根节点的小的数在左边，比根节点大的数在右边，通过遍历的方式一直查找，要是遇到了 null ，代表就没有这个数。代码实现//查找元素 //查找复杂度：O(logN) //最坏情况：O(N) public boolean search(int node) { if(root == null) { return false; } TreeNode cur = root; while(cur != null) { if(node < cur.val) { cur = cur.left; }else if(node > cur.val) { cur = cur.right; }else { return true; } } return false; } 画图分析新增功能新增节点，我们就分两种情况，一种没有节点，一种有节点，但大致开始用 cur 遍历找到需要插入的位置，再用一个 prev 记住 cur 的前一个节点。且相同是不需要添加的。当 cur 于 null 的时候，就用 prev 来判断它大于 key ，就将新增节点放在它的左边不然就放在右边具体代码//新增元素 public boolean push(int node) { if(root == null) { root = new TreeNode(node); return true; } TreeNode cur = root; TreeNode prve = null; while(cur != null) { if(node < cur.val) { prve = cur; cur = cur.left; }else if(node > cur.val){ prve = cur; cur = cur.right; }else { return false; } } TreeNode treeNode = new TreeNode(node); if(prve.val > node) { prve.left = treeNode; }else { prve.right = treeNode; } return true; }画图分析删除功能删除就比较复杂一点，得分几种情况，而这几种情况中又得细分：当需要删除的节点左边没有元素1 需要删除的是头节点2 需要删除的在父节点的左边3 需要删除的节点在父节点的右边当需要删删出的节点右边没有元素1 需要删除的是头节点2 需要删除的在父节点的左边3 需要删除的节点在父节点的右边当需要删除的节点两边都有元素这里是比较难处理的，我们不能直接删除这个结点，这里我们使用替换法：找到删除节点右边的最小节点，将最小节点的值赋值给需要删除的那个元素，再将最小节点删除，在删除这个最小节点的时候我们也要考虑：它的左边有没有元素，它的右边有没有元素，还是左右都没有元素具体代码//删除元素 public boolean poll(int key) { TreeNode cur = root; TreeNode parent = null; while(cur != null) { if(key < cur.val) { parent = cur; cur = cur.left; }else if(key > cur.val) { parent = cur; cur = cur.right; }else { removeNode(cur, parent); return true; } } return false; } private void removeNode(TreeNode cur, TreeNode parent) { //删除节点左边为空 if(cur.left == null) { if(cur == root) { root = root.right; }else if(parent.left == cur) { parent.left = cur.right; }else { parent.right = cur.right; } //删除节点右边为空 }else if(cur.right == null) { if(root == cur) { root = root.left; }else if(parent.left == cur) { parent.left = cur.left; }else { parent.right = cur.left; } //都不为空 }else { TreeNode xparent = cur; TreeNode x = cur.right; while(x.left != null) { xparent = x; x = x.left; } cur.val = x.val; if(xparent.left == x) { xparent.left = x.right; }else { xparent.right = x.right; } } } }画图分析搜索树的性能这里我们可以把查找的效率看做整个搜索树的性能，因为不管是新增和删除都是需要查找的嘛。对于搜索树，我们知道，它就是一颗二叉树，所以比较的次数就是树的深度。但是所有情况都是这样嘛，这里会因为一个数据集合，如果他们数据插入的次序不一样，则会得到不一样的数据结构，比如下图：这里我们就知道了，在最坏情况下搜索树会退化成一个链表所以：最好情况时间复杂度：O(logN)最坏情况时间复杂度：O(N)搜索树与Java类集合的关系Java 中的 TreeMap 和 TreeSet 就是利用搜索树实现的，但是呢它们底层使用的是搜索树的进化再进化版红黑树（搜索树 - LAV 树 - 红黑树），LAV 树就是对搜索树的改进，遇到链表情况下它就是翻转这个链表，让他变成一个高度平衡的搜索树，而红黑树是在这个基础加上颜色一节红黑树性质的验证进一步的提高了它的效率。Set和Map概念Map 和 Set 是一种专门用来进行搜索的容器或者数据结构，它的搜索效率和实现它们的子类有关。一般比较简单的搜索方式有：直接遍历，复杂度为 O(N),效率比较底下二分查找，复杂度为O(logN),但它麻烦的是必须是有序的而这些搜索方式只适合静态的搜索，但对于区间这种插入和删除的操作他们就不行了，这种就属于动态搜索方式。Map 和 Set 就是用来针对这种的动态查找的集合容器模型这集合中，一般把搜索的数据称为关键字 Key 和关键字的对应值 Value，这两个称为键值对，一般有两种模型：纯 Key 模型，即只需要一个数据，比如：查找手机里面有没有这个联系人Key-Value 模型，比如：查找这个篇文章里面这个词出现了几次（词，出现的次数）Map 就是 Key-Value 模型，Set 是纯 Key 模型Map 接口下继承了 HashMap 和 TreeMap 两个类，而 Set 接口下继承了 TreeSet 和 HashSet 两个类TreeMap 和 TreeSet 底层是红黑树，而 HashMap 和 HashSet 底层是哈希表MapMap是一个接口，它没有和其他几个类一样继承Collection，它存储的是 <K,V> 键值对，且K是唯一的，V可以重复Map.Entry<K,V>Map.Entry<K,V> 在 Map 中是一个内存类，它是用来 Map 内部实现存放 <K,V> 键值对映射关系的，它还提供了 Key ，value 的设置和 Key 的比较方式：这里要注意它没有提供设置 Key 的方法Map 的常用方法注意事项：1 Map 是一个接口，它不可以实例化对象，要实例化只能实例化它的子类 TreeMap 或者 HashMap2 Map 中存放键值对里的 Key 是唯一的，value 是可以重复的3 在 TreeMap 中插入键值对时，Key 不能为空，否则就会抛 NullPointerExecption 异常，value 可以为空。但是 HashMap 的 Key 和 value 都可以为空4 Map 中的 Key 是可以分离出来的，存储到 Set 中来进行访问（因为 Key 不能重合）5 Map 中的 value 也可以分离出来，存放到 Collection 的任何一个子集合中，但是 value 可能会重合 6 Map 中的键值对 Key 不能直接修改，value 可以修改，如果要修改 Key，只能先将 Key 先删除，再来插入TreeMap 和 HashMap 的比较使用栗子：HashMap：public static void main(String[] args) { Map<String, Integer> map = new HashMap<>(); map.put("猪八戒", 500); map.put("孙悟空", 550); map.put("唐僧", 40); map.put("沙和尚", 100); map.put("白龙马", 300); System.out.println(map.get("猪八戒")); System.out.println(map.remove("八戒")); System.out.println(map.get("猪八戒")); Set<Map.Entry<String, Integer>> set = map.entrySet(); for(Map.Entry<String, Integer> entry : set) { System.out.println(entry); } System.out.println(map.containsKey("猪八戒")); }TreeMap：public static void TestMap() { Map<String, String> m = new TreeMap<>(); // put(key, value):插入key-value的键值对 // 如果key不存在，会将key-value的键值对插入到map中,返回null m.put("林冲", "豹子头"); m.put("鲁智深", "花和尚"); m.put("武松", "行者"); m.put("宋江", "及时雨"); String str = m.put("李逵", "黑旋风"); System.out.println(m.size()); System.out.println(m); // put(key,value): 注意key不能为空，但是value可以为空 // key如果为空，会抛出空指针异常 // m.put(null, "花名"); str = m.put("无名", null); System.out.println(m.size()); // put(key, value): // 如果key存在，会使用value替换原来key所对应的value，返回旧value str = m.put("李逵", "铁牛"); // get(key): 返回key所对应的value // 如果key存在，返回key所对应的value // 如果key不存在，返回null System.out.println(m.get("鲁智深")); System.out.println(m.get("史进")); //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值 System.out.println(m.getOrDefault("李逵", "铁牛")); System.out.println(m.getOrDefault("史进", "九纹龙")); System.out.println(m.size()); //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN) // 按照红黑树的性质来进行查找 // 找到返回true，否则返回false System.out.println(m.containsKey("林冲")); System.out.println(m.containsKey("史进")); // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N) // 找到返回true，否则返回false System.out.println(m.containsValue("豹子头")); System.out.println(m.containsValue("九纹龙")); // 打印所有的key // keySet是将map中的key防止在Set中返回的 for (String s : m.keySet()) { System.out.print(s + " "); } System.out.println(); // 打印所有的value // values()是将map中的value放在collect的一个集合中返回的 for (String s : m.values()) { System.out.print(s + " "); } System.out.println(); // 打印所有的键值对 // entrySet(): 将Map中的键值对放在Set中返回了 for (Map.Entry<String, String> entry : m.entrySet()) { System.out.println(entry.getKey() + "--->" + entry.getValue()); } System.out.println(); }SetSet 和 Map 的不同点就在于 Set 是继承于 Collection 接口类的，Set 只存储了 Key。Set 的常用方法注意事项：1 Set 是继承 Collection 的一个接口2 Set 只存储 Key，且要求 Key 是唯一的3 TreeSet 的底层是使用了 Map 来实现的，其使用 Key 与 Object 的一个默认对象作为键值对插入到 Map 中4 Set 的最大特点就是去重5 实现 Set 接口的常用类有 TreeSet 和 HashSet，还有一个 LinkedSet，它是在 HashSet 上维护了一个双向链表来记入插入元素的次序6 Set 中的 Key 不能修改，如果要修改的话，呀先将原来的删除，再重新插入7 TreeSeet 中不能插入 null 的 Key，但 HashSet 可以TreeSet 和 HashMap 的比较栗子：public static void TestSet2(){ Set<String> s = new TreeSet<>(); // add(key): 如果key不存在，则插入，返回ture // 如果key存在，返回false boolean isIn = s.add("apple"); s.add("orange"); s.add("peach"); s.add("banana"); System.out.println(s.size()); System.out.println(s); isIn = s.add("apple"); // add(key): key如果是空，抛出空指针异常 //s.add(null); // contains(key): 如果key存在，返回true，否则返回false System.out.println(s.contains("apple")); System.out.println(s.contains("watermelen")); // remove(key): key存在，删除成功返回true // key不存在，删除失败返回false // key为空，抛出空指针异常 s.remove("apple"); System.out.println(s); s.remove("watermelen"); System.out.println(s); Iterator<String> it = s.iterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); }

浏览量2034

英勇黄铜

栈与队列

栈栈的概念栈它是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守着先进后出的规则。压栈：栈的插入操作叫做进栈，压栈，入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据在栈顶。栈的使用代码示范：public class Test { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.empty()); System.out.println(stack.size()); } }栈的模拟实现Stack 继承了 Vector ，Vector 和 ArrayList 类似，都是动态的顺序表，但不同的是 Vector 是线性安全的。代码模拟实现：public class MyStack implements Istack{ private int[] elem; private int usedsize; private static final int DEFAULT_CAPACITY = 10; public MyStack() { this.elem = new int[DEFAULT_CAPACITY]; } @Override public void push(int x) { if(full()) { elem = Arrays.copyOf(elem, 2*elem.length); } elem[usedsize] = x; usedsize++; } @Override public boolean full() { if(usedsize == elem.length) { return true; } return false; } @Override public int pop() { if(Empty()) { throw new Emptyexception("数组为空"); } int ret = elem[usedsize-1]; usedsize--; return ret; } @Override public int peek() { if(Empty()) { throw new Emptyexception("数组为空"); } return elem[usedsize - 1]; } @Override public int size() { return usedsize; } @Override public boolean Empty() { if(usedsize == 0) { return true; } return false; } } 栈的应用将递归转化为循环// 递归方式 void printList(Node head){ if(null != head){ printList(head.next); System.out.print(head.val + " "); } } // 循环方式 void printList(Node head){ if(null == head){ return; } Stack<Node> s = new Stack<>(); // 将链表中的结点保存在栈中 Node cur = head; while(null != cur){ s.push(cur); cur = cur.next; } // 将栈中的元素出栈 while(!s.empty()){ System.out.print(s.pop().val + " "); } }栈，虚拟机栈，栈帧的区分栈：是一种数据结构虚拟机栈：是 java 虚拟机 JVM 中分配的一块内存栈帧：是在调用方法的时候，会在虚拟机中为这个方法分配一块内存队列（ Queue ）队列的概念队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO ( FirstIn First Out ) 入队列：进行插入操作的一端称为队尾（ Tail / Rear ）出队列：进行删除操作的一端称为队头队列的使用在 java 中， Queue 是一个接口，底层是通过链表来实现的这里要注意一个点：Queue 是一个接口，在实例化时必须实例化 LinkedList 的对象，因为 LinkedList 实现了 Queue 接口public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5); // 从队尾入队列 System.out.println(q.size()); System.out.println(q.peek()); // 获取队头元素 q.poll(); System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 if(q.isEmpty()){ System.out.println("队列空"); }else{ System.out.println(q.size()); } }队列模拟实现链式结构对列：public class MyLinkqueue { static class ListNode { int val; ListNode prev; ListNode next; public ListNode(int val) { this.val = val; } } ListNode head; ListNode last; int usedsize; public void offer(int val) { ListNode node = new ListNode(val); if(head == null) { head = node; last = node; usedsize++; return; } last.next = node; node.prev = last; last = node; usedsize++; } public int poll() { if(head == null) { return -1; } int ret = head.val; if(head.next == null) { head = null; last = null; } else { head.next.prev = null; head = head.next; } usedsize--; return ret; } public int peek() { if(head == null) { return -1; } return head.val; } public boolean Empty(){ return head == null; } public int size() { return usedsize; } } 循环队列实际中我们有时还会使用一种队列叫循环队列，操作系统课程讲解生产者消费者模型时可以就会使用循环队列，环形队列通常使用数组实现代码：class MyCircularQueue { int[] elem; int front; int rear; public MyCircularQueue(int k) { elem = new int[k+1]; } public boolean enQueue(int value) { if(isFull()) { return false; } elem[rear] = value; rear = (rear+1) % elem.length; return true; } public boolean deQueue() { if(isEmpty()) { return false; } front = (front+1)% elem.length; return true; } public int Front() { if(isEmpty()) { return -1; } return elem[front]; } public int Rear() { if(isEmpty()) { return -1; } int ret = (rear == 0) ? elem.length-1 : rear-1; return elem[ret]; } public boolean isEmpty() { return front == rear; } public boolean isFull() { return (rear+1) % elem.length == front; } }双端队列双端队列是指允许两端都可以进行入队和出队操作的队列， deque 是 “ double ended queue ” 的简称，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队，Deque 是一个接口，使用时必须创建 LinkedList 的对象

浏览量2047

英勇黄铜

Java对象的比较

priorityQueue 中如何插入对象我们知道，优先级队列在插入元素时有一个要求：需要可以比较的对象才能插入。这里我们需要知道怎样插入自定义类型对象：比如我们插入这个 student 对象：class student { int age; String name; public student(int age, String name) { this.age = age; this.name = name; } } public class Test { public static void main(String[] args) { PriorityQueue<student> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(new student(12,"小猪佩奇")); priorityQueue.offer(new student(12,"小猪乔治")); }在运行后发现它会报类型不兼容的异常，这是因为在堆中插入元素，为了满足堆的性质，需要进行对象的比较，但是我们的 student 类型对象时不能直接比较的，所以会报错元素的比较基本类型的比较在 Java 中，基本类型的对象是可以直接进行比较大小的class TestCompare { public static void main(String[] args) { int a = 10; int b = 20; System.out.println(a > b); System.out.println(a < b); System.out.println(a == b); char c1 = 'A'; char c2 = 'B'; System.out.println(c1 > c2); System.out.println(c1 < c2); System.out.println(c1 == c2); boolean b1 = true; boolean b2 = false; System.out.println(b1 == b2); System.out.println(b1 != b2); } }对象类型的直接比较class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } } public class TestPriorityQueue { public static void main(String[] args) { Card c1 = new Card(1, "♠"); Card c2 = new Card(2, "♠"); Card c3 = c1; //System.out.println(c1 > c2); // 编译报错 System.out.println(c1 == c2); // 编译成功 ----> 打印false，因为c1和c2指向的是不同对象 //System.out.println(c1 < c2); // 编译报错 System.out.println(c1 == c3); // 编译成功 ----> 打印true，因为c1和c3指向的是同一个对象 } }这里我们知道，直接进行对象比较的是地址，只有相同才会返回 true，不同就会报错。但是这里为毛 == 可以比较呢？这就得提到 Object 类了，因为自定义类也会继承 Object 类，这个类中提供了 equal 方法，== 的情况下就是用的 Object 的equal 方法。但是这个方式比较的就是引用对象的地址，没有比较对象的内容，这就头疼了。// Object中equal的实现，可以看到：直接比较的是两个引用变量的地址 public boolean equals(Object obj) { return (this == obj); }对象正确的比较方式重写 equals 方法class student { int age; String name; public student(int age, String name) { this.age = age; this.name = name; } @Override public boolean equals(Object obj) { if(this == obj) { return true; } if(obj == null || !(obj instanceof student)) { return false; } student o = (student) obj; return this.age == ((student) obj).age && this.name.equals(o.name); } }如果指向一个对象，返回 true如果传入的是 null 或者不是 student，返回 false按照类的成员对象比较，只要成员对象相同就返回 true注意下调其他引用类型的比较也要调用 equals这里的缺陷就是：equals 只能按照相等来比较，不能比较大小基于 Comparble 接口类的比较Comparable 接口的源码：public interface Comparable<E> { // 返回值: // < 0: 表示 this 指向的对象小于 o 指向的对象 // == 0: 表示 this 指向的对象等于 o 指向的对象 // > 0: 表示 this 指向的对象大于 o 指向的对象 int compareTo(E o); }对用户自定义类型，想要按照大小比较时，在定义类的时候，实现 Comparable 接口即可。然后在类中实现 compareTo 方法：class student implements Comparable<student>{ int age; String name; public student(int age, String name) { this.age = age; this.name = name; } @Override public int compareTo(student o) { if(o == null) { return 1; } return this.age - o.age; } }基于比较器比较用户自定义比较器类，需要实现 Comparator 接口：public interface Comparator<T> { // 返回值: // < 0: 表示 o1 指向的对象小于 o2 指向的对象 // == 0: 表示 o1 指向的对象等于 o2 指向的对象 // > 0: 表示 o1 指向的对象等于 o2 指向的对象 int compare(T o1, T o2); }这里要注意区分 Comparable 和 Comparator 接口在自定义比较器类中重写 compare 方法：import java.util.Comparator; class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } } class CardComparator implements Comparator<Card> { // 根据数值比较，不管花色 // 这里我们认为 null 是最小的 @Override public int compare(Card o1, Card o2) { if (o1 == o2) { return 0; } if (o1 == null) { return -1; } if (o2 == null) { return 1; } return o1.rank - o2.rank; } public static void main(String[] args){ Card p = new Card(1, "♠"); Card q = new Card(2, "♠"); Card o = new Card(1, "♠"); // 定义比较器对象 CardComparator cmptor = new CardComparator(); // 使用比较器对象进行比较 System.out.println(cmptor.compare(p, o)); // == 0，表示牌相等 System.out.println(cmptor.compare(p, q)); // < 0，表示 p 比较小 System.out.println(cmptor.compare(q, p)); // > 0，表示 q 比较大 } }这里使用 Comparator 需要导入 java.util 包集合框架中 priorityQueue 的比较方式集合框架中的 PriorityQueue 底层使用堆结构，因此其内部的元素必须要能够比大小 PriorityQueue 采用了：Comparble和 Comparator 两种方式。 1. Comparble 是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现 Comparble 接口，并覆写 compareTo 方法2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现 Comparator 接口并覆写 compare 方法。 JDK中的源码：// 用户如果没有提供比较器对象，使用默认的内部比较，将comparator置为null public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } // 如果用户提供了比较器，采用用户提供的比较器进行比较 public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; } private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } @SuppressWarnings("unchecked") private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; }画图分析：

浏览量2031

cloud-atlas

顺序表与ArrayList

String类对象的创建与字符串常量池的“神秘交易”

二叉树

哈希表

链表与LinkedList

时间复杂度和空间复杂度

搜索树 与 Java集合框架中的Set，Map

栈与队列

Java对象的比较

搜索树与 Java集合框架中的Set，Map