cmu 15445 5: hash table

2021-02-11

intro

前面我们已经写完了buffer pool, 现在我们在一个数据库系统中的第三部分acess methods 这一部分支持了DBMS执行引擎对page上的数据的读写;

哈希表

哈希表就是一个无序关联数组能够把key map到values;

底层是一个关联数组, 使用hash函数来计算key在关联数组中的偏移量(下标)

静态哈希表

提前分配了一个能够存放所有元素的巨大的数组, 查找时直接取mod长度就行;

hash 函数

目标:

对于一个key, 返回一个integer代表这个key
不想用密码学的hash function
想要找到一些速度快, 冲突率低;

不同hash函数的benchmark, 在给的代码的中找到了murmur.

hash schema

先放一下吧… 和proj无关.

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true