本篇是「比照 Python 学习 Go」系列的第四篇，本篇文章咱们来看下 Go 的高级数据结构，因文章偏长分为两篇，此为下篇。本系列的其余文章可到 「比照 Python 学习 Go」- 开篇 查看，上面咱们开始明天的分享。

上篇说道，Go和Python的数据结构可分为类数组和哈希构造。本篇咱们来看下哈希构造相干的类型。

哈希构造

哈希构造又叫做散列表（hash table），它是数组的一种扩大。它通过散列函数把元素的键值映射为数组的下标，而后将数据存储在数组中对应下标的地位。当咱们依照键值查问元素时，咱们用同样的散列函数，将键值转化数组下标，从对应的数组下标的地位取数据。通过散列函数，咱们能够相似数组下标一样间接定位数据，工夫复杂度能够到O(1)。

哈希构造中，最重要的两个知识点是「哈希函数的构建」和「散列抵触的解决」。

哈希函数构建的好坏间接影响到数据结构的性能，哈希的key 散布平均的话，会缩小散列抵触的产生。
散列抵触是哈希构造不可避免的，解决散列抵触的办法次要有两种，是「凋谢寻址法(open addressing)」和「列表法(chaining)」。

开发寻址法，即利用一些算法查找下一个为空的数组地位。列表法，是在以后key的数组地位，以链表的模式，减少额定空间。

更多哈希常识，可参考我整顿的无关散列表的笔记 数据结构与算法 - 散列表。

理解了上边列出的哈希构造的基本知识后，咱们来看看Go和Python的哈希构造是如何的。

Go

Go语言的中的哈希构造为 map 构造，依据map的源码剖析，map的底层构造大抵如下：

最外层为一个hmap的构造体，应用一个[]bmap数组寄存了bmap的地址，bmap用来存储数据，每个bmap最多可存储8个kv对，另外还有一个overflow，存储后一个bmap的地址。
oldbuckets 用来寄存老的buckets数组地址，在扩容的时候会应用来暂存还没有移到新buckets数组的bmap地址。mapextra 用来寄存非指针数据，用于优化存储和拜访。

对于map内存的增长扩容，则次要是[]bmap数组的扩容。当数据越来越多时，[]bmap数组后边挂的bmap也会越来越多，bmap的数量越多，在查找时，则大部分工夫会破费在链表的查找上。这里有个规范，通常是在装填因子(填入表中的元素个数/散列表的长度)大于6.5时，会触发[]bmap数组的扩容，通常是源数组的两倍。扩容后，并不会立刻迁徙数据，而是先将老的[]bmap数组挂在olebuckets上，待有新的更新或插入操作时，才进行bmap的迁徙。

依据咱们对Go map内存构造的剖析，联合散列表的常识，咱们能够晓得，Go应用了「链表法」来解决散列抵触。只不过，链表中的节点并非是值，而是一个bmap构造的存储块，这样能够缩小单个链上的对象块，不便内存治理，利于GC操作。

在哈希函数方面，采纳哈希低位确定bmap，高位比照确定是否有存储的key，进步了哈希比对搜寻的效率。

另一个在bmap中，并没有key-value结对存储，而是将绝对占用空间小的key放一块，value按雷同的程序放一块。这样利用内存对齐，节俭空间。

Go map的设计处处走漏着对性能的极致谋求，强烈建议好好钻研一番。

上面咱们来看看Go map的一些罕用操作：

// 初始化// 应用make函数myMap := make(map[string]int)fmt.Println(myMap) // map[]// 应用字面量myResume := map[string]string{"name": "DeanWu", "job": "SRE"}fmt.Println(myResume)  // map[job:SRE name:DeanWu]// 申明一个空map//var myResume1 map[string]string//myResume1["name"] = "DeanWu"  //panic: assignment to entry in nil map// 空的map，零碎并没有分配内存，并能赋值。// 键值的类型能够是内置的类型，也能够是构造类型，只有这个值能够应用 == 运算符做比拟// 切片、函数以及蕴含切片的构造类型，这些类型因为具备援用语义，可被其余援用扭转原值，不能作为映射的键。//myMap1 := map[[]string]int{}//fmt.Println(myMap1)  // invalid map key type []string// 更新、赋值keymyResume["job"] = "web deployment"fmt.Println(myResume)  // map[job:web deployment name:DeanWu]// 获取某个key的值value, exists := myResume["name"]if exists {  fmt.Println(value) // DeanWu}value1 := myResume["name"]if value1 != ""{  fmt.Println(value1) // DeanWu  // 举荐上边的写法，因为即便map无此key也会返回对应的零值。须要依据数据类型，做相应的判断，不如上边的对立，不便。}// 删除键值对delete(myResume, "job")delete(myResume, "year")  // 当map中没有这个key时，什么都不执行。fmt.Println(myResume)  // map[name:DeanWu]

map 也能够嵌套。

// map嵌套myNewResume := map[string]map[string]string{  "name": {    "first": "Dean",    "last":"Wu",  },}fmt.Println(myNewResume) // map[name:map[first:Dean last:Wu]]

Python

Python 中的哈希构造，有字典和汇合两种。

字典

字典依据Python3的源码，底层构造大抵如下：

其中最外层是PyDictObject，其中定义了一些字典的全局管制字段。其中有个PyDictKeysObject定义了字典哈希表的一些字段。其中有两个数组 dk_indices[] 和 dk_entries[]，这两个便是真正的存储数据的数组。kv数据保留在dk_entries[]数组中，dk_indices[]来存储kv数据在dk_enties数组中保留的索引。其中每个kv数据以entry的数据结构来存储，如下：

typedef struct {    /* Cached hash code of me_key. */    Py_hash_t me_hash;    PyObject *me_key;    PyObject *me_value; /* This field is only meaningful for combined tables */} PyDictKeyEntry;

me_hash缓存存key的哈希值，避免哈希值的反复计算。me_key和me_value便是key和value的真正数据了。

哈希表的扩容，从源码中能够看出，一个字典的最小容量为8，Python 采纳了"翻倍扩容"的策略。依据教训值得出，哈希表数组中，装填因子为2/3时，是一个哈希抵触的临界值。所以，当哈希数组dk_entries装填因子到2/3时，便会扩容。

这里Python为了节俭内存，将索引和哈希表数组离开，分为dk_indices和dk_entries。前者保留的是数据的索引，占空间小，可申请所有元素个数的空间。后者能够只申请原大小的2/3空间。因为到2/3之后，便会扩容，这个2/3能够依据dk_indices取得。

剖析了Python 字典的底层构造，依据哈希表的常识，咱们能够晓得Python 是用「凋谢寻址法」来解决哈希抵触的。

Python 字典的罕用操作：

# 初始化myDict1 = dict()myDict2 = {}   # 举荐应用print(myDict1, myDict2)  # {} {}# 赋值myDict3 = {'name': 'Tim', 'age': 18}myDict3['job'] = 'student'print(myDict3)  # {'name': 'Tim', 'age': 18, 'job': 'student'}# 取值print(myDict3['name'])  # Tim# print(myDict3['phone'])  # KeyError: 'phone'print(myDict3.get('phone'))  # None 若没有key，应用get 办法不会抛出谬误print(myDict3.get('phone', '136xxxxxxx'))  # 136xxxxxxx  给没有key的，附默认值# 删除del[myDict3['job']]print(myDict3)  # {'name': 'Tim', 'age': 18}# 字典提供丰盛的内建办法# radiansdict.clear() 删除字典内所有元素# radiansdict.copy() 返回一个字典的浅复制，返回原字典的援用# radiansdict.fromkeys() 创立一个新字典，以序列seq中元素做字典的键，val为字典所有键对应的初始值# radiansdict.get(key, default=None) 返回指定键的值，如果值不在字典中返回default值# key in dict 如果键在字典dict里返回true，否则返回false# radiansdict.items() 以列表返回可遍历的(键, 值) 元组数组# radiansdict.keys() 以列表返回一个字典所有的键# radiansdict.setdefault(key, default=None) 和get()相似, 但如果键不存在于字典中，将会增加键并将值设为default# radiansdict.update(dict2) 把字典dict2的键/值对更新到dict里# radiansdict.values() 以列表返回字典中的所有值# pop(key[,default]) 删除字典给定键 key 所对应的值，返回值为被删除的值。key值必须给出。 否则，返回default值。# popitem() 随机返回并删除字典中的一对键和值(个别删除开端对)。

汇合

汇合和字典一样，底层也是哈希构造，和字典相比，可了解为只有key，没有values。依据Python3源码，大抵构造如下：

相比字典，汇合简略了不少。在PySetObject中间接保留了存储数据的数组。

依据汇合的底层数据结构剖析，它解决哈希抵触也是应用的「开发寻址法」。

汇合的一些罕用操作：

# 初始化s1 = {'1', '2', '3'}  # 不举荐，当元素中有字典时，会报错s2 = set(['1', '4', '5'])print(s1)  # {'3', '1', '2'}print(s2)  # {'3', '1', '2'}# 交加print(s1&s2)  # {'1'}# 并集print(s1|s2)  # {'3', '5', '4', '2', '1'}# 差集print(s1 - s2)  # {'3', '2'}# 判断子集和超集s2.issubset(s1)   # s2 是否为s1 的子集s1.issuperset(s2)  # s1 是否为 s2 的超集# 汇合的一些内建办法# set.add(obj) 增加汇合元素# set.remove(obj) 删除汇合元素# set.update(set) 合并汇合# set.pop() 随机删除一个元素，并返回该元素

独有数据结构

除了类数组和哈希构造外，Go还有本人独有的一些构造。

Go - 指针

Go 语言具备指针。 指针保留了变量的内存地址。类型 *T是指向类型 T的值的指针。其零值是 nil。

  • &符号会生成一个指向其作用对象的指针。
  • *符号示意指针指向的底层的值。

与 C 不同，Go 没有指针运算。

i, j := 42, 2701p := &i         // point to ifmt.Println(*p) // read i through the pointer*p = 21         // set i through the pointerfmt.Println(i)  // see the new value of ip = &j         // point to j*p = *p / 37   // divide j through the pointerfmt.Println(j) // see the new value of j

Python 中并没有指针的概念，内存的地址被叫做“援用”。和这里的指针有殊途同归之妙，但仅仅是体现在逻辑剖析上，并没有语法反对。

Go - 构造体

Go语言中，构造体（struct）就是一个字段的汇合，构造体字段能够通过构造体指针来拜访。

// 定义构造体，主动名必须大写结尾，作为公共变量type Vertex struct {  X int  Y int}// 初始化var ver Vertexver.X = 4  // 可应用. 来赋值和拜访构造体fmt.Println(ver.X)  // 4// 可应用指针来拜访v := Vertex{1, 2}p := &vp.X = 1e9fmt.Println(v)  // {1000000000 2}

构造体能够实现嵌套，当嵌套时，会继承嵌套构造体的所有字段。

type NewVertex struct {  Vertex  Z int}var v1 NewVertexv1.X = 12v1.Z = 13fmt.Println(v1.X) // 12fmt.Println(v1)  // {{12 0} 13}

正因为构造体的上边的这些个性，加之Go语言中并没有类的概念，构造体在很多Web框架中，被当做“类”来应用。

总结

本篇咱们我学习了Go和Python的高级数据结构，他们底层都遵循了肯定的数据结构，但又都有本人的特色。汇合本人语言的个性，设计奇妙。总之，不论何种语言，咱们在应用时，既要理解构造的根本用法，还要理解其底层的逻辑构造，能力防止在应用时的一些莫名的坑。

我是DeanWu，一个致力成为真正SRE的人。

关注公众号「码农吴先生」, 可第一工夫获取最新文章。回复关键字「go」「python」获取我收集的学习材料，也可回复关键字「小二」，加我wx拉你进技术交换群，聊技术聊人生~