Sy Blog

Thinking will not overcome fear but action will.

A Write-friendly Hashing Scheme for Non-volatile Memory Systems

MSST’2017 Path Hash

这一篇论文提出了一种新型的解决哈希冲突的方案，全文8页，现在已存的Hash方案容易造成级联写，对于寿命有限的PCM并且写延迟高的PCM来说不太友好。这里主要讲一下大致的结构，以及增删改查操作。 1.The Design Of Path Hashing 1.1Position Sharing 这里可以看出对于一个X，Hash到2的位置，那么下面的从这个叶节点到根节点的路径上的...

Posted by HustDsy on October 14, 2020

12.动态内存

C++

12.动态内存 主要从动态内存与智能指针，动态数组这两个方面来进行学习 12.1 动态内存与智能指针 在C++中,动态内存的管理是通过一对运算符来完成的:new,在动态内存中为对象 分配空间并返回一个指向该对象的指针,我们可以选择对对象进行初始化:delete,接受一个动态对象的指针,销毁该对象,并释放与之关联的内存。 然而动态内存的管理方式很容易造成内存泄漏等问题，因为确保...

Posted by HustDsy on October 8, 2020

Revisiting Hash Table Design for Phase Change Memory

PFHT

Revisiting Hash Table Design for Phase Change Memory PFHT(PCM Friendly Hash Table),它考虑了PCM的一些特定的属性，与现有的基于DRAM设计的Hash相比，它在性能，写次数和负载系数方面提供了很好的权衡。 1.背景 PCM具有写寿命有限以及读写不均衡的两大特点，因此限制写次数很有必要。 $...

Posted by HustDsy on October 7, 2020

11.关联容器

C++

关联容器和顺序容器有着根本的不同:关联容器中的元素是按关键字来保存和访问的。与之相对,顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。 关联容器的主要包括$map$和$set$两大类，标准库提供8个关联容器。这8个关联容器间的不同主要体现在以下三个维度 或者是一个$set$或者是一个$map$ 或者要求不重复的关键字，或者允许重复的关键字 按顺序保存元素 ...

Posted by HustDsy on October 5, 2020

Cuckoo Filter:Practically Better Than Bloom

布谷鸟过滤器

这篇论文提出了一个新的过滤器-布谷鸟过滤器，相对于布隆过滤器来说达到相同的假阳性率(小于$3\%$)，Cuckoo Filter的容量利用率以及失败查找次数等属性都更加优越。这篇博客主要记录一下Cuckoo的一些特性，以及简单的公式推导。 1.Cuckoo Hash $Cuckoo\ Hash$有两个$Hash$函数，对于一个$Item$我们可以计算出两个位置$a,b$，我们随机...

Posted by HustDsy on September 29, 2020

布隆过滤器

Hash

最近在看Hash有关的文章，打算从头开始看，那就从最简单的部分开始了解吧。参考博客布隆过滤器 Hash函数 $Hash$函数的作用主要是将一个大的数据集映射到小的数据集上，这些小的数据集称作为哈希值或者散列值。$Hash\ Table$(哈希表，散列表)是根据哈希值进行访问的数据结构，也就是说我们通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。下面是一个典型的$Has...

Posted by HustDsy on September 24, 2020

9.虚拟内存

Vitrual Memory

虚拟内存提供了三个重要的能力: 1)它将主存看成是一个存储在磁盘上的地址空间的高速缓存,在主存中只保存活动区域,并根据需要在磁盘和主存之间来回传送数据,通过这种方式,它高效地使用了主存。2)它为每个进程提供了一致的地址空间,从而简化了内存管理。3)它保护了每个进程的地址空间不被其他进程破坏。 9.1物理和虚拟寻址 计算机系统的主存被组织成一个由$M$个连续的字节大小的单元组成的数...

Posted by HustDsy on September 23, 2020

HMEH:write-optimal extendible hashing for hybrid DRAM-NVM memory

Hash索引

这是一篇学姐发的和Hash索引有关的论文，要好好看的啊！主要将关键部分，比如设计和一致性保证这两个问题。 HMEH Design And implementation HMEH的架构如下 A.Two Structures of Directory 由于目录查找比较耗时，作者使用DRAM存储目录，由于DRAM中的数据掉电会丢失，为了恢复，采用一个$Radix-tree$来进行恢...

Posted by HustDsy on September 16, 2020

马拉车算法

一种求回文串的方法

一个求回文数或者回文子串的算法。 1975年，一个叫Manacher发明了Manacher Algorithm算法，俗称马拉车算法，其时间复杂为O(n)。该算法是利用回文串的特性来避免重复计算的，至于如何利用，这篇博客自己阐述一下自己的理解。 首先对于字符串$S$,为了方便处理，我们将$S$的首尾和中间都加上#号，比如$S=”abba”$，我们将其转换为S=#...

Posted by HustDsy on September 15, 2020

静态哈希和动态哈希的区别

Hash

这一篇主要讲困惑了自己很久的静态哈希和动态哈希的区别！！！！！！！ 文中哈希函数计算出来的结果称为地址，也就是$hash(key)$ 静态哈希和动态哈希的区别 ​ 这里直接给出答案，静态哈希和动态哈希区别并不是容量大小可不可以动态大小的调整，这个只是它们区别带来的结果，不能算根本意义上的区别。根本上的区别是静态哈希的哈希函数所计算出来的索引值永远是在固定的区间内。这就导致静态哈希...

Posted by HustDsy on September 14, 2020

FEATURED TAGS
树索引 C++ Primer idea Optane Performance CSAPP 算法 排序 Hash索引 过滤器 PMDK Git
ABOUT ME

我自是年少，韶华倾负！

✉️ 379644660@qq.com

FRIENDS