数据库 JavaSE editor android教程 ip 八大员 nodejs教程视频 jquery的each循环 jquery第一个子元素 matlab读取dat文件 mser算法 pcm接口 maven插件 python正则 二分查找python python搭建环境 python正则表达 python匹配字符串 java基础 javapackage java案例 filejava java在线课程 学java基础 狮子狗出装 魔兽地图七个人 js倒计时 adobe卸载工具 草图大师版本转换器 oracle表分区 什么是人肉搜索 winhex中文版下载 中文微信小程序API 女圣骑 苹果8怎么截屏 安卓人脸识别 樱桃b站怎么发动态 ps反光效果 python进程池 xshow
当前位置: 首页 > 学习教程  > 编程语言

字符串哈希表

2020/10/8 18:33:59 文章标签:

在处理电脑中文件名的存储问题时,为了节约存储空间,需要完成字符串的去重操作,前提得实现字符串的快速查找,之前的做法是采用平衡二叉树存储,但是操作比较复杂,而且树结点中指针及其他额外的变量占用了较多…

在处理电脑中文件名的存储问题时,为了节约存储空间,需要完成字符串的去重操作,前提得实现字符串的快速查找,之前的做法是采用平衡二叉树存储,但是操作比较复杂,而且树结点中指针及其他额外的变量占用了较多的空间,在网上查了许多字符串哈希算法,最后选了个最简单性能较好的BKDR哈希算法,使用哈希链表处理冲突,这种操作很简单,效率也比之前的平衡二叉树要高,但是这种方法失去了字符串的顺序性,虽然这种顺序性目前没有被利用,但是以后对字符串进行压缩时可能会利用这种顺序。

目前的哈希表长是固定的还在试验,装填因子维持在0.65左右,冲突链最长没超过10。

// strHash.h

#pragma once

#include <string.h>
#include <stdlib.h>

typedef struct STR_NODE {
	struct STR_NODE* next;
	unsigned char nodeCite;  /* 结点引用数超过255后设置此结点不能删除 */
	unsigned char strLength; /* 字符串长度大于255时设置此长度变量不可用 */
	unsigned char tag;
	char str[1];

	static const unsigned char TAG_CANNOTERASE     = 0B00000001; /* 结点不可被删除 */
	static const unsigned char TAG_CANNOTUSELENGTH = 0B00000010; /* 长度变量不可用 */
	static const unsigned char TAG_CONTAINNOANSI   = 0B00000100; /* 含非ANSI字符 */
	static const unsigned char TAG_CHECKED         = 0B00001000; /* 此结点已被查询过 */
	static const unsigned char TAG_CHECKEDANDOK    = 0B00010000; /* 此结点已被查询过且符合要求 */

	/* 应调用此函数获取准确的字符串长度 */
	size_t _strLength() { return tag & TAG_CANNOTUSELENGTH ? strlen(str) : strLength; }

	/* 新建结点 */
	static STR_NODE* newNode(const char* str, size_t strLength, unsigned char tag)
	{
		PSTR_NODE newNode = (PSTR_NODE)malloc(sizeof(STR_NODE) + strLength);
		if (!newNode) exit(1);

		newNode->next = NULL;
		newNode->nodeCite = 1;
		newNode->strLength = strLength;
		newNode->tag = tag;

		memcpy(newNode->str, str, strLength);
		newNode->str[strLength] = 0;
		return newNode;
	}
}STR_NODE, *PSTR_NODE;

/* 哈希表头结点 */
typedef struct {
	PSTR_NODE first;
}STR_HASH_TABLE_HEAD_NODE;

class StrHashTable {
public:
	StrHashTable(size_t size);
	~StrHashTable();

	PSTR_NODE insert(const char* str, size_t strLength, unsigned char tag);
	void erase(const char* str);

private:
	static const size_t DEFAULT_SIZE_BIG = 218357; /* 默认主文件名哈希表长 */
	static const size_t DEFAULT_SIZE_SMALL = 1627; /* 默认后缀名哈希表长 */

	size_t size;
	STR_HASH_TABLE_HEAD_NODE* table;

	size_t BKDRHash(const char* str);
	PSTR_NODE deleteNode(PSTR_NODE& node); /* 返回删除操作后待删除结点前驱的新后继 */
};
// strHash.cpp

#include "strHash.h"

#include <iostream>

StrHashTable::StrHashTable(size_t size)
{
	this->size = size;
	table = (STR_HASH_TABLE_HEAD_NODE*)malloc((size + 1) * sizeof(STR_HASH_TABLE_HEAD_NODE));
	if (!table) exit(1);

	for (size_t i = 0; i <= size; ++i) table[i].first = NULL;
}

StrHashTable::~StrHashTable()
{
	if (table) {
		for (size_t i = 0; i < size; ++i) {
			PSTR_NODE p = table[i].first;
			PSTR_NODE temp = NULL;
			while (p) {
				temp = p;
				p = p->next;
				free(temp);
				temp = NULL;
			}
		}
		free(table);
		table = NULL;
	}
}

PSTR_NODE StrHashTable::insert(const char* str, size_t strLength, unsigned char tag)
{
	if (!str) return NULL;

	size_t addr = BKDRHash(str) % size;
	PSTR_NODE p = table[addr].first;
	while (p) {
		if (strcmp(str, p->str) == 0) break;
		p = p->next;
	}

	if (p) {
		if (p->tag & STR_NODE::TAG_CANNOTERASE);
		else if (p->nodeCite == 255) p->tag |= STR_NODE::TAG_CANNOTERASE;
		else p->nodeCite++;
	}
	else {
		p = STR_NODE::newNode(str, strLength, tag);
		p->next = table[addr].first;
		table[addr].first = p;
	}
	return p;
}

void StrHashTable::erase(const char* str)
{
	if (!str) return;

	/* 找到结点 */
	size_t addr = BKDRHash(str) % size;
	PSTR_NODE p = table[addr].first;
	while (p) {
		if (strcmp(str, p->str) == 0) break;
		p = p->next;
	}
	if (!p) return;

	/* 是头结点 */
	if (table[addr].first == p) table[addr].first = deleteNode(p);

	/* 是中间结点 */
	else {
		PSTR_NODE pre = table[addr].first;
		while (pre->next != p) pre = pre->next;
		pre->next = deleteNode(p);
	}
}

size_t StrHashTable::BKDRHash(const char* str)
{
	register size_t key = 0;
	size_t c = 0;
	while (c = (size_t)*str++) key = key * 131 + c;
	return key;
}

PSTR_NODE StrHashTable::deleteNode(PSTR_NODE& node)
{
	if (node->tag & STR_NODE::TAG_CANNOTERASE) return node; /* 不可删除 */

	node->nodeCite--;
	if (node->nodeCite == 0) {
		PSTR_NODE retNode = node->next;
		free(node);
		node = NULL;
		return retNode;
	}
	return node;
}


本文链接: http://www.dtmao.cc/news_show_250065.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?