[译]C语言实现一个简易的Hash table(1)

徐建岗网络管理 2019-06-30

[译]C语言实现一个简易的Hash table(1)

说明

Hash table翻译过来就是Hash表,是一种提供了类似于关联数组的数据结构,可以通过key执行搜索、插入和删除操作。Hash表由一些列桶(buckets)组成,而每一个bucket都是由key-value的形式组成。存储时都是以key-value存储的,因为当要定位一个value时,需要把key传给一个散列函数(hash函数),这个函数返回一个数(索引),代表查找的value位于哪一个bucket中。同理,当我们要从所有的buckets中取回key-value时,一样是先把key传给散列函数,再由返回的索引取到value

在数组中,通过下标(索引)获取值时,复杂度为O(1),所以Hash表上查找和存储数据会很快。

我们这个简易的Hash表会使用字符串作为keyvalue,这种方法也适用于任意其他类型的keyvalue。本教程只支持ASCII中的字符串,unicode 类型比较复杂已经超出了本教程的范围。

本教程中的Hash表支持的API

本教程中,关联数组是一个未排序过的key-value集合,不允许重复的key,支持一下操作:

  • search(a, k): 如果关联数组a中存在k对应的v,就返回v,不存在就返回NULL
  • insert(a, k, v): 向关联数组a中插入k-v
  • delete(a, k): 根据k删除一条记录,如果k不存在则什么也不做

本教程代码目录结构

本教程中所有的代码都会按如下目录结构存放:

.
├── build
└── src
    ├── hash_table.c
    ├── hash_table.h
    ├── prime.c
    └── prime.h

src 目录存放我们的源代码,build 目录存放编译过的二进制文件。

教程中的一些名词解释

本文中所涉及到的一些名词解释:

  • 关联数组:实现了上面的API的一种抽象数据结构,也称映射(Map)符号表(symbol table)字典(dictionary)
  • Hash表:使用了散列函数实现关联数组的一种数据结构,也称为哈希映射,映射,哈希或字典

关联数组可以用许多不同的底层数据结构实现。可以通过简单地将值存储在数组中并在搜索时迭代数组来实现(非高性能的)。关联数组和散列表经常被混淆,因为关联数组经常被实现为散列表。

下一章:hash表结构


相关推荐