持久哈希表

• 下载源代码 - 2.39 KB
• 下载二进制文件 - 5.74 KB

介绍 

我受到 NO SQL 的启发，想自己开始编写一个，我看到了一些非常好的开源 C++ NO SQL，比如 "MongoDB" 和 "levelDB"，并想自己编写一个键值存储。 我想从一套极简主义的目标开始，并在一个周末内完成。 因此，考虑到这些参数，我发布了这篇文章。 我希望它对那些想作为初学者开发键值存储的人有所帮助。 

背景

创建表和访问表的方法有很多种，每种方法都有其自身的优点和缺点。 在这里，我使用哈希函数来访问文件中的记录。 其他方法包括维护索引表、顺序访问、b+树、持久指针等。

Using the Code

我使用一个简单的逻辑来构建持久哈希表。 如果我们定义了桶的数量、它们的大小和记录大小，那么存储和检索就很容易了。 当我们要写入或读取记录时，key 被传递给哈希函数，通过哈希值，推导出桶的偏移量。 然后我们需要跳到那个偏移量并写入记录或读取记录。 在这样做之前，会检查该位置是否已经存在记录，如果存在，则跳到下一条记录，然后写入该记录。

• CHash(long nBuck,long bucksize,long recsize): 是一个重载的构造函数，我们在这里传递桶的数量、桶的大小和每条记录的大小（表的大小）。 对于此表，key 应该是 long 类型。
• CHash(long nBuck,long bucksize,long recsize,unsigned long (*uh)(void *)): 是另一个构造函数，可以在这里传递用户定义的哈希函数指针。 key 可以是用户定义的类型。
• createdb: 创建具有给定名称的 hdb 文件，可以进行写入和读取。
• writedb: 打开文件进行写入
• readdb: 打开文件进行读取
• closedb: 关闭文件句柄
• writerec: 写记录有两个重载，一个用于 key 类型 long，另一个用于用户定义的 key 类型，写入用户定义的数据，如果记录存在（即发生冲突），则将数据写入桶中，然后跳到下一条记录，直到找到一个空闲位置进行写入。
• readrec: readrec  有两个重载，一个用于 key 类型 long，另一个用于用户定义的 key 类型，读取用户定义的数据。 从桶的偏移量读取记录，如果搜索的值不同，则使用 readnextrec 获取来自先前 readrec 调用的偏移量的下一条记录。
• readnextrec: 如上所述，这需要用于通过传递来自 readrec 的偏移量来读取同一桶中的连续元素。
• writeoffset,readoffset,GetbucketOffset 是用于在文件中移动以进行写入和读取的辅助函数。

int CHash::GetbucketOffset(long buckno)//returns the bucket offset
{
   int offset = 1;
   offset = buckno * m_bucketsize;
   return offset;
}

int CHash::writerec(void* key,void *data)
{
	long buckno = GetbucketOffset(hash(key));
    void *temp = malloc(m_recsize);
	while(0 != readoffset(buckno,temp,m_recsize))
	{
		buckno += m_recsize;//go to the next record
	}
	free(temp);
	writeoffset(buckno,data,m_recsize);
	return 0;
}

int CHash::writerec(void* key,void *data)
{
	long buckno = GetbucketOffset(hash(key));
    void *temp = malloc(m_recsize);
	while(0 != readoffset(buckno,temp,m_recsize))
	{
		buckno += m_recsize;//go to the next record
	}
	free(temp);
	writeoffset(buckno,data,m_recsize);
	return 0;
}

int CHash::readrec(long key,void *data,long &offset)
{
	long buckno = GetbucketOffset(hash(key));
	readoffset(buckno,data,m_recsize);
	offset = buckno;
	return 0;
}

int CHash::readrec(void* key,void *data,long &offset)
{
	long buckno = GetbucketOffset(hash(key));
	readoffset(buckno,data,m_recsize);
	offset = buckno;
	return 0;
}

int CHash::readnextrec(long offset,void *data)
{
	offset += m_recsize;
	readoffset(offset,data,m_recsize);
	return 0;
}

Testhash.cpp 编写用于演示如何使用此类。

限制

也许在我的下一篇文章中，我可以改进对桶和表的大小进行预定义。 相反，我将使用其他类构建这些表或使用其他技术。 我发现的另一个限制是，如果未给桶分配足够的空间，则可能会发生数据损坏。 所有这些都归因于固定大小。