// 先声明map
你所需要的网站建设服务，我们均能行业靠前的水平为你提供.标准是产品质量的保证，主要从事做网站、成都网站建设、企业网站建设、手机网站制作、网页设计、品牌网站设计、网页制作、做网站、建网站。创新互联拥有实力坚强的技术研发团队及素养的视觉设计专才。
var m1 map[string]string
// 再使用make函数创建一个非nil的map，nil map不能赋值
m1 = make(map[string]string)
// 最后给已声明的map赋值
m1["a"] = "aa"
m1["b"] = "bb"
// 直接创建
m2 := make(map[string]string)
// 然后赋值
m2["a"] = "aa"
m2["b"] = "bb"
// 初始化 + 赋值一体化
m3 := map[string]string{
"a": "aa",
"b": "bb",
}
望采纳。。
// ==========================================
// 查找键值是否存在
if v, ok := m1["a"]; ok {
fmt.Println(v)
} else {
fmt.Println("Key Not Found")
}
// 遍历map
for k, v := range m1 {
fmt.Println(k, v)
}
map 是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？
总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。
golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表)，高位用于放在bmap的[8]uint8数组中，用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。
Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫 hmap (a header for a go map)，一个叫 bmap (a bucket for a Go map，通常叫其bucket)。这两种结构的样子分别如下所示：
hmap :
图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段： buckets数组 。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢？
bucket ：
相比于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：
由此看出hmap和bucket的关系是这样的：
而bucket又是一个链表，所以，整体的结构应该是这样的：
哈希表的特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思。
Golang把求得的值按照用途一分为二：高位和低位。
如图所示，蓝色为高位，红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。 需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:
并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费 。
现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)
map的扩容
当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。
加载因子
判断扩充的条件，就是哈希表中的加载因子(即loadFactor)。
加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。
每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容。
Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。
当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。
如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组
上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘黄色代表空的bucket。
扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：
注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。
map中数据的删除
如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。
值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：
1
2
3
4
1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；
2、如果是值类型的，则清除相关内存。
3、同理，对``value``做相同的操作。
4、最后把key对应的高位值对应的数组index置为空。
最近在刷MIT 6.851，记录下笔记。
可持久化数据结构就是能存储、查询数据的历史版本的数据结构。
可持久化数据结构简介
MIT 6.854j-advanced-algorithms
很赞！！可惜没video。
Making Data Structures Persistent
太长没看
总结了下大致包括如下领域应用：
并发事务的原子性（便于Rollback）、隔离性。
同上。
便于实现diff,rollback
可持久化数据结构最初设计出来的目的是为了在高维查询中降维，把其中一个维度当做时间，用可持久化数据结构处理效率更高
可以看下MIT 6.851老师的介绍。
这种思想在高维处理中很常见，比如求二维range sum query时候，把其中一个维度当时间、拿来做扫描线也是这种降维思路（见《算法竞赛进阶指南》）：
可持久化数据结构简介
自己轮一个.net可持久化库 Persistent Data Structures 下面有讨论use case
中文翻译见 可持久化数据结构
Functional Go: 持久化数据结构简介
这部分可以看6.851视频
6.851把链式数据结构的模型叫pointer machine model。对于基于pointer machine model的数据结构，有没有通用的方法将他们改造成persistent？
note see
video see
O(1)写，读时对于每个点都要执行O(logm)的查询。假设一次查询要读v个点，时间复杂度O(vlogm)
所以对写友好，对读不友好
看到这里有个问题：每个点的history放hashmap里不就行了？读时也只需要O(1)的查找
但这样做的话，hashmap不支持ceil操作，因此要支持ceil没办法只能用有序结构、log级别查询
（这里的假设是有个全局时间戳，而不是每个key对应一个自己的自增时间戳）
个人理解，想做可持久化key/value Map的话即可按这种方法，每个key对应的entry存放所有历史值，这也可以看成是邻接表。
说白了就是写时分裂节点，从root开始分裂到要写的点。将所有version的root存到字典里
上面两个要么对写不好，要么对读不好，能否兼得？
难以置信，说白了就是给path copying方法中每个node加一个log cache，最后算出来的写时amortized time complexity就是O(1)了。
What about non-tree data structures？
平衡树怎么处理？
平衡树要旋转，想想就感觉很难改造成持久化。6.854课件讲的很粗没懂。 算法竞赛中常用的可持久化平衡树一般就是 可持久化无旋转 Treap ，省去了旋转可持久化的复杂。
a. fat nodes
每个点存的log从version queue变成version tree,查询每个点时要从树中找到最近祖先
b. path copying
没区别
c. modification box
怎么找根节点？
i. pointer per version，可能多个pointer指向一个root
ii.存root tree,查询时先找最近祖先
怎么修改old version
i. 修改时放box,满了就分裂出来一个新节点
但这样有问题：分裂出来的还是满的，如果整条链都是满的，每次修改复制全部，下次修改还得复制全部。而且这样还不好存root，比如最右边图，代表0的root有俩
ii. 修改时放box,满了就分裂出来一个新节点，但分裂时自动apply有用的log、丢弃没用的log
What about non-tree data structures？
6.851有讲，分裂成两个节点，log分成两部分，新节点拿一个子树的log，新节点apply log直到自己的子树，每部分丢弃自己用不到的。
6.851讲了 太复杂没听懂。
网上关于可持久化数据结构的优质资料都是算法竞赛的，因此收集总结了下竞赛常用的。看了下基本都是partial persistent,有的是fully persistent,都没用到modification box技术。
和可持久化线段树类似的方法，基于path copy实现partial persistence。
问题是每个点在拷贝时都要复制O(R)个指针，插入的时间复杂度为O(len*R)
查询时先从字典（数组/哈希表）里找到指定version的root，然后访问，O(len)
在竞赛中常用的是可持久化01字典树，比如xor问题，见 ，没看懂
算法竞赛中常用的可持久化平衡树一般就是 可持久化无旋转 Treap ，省去了旋转可持久化的复杂。
【AgOHの数据结构】可持久化数组
方案：
a. fat nodes
每个节点放所有历史，查询时在所有历史版本中找最近祖先版本
b. path copying
存到可持久化线段树里。
为什么好好的线性结构要树化？直觉上理解，是为了分裂新版本时减少指针复制。
如果是稀疏数组，朴素方法太浪费空间了，可以基于动态开点来优化空间存储，见
【AgOHの数据结构】可持久化并查集
并查集基于数组，可持久化并查集就基于可持久化数组。可持久化数组用可持久化线段树实现，因此可持久化并查集用可持久化线段树实现
《 可持久化数据结构研究 》
不过文中写的太简略了，个人推测的维护方法为：
讨论支持如下操作的抽象数据结构(ADT)如何可持久化：
a. 基于普通数组
只能copy on write
b. 基于可持久化数组/可持久化线段树
问题是怎么处理新增节点、删除节点？得想办法魔改线段树
c. 可持久化链表
d. 可持久化块状链表
e. 可持久化平衡树
f. 文中提到的vector trie
名字挺骚的没反应过来，看了一会发现：这玩意就是可持久化数组（可持久化线段树），只不过是多叉树，叫“可持久化多叉线段树”比较形象。文章也没提怎么处理新增节点、删除节点。
persistent-hash-table-implementation
a. 可持久化平衡树
b. 还用hashmap，但是每个entry改造成fat node（存放所有log)，查询时先找到entry，再在所有log 中找最近祖先版本
c. 可持久化数组。
考虑到HashMap本来就能只用一个数组实现（解决冲突时用open addressing方法，不用Chaining），那么实现了可持久化数组就相当于实现了可持久化HashMap
d. Hash_trie
hash(key)的值存在trie里,value放到trie的叶子节点。优化版本包括 Hash array mapped tries and Ctries
HAMT这名字起的很奇怪。原理就是块状hash trie（所谓块状是我自己起的名，指每个节点区分儿子时不是单纯的比较某1位，而是比较某2位甚至多位）（或者理解成hash trie+动态开点多叉线段树也行）（反正就是bitwise hash trie加上一堆优化，懒得记就记hash trie就行了，真要自己实现的时候这些优化trick也能想到）
文中讲hamt的碰撞处理有点扯，个人理解可以chaining，可以open addressing。细节没深究，可以看 论文 和 讨论 。按作者的意思AMT是之前他提出的一种Trie的优化，比Tenary search trie要好。
// TOOD
Planar Point Location问题见
朴素的方法是线段树套线段树，以便支持二维RMQ，时间复杂度O(logN*logN）。
个人理解，最优的二维RMQ数据结构应该是用modification box实现的可持久化值域线段树，O(N)的构造时间、空间，O(logN)的查询。
如果统计操作具有“区间可加性”、“区间可减性”，那么该操作二维统计问题可以使用可持久化线段树。
range minimum query中的min()操作其实不具有区间可减性，但是range minimum query问题可以归约成range select query问题，进而可以归约成range count query问题，而count()操作具有区间可加减性，因此也能用可持久化线段树。
所以我们得到了一类二维统计问题的通用数据结构：对于可归约成具有“区间可加性”、“区间可减性”统计操作的二维统计问题，可以使用可持久化线段树存储，以便支持快速查询（统计）。
能否找到一类高维统计问题，具有通用的logN级别解？个人理解可以借鉴代数的思想，只要有区间可加减性的都能归约成K维RMQ问题，用modification box实现的可持久化值域线段树解决。
// TOOD 只是个人畅想，没细想。
bigtable(hbase)可以看成外存模型下的可持久化map：
但需要注意的是删除操作会真的删掉之前的老版本数据：
其实任何支持前缀匹配的db都能作为可持久化map，你只需要把rowkey设计成"key@@timestamp"即可
