Hash Based String Integer Bidirectional Mapping


功能:把一个字符串转成一个整数ID,根据一个整数ID找回字符串

#pragma once
#include<unordered_map>
#include<string>
#include<fstream>
#include<vector>
namespace ANNSearch {
	class StringArray
	{
		std::vector<char> charVector;
		std::vector<int> offsets;
	public:
		void Append(const char *str, size_t strLen);
		void Remove(size_t idx);
		__int64 Search(const char *str, size_t strLen);
		std::string At(size_t idx);
		void Save(std::ofstream& out);
		void Load(std::ifstream& in);
	};

	class StringIntBiMap {
	public:
		int BitOfBucket = 32;
		std::vector<StringArray> keyBuckets;
		std::vector <std::vector<__int64>> valueBuckets;
		int m_bucketCount;
		StringIntBiMap(int buckectCount = 50000011);
		uint64_t FNV64aHash(void *buf, size_t len);
		__int64 Add(std::string& key, bool &alreadyAdded);
		__int64 Delete(std::string& key);
		std::string Search(__int64 value);
		void Save(const std::string& filename);
		void Load(const std::string& filename);
	};
}

#include "StringIntBiMap.h"
namespace ANNSearch
{
	void StringArray::Append(const char *str, size_t strLen)
	{
		offsets.push_back(charVector.size());
		charVector.insert(charVector.end(), str, str + strLen);
		charVector.push_back('\0');
	}

	void StringArray::Remove(size_t idx)
	{
		int size = offsets.size();
		if (idx >= size)
		{
			return;
		}

		auto offset = offsets[idx];
		int ed = idx + 1 < size ? offsets[idx + 1] : charVector.size();
		charVector.erase(charVector.begin() + offset, charVector.begin() + ed);
		offsets.erase(offsets.begin() + idx);
		int length = ed - offset;
		for (int i = idx; i < size; i++)
		{
			offsets[i] -= length;
		}
	}

	__int64 StringArray::Search(const char *str, size_t strLen)
	{
		size_t size = offsets.size();
		for (size_t i = 0; i < size; i++)
		{
			if (strcmp(charVector.data() + offsets[i], str) == 0)
			{
				return i;
			}
		}

		return -1;
	}

	std::string StringArray::At(size_t idx)
	{
		if (idx >= offsets.size()) return "";
		return charVector.data() + offsets[idx];
	}

	void StringArray::Save(std::ofstream& out)
	{
		auto size = charVector.size();
		out.write((char *)&size, sizeof(size));
		out.write(charVector.data(), size * sizeof(char));
		size = offsets.size();
		out.write((char *)&size, sizeof(size));
		out.write((char *)offsets.data(), size * sizeof(int));
	}

	void StringArray::Load(std::ifstream& in)
	{
		size_t size = 0;
		in.read((char *)&size, sizeof(size));
		charVector.resize(size);
		in.read(charVector.data(), size * sizeof(char));
		in.read((char *)&size, sizeof(size));
		offsets.resize(size);
		in.read((char *)offsets.data(), size * sizeof(int));
	}
	

	StringIntBiMap::StringIntBiMap(int buckectCount)
		:m_bucketCount(buckectCount)
	{
		keyBuckets.resize(m_bucketCount);
		valueBuckets.resize(m_bucketCount);
	}

	uint64_t StringIntBiMap::FNV64aHash(void *buf, size_t len)
	{
		uint64_t hval = 0xcbf29ce484222325ULL;
		unsigned char *bp = (unsigned char *)buf;
		unsigned char *be = bp + len;
		while (bp < be) {
			hval ^= (uint64_t)*bp++;
			hval += (hval << 1) + (hval << 4) + (hval << 5) +
				(hval << 7) + (hval << 8) + (hval << 40);
		}

		return hval % m_bucketCount;
	}

	__int64 StringIntBiMap::Add(std::string& key, bool &alreadyAdded)
	{
		alreadyAdded = false;
		auto bucketId = FNV64aHash((void *)key.c_str(), key.length());
		auto keyBucket = keyBuckets.begin() + bucketId;
		auto valueBucket = valueBuckets.begin() + bucketId;

		auto IdInBucket = keyBucket->Search(key.c_str(), key.length());
		if (IdInBucket >= 0)
		{
			alreadyAdded = true;
			return (bucketId << BitOfBucket) + valueBucket->at(IdInBucket);
		}

		__int64 lowBitValue = 0;

		if (valueBucket->size() > 0)
		{
			lowBitValue = *(valueBucket->rbegin()) + 1;
		}

		valueBucket->push_back(lowBitValue);
		keyBucket->Append(key.c_str(), key.length());
		return (bucketId << BitOfBucket) + lowBitValue;
	}

	__int64 StringIntBiMap::Delete(std::string& key)
	{
		auto bucketId = FNV64aHash((void *)key.c_str(), key.length());
		auto keyBucket = keyBuckets.begin() + bucketId;
		auto valueBucket = valueBuckets.begin() + bucketId;
		auto IdInBucket = keyBucket->Search(key.c_str(), key.length());

		if (IdInBucket < 0)
		{
			return -1;
		}

		__int64 lowBitValue = valueBucket->at(IdInBucket);
		keyBucket->Remove(IdInBucket);
		valueBucket->erase(valueBucket->begin() + IdInBucket);
		return (bucketId << BitOfBucket) + lowBitValue;
	}

	std::string StringIntBiMap::Search(__int64 value)
	{
		__int64 bucketId = value >> BitOfBucket;
		__int64 lowBitValue = value & ((1LL << BitOfBucket) - 1);
		auto valueBucket = valueBuckets.begin() + bucketId;
		auto size = valueBucket->size();
		if (size > 16)
		{
			__int64 lef = 0;
			__int64 rig = size;
			_int64 mid = 0;
			while (lef < rig)
			{
				mid = (lef + rig) >> 1;
				__int64 cur = valueBucket->at(mid);
				if (cur == lowBitValue)
				{
					return std::move((keyBuckets.begin() + bucketId)->At(mid));
				}
				else if (cur > lowBitValue)
				{
					rig = mid;
				}
				else
				{
					lef = mid + 1;
				}
			}
		}
		else
		{
			for (int i = 0; i < size; i++)
			{
				if (valueBucket->at(i) == lowBitValue)
				{
					return std::move((keyBuckets.begin() + bucketId)->At(i));
				}
			}
		}

		return "";
	}

	void StringIntBiMap::Save(const std::string& filename)
	{
		std::ofstream out(filename, std::ios::out | std::ios::binary);
		out.write((char *)&BitOfBucket, sizeof(BitOfBucket));
		out.write((char *)&m_bucketCount, sizeof(m_bucketCount));
		for (int i = 0; i < m_bucketCount; i++)
		{
			keyBuckets[i].Save(out);
			auto size = valueBuckets[i].size();
			out.write((char *)&size, sizeof(size));
			out.write((char *)valueBuckets[i].data(), size * sizeof(__int64));
		}

		out.close();
	}

	void StringIntBiMap::Load(const std::string& filename)
	{
		std::ifstream in(filename, std::ios::in | std::ios::binary);
		in.read((char *)&BitOfBucket, sizeof(BitOfBucket));
		in.read((char *)&m_bucketCount, sizeof(m_bucketCount));
		keyBuckets.resize(m_bucketCount);
		valueBuckets.resize(m_bucketCount);
		for (int i = 0; i < m_bucketCount; i++)
		{
			keyBuckets[i].Load(in);
			size_t size = 0;
			in.read((char *)&size, sizeof(size));
			//LogAsset(size == keyBuckets[i].Size());
			valueBuckets[i].resize(size);
			in.read((char *)valueBuckets[i].data(), size * sizeof(__int64));
		}

		in.close();
	}
}


留言: