CMU 15445 第五讲 Hash Table

归属模块： Access Methods，一种我们用来对数据库数据进行读或写的方式。

之前讨论的page table和page directory就是一个hash table，传入pageid获得 frame 或对应磁盘上的位置。

关心的事：

• 数据结构是什么样的，我们需要知道该如何对我们存放再内存或磁盘中page上的这些元素进行表示。我们要高效方式做到，无须对数据结构进行大改或每次重新转换整个数据结构情况下进行快速读写。
• 如何让多个线程或多个查询去访问我们的数据结构。并且该数据结构表示的数据并不会再物理存储层面出现问题。

static hash table：预设key的具体数量，并且知道这些key对应的值。

Design Goal：

1. hash function：如何将一个任意的key映射到一个较小范围的integer值上；需要在fast和collision rate之间取舍
2. Hashing schema：当我们在hash table中碰见hash碰撞时，用来处理这种情况的机制或步骤。在一个大的hash table和additional instructions to find/insert keys中取舍。

Hash function：我们不想要一个cryptographic（密码学）hash函数，而是一个快速且碰撞率低的hash函数。

CRC-64 MurmurHash Google LityHash FaceBook xxHash Google FarmHash 我们在使用时，其实不关注如何实现

Static Hashing Schema：

#1 Linear Probe Hashing(open addressing):处理collision：紧挨着这条数据往下扫描，知道遇到下一个能插入数据的空slot（空位）为止。

• 一个hash table满了，要复制然后新建一个更大的hash table的话，代价非常大。
• 存在问题：删除一个已存在的值，可能导致要寻找直接因碰撞导致后移的值时直接在该删除出现的空位停止。
• 解决：#1 Tombstone，给出标志，该处没有值，但是不是代表一个空的slot，因此查找不会在此停止。这种会导致空间的浪费。#2 Movement 太过复杂

Non-unique Keys:

choice#1：Separate Linked List（一个key对应的所有值都存储在一个链表） choice#2：Redundant Keys（冗余key）：在hash table中不断复制重复的key

#2 Robin Hood Hashing:劫富济贫。

让"poor"key从"rich"key中偷取到slot。

Number of positions：表示所在位置与第一次进行hash所计算位置间的距离差。

操作：试着对整个Hash table进行平衡，试着让每个key尽可能靠近它原本的位置。即要插入一个元素，hash后发生碰撞，往后移动时不断和所移动到的位置key的Number of positions比较，如果当前要插入元素的该统计值较大，则插入到该位置，该位置上的原元素则后移一个位置放入（发生碰撞同理）。

实战中：Linear probing hahsing依旧碾压一切。

Dynamic Hashing：

#Cuckoo Hashing

无元素时，对一个key处理hash1(A), hash2（A)，给出不同的seed。随机选择一个hash table插入。插入B，依次处理两个hash（B），若hash1（B)已经被A占据，则选择hash2(B)。再插入C，如果hash1（C）已经被A占据，hash2（C）已经被B占据，则随机选择一个位置，删除原有元素，插入C。加入选择B，然后重新hashB，与A碰撞，删除A，然后再hashA，直到插入A。如果最后一个元素hash后发现来到了最初的位置（碰撞），或者唤醒hash可能会在一个循环中卡位，因此要区分出起点，当发现回到起点，则必须扩容。

#chained hashing

维护一个包含了buckets的链表（会导致查找退化为循序查找），将具有相同hash key的所有元素放入到相同的bucket。

#Extendible hashing

与其让链表不断增长，不如考虑拆分。拆分和重建的区别：我们只会将那些overflowed的chain进行拆分，而不是将整个数据结构进行拆分。

对overflowed bucket拆分后的结果来说，不允许该结果对应的hash table中，这几个slot位置指向的是同一个bucket chain。每一个bucket对应一个page。

IMG_20211006_114109_edit_211856451543713.jpg