分为两个问题，一个是为什么创建HashMap时的容量都是2的幂次方，第二个是为什么扩容时是扩大两倍。 容量为2的幂次方 目的是为了更快的取模，假设容量为N，哈希值是hash，如果N是2的幂次方，则hash % N = hash & (N - 1) 2的幂次方的二进制表示，只有最高位是1，其他位都是0，2的幂次方减一的二进制表示则全部是1。 hash & (N -1)本质上是只保留hahs的末尾几位，得到的结果一定小于N, 在0到N-1之间。 扩容扩大两倍 扩大两倍可以保证原有的元素要么保持在原来的索引上，要么移动到原索引加N的位置，可以保证数据在扩张后的分布不会变得更差。 首先map的容量都是2的幂次方，那么扩大两倍，本质上就是在取模的时候多保留一位，那么原来的哈希值如果上一位是0，则扩容后取模的结果不会变，如果上一位是1，那么扩容后取模的结果就是二进制数最前面加上1 在二进制最高位+1，相当于十进制里+N，比如从16扩大到32，那么相当于本来取4位，变成取5位，取5位相当于在原来的索引上+16 举个例子: hash值是110010，此时map的大小是16，那么取后4位，0010做索引，也就是2 扩大两倍后（总大小是32），取后5位，也就是10010做索引，结果是18 扩大两倍后会不会有在扩容前没有hash冲突的两个hash值，扩容后hash冲突了 按照上文的结论，扩容后，原来hash值要么还在原来的索引上，要么在原来的索引+N的位置上（N是扩容前的大小） 两个索引（在扩容前不冲突）在扩容后只可能有3种情况： 两个索引位置都不变，那么扩容后也不会有冲突 两个索引的位置都+N，那么也不会有冲突 一个索引变化，另一个不变化 第三种情况，有没有可能出现，扩容前不冲突，扩容后冲突的情况。因为扩容后，索引要么不变，要么+N，如果想要扩容后发生冲突，那么需要两个hash值，为hash1，hash2 假设 hash1与hash2在扩容前不冲突，扩容后冲突。 则一定有: hash1在扩容后+N，hash2扩容后不移动 扩容前hash2的索引正好比hash1大N 扩容前取模运算保留低位的n位，而扩容后保留n+1位， 因为hash1在扩容后+N，说明hash1的第n+1位是1，而hash2扩容后不移动，说明hash2的第n+1位是0， 扩容前hash2的索引正好比hash1大N, 就需要hash2的索引的低n-1位和hash1的索引的低n-1位相同。并且hash2的索引的第n位是1，hash1的索引的第n位是0 那么我们会得到 n+1 n 相同的低位 hash1: 1 0 XXX hash2: 0 1 XXX 因为hash1和hash2的低n+1位不完全一致，所以扩容后取n位hash1和hash2不可能落到一个索引上，假设不成立。

操作系统的职责之一是直接操作硬件并暴露更好用的接口给应用程序。操作系统直接操作的众多硬件中，就有内存。 内存需要通过地址来访问，直接访问内存的地址是物理地址。如果每个应用程序直接使用物理地址存放并读取自己的数据，会有很多问题（最典型的是程序A可以修改程序B的数据）。 所以操作系统对应用程序屏蔽了物理地址，应用程序只能使用虚拟地址来存放并读取自己的数据。操作系统拿到应用程序想要使用的虚拟地址，转化为物理地址做实际的存储，所以操作系统承担了一个中间人的身份。 假如我们需要操作一块512GB的内存，并且我们使用64bit的虚拟地址（也就是指针的大小是64bit）。512GB是2^39字节，也就是说有2^39个地址需要表示。如何用一个64bit的指针，去表示2^39个地址，是一门学问。有一种表示的方案叫做Sv39, Sv39只使用到了39个bit, 其他的bit用于拓展等用途。 操作系统在做虚拟地址到物理地址的转化，本质上操作系统需要在内存中维护一个哈希表，这个哈希表当然越小越好，接下来所述的各种方案和优化，目的都是为了让这张哈希表更小。 一个虚拟地址，经过这个哈希表，可以拿到一个物理地址。（当然实际的编程中，不是使用常见的哈希表，会有一些编程技巧）。 首先我们使用2^27个PTE，每个PTE用一个字节表示，那么2^27个PTE一共占用128MB，这么多PTE合在一起叫做Page Table。128MB确实大，后面会做优化。现在来看这种情况如何使用。 虚拟地址中的27位地址交给PTE后，可以拿到一个PPN，PPN+虚拟地址中的offset（大小是12位）可以拼接得到物理地址。虚拟地址中的offset实际上是一个页的大小，留offset实际上是部分保留了应用程序中的代码和数据的相对位置。如果不考虑Page Table的大小, offset为0的话, 代码位置自由度是最高的，实际上是操作系统去安排所有应用程序的每一个代码和数据的物理地址位置，也可以做到没有任何内存碎片， 但是代价太大了， 本质是内存只能用一半，另一半全放Page Table了。如果offset设置和物理地址一样大, 那操作系统控制不了应用程序代码直接的相对关系，只能同时服务一个应用。 如果512GB的内存中都要使用128MB来做虚拟地址到物理地址的转化，实在是太浪费了。可以使用三级缓存，也就是一级Page Table找到二级Page Table, 二级Page Table找到三级，三级找到物理地址。 这个实现思路很多人都能看懂，但是为什么这样可以节省内存？ 首先，三级缓存的所有页表不可能同时都放到内存里，如果整个三级缓存的所有页表都出现，那需要2^9 + 2^9 * 2^44+2^9 * 2^44 * 2^44个PTE，也就是1.5845633e+29这么多的PTE。显然装不下。首先，确认的是如果要使用三级缓存寻址512GB的内存，1.5845633e+29这么多的PTE中的每个页表是都有可能出现的，但是我们也能确定，这么多页表不可能同时出现，甚至大部分时候就使用3到4张。这个结论的论据也比较简单，程序的局部性原理。运行过程中如果一些页表不需要使用了就可以下掉了。这相当于火车运行时，一直从火车后把铁路放到火车前面，这样总体的铁路长度就很短。 每个2^9的page table占0.5KB，如果一个进程占用的地址不超过2^21也就是2M（一张页表9bit, offset12bit），那只会分配1.5KB的page table，每大于2M会增加0.5KB的页,每多2^30既1GB（1+9+12），会多分1kb，这几乎很小很小了。

前言 Mysql的事务机制，各类书籍博客上都讲了很多，八股文也基本都有，但是我属于不实践都搞不懂的笨蛋，所有本文来通过实践理解mysql的四个事务级别。 mysql安装（已经安装的可以跳过） 首先安装mysql，我使用的是Mac，安装mysql很简单。 brew install mysql 接着执行 brew services start mysql启动mysql 因为只是在本地测试，直接使用mysql -u root登录就可以 本文的目的是想要实践mysql的事务，为了更加直观的操作，所以不使用额外的客户端操作mysql，但是直接使用终端比较麻烦，所以我推荐安装mycli 在Mac上的安装也很简单，brew install mycli 这时就可以使用mycli -u root连接mysql了 测试数据准备 本文的测试数据使用官方的测试数据集, 按照readme文档，设置数据就好。 开始研究 首先执行select * from employees limit 10;看一下有那些数据。 ANSI SQL标准定义了4种隔离级别。 READ UNCOMMITTED READ COMMITTED REPEATABLE READ SERIALIZABLE READ UNCOMMITTED 如其名所描述，这种数据库隔离级别的特征肯定是读到uncommitted的数据。首先我们打开不同的终端，开启两个数据库连接。在两个数据库终端中设置当前会话的事务提交类型为READ UNCOMMITTED SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED; 接着在两个数据库连接中都开启事务 start transaction; 首先，我们在两个事务中都查询一下编号为10002的员工的性别。 select * from employees where emp_no = '10002'; 打开第三个终端，查询当前事务的状态。 SELECT * FROM INFORMATION_SCHEMA.INNODB_TRX\G 当前，有两个事务，分别是281479414878104和28147941487731，他们的事务级别也都是READ UNCOMMITTE，值得注意的是trx_weight这个字段。InnoDB目前处理死锁的方式是将持有最少行级排他锁的事务回滚。为了解决死锁,InnoDB 选择一个小的权重的事务来回滚。...

给定一个矩阵, 通过for循环可以有多少种遍历方式以及各种遍历方式的方向是怎么样的? 给定矩阵比较抽象, 我们举一个更具体的例子: 给定一个字符串"babad", 有多少种不同的遍历方式?各种遍历方式的遍历方向又是什么样子的? 右斜遍历 s = "babad" n = len(s) for L in range(n): for i in range(n): j = i + L if(j >= n): continue print((i,j))

力扣 931. 下降路径最小和 是一道经典的动态规划题，但是我卡在了边界问题上。 如何优雅的处理col为0和col为n-1的情况。 dp[row][col] = min(dp[row-1][max(col-1,0)], dp[row-1][col], dp[row-1][min(col+1,n-1)]) 通过max和min来约束边界。

目前我们业务代码里有一种常见的模式，定义一个接口，接着通过多个handler类实现这个接口, 在面对不同的情况时通过调用不同的handler类来处理业务代码，通常这些handler类都会继承一个公用的父类，父类中会有一些公共的方法。 本文不讨论这种模式的合理性，单纯从技术角度分析实现的方案。因为在Java生态下，都是使用spring框架。所以之前的业务代码中都会把这些handler做成bean，而如何使用这些bean，实现方案千奇百怪。有交给spring ioc容器管理后，自行从context中根据bean name获取的。也有手动注入到一个大map中的。 其实官方文档里指出里Autowired注解是可以自动注入map和list的，这句话有点奇怪，我还是直接show code吧。 我使用的java版本是 openjdk 21.0.2 2024-01-16 OpenJDK Runtime Environment (build 21.0.2+13-58) OpenJDK 64-Bit Server VM (build 21.0.2+13-58, mixed mode, sharing) 对于使用spring的ioc容器和bean而言，只需要spring-context依赖即可。 <dependency> <groupId>org.springframework</groupId> <artifactId>spring-context</artifactId> <version>6.1.4</version> </dependency> 首先我们定义一个接口IMan和它的两个字类Teacher和Student, 为了方便我们不加入额外的逻辑和属性 public interface IMan {} public class Teacher implements IMan{} public class Student implements IMan{} 我们在实现一个ClassRoom类，该类使用@AutoWried注解注入一个元素类型为IMan的list和一个key为String, Value类型为IMan的map public class ClassRoom { @Autowired IMan[] people; @Autowired Map<String, IMan> categories; } 同时，使用xml配置自动装配和相关的bean <?xml version="1.0" encoding="UTF-8"?> <beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:context="http://www.springframework.org/schema/context" xsi:schemaLocation="http://www.springframework.org/schema/beans http://www....

题目 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。 卡点 这道题我想到了使用bfs遍历树并且去记录深度，但有两点未思考到 深度记录的方式应该是和节点绑定，即每个节点应该有自己的深度变量。我试图通过一个变量记录深度，结果难以通过队列的变化确定（应该可以通过遍历前记录队列中节点数量，然后for循环遍历完成后对全局深度+1） dfs和bfs都可以在遍历前去获取到父节点信息，而且是要在对节点进行操作之前，bfs是在入队列前，而我在思考的时候是思考的节点进入队列后如何判断它的父节点。当然这里也可以判断，如果我不使用队列，而是使用一个数据，元素不停的加入，而元素的pop是通过移动一个队首的指针完成，那么我就可以通过下标运算得到父节点的值，但这样内存消耗会大一些。 答案 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right # dfs class Solution: def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool: queue = [] queue....

全局包管理工具 brew python (system) pyenv(install by brew) echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.zshrc echo '[[ -d $PYENV_ROOT/bin ]] && export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.zshrc echo 'eval "$(pyenv init -)"' >> ~/.zshrc poetry(install by brew) poetry install poetry env remove 3.12 go (install with official installer) warp (终端)

• Installing numpy (1.25.2): Failed ChefBuildError Backend 'setuptools.build_meta:__legacy__' is not available. Traceback (most recent call last): File "/opt/homebrew/Cellar/poetry/1.7.1/libexec/lib/python3.12/site-packages/pyproject_hooks/_in_process/_in_process.py", line 77, in _build_backend obj = import_module(mod_path) ^^^^^^^^^^^^^^^^^^^^^^^ File "/opt/homebrew/Cellar/python@3.12/3.12.1_1/Frameworks/Python.framework/Versions/3.12/lib/python3.12/importlib/__init__.py", line 90, in import_module return _bootstrap._gcd_import(name[level:], package, level) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "<frozen importlib._bootstrap>", line 1387, in _gcd_import File "<frozen importlib._bootstrap>", line 1360, in _find_and_load File "<frozen importlib._bootstrap>", line 1310, in _find_and_load_unlocked File "<frozen importlib._bootstrap>", line 488, in _call_with_frames_removed File "<frozen importlib._bootstrap>", line 1387, in _gcd_import File "<frozen importlib....