Lotus Docs Screenshot

RubitCat

每个优秀的人,都有一段沉默的时光。那段时光,是付出了很多努力,却得不到结果的日子,我们把它叫做扎根。

精选文章

Hero Image
HashMap

HashMap link哈希映射旨在解决快速查找和访问一个集合中的元素的问题。常用于数据库索引、基于磁盘的数据结构以及数据压缩算法,在密码学上常用于密码的存储。 对于哈希我们关注以下概念: 键(key):键可以是整形、字符串甚至是更复杂的复合类型,用于输入哈希函数生成哈希索引。 哈希函数(hash function):输入键并生成键对应的哈希索引,该索引用于哈希表寻址。 哈希表(hash table):哈希表通常为一个列表数组,存储与键对应的值。 负载系数(load factor):哈希表的负载系数为哈希表元素个数与哈希表大小的比值。默认值为0.75。 哈希具有如下优点: 增删和搜索的时间复杂度为$O(1)$ JDK中的HashMap实现 link我们通过几个问题回答一下实现原理: 哈希映射是怎么存储的? link哈希映射采用哈希表存储,哈希表每个槽(Solt)为一个集装箱(Bin),取哈希表容量与键的哈希值比值的余数获取哈希表索引进行存储。 哈希映射以2整数次方大小创建哈希表,根据公式$h \mod 2^n = h \& (2^n-1)$取余运算可以转化为按位与运算,$(2^n-1)$代表n位二进制数的最大值,按位与该值等同于取原值的后$n$位二进制数,和取余是等价的。位运算的速度相对更快,哈希映射源码中使用位运算i = (n - 1) & hash来计算哈希表集装箱位置,提高运算效率。 当哈希表的元素个数超过负载系数规定的阈值时进行哈希表扩容,每次扩容为原来的2倍。 源码中使用位运算newThr = oldThr << 1生成新的阈值。 哈希映射是如何解决哈希冲突的? link当集装箱元素个数小于阈值时采用链表存储数据,当元素个数大于阈值时采用红黑树存储数据。树化阈值TREEIFY_THRESHOLD默认为8。 哈希映射是如何在红黑树中插入一个键的? link哈希映射优先使用键的哈希值进行比较,若哈希值不可比较(哈希冲突)则检查键类型是否实现Comparable接口并进行比较,若仍不可比较则使用决胜局算法tieBreakOrder比较。在采用决胜局算法比较前会先调用红黑树搜索算法查找,以确认待插入键不在数据集内。

最近文章

Hero Image
git

基本概念 link Git是世界上最先进的分布式版本控制系统. git跟踪文本内容而不是文件, git的add命令将新文件或新修改的文件快照暂存到index中, 准备好下一次提交 commit对象 tree对象: 一个tree实体关联一个或多个blob实体, 一个tree实体可以关联两外一个tree实体, 从而构建目录结构 blob对象 tag对象 adduser -r -c 'git version control' -d /home/git -m git # 设置用户名和邮箱,在~/.gitconfig文件中保存以下信息 git config --global user.name "xxxxx" git config --global user.email "xxxxx@xxxxx" git config --get remote.origin.url # 查看远程仓库地址 git config -l # 查看仓库参数 git push -u origin main 单分支管理 link # 创建仓库有两种方式,一是通过git初始化一个仓库,二是通过git克隆一个远程仓库到本地 git clone xxx git init # --bare指定一个没有工作目录的仓库, 一般用于服务器仓库,用作其他仓库的数据共享 # 修改工作目录文件,并添加文件到暂存区. git add xxxx git diff --cached #查看暂存区即将被提交的修改 git status #查看git管理状态o # 提交暂存区内容到版本库, git每次提交都需要输入改动注释。:commit注释最好以一行短句子作为开头,来简要描述一下这次 # commit所作的修改(最好不要超过50个字符);然后空一行再把详细的注释写清楚。这样就可以很方便的用工具把 # commit释变成email通知,第一行作为标题,剩下的部分就作email的正文. git commit # -a选项可以未保存到暂存区的已修改文件(不包含新建文件)存入暂存区并进行一次提交 # 分支创建、切换、合并、冲突处理 git branch #查看所有分支,后面如果指定了分支名则创建分支,-d参数可以删除一个已合当前分支合并的分支,-D表示删除没合并的分支 git checkout xxx # 切换分支 git merge xxx # 分支合并,隐含一个提交操作。若没有冲突则自动合并完毕,若合并失败,暂存区会进入特殊状态,直到你把冲突解决和才能提交成功。 git diff # 若分支合并失败,使用该命令查看冲突位置,手动解决后通过commit进行一次提交 gitk # 该命令可以以图形化方式展示git信息 # 差异比较 git diff 分支1..分支2 git diff 分支 # 查看当前工作目录与指定分支间的差异 git diff --cached # 查看暂存区与上次提交的差异 git diff HEAD # 查看工作目录与上次提交的差异 # 回滚 git reset --hard HEAD # reset命令可以回退版本库状态,并重置暂存库和工作区。--hard模式直接重置暂存区将工作区会退到版本库状态。已经提交合并操作可以使用--hard ORIG_HEAD模式回退 git revert # 迭代回滚,他和reset的区别是revert是向前迭代进行回滚的,会记录信息,而reset是删除信息。 # 日志 git log # 显示git提交记录,--stat显示文件更改信息,--pretty可以格式化日志,--graph会有一个终端图形效果 # 远程仓库同步 git remote add xxx xxxx # 给远程仓库起别名,该别名可以在pull和push中使用 git pull 仓库别名或仓库地址 分支 git push 仓库别名或仓库地址 分支 git fetch 仓库别名/分支 git merge 仓库别名/分支 多分支管理 linkgit-merge linkgit-rebase link变基自动分析当前分支与上游分支的共同提交与差异提交,设置当前分支以上游分支为基础并尝试将当前分支上的差异提交应用进来。若当前分支与上游分支的不同提交有冲突时,则需要进行冲突修正之后才能继续进行变基,变基的过程中还可以操控当前分支不同提交应用到上游分支的过程(例如修改某个当前分支不同提交中的某个提交的提交日志)。

Hero Image