InnoDB给树中的每个页面都分配一个级别，叶子页面被分配为0级，级别在树种递增。根页面级别基于树的深度。如果区别很重要的话，所有既不是叶子页面也不是根页面的页都可以称为内部页面。...该链表从infimum开始，按key的升序链接所有记录，到supermum结束。这些记录并不是在页面中安物理顺序排列的，他们在插入的时候占用的可用的空间。他们唯一的顺序来自于他们在链表中的位置。...同一级别的页 大多数索引包含多个页面，因此多个页安升序和降序链接在一起： ? 每个页上都有一个上一页和下一页的指针，在页眉中，这些指针用于索引页面，用于形成相同级别页面的双向链表。...输出列中的key是索引的键字段数组，而row是非键字段数组。 transaction_id和roll_pointer字段是每个记录中包含的MVCC的内部字段。因为这是要给集群键（主键）。...header总的下一个字段是一个相对offset，必须将其添加到当前记录的offset中，才能计算出下一个记录的实际offset。为了方便期间，这个计算offset被包括在散列next中。
initialCapacity 表示链表内部数组的大小。 每次使用 put(...) 在 Map 中添加新的键/值时，该函数都会检查是否需要增加内部数组的容量。...但是，之前在同一个桶中的 2 个具有不同哈希键的条目在转换后可能不在同一个桶中。 图片 图片显示了调整内部数组大小之前和之后的表示。...仅供参考，这是存储在 TreeNode 中的数据的详尽列表 红黑树是自平衡二叉搜索树。尽管新添加或删除节点，它们的内部机制确保它们的长度始终在 log(n) 中。...使用这些树的主要优点是在许多数据位于内部表的同一索引（桶）中的情况下，在树中的搜索将花费 O(log(n))而它会花费O(n)带有链表。...唯一的区别是散列（键的）函数在桶中分配条目。 这是 JAVA 中的一个极端示例，我创建了一个哈希函数，将所有数据放在同一个存储桶中，然后添加 200 万个元素。
数组可以是基本类型，也可以是引用类型 集合只能是引用类型 C:元素内容 数组只能存储同一种类型...通过compareTo或者compare方法中的来保证元素的唯一性。元素是以二叉树的形式存放的。...泛型 早期的Object类型可以接收任意的对象类型，但是在实际的使用中，会有类型转换的问题。...(可以get获取指定的)，而是先转成Set集合，在通过迭代获取元素 Map集合中键要保证唯一性 Hashtable：线程安全，速度慢，不允许存放null键，null值，已被HashMap替代。...执行语句； } 常见数据结构 栈 队列 数组 链表 树 哈希表 静态导入 •格式：import static 包名….类名.方法名; •可以直接导入到方法的级别 注意事项 •方法必须是静态的
在 HashMap 中，数组的初始容量为 16，加载因子默认为 0.75，也就是说，当数组中的元素数量超过 12（16*0.75）时，数组会进行扩容，新的数组长度是原数组长度的两倍。...HashMap 通过哈希函数将键（Key）映射到数组的某个位置，如果出现哈希冲突，就将新的键值对添加到链表或红黑树中。...扩容操作包括创建一个新的哈希桶，然后将原来哈希桶中的元素重新映射到新的哈希桶中。 在多线程环境下，如果多个线程同时触发了扩容操作，并且同时对同一个桶进行操作，可能会导致数据结构混乱和形成环形链表。...具体来说，当两个线程同时对同一个桶进行扩容操作时，它们可能会获取到相同的节点引用，并试图将这些节点插入到新的哈希桶中。...这样，不同段的更新操作可以并发进行，提高了并发性能。 哈希函数：ConcurrentHashMap 使用了一个特殊的哈希函数，可以将相同的键哈希到同一个段中。
HashMap底层是数组+链表，它根据键的HashCode值存储数据,根据键可以直接获取它的值，访问速度很快。所以在Map中插入、删除和定位元素比较适合用hashMap。...理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。...，先生成新的数组，然后转移元素到新数组中 扩容的判断也是每个Segment内部单独判断的，判断是否超过阈值 JDK1.7的 ConcurrentHashMap 底层采⽤ ReentrantLock和分段的数组...扩容的过程中，ConcurrentHashMap 会将原来的小哈希表逐一复制到新的大哈希表中，这个过程中仍然可以保证线程安全。...在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。
具体的转换过程通常涉及到取模运算（%）和一些位运算，以确保索引值在合理的范围内。检查索引位置是否已经有元素： 如果数组中的对应索引位置为空，表示该位置还没有键值对，直接将新的键值对插入到这个位置。...链地址法： 在碰撞的位置上维护一个链表（或其他数据结构），将新的键值对添加到链表中。这就是为什么HashMap允许多个键具有相同的哈希值。...在这种方法中，HashMap的每个桶（bucket）不再是一个单一的位置，而是一个链表。当发生哈希冲突时，新的键值对会被添加到相应桶的链表上。这样，每个桶可以容纳多个键值对，它们共享同一个哈希值。...这个过程涉及到重新计算每个元素的哈希值，以确定它在新数组中的位置。重新计算哈希值： 哈希值的重新计算是为了确保元素在新数组中的均匀分布。...查找链表或红黑树： 由于不同键的哈希值可能相同，可能存在哈希冲突。在这种情况下，具有相同哈希值的键值对会存储在同一个数组索引位置的一个链表或红黑树中。
索引相关问题 优化你的索引 平衡多路查找树 B-Tree 根节点至少包括两个孩子 树中每个节点最多含有m个孩子（m>=2） 除根节点和叶节点外，其他节点至少有ceil(m/2)个孩子 向上取整 所有的终端叶子节点都位于同一层...密集索引文件中的每个搜索码值都对应一个索引值------- 即叶子节点不仅保存了键值，还保存了位于同一条记录的其他列信息，由于密集索引决定了表的物理排列顺序，一个表只能创建一个密集索引 稀疏索引文件只为索引码的某些键建立索引项...**考察事物的隔离级别 InnoDB可重复读隔离级别下，如何避免幻读？...，在可重复读级别下可能读取到之前版本的数据，取决于快照的时间 RC，RR级别下的InnoDB的非阻塞读（快照度）如何实现？...futureTask是间接继承Runable接口的，所以可以将FutureTask对象传入到Thread构造函数中 线程的状态 在Thread源码中，有一个State的枚举类型，该枚举类型中有6个值
数组的缺点是每个元素之间不能有间隔，当数组大小不满足需要扩容时，就要将旧的数组复制到新的数组中。当从 ArrayList 的中间位置插入或者删除元素时，对数组进行复制、移动需要的代价比较高。...当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的 1.5 倍，如果设置的新容量还不够，则直接将新容量设置为传入的参数，而后用 Arrays.copyof() 方法将元素拷贝到新的数组。...在 JDK 1.8 以前，HashMap 还采用的是 数组 + 链表 的形式存储，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的链表部分就麻烦了，需要顺着链表一个个比较下去才能找到我们需要的...JDK1.8 中的 ConcurrentHashMap 选择了与 HashMap 相同的底层实现 数组 + 链表 + 红黑树；在锁的实现上，抛弃了原有的 Segment 分段锁，采用 CAS + synchronized...将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点，就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。 ?
ArrayList什么时候缩容 当调用remove方法的时候可能就会缩容，当移除元素后，检查当前元素数量是否低于内部数组容量的一定比例（默认是50%）如果是，就会缩容，把元素复制到新数组中，然后把旧的丢弃节省空间...通过复制机制实现，对于写操作，他会复制出另一个数组让多线程进行操作，写操作执行完之后，再让引用指向新数组，对于读操作就是对原数组进行。...33 redis的淘汰策略 Redis 中的淘汰策略用于在内存不足时删除键以释放空间，volatile-lru：在设置了过期时间的键中，从最近最少使用的键中删除，volatile-ttl：在设置了过期时间的键中...，根据键的过期时间来删除，volatile-random：在设置了过期时间的键中，随机删除一个键。...37 B+树和B树的区别 在B+树中，非叶子节点只存储索引键，而不存储数据，所有数据都存储在叶子节点中。在B树中，每个节点既存储数据，又存储子节点的指针。
这意味着，当Shiftr执行输入数据和Spec的并行树遍历时，它会跟踪在Spec树的每个级别上处理了多少匹配项。如果您想将一个JSON映射转换成一个JSON数组，而不关心数组的顺序，这是非常有用的。...explicitly tell Shiftr to operate on the input JSON value of the parent key "foo" } } 因此，@通配符是将树中此级别的数据值复制到输出...树的每一层，Defaultr从最具体到最不具体的Spec键: 优先匹配对比具体值 "|"，根据有多少个或值进行子排序，然后按字母顺序排序(用于确定性行为) "*" 在Defaultr Spec树的给定级别上...，只有文字键强制Defaultr在输入数据中创建新条目:要么作为单个文字值，要么添加新的嵌套数组或映射对象。...通配符操作符是在文字键之后应用的，如果这些键在输入文档中还没有出现，则不会导致添加这些键(自然地或者已经从文字规范键中默认添加)。
在HashMap中，哈希函数的作用是将键映射到一个索引位置，以便快速查找和存储键值对。 哈希冲突 当两个或多个键的哈希值相同时，它们将映射到同一个索引位置，这种现象称为哈希冲突。...数组是HashMap的主体，用于存储键值对；链表用于解决哈希冲突；红黑树是在链表长度超过一定阈值（默认为8）时，将链表转换为红黑树，以提高查找效率。...每个Node对象包含四个属性：key（键）、value（值）、hash（哈希值）和next（指向下一个Node的指针）。当发生哈希冲突时，新的键值对将被添加到链表中。...如何扩容 扩容操作包括两个步骤：创建新的数组和重新计算键的哈希值。首先，HashMap会创建一个新的数组，其大小是原数组大小的两倍。...然后，HashMap会遍历原数组中的每个元素，重新计算键的哈希值，并将键值对存储到新的数组中。在重新计算哈希值时，HashMap会使用一个特殊的算法来确保相同的键在新的数组中仍然具有相同的哈希值。
期间崩溃过无数次，很多次面试都被虐到怀疑人生，也有三面被刷掉无奈，一次次整装重新出发，一次次从头再来。今天有时间整理最近面试过程中涉及到的问题和经验，希望可以帮助到正在面试中或即将面试的同行们。...Spring中@Bean注解如何解析？ Spring阅读源码入口？ Spring整合Mybatis是，实现原理？ Spring中的定时任务原理？ @Autowried注入的是同一个对象么？...allkeys-random：加入键的时候如果过限，从所有key随机删除 volatile-random：加入键的时候如果过限，从过期键的集合中随机驱逐 volatile-ttl：从配置了过期时间的键中驱逐马上就要过期的键...唯一性差; 频繁更新的字段不用（更新索引消耗）; where中不用的字段; 索引使用时，效果一般; 存储引擎InnoDB和MyISAM的区别 InnoDB支持事务，支持表级别锁和行级别锁，数据和索引绑定在一起...为什么MySQL选择B+树做索引 1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多
但在不需要的情况下放 Key 只会浪费内存空间。因此，需要了解它的应用场景。 大部分情况下不需要使用 Key。在添加、删除或重排同一类型的 widget 集合时，Key 非常有用。...这些 widget 保持某些状态，并且在 widget 树中处于相同的级别。如果没有 Key，更新这样的 widget 集合可能不会产生预期的结果。...将自身元素对象标记为脏元素并放到脏元素数组中，期间会触发 Vsync 信号，等待系统更新脏元素数组中的元素。...在将 key 添加到色块 widget 中后，元素树和 widget 树会使用键值进行更新。...键类型 Key 一般分两种类型： 本地类型 全局类型 本地键 在拥有相同父元素的元素中必须是独特的。本地键可以进一步分类如下： 比如同一个父节点下的孩子节点之间是独特存在的。
HashMap 的基本结构 基本结构： HashMap 是基于数组 + 链表 + 红黑树实现的。...通过哈希函数将键值对映射到数组的某个索引位置，数组存储的是链表（JDK1.8 之前）或红黑树（JDK1.8 之后）。 当链表长度超过阈值（默认 8）时，会转化为红黑树，优化查询效率。...存储原理： 调用 hashCode 方法计算键的哈希值，再通过 (n - 1) & hash 计算出数组索引。 解决哈希冲突的方法是拉链法。 5. HashMap 是否可以存放空值？...可以放空值： 键 null 只会被映射到数组的第一个位置（索引 0）。 值 null 无限制，可以存储任意多个。...Spring 如何解决循环依赖： 通过 三级缓存（单例池、提前暴露的对象和正在创建中的 Bean）实现。 在实例化和初始化过程中暴露一个早期代理对象。
当从存储引擎新写入一个新文件时，它有一堆键值对。为了便于查找键，这些键与前面编写的文件合并。每个 LSM 树都具有某种形式的扇出，其中较低级别的树保存在更多的文件中。...因此，在越来越受欢迎的 LSM 结构中，有各种各样的实现选择: 平衡合并 当一个新文件被添加到一个级别时，在循环遍历中选择下一个文件，并将其与下一个级别的文件合并。...假设从10个文件中选择一个扇出，会发现文件中的键范围通常涵盖了下面级别中大约10个文件中的键范围。把11个文件合并在一起，一个下降到下个级别，进而得到11个文件。...平衡合并有着很大的写入放大， 每次将一个新的键值对写入到级别0，在每个级别上都要重写10到11次，但是读取数据的成本较少。...通过将相关数据分组为一个键值对，很容易获取这个值 ，然后发出请求到远程系统。 如果规范化这个大型分片系统中的数据，规范化的值将可能不会在同一个分片上，执行分布式联接比执行集中式联接更加烦人。
键索引计数法（计数排序） 计数排序如果n个输入元素中的每个都是在0到k区间的一个整数，当中k为某个整数。 思想：对每个输入元素x，确定小于x的元素个数。...1.频率统计： 第一步就是使用int数组cout[]计算每一个键出现的频率。 对于数组中的每一个元素。都使用它的键訪问count[]中的对应元素并将其加1。...我们会使用count[]来计算每一个键在排序结果中的起始索引位置。 在这个演示样例中。由于第一组中有3个人，第二组中有5个人，因此第三组中的同学在排序结果数组中的起始位置为8。...（这样的实现方式的稳定性是非常关键的——键同样的元素在排序后会被聚集到一起，但相对顺序没有变化。）...由于输入数据时均匀、独立地分布在[0,M）区间上，所以一般不会出现非常多数落在同一个桶中的情况。 为了得到输出结果。我们先对每一个桶中的数进行排序，然后遍历每一个桶。
下面排序算法是用运算而不是比較来确定排序顺序的。因此下界nlgn对它们是不适用的。 键索引计数法（计数排序） 计数排序如果n个输入元素中的每个都是在0到k区间的一个整数，当中k为某个整数。...我们会使用count[]来计算每一个键在排序结果中的起始索引位置。 在这个演示样例中。由于第一组中有3个人，第二组中有5个人，因此第三组中的同学在排序结果数组中的起始位置为8。...（这样的实现方式的稳定性是非常关键的——键同样的元素在排序后会被聚集到一起，但相对顺序没有变化。）...键索引计数法不须要比較，仅仅要当范围R在N的一个常数因子范围之内，它都是一个线性时间级别的排序方法。 基数排序 有时候，我们须要对长度都同样的字符串进行排序。...由于输入数据时均匀、独立地分布在[0,M）区间上，所以一般不会出现非常多数落在同一个桶中的情况。 为了得到输出结果。我们先对每一个桶中的数进行排序，然后遍历每一个桶。
按照key关键字的哈希值和buckets数组的长度取模查找桶的位置，如果key的哈希值相同，Hash冲突（也就是指向了同一个桶）则每次新添加的作为头节点，而最先添加的在表尾。 ?...数组的索引位置就是一个个桶的索引地址。 ? 从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。...JDK1.8中使用一个Node数组来存储数据，但这个Node可能是链表结构，也可能是红黑树结构如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。...3、存放每一个Entry对象时都会按照key键的大小按照二叉树的规范进行存放，所以TreeMap中的数据是按照key从小到大排序的。...TreeMap总结： 程序添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。
按照key关键字的哈希值和buckets数组的长度取模查找桶的位置，如果key的哈希值相同，Hash冲突（也就是指向了同一个桶）则每次新添加的作为头节点，而最先添加的在表尾。 ?...数组的索引位置就是一个个桶的索引地址。 ? 从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。...JDK1.8中使用一个Node数组来存储数据，但这个Node可能是链表结构，也可能是红黑树结构如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。...TreeMap总结： 程序添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。...如果新节点比该节点大，则添加其为右子节点。如果新节点比该节点小，则添加其为左子节点；
但由于在事务的执行中可以读取到其他事务提交的结果，所以在不同时间的相同 SQL 查询中，可能会得到不同的结果，这种现象叫做不可重复读； REPEATABLE_READ：可重复读，它能确保同一事务多次查询的结果一致...事务传播行为类型 说明 PROPAGATION_REQUIRED 如果当前没有事务，就新建一个事务，如果已经存在一个事务中，加入到这个事务中。这是最常见的选择。...JDK 1.8 HashMap 采用数组 + 链表 + 红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，解决了 Entry 链死循环和数据丢失问题。...Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。...即当对象进行写操作时，使用了Lock锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行的读操作，则直接返回结果，操作过程中不需要进行同步。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
云直播
对象存储
腾讯会议
