06-哈希表

[TOC]

6-哈希表

数据库引擎如何从页面读取写入数据

哈希表和树状结构是最常用的数据结构

0-哈希表应用

• Internal Meta Data：内部数据

• 核心数据：如redis的数据

• 临时数据结构：hash join

• 数据索引

设计哈希表的考虑：

• 哈希数据结构
• 并发问题：ConcurrentHashMap(JAVA)

1-什么是哈希表

一个Map，一段是Key，一段是Value

当Key过来时，会算Key的哈希值，然后存数据到对应位置

效率：

• 空间：$O(n)$
• 时间：$O(1)$一般，最差情况下$O(n)$

静态哈希表

一个数组，存下所有K-V，对key哈希之后取模

缺点：

2-

3-