todo list
mysql事务,外键复习
mysql锁
mysql隔离及其实现原理
mysqlMVCC原理
begonia源码app层``
begonia源码logic层``
begonia源码dispatch层``
io标准包理解与学习**(搁置)**
字典树学习
压缩字典树学习
gin源码tree部分**(搁置)**
gin源码serveHttp部分
keycenter阅读源码
begonia代码生成模式使用
分布式锁理解
begonia设计文档阅读
阻塞锁,非阻塞锁,自旋锁,互斥锁等概念的理解
gorilla/websocket包文档阅读**(搁置)**
反射学习
golang调度GMP模型理解
golangGC垃圾回收机制学习
golang接口底层学习
golang反射原理学习
golang unsafe包学习
字节跳动算法题
字节跳动面试八股文
重邮帮源码理解
leetcode刷题记录
剑指offer 03
题面
https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
思考
淼题
有两种思路,一种是时间换空间,对数组进行排序,扫一遍出结果;另一种类似桶排序,是用空间换时间。
不过在解题时,出现了一些问题,由于之前写算法题一直使用c++,而且写golang时习惯用IDE
自动提示,导致go语法记不熟,出现了下面这段鬼畜的代码:
1234567891011func findRepeatNumber(nums []int) int { len := nums.len var a [len]int for k, v := range nums { if a[v] != 0 { fmt.Println(v) break } ++a[v] }}
这段代码有几个问题:
求一个切片的长度应该用len(Slice)
不能用变量给数组设置大小(至于为什么可以联想一下之前学的CSAPP)
k没 ...
go语言反射底层原理学习
interface
反射是基于interface底层的。先复习一下空interface的底层:
1234type eface struct { _type *_type data unsafe.Pointer}
第一个字段是接口存放实体的类型详细信息,第二个字段放的是实体的地址
反射基本函数源码
反射包里面定义个一个接口和一个结构体,即 reflect.Type 和 reflect.Value,它们提供很多函数来获取存储在接口里的类型信息。
reflect.Type主要提供了关于类型相关的信息,所以它和_type关联比较紧密,后者则结合_type和data两者,因此程序员可以获取甚至改变类型的值
可以使用两个基础的关于反射的函数来获取上述的接口和结构体:
12func TypeOf(i interface{}) Type func ValueOf(i interface{}) Value
关于源码:
12345678910111213141516func TypeOf(i interface{} ...
interface底层原理学习
iface和eface
Go中描述接口的底层结构体为iface和eface,iface描述的接口包含方法,而eface不包含方法,为空接口:interface{}
iface
123456789101112131415type iface struct { tab *itab data unsafe.Pointer}type itab struct { inter *interfacetype _type *_type link *itab hash uint32 // copy of _type.hash. Used for type switches. bad bool // type does not implement interface inhash bool // has this itab been added to hash? unused [2]byte fun [1]uintptr // variable sized}
看一下iface结构体的源码,可以发现由两个属性构成, ...
golang垃圾回收机制
关于GC
即垃圾回收机制,对于高级编程语言来说比较重要,尤其是业务性比较强的语言,比如python,java,可以让程序员更加关注业务而非内存管理本身,降低开发成本。
Go V1.3的标记清除法
流程
如图,首先是程序与对象之间的可达关系,可以看出目前的可达对象有1-2-3,4-7等五个对象,当触发GC机制的时候,会先进行STW操作进行暂停,之后对1-23,4-7等五个对象打上标记。而没有标记的对象没有被程序需要,就是垃圾会被回收。接下来STW结束,继续跑。
缺点
需要进行STW操作,让程序暂停,程序会出现卡顿(重要问题)
标记需要扫描整个heap
清楚数据会产生heap碎片
改进
早期的go语言尝试了减小STW的暂停范围来减少STW所需要的时间。
通常在STW之后,要经过启动STW->标记->清除->停止STW的流程,而清除事实上可以放到停止STW之后再进行,另开一个线程进行清除操作。
但是这样还是无法满足需要,所以采用了新的方法来代替标记清除法。
Go V1.5三色标记法
流程
第一步,首先只要是新创建的对象,默认的颜色就是被标记为白色。
第二步,每次的G ...
golang调度学习笔记
协程调度器的由来
单进程时代
早期的操作系统为单进程,按照时间轴顺序执行进程,同一时刻只可以执行一个进程。
但是单进程也会遇到一些问题,比如效率低,只能一个任务一个任务的处理;可能会遇到阻塞问题。
多线程/多进程操作系统
并发
此时就需要引入CPU调度器。
比如存在多个进程,调度器可以按照时间分为一个个的时间片,划分给不同进程,对于一个进程,如果超过了时间片,就会强制停止,切换下一个进程,然后等待它的下一个时间片。这么做虽然看起来断断续续进行,但是在宏观上是连续的。
这么做可以达到并发的效果,同时也解决了阻塞的问题,当一个进程阻塞时,就切换下一个进程。
但是这么做也存在问题,既然要切换进程,就要保存当前进程的状态,同时切换也会存在时间成本,这个问题就会使进程/线程的数量越多,切换的成本就会越大,也就越浪费。此外,多线程也会使开发变得更加复杂,就要涉及到竞争,锁之类的领域。
并发还会造成高消耗调度CPU,高内存占用等问题。
用户/内核空间
对于一个线程,操作系统把它分为了用户空间和内核空间,内核空间用来处理系统相关,比如IO操作,内存相关,而用户空间用来处理用户的代码。操作系统只可以看到 ...
使用Tarjan离线算法处理LCA问题
最近在刷面试算法题是看到了这样一题:最近公共祖先祖先
也就是大家喜闻乐见的LCA问题,这个问题有许多种处理方法,比如Tarjan离线算法,倍增 ,线段树处理什么的…
由于这题数据比较水,对于每一棵树只有一组测试点,所以我就简单的遍历处理了,最终也是过了。
But,我回想起了LCA问题的另一种解法:Tarjan离线处理。
说到这个算法我就不由想到了高二那个炎热的暑假,当班里的同学都满头大汗的教室里面补课时,我却跑到了宿城二中的空调房里面划水摸鱼蹭算法课。
大多数人的第一个图论算法都是最短路径问题,而我不是,在宿城二中的小姐姐旁边(啊她还夸过我长得帅QwQ),我学会了我的一个图论算法:LCA问题的Tarjan离线解法。
在应聘时的算法题中,绝对不会变态到考查这种方法,但是可以拿来在面试官面前装b,毕竟时间复杂度和能解决的范围又更深了一步。
下面就来介绍一下这个算法:
mysql底层探究
数据类型
时间类型
需要注意的是这里的TIMESTAMP和DATETAME两种类型。
DATETAME
占8个字节
无时区检索
两个该类型不可以相减,否则会把时间拼接成十进制直接相减,由于时间不是十进制,所以结果毫无意义
当赋值为NULL,保存的内容就是NULL
当插入无效值时,会保存 0000-00-00 00:00:00
存储范围比TIMESTAMP更大一些
TIMESTAMP
占4个字节
存储的实际上是时间戳,所以可以直接相减获得秒数
有时区差别,按照utc时间存储,如果储存时的时区和检索时的时区不一样,拿出来的数据也不一样
当存储为NULL时,会保存为当前时间
当插入无效值时,会保存 0000-00-00 00:00:00
可以设置自动更新功能,详情见mysql的timestamp类型自动更新问题
Mysql索引
总的来说,Mysql索引是基于B+-Tree
B+Tree和B-Tree
见https://www.bilibili.com/video/BV1DE411i77d?t=1623
和https://www.bilibili.com/video/BV1n7411 ...
golang使用RSA签名与验签
RSA是一种非对称加密算法,它产生了公钥和密钥,公钥加密,私钥解密,或者私钥签名,公钥验签。
下面以Token签发的RSA相关操作探究一下应用。
创建Token
1234567891011121314// CreateToken 根据info创建一个tokenfunc CreateToken(info map[string]string, duration time.Duration, sub string) (token Token) { t := &Token{} t.Info = info t.Sub = sub t.setExp(duration) payload := t.Payload() sign := keycenter.Key().Signature(payload) //这里得到了序列化的payload之后,获取签名 t.sign = sign return *t}
获取payload签名
1234567// Signature 使用该key给一段数据签名// 签名方法:先对数据取sha256散列 然后rsa私钥加密 ...
golang实现快排的不同思路
一直不喜欢快速排序的那种常见实现方法,因为总有一些奇奇怪怪的边界值,什么时候用等于,什么时候该用大于等于一直弄不清楚。
这里找到一种很容易理解的实现方法,反正我个人很喜欢。
12345678910111213141516171819202122232425262728293031323334353637package mainimport "fmt"func partition(arr []int, begin, end int) int { i := begin + 1 j := end for i < j { if arr[i] > arr[begin] { arr[i], arr[j] = arr[j], arr[i] j-- } else { i++ } } if arr[begin] <= arr[j] {//这里需要加上等于,为了保证元素全部相等时仍然可以正常运行 i-- } arr[begin], arr[i] = arr[i ...