Go语言内置运行时（就是runtime），不同于传统的内存分配方式，go为自主管理，最开始是基于tcmalloc架构，后面逐步迭新。自主管理可实现更好的内存使用模式，如内存池、预分配等，从而避免了系统调用所带来的性能问题。 1. 基本策略 每次从操作系统申请一大块内存，然后将其按特定大小分成小块，构成链表(组织方式是一个单链表数组，数组的每个元素是一个单链表，链表中的每个元素具有相同的大小。)； 为对象分配内存时从大小合适的链表提取一小块，避免每次都向操作系统申请内存，减少系统调用。 回收对象内存时将该小块重新归还到原链表，以便复用；若闲置内存过多，则归还部分内存到操作系统，降低整体开销。 1.1 内存块 span：即上面所说的操作系统分配的大块内存，由多个地址连续的页组成； object：...阅读全文
面试题25. 合并两个排序的链表 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制： 0 <= 链表长度 <= 1000 注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/ 148. 排序链表 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->...阅读全文
跳表 前言 文中附代码实现. 在公众号回复 【跳表】 也可以获取哦。 什么是跳表 跳表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。 from. 维基百科 引题 线性表这种数据有两种具体实现, 数组和链表。具体的内容之前的文章里也有说过，可以翻翻看哇~。在这里两种数据结构中，数组的优点是查找速度快,而链表的优点是增删的效率高，这也是我们常说的。其实，非也。 数组是一种内存连续的数据结构,其优点是可以通过首地址+N*(sizeOf(Node)) 来快速获取指定位置上的元素.假如我们不知道指定元素的位置呢? 链表是一种非内存连续的数据，其优点是通过改变指针地址来快速增减元素。很明显的问题，你首先要知道你要...阅读全文
深入理解 Go panic and recover 作为一个 gophper，我相信你对于 panic 和 recover 肯定不陌生，但是你有没有想过。当我们执行了这两条语句之后。底层到底发生了什么事呢？前几天和同事刚好聊到相关的话题，发现其实大家对这块理解还是比较模糊的。希望这篇文章能够从更深入的角度告诉你为什么，它到底做了什么事？ 思考 一、为什么会中止运行 func main() { panic("EDDYCJY.") } 输出结果： $ go run main.go panic: EDDYCJY. goroutine 1 [running]: main.main() /Users/eddycjy/go/src/github.com/EDDYCJY/awesomeProject/ma...阅读全文
golang 提供了几个简单的容器供我们使用，本文在介绍几种Golang 容器的基础上，实现一个基于Golang 容器的LRU算法。 容器介绍 Golang 容器位于 container 包下，提供了三种包供我们使用，heap、list、ring. 下面我们分别学习。 heap heap 是一个堆的实现。一个堆正常保证了获取/弹出最大（最小）元素的时间为log n、插入元素的时间为log n.golang的堆实现接口如下： // src/container/heap.go type Interface interface { sort.Interface Push(x interface{}) // add x as element Len() Pop() inter...阅读全文
链表 Go语言的链表实现在其标准库的container/list代码包中。 这个包包含了2个程序实体： List : 实现了一个双向链表 Element : 代表了链表中元素的结构 操作链表 移动链表里的元素： func (l *List) MoveBefore(e, mark *Element) // 把元素e移动到mark元素的前面 func (l *List) MoveAfter(e, mark *Element) // 把元素e移动到mark元素的后面 func (l *List) MoveToFront(e *Element) // 把元素e移动到链表的最前端 func (l *List) MoveToBack(e *Element) // 把元素e移动到链表的最后端 上面的方法都...阅读全文
题目描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 思路 1.仿照归并排序中merge的逻辑即可。 Java代码实现 public ListNode Merge(ListNode list1,ListNode list2) { ListNode p = new ListNode(-1); ListNode res = p; while(list1 != null || list2 != null){ int cur1 = list1 == null ? Integer.MAX_VALUE : list1.val; int cur2 = list2 == null ? Integer.MAX_VALUE : list2.val; if(cur...阅读全文
双链表的实现 基本概念 每一个节点都存储上一个和下一个节点的指针 实现思路 创建一个节点结构体 每个节点都有上节点指针与下节点指针 每个节点都有一个key => value 创建一个链表结构体 链表容量大小属性 链表大小属性 链表锁, 实现并发安全 链表头节点 链表尾节点 实现链表操作方法 添加头部节点操作AppendHead 添加尾部节点操作AppendTail 追加尾部节点操作Append 插入任意节点操作Insert 删除任意节点操作Remove 删除头部节点操作RemoveHead 删除尾部节点操作RemoveTail 获取指定位置的节点Get 搜索任意节点Search 获取链表大小GetSize 打印所有节点操作Print 反转所有节点操作Reverse 总结 学好算法是一个不断积...阅读全文
在学习Go的过程中，最让人惊叹的莫过于goroutine了。但是goroutine是什么，我们用go关键字就可以创建一个goroutine，这么多的goroutine之间，是如何调度的呢？ 1. 结构概览 在看Go源码的过程中，遍地可见g、p、m，我们首先就看一下这些关键字的结构及相互之间的关系 1.1. 数据结构 这里我们仅列出来了结构体里面比较关键的一些成员 1.1.1. G(gouroutine) goroutine是运行时的最小执行单元 type g struct { // Stack parameters. // stack describes the actual stack memory: [stack.lo, stack.hi). // stackguard0 is the ...阅读全文
题目描述 输入一个链表，输出该链表中倒数第k个结点。 思路 设置一对快慢指针 2.快指针先走k步，若快指针没走完k步便为null，直接返回null即可 3.快慢指针同时移动，若快指针指向null，直接返回慢指针即可 Java代码实现 public ListNode FindKthToTail(ListNode head,int k) { ListNode fast = head; ListNode slow = head; while(k>0 && fast != null){ fast = fast.next; k--; } if(k>0){ return null; } while(fast != null){ slow = slow.next; fast = fast.next; } ...阅读全文
栈 在上一部分中，我们用Go实现了最常用的数据结构-数组，并实现了数组的添加元素、删除元素、数组遍历、数组排序和数组查找等功能。 在数组中我们可以实现任意位置的添加或删除元素，但是在某些场景中，需要我们对数据的添加或删除进行进一步的限制，于是就有了栈和队列。本章将使用Go来实现栈和栈的一些基本功能。 栈是一种运算受限的线性表，对栈中数据进行操作的时候需要遵循后进先出（LIFO）原则。在栈中对元素进行入栈或出栈操作的一端叫作栈顶，另一端则为栈底。 本章中将基于Golang切片和链表两种实现方法来实现栈。 栈定义 首先定义栈接口，其中包含以下方法： Push(e ...Element)：添加若干元素到栈顶 Pop() Element：弹出一个栈顶元素 Peek() Element：返回栈顶元素，...阅读全文
_ _ _ _ _ _ _ | (_) | | | | | (_) | | | |_ _ __ | | _____ __| | | |_ ___| |_ | | | '_ \| |/ / _ \/ _` | | | / __| __| | | | | | | < __/ (_| | | | \__ \ |_ |_|_|_| |_|_|\_\___|\__,_| |_|_|___/\__| 1.1 原理 链表与数组都非常基础也非常常用，从底层数据结构上看，数组需要一块连续的内存空间来存储数据，而链表则不需要，链表通过指针将一组零散的内存块串联起来使用。 日常中有三种常见的链表结构： 单向链表 双向链表 循环链表 1.2 分析 对于单链表来说，插入和删除操作的时间复杂度为 $O(1)$。双向链表...阅读全文
这篇文章主要讲 map 的赋值、删除、查询、扩容的具体执行过程，仍然是从底层的角度展开。结合源码，看完本文一定会彻底明白 map 底层原理。 我要说明的是，这里对 map 的基本用法涉及比较少，我相信可以通过阅读其他入门书籍了解。本文的内容比较深入，但是由于我画了各种图，我相信很容易看懂。 什么是 map 维基百科里这样定义 map： In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appe...阅读全文
package main import "fmt" type Node struct { data int next *Node } func Shownode(p *Node){ //遍历 for p != nil{ fmt.Println(*p) p=p.next //移动指针 } } func main() { var head = new(Node) head.data = 0 var tail *Node tail = head //tail用于记录最末尾的结点的地址，刚开始tail的的指针指向头结点 for i :=1 ;i<10;i++{ var node = Node{data:i} (*tail).next = &node tail = &node } Shownode(h...阅读全文
.-. .- .-,.--..-,.--. \ \ / / __ | .-. | .-. | __ \ \ / / .:--.'. | | | | | | |.:--.'. \ \ / / / | \ || | | | | | / | \ | \ \ / / `" __ | || | '-| | '-`" __ | | \ ` / .'.''| || | | | .'.''| | \ / / / | || | | | / / | |_ / / \ \._,\ '|_| |_| \ \._,\ '|`-' / `--' `" `--' `" '..' GolangOnline Go tutorial 1.1 原理 数组（Array）是一种线性表数据结构，通过在内存中申请一组连续的存储空间，用于...阅读全文
HashMap介绍 HashMap是我们编程时经常会使用到的数据结构。这个数据结构的最大好处是能够帮助我们快速定位在内存中的某一个内容。 例如在Java中，我们快速取得Key所对应的值 //假设 map 是一个HashMap
在学习《算法》这本书时，第一章有一个 Bag 的数据结构，它定义为不能删除元素的集合。之前看到一篇文章，说数据结构底层结构其实只有数组与链表，所以在实现 Bag 时想使用数组和链表分别实现。 但是在设计 Bag API 时发现，该如何提供一个通用的遍历方式给第三方调用？因为不像 Java，Golang 并未提供一个迭代接口，只是原生语法上支持对一些容器的遍历，如下所示： // 如果 container 是数组或者 Slice，那么 k => index，v => 数组元素； // 如果 container 是 Map，那么 k => key，v => value； for k, v := range container { } // 对于 channel 也是使用 range 方式，但是返回...阅读全文
哈希表：散列查找 一、线性查找 我们要通过一个键key来查找相应的值value。有一种最简单的方式，就是将键值对存放在链表里，然后遍历链表来查找是否存在key，存在则更新键对应的值，不存在则将键值对链接到链表上。 这种链表查找，最坏的时间复杂度为：O(n)，因为可能遍历到链表最后也没找到。 二、散列查找 有一种算法叫散列查找，也称哈希查找，是一种空间换时间的查找算法，依赖的数据结构称为哈希表或散列表：HashTable。 Hash: 翻译为散列，哈希，主要指压缩映射，它将一个比较大的域空间映射到一个比较小的域空间。 简单的说就是把任意长度的消息压缩到某一固定长度的消息摘要的函数。Hash 算法虽然是一种算法，但更像一种思想，没有一个固定的公式，只要符合这种思想的算法都称 Hash 算法。 散...阅读全文
# golang值拷贝导致使用container/list出现的诡异问题分析 ## 先看正确使用list的两种方式 - 使用list.New() ```go package main import ( "container/list" "fmt" ) func main() { lPtr := list.New() lPtr.PushBack(1) for front := lPtr.Front(); front != nil; front = front.Next() { fmt.Println(front.Value) } } ``` 输出 ```go 1 ``` - 使用list.New() ```go package main import ( "container/list" "f...阅读全文
两数相加（Add-Two-Numbers） 这是 LeetCode 的第二题，题目挺常规的，题干如下： 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807来源：力扣 解题思路 这个题目的解法类似我们小时候算两个多位数的加法：从低位开始相加，大于等于10时则取值的个位数，并向前进1。只不过现在多位数用链表来表示了并且最后的值用链表返回了而已。 根据上面...阅读全文
从很早开始就认识到 Handler 了，只不过那时修为尚浅，了解的不够深刻，也没有应用自如。不过随着工作时间的增长，对 Handler 又有了更深层次的认识，于是有了这篇博客，希望尽可能的总结出多的知识点。 Handler 在 Java 层源码主要有 4 个类：Looper、MessageQueue、Message、Handler。我归纳了他们的几个主要知识点： Looper：sThreadLocal、Looper.loop()；Message：数据结构、消息缓存池；MessageQueue：enqueueMessage、next、管道等待、同步消息隔离、idleHandler；Handler：send/post、dispatchMessage 消息处理优先级。LooperLooper 数据...阅读全文
文链接：go letcode，作者：三斤和他的喵 php 代码个人原创 两数相加（Add-Two-Numbers） 这是 LeetCode 的第二题，题目挺常规的，题干如下： 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807来源：力扣 解题思路 这个题目的解法类似我们小时候算两个多位数的加法：从低位开始相加，大于等于10时则取值的个位数，并向前进1...阅读全文
基本概念 基本策略: 先从操作系统申请一块大内存,以减少系统调用 将申请到的内存按照特定大小预先切成小块，构成一个链表 为对象分配内存时，只需从链表中取出一个大小合适的块使用就好 回收对象内存是，只需将对象放回原链表，以便服用 闲置过多时，会将部分内存归还系统，降低整体开销 内存块 分配器将其管理的内存块分成两种: span: 有多个地址连续的页(page)组成的大块内存 object: 将span按特定大小分成多个小块， 每个小块可存储一个对象 用途上来说，span面向的是内部管理，object面向的是对象的分配. 分配器按页数大小来区分不同大小的span。比如，以页数为单位将span存放到管理数组中，需要的时候就可以以页数为索引进行查找. 在runtime/sizeclasses.go中...阅读全文
Go语言内置运行时（就是runtime），抛弃了传统的内存分配方式，改为自主管理，最开始是基于tcmalloc，虽然后面改动相对已经很大了。使用自主管理可以实现更好的内存使用模式，比如内存池、预分配等等，从而避免了系统调用所带来的性能问题。 在了解Go的内存分配之前，我们可以看一下内存分配的基本策略，来帮助我们理解Go的内存分配 基本策略： 每次从操作系统申请一大块内存，以减少系统调用 将申请的大块内存按照特定大小预先切成小块，构成链表 为对象分配内存时，从大小合适的链表中提取一块即可 如果对象销毁，则将对象占用的内存，归还到原链表，以便复用 如果限制内存过多，则尝试归还部分给操作系统，降低整体开销 下面我们从源码角度来分析Go的内存分配策略有何异同 准备 在追踪源码之前，我们需要首先了解一...阅读全文
今天看了下内核使用的malloc和free，受益颇丰，现在回想起来以前看golang的runtime中内存的管理部分感觉清晰了很多。linux0.11部分内核的方法名也叫malloc，之后的版本为了和用户程序的区分改成了kmalloc，但分桶思想大概相同 首先明确几个变量和数据结构 free_bucket_desc 这个是当前未使用的桶描述符的链表 _bucket_dir，通描述符目录，每个大小的通描述符的目录，其中size记录了桶的大小，bucket_desc是指向桶描述符的指针。每个bucket_desc都有next指针来组成一个链表 bucket_desc，关键对象，一个描述符被第一次使用的时候，会申请一页地址，并且根据该描述符所在的大小将该页切割成不同的块，每个块初始化的时候前4个字...阅读全文
单向链表特点：1、Head 节点 上一个节点为空2、Tail 节点下一个节点为空3、除Tail节点外，每个节点连接到下一个节点package main import ( "fmt" ) type LinkNode struct { Data interface{} Next *LinkNode } type SingleLink struct { head *LinkNode tail *LinkNode size int } // 初始化链表 func InitSingleLink()(*SingleLink){ return &SingleLink{ head:nil, tail:nil, size:0, } } // 获取头部节点 func (sl *SingleLink)GetHea...阅读全文
Golang: 思路：这里可以取巧，拿到两个链表里所有的值，然后直接排序，用一个新的链表存一下并返回即可，但这种解法显然少了些营养。所以我们通过分别对两个链表进行比较，比较时，值小的那个被存进链表，然后该链表向后一格再做比较，直至某一条链表到达尾部。 func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { var head =&ListNode{Val:0} res:=head for{ if l1==nil{ res.Next=l2 break } if l2==nil { res.Next=l1 break } if l1!=nil&&l2!=nil{ if l1.Val>l2.Val{ test:=ListNode{Val:...阅读全文
Go 1.13版本中有几个比较大的修改，其中之一是sync.Pool修改了部分实现，减小某些极端情况下的性能开销。文中内容来源于笔者读完sync.Pool源代码的思考和总结，内容以Go 1.13中的实现为准，少量内容涉及到Go 1.13之前，如有误区请读者多多指教。 概念 在本文内容开始之前需要理解几个在Go runtime中的概念，以便于更好的理解sync.Pool中一些实现。 goroutine抢占 Go中调度器是GMP模型，简单理解G就是goroutine；M可以类比内核线程，是执行G的地方；P是调度G以及为G的执行准备所需资源。一般情况下，P的数量CPU的可用核心数，也可由runtime.GOMAXPROCS指定。本文的重点并非goroutine调度器，在此不做详细解释，感兴趣可以翻...阅读全文
去年开始写文章的第一篇就是关于 defer，名字比较文艺：《Golang 之轻松化解 defer 的温柔陷阱》，还被吐槽了。因为这篇文章，到《Go 夜读》讲了一期。不过当时纯粹是应用层面的，也还没有跳进 Go 源码这个大坑，文章看着比较清新，也没有大段的源码解析。 自从听了曹大在《Go 夜读》分享的 Go 汇编，以及研读了阿波张的 Go 调度器源码分析的文章后，各种源码、汇编满天飞…… 上次欧神写了一篇《Go GC 20 问》，全文也没有一行源码，整体读下来很畅快。今天这篇也来尝试一下这种写法，不过，我们先从一个小的主题开始：defer 链表是如何被遍历并执行的。 关于 defer 的源码分析文章，网络上也有很多。不过，很少有能完全说明白这个话题的，除了阿波张的。 我们知道，为了在退出函数前...阅读全文
数组与链表 数组是连续内存的应用方式，它的特点就是所有的单元的内存地址都是连续的，当需要扩展而初始化的内存不足够的时候，就需要重新申请内存。 链表是已上一个元素指向来完成存储的，它在内存的存储是分散的，无论是添加还是删除较数组的最大优势就是都不需要整体动，只需要上一个元素的指向调整就好，缺点就是无法直接通过计算获得某个元素，如果要在链表中查找某一个元素，就需要遍历整个链表（最差情况） 选择排序 遍历所有元素，挑出最小的元素放在结果集中并删除该元素，直到要排序的数据集中没有元素为止。 golang版本 package main import "fmt" func main() { info := []int{12, 3, 54, 6, 6777, 2342, 234, 55, 6, 6777,...阅读全文
★container | heap堆操作, list双向链表,ring环形链表 现在网上的算法题，很少有可以用golang作答的，不过看看别人造的轮子还是挺有意思的 container本身并不是包，但目录下包括三个子包：heap，list，ring heap 包含一个Interface接口，接口定义了Push(x interface{})，Pop() interface{} ，并包含了sort.Interface接口。 这里的堆是小顶堆 heap并没有可用的实现，但在test中找到一个： // An IntHeap is a min-heap of ints. type IntHeap []int func (h IntHeap) Len() int { return len(h) } fu...阅读全文
前些天看了DAVE CHENEY大神的直播。里面讲到了go的map实现。做个笔记 (我用的是go1.13 貌似大神直播时候用的是还没发布的1.15 所以本文中的代码都是1.13中的。与1.15略有差异) compile time rewriting: 左边对map的操作实际上被编译成了右边的调用 v := m["key"] -> runtime.mapaccess1(m, "key", &v) v, ok := m["key"] -> runtime.mapaccess2(m, "key", &v, &ok) m["key"] = 9001 -> runtime.mapinsert(m, "key", 9001) delete(m, "key") -> runtime.mapdelete(m...阅读全文
Go 1.13持续对 sync.Pool进行了改进，这里我们有两个简单的灵魂拷问： 1、做了哪些改进？2、如何做的改进？ 首先回答第一个问题： 对STW暂停时间做了优化, 避免大的sync.Pool严重影响STW时间 第二个优化是GC时入股对sync.Pool进行回收，不会一次将池化对象全部回收，这就避免了sync.Pool释放对象和重建对象导致的性能尖刺，造福于sync.Pool重度用户。 第三个就是对性能的优化。 对以上的改进主要是两次提交：: sync: use lock-free structure for Pool stealing和sync: use lock-free structure for Pool stealing。 两次提交都不同程度的对性能有所提升，依据不同的场景，...阅读全文
题目描述 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 思路 1.这道题的核心思想是跳过值重复的结点。 2.可以设置一个哑结点，防止链表中全部的值都是重复的。 3.可以设置两个值，分别用于标记当前结点是否重复。 4.整体流程就是： 进入循环 保存当前结点 循环跳过重复结点 判断当前结点是否移动过，若移动过，需要跳过 Java代码实现 class Solution { public int findMin(int[] array) { if(array.length == 0) return 0; int left = 0; int right = array.len...阅读全文
在同一个goroutine中： 多个defer的调用栈原理是什么？defer函数是如何调用的? 为了探究其中的奥秘我准备了如下代码： package main import "fmt" func main() { xx() } func xx() { defer aaa(100, "hello aaa") defer bbb("hello bbb") return } func aaa(x int, arg string) { fmt.Println(x, arg) } func bbb(arg string) { fmt.Println(arg) } 输出：bbb100 hello aaa从输出结果看很像栈的数据结构特性：后进先出(LIFO)。 首先从汇编入手去查看xx()函数的执行过程，...阅读全文
List 1. 为什么 arraylist 不安全？ 我们查看源码发现 arraylist 的 CRUD 操作，并没有涉及到锁之类的东西。底层是数组，初始大小为 10。插入时会判断数组容量是否足够，不够的话会进行扩容。所谓扩容就是新建一个新的数组，然后将老的数据里面的元素复制到新的数组里面(所以增加较慢)。 2. CopyOnWriteArrayList 有什么特点？ 它是 List 接口的一个实现类，在 java.util.concurrent（简称 JUC，后面我全部改成 juc，大家注意下）。 内部持有一个 ReentrantLock lock = new ReentrantLock(); 对于增删改操作都是先加锁再释放锁，线程安全。并且锁只有一把，而读操作不需要获得锁，支持并发。 读...阅读全文
栈的性质 只允许一段插入和删除数据 先进后出 栈可以用链表实现也可以用数组实现 操作时间复杂度 入栈和出栈时间复杂度都为Ｏ(1) (因为只涉及操作栈顶部的第一个元素） 涉及到可扩容的栈的时候，因为栈满了要扩容，数据迁移时间复杂度为Ｏ(n) 但是前ｎ次插入的时间复杂度都是Ｏ(1) 进行均摊后， 时间复杂度为O(2) = O(1) 所以不管是否扩容 时间复杂度都是O(1) 曾经（去年） 面试的时候有个面试官曾过我， 你知道栈吗？ 两个栈怎么组成一个先进先出的队列， 可是我太年轻那，bb半天也没有让人家满意。 栈的golang代码实现 type ArrayStack struct { data []interface{} top int } func NewArrayStack() *ArrayS...阅读全文
1 前言 Redis的5种数据类型（String，Hash，List，Set，Sorted Set），每种数据类型都提供了最少两种内部的编码格式，而且每个数据类型内部编码方式的选择对用户是完全透明的，Redis会根据数据量自适应地选择较优化的内部编码格式。 查看某个键的内部编码格式，使用命令object encoding keyname Reids的每个键值内部都是使用叫redisObject这个C语言结构体保存的，代码如下： type：表示键值的数据类型，也就是那5种基本数据类型。 encoding：表示键值的内部编码方式， #define OBJ_ENCODING_RAW 0 /* Raw representation */ #define OBJ_ENCODING_INT 1 /* E...阅读全文
载自图解Go语言内存分配 Go语言内置运行时（就是runtime），抛弃了传统的内存分配方式，改为自主管理。这样可以自主地实现更好的内存使用模式，比如内存池、预分配等等。这样，不会每次内存分配都需要进行系统调用。 Golang运行时的内存分配算法主要源自 Google 为 C 语言开发的TCMalloc算法，全称Thread-Caching Malloc。核心思想就是把内存分为多级管理，从而降低锁的粒度。它将可用的堆内存采用二级分配的方式进行管理：每个线程都会自行维护一个独立的内存池，进行内存分配时优先从该内存池中分配，当内存池不足时才会向全局内存池申请，以避免不同线程对全局内存池的频繁竞争。 基础概念 Go在程序启动的时候，会先向操作系统申请一块内存（注意这时还只是一段虚拟的地址空间，并不...阅读全文
注意：还没有解决hash冲突和hash倾斜的问题。 package main import "fmt" var nowCapacity = 10 //当前容量 const maxCapacity = 100 //最大容量 const loadFactor = 0.75 //负载因子(决定扩容因数) type Entry struct { k string //key v interface{} //值 next *Entry } type HashMap struct { size int //map的大小 bucket []Entry //存放数据的桶,为slice } //创建一个CreateHashMap的函数，返回一个HashMap指针 func CreateHashMap() *H...阅读全文
最近在看gokit的熔断器源码的时候看到了内部有使用到 container/ring 的这个数据结构；虽然大体知道这个数据结构提供的一个常用API，也知道该怎么用；但是不知道内部具体是怎么实现的。所以就看了内部的源码实现；在这里分享出来，有不对的地方欢迎大家指正。 在正式开始讲解源码之前先铺垫几个基础的数据结构知识 1、单链表 节点内部会存储当前节点的值跟下一个节点的指针，单链表的访问只能向前推进访问不能后退 单链表 2、单向循环链表 单向循环链表的尾节点的后继节点指向了链表的头结点；其他跟单链表完全相同 单向循环链表 3、双向链表 双向链表每个节点内部存储了当前节点的值，后继节点的指针，前驱节点的指针 双向链表 4、双向循环链表 双向循环链表的头结点的前驱节点为链表的尾节点指针，而尾结点的...阅读全文
题目：从尾到头打印链表 要求：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例： ` 输入：head = [1,3,2] 输出：[2,3,1] ` 限制： 0 <= 链表长度="" <="10000 题解1：递归法 因为是从尾到头返回每一个节点的值，所以很容易想到如果从最后的节点将值放入数组中，然后再往前逐步将数据放入数组，最后回到头节点返回即可，可以想到递归就能轻松做到，只要注意递归函数的结束条件即可。 /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reversePrint(head *ListNode...阅读全文
合并两个有序链表（Merge-Two-Sorted-Lists） 题干如下： 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4来源：力扣 这个题目和 两数相加 相似，都是考察对链表的操作。其实具体实现方式也差不多啦。 解题思路 根据题干我们知道，给定的两个链表是有序的。假设 l1 指向其中一个链表的头部，l2 指向另一个链表的头部，并初始化 head 和 current，使它们指向一个默认的节点。我们比较 l1 指向节点的值 V(l1) 与 l2 指向节点的值 V(l2) 的大小，如果 V(l1) 的值小于 V(l2) 的值，则使 current.next 指向...阅读全文
Go语言内置运行时（就是runtime），抛弃了传统的内存分配方式，改为自主管理。这样可以自主地实现更好的内存使用模式，比如内存池、预分配等等。这样，不会每次内存分配都需要进行系统调用。Golang运行时的内存分配算法主要源自 Google 为 C 语言开发的 TCMalloc算法，全称 Thread-CachingMalloc。核心思想就是把内存分为多级管理，从而降低锁的粒度。它将可用的堆内存采用二级分配的方式进行管理：每个线程都会自行维护一个独立的内存池，进行内存分配时优先从该内存池中分配，当内存池不足时才会向全局内存池申请，以避免不同线程对全局内存池的频繁竞争。为了更好的阅读体验，手动贴上文章目录： 基础概念Go在程序启动的时候，会先向操作系统申请一块内存（注意这时还只是一段虚拟的地址...阅读全文
题目描述 输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） 思路 假设两个链表的第一个公共结点为c。 链表1可以表示为a+c，链表2可以表示为b+c。 可以通过a+c+b+c = b+c+a+c来快速求出c的值，若没有公共结点，那c便是null。 可以根据下图，简单理解下这个过程。 Java代码实现 public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p1 = pHead1; ListNode p2 = pHead2; while(p1 != p2){ p...阅读全文
简介 延迟调用(defer)的优势是: 即使函数执行出错，依然能保证回收资源等操作得以执行 可以在变量的定义处加入defer，代码结构上避免忘记做某些数据的回收 劣势: 性能上会会比直接调用慢一些 如果在defer中释放，相对来说只会在函数执行结束的时候才会调用，变量生命周期会变长. 定义 编写以下程序, dump出汇编. defer主要调用了一下两个函数func deferprocStack(d *_defer)和func deferreturn(arg0 uintptr) package main import ( "fmt" ) func main() { defer fmt.Println(0x11) } (base) ➜ readsrc go tool objdump -s "ma...阅读全文
底层数据结构 type hchan struct { qcount uint // total data in the queue dataqsiz uint // size of the circular queue buf unsafe.Pointer // points to an array of dataqsiz elements elemsize uint16 closed uint32 elemtype *_type // element type sendx uint // send index recvx uint // receive index recvq waitq // list of recv waiters sendq waitq // list of send...阅读全文
去年开始写文章的第一篇就是关于 defer，名字比较文艺：《Golang 之轻松化解 defer 的温柔陷阱》，还被吐槽了。因为这篇文章，到《Go 夜读》讲了一期。不过当时纯粹是应用层面的，也还没有跳进 Go 源码这个大坑，文章看着比较清新，也没有大段的源码解析。 自从听了曹大在《Go 夜读》分享的 Go 汇编，以及研读了阿波张的 Go 调度器源码分析的文章后，各种源码、汇编满天飞…… 上次欧神写了一篇《Go GC 20 问》，全文也没有一行源码，整体读下来很畅快。今天这篇也来尝试一下这种写法，不过，我们先从一个小的主题开始：defer 链表是如何被遍历并执行的。 关于 defer 的源码分析文章，网络上也有很多。不过，很少有能完全说明白这个话题的，除了阿波张的。 我们知道，为了在退出函数前...阅读全文
基本概念 定义：零个或者多个数据元素的有限序列，在复杂的线性表中，一个数据元素可以由若干个数据项组成。 直接前驱元素：若线性表记为(a1a2a3...an),则表中a2领先于a3，则称a2是a3的直接前驱元素，且有且仅有一个直接前驱元素 直接后继元素：称a3是a2的直接后继元素，且有且仅有一个直接后继元素 线性表的长度：线性表的元素个数n，为线性表的长度，随着线性表插入和删除操作，该值是变动的，线性表的存储长度一般小于数组的长度 数组的长度：存放线性表的存储空间的长度，存储分配后这个值一般是不变的 空表：长度n为0时，该线性表为空表 地址：存储器的每个存储单元都有自己在内存的编号，简称为地址 线性表的存储 顺序存储结构 线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素...阅读全文
Golang: 思路：先得出链表长度，然后就可以对k做处理，打个比方，链表长度5，那么k=6与k=1的情况就是一致的，但是我最后代码写的还是很复杂，不做参考吧。 代码如下： func rotateRight(head *ListNode, k int) *ListNode { if k==0||head==nil||head.Next==nil { return head } length,temp:=0,head for temp.Next!=nil{ temp=temp.Next length++ } length++ var res *ListNode last,i:=temp,0 temp=head k=k%length if k==0 { return head }else { l...阅读全文
