runtime

• go struct能不能比較

同一個(gè)struct的2個(gè)實(shí)例能否比較
1.成員變量帶有了不能比較的成員茬射，== 會(huì)報(bào)錯(cuò) mismatched types
2.指針類型可以比較沼头，就是比較指針中存儲(chǔ)的地址
3.成員變量沒(méi)有不能比較的成員推盛，== 會(huì)比較每個(gè)字段的值

不同的結(jié)構(gòu)體，如果可以強(qiáng)制轉(zhuǎn)換玫鸟，強(qiáng)制轉(zhuǎn)換之后轿曙，如果成員變量不含有不可比較成員變量袒哥，可以比較

可排序的數(shù)據(jù)類型有三種挺身，Integer侯谁，F(xiàn)loating-point，和String
可比較的數(shù)據(jù)類型除了上述三種外章钾，還有Boolean墙贱，Complex，Pointer贱傀，Channel惨撇，Interface和Array
不可比較的數(shù)據(jù)類型包括，Slice, Map, 和Function

struct必須是可比較的府寒，才能作為map的key魁衙，否則編譯時(shí)報(bào)錯(cuò)

DeepEqual
Two values of identical type are deeply equal if one of the following cases applies.
Values of distinct types are never deeply equal.

1.Array values are deeply equal when their corresponding elements are deeply equal.

2.Struct values are deeply equal if their corresponding fields, both exported and unexported, are deeply equal.

3.Func values are deeply equal if both are nil; otherwise they are not deeply equal.

4.Interface values are deeply equal if they hold deeply equal concrete values.

5.Map values are deeply equal when all of the following are true:
they are both nil or both non-nil,
they have the same length,and either they are the same map object or their corresponding keys (matched using Go equality) map to deeply equal values.

Pointer values are deeply equal if they are equal using Go's == operator or if they point to deeply equal values.

Slice values are deeply equal when all of the following are true: they are both nil or both non-nil, they have the same length,
and either they point to the same initial entry of the same underlying array (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal. Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil)) are not deeply equal.

func DeepEqual(x, y interface{}) bool {
    if x == nil || y == nil {
        return x == y
    }
    v1 := ValueOf(x)
    v2 := ValueOf(y)
    if v1.Type() != v2.Type() {
        return false
    }
    return deepValueEqual(v1, v2, make(map[visit]bool), 0)
}

// Tests for deep equality using reflected types. The map argument tracks
// comparisons that have already been seen, which allows short circuiting on
// recursive types.
func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool {
    if !v1.IsValid() || !v2.IsValid() {
        return v1.IsValid() == v2.IsValid()
    }
    if v1.Type() != v2.Type() {
        return false
    }

    // if depth > 10 { panic("deepValueEqual") }    // for debugging

    // We want to avoid putting more in the visited map than we need to.
    // For any possible reference cycle that might be encountered,
    // hard(v1, v2) needs to return true for at least one of the types in the cycle,
    // and it's safe and valid to get Value's internal pointer.
    hard := func(v1, v2 Value) bool {
        switch v1.Kind() {
        case Map, Slice, Ptr, Interface:
            // Nil pointers cannot be cyclic. Avoid putting them in the visited map.
            return !v1.IsNil() && !v2.IsNil()
        }
        return false
    }

    if hard(v1, v2) {
        addr1 := v1.ptr
        addr2 := v2.ptr
        if uintptr(addr1) > uintptr(addr2) {
            // Canonicalize order to reduce number of entries in visited.
            // Assumes non-moving garbage collector.
            addr1, addr2 = addr2, addr1
        }

        // Short circuit if references are already seen.
        typ := v1.Type()
        v := visit{addr1, addr2, typ}
        if visited[v] {
            return true
        }

        // Remember for later.
        visited[v] = true
    }

    switch v1.Kind() {
    case Array:
        for i := 0; i < v1.Len(); i++ {
            if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
                return false
            }
        }
        return true

• client如何實(shí)現(xiàn)長(zhǎng)連接

• 主協(xié)程如何等其余協(xié)程完再操作

• slice，len株搔，cap剖淀，共享，擴(kuò)容

• list的實(shí)現(xiàn)邪狞，arrayList

// List holds the elements in a slice
type List struct {
    elements []interface{}
    size     int
}

// Add appends a value at the end of the list
func (list *List) Add(values ...interface{}) {
    list.growBy(len(values))
    for _, value := range values {
        list.elements[list.size] = value
        list.size++
    }
}

// Expand the array if necessary, i.e. capacity will be reached if we add n elements
func (list *List) growBy(n int) {
    // When capacity is reached, grow by a factor of growthFactor and add number of elements
    currentCapacity := cap(list.elements)
    if list.size+n >= currentCapacity {
        newCapacity := int(growthFactor * float32(currentCapacity+n))
        list.resize(newCapacity)
    }
}

func (list *List) resize(cap int) {
    newElements := make([]interface{}, cap, cap)
    copy(newElements, list.elements)
    list.elements = newElements
}
// Remove removes the element at the given index from the list.
func (list *List) Remove(index int) {

    if !list.withinRange(index) {
        return
    }

    list.elements[index] = nil                                    // cleanup reference
    copy(list.elements[index:], list.elements[index+1:list.size]) // shift to the left by one (slow operation, need ways to optimize this)
    list.size--

    list.shrink()
}
// Shrink the array if necessary, i.e. when size is shrinkFactor percent of current capacity
func (list *List) shrink() {
    if shrinkFactor == 0.0 {
        return
    }
    // Shrink when size is at shrinkFactor * capacity
    currentCapacity := cap(list.elements)
    if list.size <= int(float32(currentCapacity)*shrinkFactor) {
        list.resize(list.size)
    }
}

• linkedList
• map如何順序讀取
  按照插入順序讀取，實(shí)現(xiàn)java的LinkedHashMap

// Map holds the elements in a regular hash table, and uses doubly-linked list to store key ordering.
type Map struct {
    table    map[interface{}]interface{}
    ordering *doublylinkedlist.List
}

// Put inserts key-value pair into the map.
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (m *Map) Put(key interface{}, value interface{}) {
    if _, contains := m.table[key]; !contains {
        m.ordering.Append(key)
    }
    m.table[key] = value
}

// Values returns all values in-order based on the key.
func (m *Map) Values() []interface{} {
    values := make([]interface{}, m.Size())
    count := 0
    it := m.Iterator()
    for it.Next() {
        values[count] = it.Value()
        count++
    }
    return values
}

• map如何排序
  treeMap茅撞，用紅黑樹
• 實(shí)現(xiàn)set

// Set holds elements in go's native map
type Set struct {
    items map[interface{}]struct{}
}

var itemExists = struct{}{}

// Add adds the items (one or more) to the set.
func (set *Set) Add(items ...interface{}) {
    for _, item := range items {
        set.items[item] = itemExists
    }
}

• arrayList實(shí)現(xiàn)的stack

// Stack holds elements in an array-list
type Stack struct {
    list *arraylist.List
}

// New instantiates a new empty stack
func New() *Stack {
    return &Stack{list: arraylist.New()}
}

// Push adds a value onto the top of the stack
func (stack *Stack) Push(value interface{}) {
    stack.list.Add(value)
}

// Pop removes top element on stack and returns it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to pop.
func (stack *Stack) Pop() (value interface{}, ok bool) {
    value, ok = stack.list.Get(stack.list.Size() - 1)
    stack.list.Remove(stack.list.Size() - 1)
    return
}

// Peek returns top element on the stack without removing it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to peek.
func (stack *Stack) Peek() (value interface{}, ok bool) {
    return stack.list.Get(stack.list.Size() - 1)
}

• linkedList實(shí)現(xiàn)的stack

// Stack holds elements in a singly-linked-list
type Stack struct {
    list *singlylinkedlist.List
}

// New nnstantiates a new empty stack
func New() *Stack {
    return &Stack{list: &singlylinkedlist.List{}}
}

// Push adds a value onto the top of the stack
func (stack *Stack) Push(value interface{}) {
    stack.list.Prepend(value)
}

// Pop removes top element on stack and returns it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to pop.
func (stack *Stack) Pop() (value interface{}, ok bool) {
    value, ok = stack.list.Get(0)
    stack.list.Remove(0)
    return
}

// Peek returns top element on the stack without removing it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to peek.
func (stack *Stack) Peek() (value interface{}, ok bool) {
    return stack.list.Get(0)
}

• 堆帆卓，優(yōu)先級(jí)隊(duì)列

• A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues.[1]:162–163 The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.[2]

• A binary heap is defined as a binary tree with two additional constraints:[3]

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.

// Heap holds elements in an array-list
type Heap struct {
    list       *arraylist.List
    Comparator utils.Comparator
}

// NewWith instantiates a new empty heap tree with the custom comparator.
func NewWith(comparator utils.Comparator) *Heap {
    return &Heap{list: arraylist.New(), Comparator: comparator}
}

// Push adds a value onto the heap and bubbles it up accordingly.
func (heap *Heap) Push(values ...interface{}) {
    if len(values) == 1 {
        heap.list.Add(values[0])
        heap.bubbleUp()
    } else {
        // Reference: https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
        for _, value := range values {
            heap.list.Add(value)
        }
        size := heap.list.Size()/2 + 1
        for i := size; i >= 0; i-- {
            heap.bubbleDownIndex(i)
        }
    }
}

// Pop removes top element on heap and returns it, or nil if heap is empty.
// Second return parameter is true, unless the heap was empty and there was nothing to pop.
func (heap *Heap) Pop() (value interface{}, ok bool) {
    value, ok = heap.list.Get(0)
    if !ok {
        return
    }
    lastIndex := heap.list.Size() - 1
    heap.list.Swap(0, lastIndex)
    heap.list.Remove(lastIndex)
    heap.bubbleDown()
    return
}

// Performs the "bubble up" operation. This is to place a newly inserted
// element (i.e. last element in the list) in its correct place so that
// the heap maintains the min/max-heap order property.
func (heap *Heap) bubbleUp() {
    index := heap.list.Size() - 1
    for parentIndex := (index - 1) >> 1; index > 0; parentIndex = (index - 1) >> 1 {
        indexValue, _ := heap.list.Get(index)
        parentValue, _ := heap.list.Get(parentIndex)
        if heap.Comparator(parentValue, indexValue) <= 0 {
            break
        }
        heap.list.Swap(index, parentIndex)
        index = parentIndex
    }
}

// Performs the "bubble down" operation. This is to place the element that is at the index
// of the heap in its correct place so that the heap maintains the min/max-heap order property.
func (heap *Heap) bubbleDownIndex(index int) {
    size := heap.list.Size()
    for leftIndex := index<<1 + 1; leftIndex < size; leftIndex = index<<1 + 1 {
        rightIndex := index<<1 + 2
        smallerIndex := leftIndex
        leftValue, _ := heap.list.Get(leftIndex)
        rightValue, _ := heap.list.Get(rightIndex)
        if rightIndex < size && heap.Comparator(leftValue, rightValue) > 0 {
            smallerIndex = rightIndex
        }
        indexValue, _ := heap.list.Get(index)
        smallerValue, _ := heap.list.Get(smallerIndex)
        if heap.Comparator(indexValue, smallerValue) > 0 {
            heap.list.Swap(index, smallerIndex)
        } else {
            break
        }
        index = smallerIndex
    }
}

• Go的反射包怎么找到對(duì)應(yīng)的方法

// MethodByName returns a function value corresponding to the method
// of v with the given name.
// The arguments to a Call on the returned function should not include
// a receiver; the returned function will always use v as the receiver.
// It returns the zero Value if no method was found.
func (v Value) MethodByName(name string) Value {
    if v.typ == nil {
        panic(&ValueError{"reflect.Value.MethodByName", Invalid})
    }
    if v.flag&flagMethod != 0 {
        return Value{}
    }
    m, ok := v.typ.MethodByName(name)
    if !ok {
        return Value{}
    }
    return v.Method(m.Index)
}
func (t *rtype) MethodByName(name string) (m Method, ok bool) {
    if t.Kind() == Interface {
        tt := (*interfaceType)(unsafe.Pointer(t))
        return tt.MethodByName(name)
    }
    ut := t.uncommon()
    if ut == nil {
        return Method{}, false
    }
    // TODO(mdempsky): Binary search.
    for i, p := range ut.exportedMethods() {
        if t.nameOff(p.name).name() == name {
            return t.Method(i), true
        }
    }
    return Method{}, false
}
// Method returns a function value corresponding to v's i'th method.
// The arguments to a Call on the returned function should not include
// a receiver; the returned function will always use v as the receiver.
// Method panics if i is out of range or if v is a nil interface value.
func (v Value) Method(i int) Value {
    if v.typ == nil {
        panic(&ValueError{"reflect.Value.Method", Invalid})
    }
    if v.flag&flagMethod != 0 || uint(i) >= uint(v.typ.NumMethod()) {
        panic("reflect: Method index out of range")
    }
    if v.typ.Kind() == Interface && v.IsNil() {
        panic("reflect: Method on nil interface value")
    }
    fl := v.flag & (flagStickyRO | flagIndir) // Clear flagEmbedRO
    fl |= flag(Func)
    fl |= flag(i)<<flagMethodShift | flagMethod
    return Value{v.typ, v.ptr, fl}
}

code

• 實(shí)現(xiàn)消息隊(duì)列（多生產(chǎn)者，多消費(fèi)者）
• Go怎么做深拷貝米丘。

基于序列化和反序列化來(lái)實(shí)現(xiàn)對(duì)象的深度拷貝

或者 反射

反射：https://github.com/jinzhu/copier

參考：https://toolchain.dexscript.com/golang-deep-copy.html

• Map是線程安全的嗎剑令？怎么解決并發(fā)安全問(wèn)題？

不是拄查，讀的時(shí)候會(huì)檢查hashWriting標(biāo)志吁津， 如果有這個(gè)標(biāo)志，就會(huì)報(bào)并發(fā)錯(cuò)誤堕扶。

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

• sync.Map 怎么解決線程安全問(wèn)題碍脏？

type Map struct {
    // 當(dāng)涉及到dirty數(shù)據(jù)的操作的時(shí)候，需要使用這個(gè)鎖
    mu Mutex
    // 一個(gè)只讀的數(shù)據(jù)結(jié)構(gòu)稍算，因?yàn)橹蛔x典尾，所以不會(huì)有讀寫沖突。
    // 所以從這個(gè)數(shù)據(jù)中讀取總是安全的糊探。
    // 實(shí)際上钾埂，實(shí)際也會(huì)更新這個(gè)數(shù)據(jù)的entries,如果entry是未刪除的(unexpunged), 并不需要加鎖河闰。如果entry已經(jīng)被刪除了，需要加鎖褥紫，以便更新dirty數(shù)據(jù)姜性。
    read atomic.Value // readOnly
    // dirty數(shù)據(jù)包含當(dāng)前的map包含的entries,它包含最新的entries(包括read中未刪除的數(shù)據(jù),雖有冗余，但是提升dirty字段為read的時(shí)候非乘杩迹快部念，不用一個(gè)一個(gè)的復(fù)制，而是直接將這個(gè)數(shù)據(jù)結(jié)構(gòu)作為read字段的一部分),有些數(shù)據(jù)還可能沒(méi)有移動(dòng)到read字段中绳军。
    // 對(duì)于dirty的操作需要加鎖印机，因?yàn)閷?duì)它的操作可能會(huì)有讀寫競(jìng)爭(zhēng)。
    // 當(dāng)dirty為空的時(shí)候门驾， 比如初始化或者剛提升完射赛，下一次的寫操作會(huì)復(fù)制read字段中未刪除的數(shù)據(jù)到這個(gè)數(shù)據(jù)中。
    dirty map[interface{}]*entry
    // 當(dāng)從Map中讀取entry的時(shí)候奶是，如果read中不包含這個(gè)entry,會(huì)嘗試從dirty中讀取楣责，這個(gè)時(shí)候會(huì)將misses加一，
    // 當(dāng)misses累積到 dirty的長(zhǎng)度的時(shí)候聂沙， 就會(huì)將dirty提升為read,避免從dirty中miss太多次秆麸。因?yàn)椴僮鱠irty需要加鎖。
    misses int
}

Load,Store,Delete

想一想及汉，mysql加鎖沮趣，是不是有表級(jí)鎖、行級(jí)鎖坷随，前文的sync.RWMutex加鎖方式相當(dāng)于表級(jí)鎖房铭。

而sync.Map其實(shí)也是相當(dāng)于表級(jí)鎖，只不過(guò)多讀寫分了兩個(gè)map温眉，本質(zhì)還是一樣的缸匪。

既然這樣，那就自然知道優(yōu)化方向了：就是把鎖的粒度盡可能降低來(lái)提高運(yùn)行速度类溢。

思路：對(duì)一個(gè)大map進(jìn)行hash凌蔬，其內(nèi)部是n個(gè)小map，根據(jù)key來(lái)來(lái)hash確定在具體的那個(gè)小map中闯冷，這樣加鎖的粒度就變成1/n了砂心。
網(wǎng)上找了下，真有大佬實(shí)現(xiàn)了

參考：https://colobu.com/2017/07/11/dive-into-sync-Map/
參考：https://juejin.im/post/6844903895227957262

• Go里面一個(gè)協(xié)程能保證綁定在一個(gè)內(nèi)核線程上面的蛇耀。

LockOSThread
當(dāng)然只能綁定用戶態(tài)線程计贰，不能綁定內(nèi)核態(tài)線程

我們知道golang的scheduler可以理解為公平協(xié)作調(diào)度和搶占的綜合體，他不支持優(yōu)先級(jí)調(diào)度蒂窒。當(dāng)你開了幾十萬(wàn)個(gè)goroutine躁倒，并且大多數(shù)協(xié)程已經(jīng)在runq等待調(diào)度了, 那么如果你有一個(gè)重要的周期性的協(xié)程需要優(yōu)先執(zhí)行該怎么辦荞怒？

可以借助runtime.LockOSThread()方法來(lái)綁定線程，綁定線程M后的好處在于秧秉，他可以由system kernel內(nèi)核來(lái)調(diào)度褐桌，因?yàn)樗举|(zhì)是線程了。

參考：http://xiaorui.cc/archives/5320

• defer A ; defer B ; defer panic("") A和B能不能執(zhí)行到

func main() {
    defer func() {
        panic("err")
    }()
    defer func() {
        println("a")
    }()
    defer func() {
        println("b")
    }()
    defer func() {
        panic("err")
    }()
    println("c")
}

c
b
a
panic: err
        panic: err

goroutine 1 [running]:
main.main.func1()
        /Users/xushuangfu/go/src/github.com/shuff1e/code-review/Temp/test/143.go:5 +0x39
panic(0x1060240, 0x1083ca0)
        /usr/local/go/src/runtime/panic.go:969 +0x166
main.main.func4()
        /Users/xushuangfu/go/src/github.com/shuff1e/code-review/Temp/test/143.go:14 +0x39
main.main()
        /Users/xushuangfu/go/src/github.com/shuff1e/code-review/Temp/test/143.go:17 +0xa4

Process finished with exit code 2

• Go切片和數(shù)據(jù)之間的區(qū)別,切片怎么擴(kuò)容,擴(kuò)容過(guò)程中需不需要重新寫入

memmove

擴(kuò)容就是為切片分配一塊新的內(nèi)存空間并將原切片的元素全部拷貝過(guò)去

• copy是操作符還是內(nèi)置函數(shù)

內(nèi)置函數(shù)

• Go的協(xié)程可以不可以自己讓出cpu象迎，一個(gè)協(xié)程掛起換入另外一個(gè)協(xié)程是什么過(guò)程荧嵌？

runtime.Gosched，暫停砾淌，釋放線程去執(zhí)行其他任務(wù)啦撮。當(dāng)前任務(wù)被放回隊(duì)列，等待下次調(diào)度時(shí)恢復(fù)執(zhí)行汪厨。

運(yùn)行時(shí)會(huì)主動(dòng)向長(zhǎng)時(shí)間運(yùn)行(10ms）的任務(wù)發(fā)起搶占調(diào)度赃春。

協(xié)作式調(diào)度

我們?cè)谠O(shè)計(jì)原理中介紹過(guò)了 Go 語(yǔ)言基于協(xié)作式和信號(hào)的兩種搶占式調(diào)度，在這里我們介紹 Go 語(yǔ)言中的協(xié)作式調(diào)度劫乱。runtime.Gosched 就是主動(dòng)讓出處理器织中，允許其他 Goroutine 運(yùn)行。該函數(shù)無(wú)法掛起 Goroutine衷戈，調(diào)度器會(huì)在自動(dòng)調(diào)度當(dāng)前 Goroutine：

func Gosched() {
    checkTimeouts()
    mcall(gosched_m)
}

func gosched_m(gp *g) {
    goschedImpl(gp)
}

func goschedImpl(gp *g) {
    casgstatus(gp, _Grunning, _Grunnable)
    dropg()
    lock(&sched.lock)
    globrunqput(gp)
    unlock(&sched.lock)

    schedule()
}

經(jīng)過(guò)連續(xù)幾次跳轉(zhuǎn)狭吼，我們最終在 g0 的棧上調(diào)用 runtime.goschedImpl 函數(shù)，運(yùn)行時(shí)會(huì)更新 Goroutine 的狀態(tài)到 _Grunnable殖妇，讓出當(dāng)前的處理器并將 Goroutine 重新放回全局隊(duì)列刁笙，在最后，該函數(shù)會(huì)調(diào)用 runtime.schedule 重新觸發(fā)調(diào)度谦趣。
另外 參考：http://interview.wzcu.com/Golang/goroutine.html

• 什么情況下 M 會(huì)進(jìn)入自旋的狀態(tài)？

（M 是系統(tǒng)線程蔚润。為了保證自己不被釋放磅氨，所以自旋尺栖。這樣一旦有 G 需要處理嫡纠，M 可以直接使用，不需要再創(chuàng)建延赌。M 自旋表示此時(shí)沒(méi)有 G 需要處理）

在Go的調(diào)度中除盏，m一旦被創(chuàng)建則不會(huì)退出。在系統(tǒng)調(diào)用挫以、cgocall者蠕、lockOSThread時(shí)，為了防止阻塞其他g的執(zhí)行掐松，Go會(huì)新建或者喚醒m(os線程)執(zhí)行其他的g踱侣，所以可能導(dǎo)致m的增加粪小。

如何保證m數(shù)量不會(huì)太多，同時(shí)有足夠的線程使p(cpu)不會(huì)空閑抡句？主要的手段是通過(guò)多路復(fù)用和m的spinning探膊。多路復(fù)用解決網(wǎng)絡(luò)和文件io時(shí)的阻塞(與net poll類似，Go1.8.1的代碼中為os.File加了poll接口)待榔，避免每次讀寫的系統(tǒng)調(diào)用消耗線程逞壁。

而m的spinning的作用是盡量保證始終有m處于spinning尋找g(并不是執(zhí)行g(shù)，充分利用多cpu)的同時(shí)锐锣，不會(huì)有太多m同時(shí)處于spinning(浪費(fèi)cpu)腌闯。不同于一般意義的自旋，m處于自旋是指m的本地隊(duì)列雕憔、全局隊(duì)列姿骏、poller都沒(méi)有g(shù)可運(yùn)行時(shí)，m進(jìn)入自旋并嘗試從其他p偷取(steal)g橘茉，每當(dāng)一個(gè)spinning的m獲取到g后工腋，會(huì)退出spinning并嘗試喚醒新的m去spinning。

所以畅卓，一旦總的spinning的m數(shù)量大于0時(shí)擅腰，就不用喚醒新的m了去spinning浪費(fèi)cpu了。
參考：http://interview.wzcu.com/Golang/goroutine.html

• go 里的 syncLock 和 channel 的性能有區(qū)別嗎翁潘？

mutex性能略好趁冈，但chan更go化，更推薦拜马。

• Golang slice 不斷 append渗勘，是如何給它分配內(nèi)存的？slice 如果分配的 capacity 是 10俩莽，那當(dāng)容量到多大的時(shí)候才會(huì)擴(kuò)容旺坠？8、9扮超、10取刃？

擴(kuò)容會(huì)發(fā)生在slice append的時(shí)候，當(dāng)slice的cap不足以容納新元素出刷，就會(huì)進(jìn)行g(shù)rowSlice

網(wǎng)上很多博客也有提到璧疗，slice擴(kuò)容，cap不夠1024的馁龟，直接翻倍崩侠；cap超過(guò)1024的，新cap變?yōu)槔蟘ap的1.25倍坷檩。

• g0棧

由于m是實(shí)際執(zhí)行體却音，m的整個(gè)代碼邏輯基本上就是整個(gè)調(diào)度邏輯改抡。

類似于Linux的內(nèi)核棧和用戶棧，Go的m也有兩類棧：一類是系統(tǒng)棧(或者叫調(diào)度棧)系瓢，主要用于運(yùn)行runtime的程序邏輯雀摘；另一類是g棧，用于運(yùn)行g(shù)的程序邏輯八拱。

每個(gè)m在創(chuàng)建時(shí)會(huì)分配一個(gè)默認(rèn)的g叫g(shù)0阵赠，g0不執(zhí)行任何代碼邏輯，只是用來(lái)存放m的調(diào)度棧等信息肌稻。當(dāng)要執(zhí)行Go runtime的一些邏輯比如創(chuàng)建g清蚀、新建m等，都會(huì)首先切換到g0棧然后執(zhí)行爹谭，而執(zhí)行g(shù)任務(wù)時(shí)枷邪，會(huì)切換到g的棧上。在調(diào)度棧和g棧上不斷切換使整個(gè)調(diào)度過(guò)程復(fù)雜了不少诺凡。

• https://www.nowcoder.com/discuss/489000

• top k 有沒(méi)有 O(k) 的方法东揣？

桶排序

冒泡排序，堆排序腹泌，快速排序等都是基于比較的排序嘶卧，時(shí)間復(fù)雜度下限為O(nlogn)。
而有一些排序的時(shí)間復(fù)雜度可以是O(n), 比如桶排序和基數(shù)排序凉袱。
但是這類排序有較為苛刻的限制條件：元素須是數(shù)值類型芥吟。
同時(shí)，如果是桶排序的話专甩，范圍不能太大钟鸵，否則需要的桶太多，空間復(fù)雜度無(wú)法接受涤躲。
桶排序的元素不一定要是整數(shù)棺耍，有時(shí)候浮點(diǎn)數(shù)也可以。
比如种樱，如果數(shù)據(jù)取值范圍在[0, 100.0], 并且只有兩位小數(shù), 可以這么解：

private static float[] pickTopKByBucketSort(float[] a, int k) {
    int[] bucket = new int[10000];

    for (int i = 0; i < a.length; i++) {
        int index = Math.round(a[i] * 100f);
        bucket[index]++;
    }

    float[] r = new float[k];
    int p = 0;
    for (int i = bucket.length - 1; i >= 0 && p < k; i--) {
        int c = bucket[i];
        while (c > 0 && p < k) {
            r[p++] = i / 100f;
            c--;
        }
    }

    return r;
}

取一萬(wàn)個(gè)桶蒙袍，將每個(gè)元素乘以100，四舍五入為整數(shù)（有一些小數(shù)在計(jì)算機(jī)二進(jìn)制中無(wú)法精確表示缸托，同時(shí)直接強(qiáng)轉(zhuǎn)成int的話是向下取整）左敌，
放到對(duì)應(yīng)的桶中瘾蛋；
然后從最大的桶開始檢索俐镐，收集100個(gè)元素。
時(shí)間復(fù)雜度跟數(shù)據(jù)量和桶數(shù)量（取決于數(shù)據(jù)的大小范圍）有關(guān)哺哼。
在數(shù)據(jù)量遠(yuǎn)大于桶數(shù)量時(shí)佩抹，時(shí)間復(fù)雜度為O(n)叼风。

• 快排的時(shí)間復(fù)雜度是 O(nlogn)，你有哪些優(yōu)化時(shí)間復(fù)雜度的方法嗎棍苹？比如空間換時(shí)間

桶排序

    private int indexFor(int a, int min, int step) {
        return (a - min) / step;
    }

    public void bucketSort(int[] arr) {

        int max = arr[0], min = arr[0];
        for (int a : arr) {
            if (max < a)
                max = a;
            if (min > a)
                min = a;
        }
        // 該值也可根據(jù)實(shí)際情況選擇
        int bucketNum = max / 10 - min / 10 + 1;
        List buckList = new ArrayList<List<Integer>>();
        // create bucket
        for (int i = 1; i <= bucketNum; i++) {
            buckList.add(new ArrayList<Integer>());
        }
        // push into the bucket
        for (int i = 0; i < arr.length; i++) {
            int index = indexFor(arr[i], min, 10);
            ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
        }
        ArrayList<Integer> bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList<Integer>) buckList.get(i);
            insertSort(bucket);
            for (int k : bucket) {
                arr[index++] = k;
            }
        }

    }

    // 把桶內(nèi)元素插入排序
    private void insertSort(List<Integer> bucket) {
        for (int i = 1; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

• 協(xié)程的椢匏蓿空間大小有限制嗎？會(huì)主動(dòng)擴(kuò)展嗎枢里？

無(wú)限大孽鸡，受到系統(tǒng)內(nèi)存的限制
會(huì)主動(dòng)擴(kuò)展

參考：https://studygolang.com/articles/1744

• 協(xié)程如果像你說(shuō)的這么牛逼，為什么只有Go支持呢栏豺，其他語(yǔ)言為什么這一兩年才開始有協(xié)程庫(kù)彬碱？協(xié)程這個(gè)概念好多年前就有了不是嗎？（從cpu的角度回答奥洼，這個(gè)問(wèn)題當(dāng)時(shí)確實(shí)問(wèn)得我有點(diǎn)懵巷疼，騰訊總監(jiān)問(wèn)的，應(yīng)該從多核發(fā)展的角度去考慮灵奖，另外結(jié)合線程/協(xié)程的調(diào)度特點(diǎn)）嚼沿。

想像一下如果沒(méi)有thread，也沒(méi)有ThreadLocal瓷患，@Transactional不起作用了骡尽，又沒(méi)有等價(jià)的工具，是不是很郁悶擅编？這么看來(lái)怎么著都不是個(gè)劃算的事情爆阶。我想Oracle對(duì)此并不會(huì)有太大興趣。