持久哈希表：第2部分

• 下载 CHash - 1.39 KB
• 下载 CSharedMemory - 823 B
• 下载 testhash - 813 B

引言

作为第一篇文章的后续，我提高了性能，但仍然保持记录大小和桶大小不变。 我通过“泛化”、“函数对象”和“共享内存”来实现。

本文对谁有用…

对于那些不熟悉共享内存以及它如何提高性能的人来说，这将说明如何通过最小化文件 I/O 来提高性能。 对于那些不熟悉“函数对象”和模板的人来说，这也将非常有用。

这次是如何完成的…

我使用了一个简单的逻辑来构建持久哈希表。 如果我们定义了桶的数量、它们的大小和记录的大小，那么存储和检索就很容易了。 首先，创建一个文件，其存储空间足以存储所有带有记录的桶。 该文件被内存映射。 当我们想要写入或读取记录时，密钥被传递给哈希函数，该哈希函数是用户提供的函数对象，并且哈希值是桶偏移量。 然后我们需要跳转到内存映射文件的基本指针 + 偏移量并写入或读取记录。 在此之前，会检查该位置是否已存在记录。 如果存在，则跳转到下一条记录，然后写入该记录。 在读取和写入记录后，内存被刷新到磁盘文件。 稍后，如果我们需要读取，可以打开记录数据库，然后使用提供的密钥，可以检索回该记录。 在此实现中，对“fseek()”的依赖性被最小化到初始文件创建。 这是迈向大型文件操作的一步。 可以改进此实现以映射文件的某个部分而不是整个文件。

实现细节…

“CSharedMemory”类是共享内存 API 的一个薄包装器。 这是共享内存的简单使用，因此不深入探讨细节。 CHash 是一个通用类，用于构造不同类型的对象以创建不同的表。

namespace persistant_hash
{
	template<typename key_type,typename value_type,typename hash,typename size>
	class CHash
	{
	private:
		long m_nbuckets;
		long m_bucketsize;
		long m_recsize;
		CSharedMemory *m_psm;
		CRITICAL_SECTION cs;
		PBYTE m_pb;
		//unsigned long hash(long key);
		hash m_hashobj;
		size m_sizeobj;
		long writeoffset(long offset,void *p,long size);
		long readoffset(long offset,void *p,long size);
		long GetbucketOffset(long buckno);
		public:
                //pass how many number of buckets to construct.
                CHash(long nBuck,long nRecinbucket,
                hash ho,size so):m_nbuckets(nBuck),m_hashobj(ho),m_sizeobj(so) 
		{
			m_recsize = so();
			m_bucketsize = nRecinbucket * m_recsize;
			InitializeCriticalSection(&cs);
		}
		long createdb(wchar_t *p);
		long opendb(wchar_t *p);
		long closedb();
		long writerec(key_type k,value_type* pd);
		long readrec(key_type k,value_type* pd,long &offset);
		long readnextrec(long offset,value_type* pd);
			
	};
}

• key_type：是需要创建表的键的类型
• value_type：是要在键值存储中配对的值的类型。
• hash 是用户需要提供的函数对象类型，整个表都依赖于它
• size 是另一个函数对象类型，用户需要提供该类型来维护记录大小，以便稍后计算文件大小。

我在这里解释几个函数。 createdb 创建一个固定大小的文件，它打开共享内存并映射整个文件，并且基指针存储在 m_pb 中。

template<typename key_type,typename value_type,typename hash,typename size>
long CHash<key_type,value_type,hash,size>:: createdb(wchar_t *p)
{
	wstring name = p;
	name = name + L".hdb";
	long filesize = m_bucketsize * m_nbuckets;
	//create that much size file
	FILE *fp = NULL;
	_wfopen_s(&fp,name.c_str(),L"w");
	fseek(fp,filesize,0);
	fprintf(fp,"%d",7);
	fclose(fp);
	m_psm = new CSharedMemory();
	m_psm->createsm(name,&m_pb);
	return 0;
};

Writeoffset 将数据写入来自 basepointer 的 offset 位置：

template<typename key_type,typename value_type,typename hash,typename size>
long CHash<key_type,value_type,hash,size>::writeoffset(long offset,void *p,long size)
{
	EnterCriticalSection(&cs);
	memcpy((m_pb + offset),p,size);
	LeaveCriticalSection(&cs);
	return 0;
}

Writerec 在指定的 offset 处写入记录，如果已经存在一些记录，则它将写入下一条记录，在这里它调用函数对象来首先获取哈希值，然后再将其发送以获取桶 offset。

template<typename key_type,typename value_type,typename hash,
typename size>
long CHash<key_type,value_type,hash,size>::
writerec(key_type k,value_type *pd)
{
	long buckoffset = GetbucketOffset(m_hashobj(k));
    void *temp = malloc(m_recsize);
	while(0 != readoffset(buckoffset,temp,m_recsize))
	{
		buckoffset += m_recsize;//go to the next record
	}
	free(temp);
	writeoffset(buckoffset,pd,m_recsize);
	return 0;
}

如何使用此类…

需要包含这两个文件，并使用命名空间 persistant_hash

#include"CHash.h"
#include"CHash.cpp"
using namespace persistant_hash;

需要编写两个函数对象，这是自定义的地方，并包含您的高性能哈希函数。 :)

class myhash
{
public:
	long operator()(long key)
	{
		return (key % NUMBUCK);
	}
};

您的尺寸函数放在这里

class size
{
	public:
	long operator() ()
	{
		return sizeof(fixedrec);
	}
};

如何实例化…

myhash hashobj;
size sizeobj;
//total of 200 * 50 records can be stored
CHash<long,fixedrec,myhash,size> hash2(200,50,hashobj,sizeobj); 
hash2.createdb(L"second");

再见…

我希望这对一些初学者有所帮助。 我将继续添加此系列，直到它达到生产级别…