jhj-coding

HashMapHashMap 主要用来存放键值对，JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。 大小HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。 底层数据结构jdk1.8之前HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。所谓扰动函数指的就是 Has ...

LinkedList 是一个基于双向链表实现的集合类。 LinkedList 插入和删除元素的时间复杂度 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。 LinkedList 实现了以下接口： List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。 Deque ：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。 Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。 Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。 每个节点的定义1234567891011121314priv ...

特性ConcurrentHashMap 是线程安全的hashmap jdk1.8后结构图 Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时，链表会转换成红黑树 初始化123456789101112131415161718192021222324252627282930313233/** * Initializes table, using the size recorded in sizeCtl. */private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { //　如果 sizeCtl < 0 ,说明另外的线程执行CAS 成功，正在进行初始化。 if ((sc = sizeCtl) < 0) // 让出 CPU 使用权 Thread.yi ...

二叉树种类二叉树有两种主要的形式：满二叉树和完全二叉树。 满二叉树如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。 完全二叉树在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。 堆就是一棵完全二叉树，同时保证父子节点的顺序关系。 二叉搜索树二叉搜索树是一个有序树。 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树 平衡二叉搜索树又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 二叉树的存储方式二叉树可以链式存储，也可以顺序存储。那么链式存储方式就用指针， 顺序存储的方式就是用数组。 链式存储顺序存储如果父节点的数组下标是 i，那么它的左孩子就是 ...

大顶堆与小顶堆根结点大 大顶堆根节点小 小顶堆堆每次pop 都是根元素所有小顶堆最终保留大元素大顶堆最终保留小元素 优先级队列其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。 leetcode 34712345678910111213141516171819202122232425262728class Solution { public int[] topKFrequent(int[] nums, int k) { HashMap<Integer,Integer> map=new HashMap<Integer,Integer>(); for(int i=0;i< ...

单调队列什么是单调队列，想必大家对单调函数还有所印象，单调队列和单调函数类似，一个队列中的元素是递增或者递减的。 如何构建单调队列呢并没有单调队列，那么如何构建呢，可以通过双端队列Deque 来进行构建。 注意事项根据题意合适的选择 递增还是递减并过略掉一些不需要的元素。 leetcode2391234567891011121314151617181920212223242526272829303132class Solution { public int[] maxSlidingWindow(int[] nums, int k) { ArrayDeque<Integer> deq=new ArrayDeque<Integer>(); int []res=new int[nums.length-k+1]; int idx=0; for(int i=0;i<nums.length;i++){ //因为要去除元素 所以记录的 ...

个人理解我理解的KMP 算法就是记录前缀与后缀，每当遇到不匹配的时候由于后缀已经被匹配过，所以下次应该跳到匹配过的后缀也就是相应的前缀后面在进行匹配。 如何计算前缀参考卡哥网站 前缀计算https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E6%80%9D%E8%B7%AF 然后利用前缀表去做匹配 leetcode 281234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { public int strStr(String haystack, String needle) { int[] next=new int[needle.length()]; int j=0; next[0]=j; for(int i=1;i<needle.length();i++){ ...

链表基础知识来看看卡哥的。卡哥链表https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html本文只关注链表在java 中的定义 链表如何定义1234567891011121314151617181920212223242526public class ListNode { // 结点的值 int val; // 下一个结点 ListNode next; // 节点的构造函数(无参) public ListNode() { } // 节点的构造函数(有一个参数) public ListNode(int val) { this.val = val; } // 节点的构造函数(有两个参数) public ListNode(int val, ListNode next) { this.val ...

前沿知识稳定：如果 A 原本在 B 前面，而 A=B，排序之后 A 仍然在 B 的前面。不稳定：如果 A 原本在 B 的前面，而 A=B，排序之后 A 可能会出现在 B 的后面。内排序：所有排序操作都在内存中完成。外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。 冒泡排序重复地遍历要排序的序列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换为止。 冒泡排序步骤 比较相邻的元素。如果第一个比第二个大，就交换它们两个； 针对所有的元素重复以上的步骤，除了最后一个；（相当于每次循环把大的都放在最后了）123456789101112131415161718192021222324252627282930/** * 冒泡排序 * @param arr * @return arr */public static int[] bubbleSort(int[] arr) { for (int i = 1; i < arr.length; i++) { ...

滑动窗口所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。也可以理解为一种双指针的做法。 leetcode76123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263class Solution { public String minWindow(String s, String t) { char[] schars = s.toCharArray(); char[] tchars = t.toCharArray(); int []sint=new int[123]; int []tint=new int[123]; for (int i=0;i<tchars.length;i++){ tint[tchars[i]]++; ...