首页 / 知识

关于哈希：在c中生成唯一ID

2023-04-15 12:29:00

Generating a Unique ID in c++

从C中的两个(或更多)短整数生成唯一ID的最佳方法是什么？我试图唯一地标识图中的顶点。顶点包含2到4个短整数作为数据，理想情况下，ID是它们的某种哈希。相对于速度或易用性，更喜欢可移植性和独特性。

这里有很多很棒的答案，我今晚将尝试所有答案，以找出最适合我的问题的方法。关于我在做什么，再说几句话。

该图是来自音频文件的样本的集合。我将图形用作马尔可夫链，从旧文件生成新的音频文件。由于每个顶点都存储一些样本并指向另一个样本，并且这些样本都是短整数，因此从数据生成ID似乎很自然。将它们组合成很长的声音听起来不错，但是我只需要像0 1 2 3 generateID这样简单的东西即可。不知道要保证唯一性需要多少空间，如果每个顶点存储2个16位样本，那么2 ^ 32种可能的组合正确吗？因此，如果每个顶点存储4个样本，那么有2 ^ 64种可能的组合吗？

与库和平台相关的解决方案与该问题并不真正相关。我不希望其他可能编译我的程序的人不得不下载其他库或更改代码以适合他们的操作系统。

有时候最简单的方法效果最好。

能否仅将一个id字段添加到Vertex对象并按构造顺序为其分配一个数字？

1 2	static int sNextId = 0; int getNextId() { return ++sNextId; }

一个简单的解决方案是使用64位整数，其中低16位是第一个顶点坐标，后16位是第二个顶点坐标，依此类推。尽管不是非常紧凑，但它对于所有顶点都是唯一的。

所以这是一些半定的代码。希望我的演员表正确。

1
2
3
4
5
6

uint64_t generateId( uint16_t v1, uint16_t v2, uint16_t v3, uint16_t v4)
{
uint64_t id;
id = v1 | (((uint64_t)v2) << 16) | (((uint64_t)v3) << 32) | (((uint64_t)v4) << 48);
return id;
}

可选地，这可以通过工会来完成(Leon Timmermans的好主意，请参见评论)。这样很干净：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

struct vertex
{
uint16_t v1;
uint16_t v2;
uint16_t v3;
uint16_t v4;
};

union vertexWithId
{
vertex v;
uint64_t id;
};

int main()
{
vertexWithId vWithId;
// Setup your vertices
vWithId.v.v1 = 2;
vWithId.v.v2 = 5;

// Your id is automatically setup for you!
std::cout <<"Id is" << vWithId.id << std::endl;
return 0;
}

如果您要构建用于存储顶点的哈希表，我可以想到几种避免冲突的方法：

直接从输入数据生成ID，而不会丢掉任何位，并使用足够大的哈希表来容纳所有可能的ID。使用64位ID时，后者将非常成问题：您将不得不使用一个小于ID范围的表，因此必须处理冲突。即使使用32位ID，您也需要超过4GB的RAM才能顺利实现这一目标。

在顶点读取时，顺序生成ID。不幸的是，这使得搜索先前读取的顶点以更新其概率非常昂贵，因为顺序ID生成器不是哈希函数。如果用于构造马尔可夫链的数据量明显小于用于马尔可夫链生成的数据量(或者它们都很小)，那么这可能不是问题。

或者，您可以使用哈希表实现为您处理冲突(例如unordered_map / hash_map)，并专注于应用程序的其余部分。

如果在Windows上，则可以使用CoCreateGUID API，在Linux上，可以使用/ proc / sys / kernel / random / uuid，也可以查看" libuuid"。

问题中" ID"的定义尚不清楚：您是否需要将其用作快速查找顶点的键？您可以为std::map定义一个比较器(请参见下面的示例)

您是否需要能够区分两个具有相同坐标(但在另一个字段中不同)的顶点对象？定义一些生成例如一系列整数，与Vertex对象的值无关。 -Fire Lancer的建议方式很多(但请注意线程安全性问题！)

在我看来，两个具有相同坐标的顶点是相同的。那么，为什么还需要一个额外的ID？

一旦您为此类型定义了"严格弱排序"，就可以将其用作例如std::map，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

struct Vertex {
typedef short int Value;
Value v1, v2;

bool operator<( const Vertex& other ) const {
return v1 < other.v1 || ( v1 == other.v1 && v2 < other.v2 ) ;
};

Vertex x1 = { 1, 2 };
Vertex x2 = { 1, 3 };
Vertex y1 = { 1, 2 }; // too!

typedef std::set<Vertex> t_vertices;

t_vertices vertices;
vertices.insert( x1 );
vertices.insert( x2 );
vertices.insert( y1 ); // won't do a thing since { 1, 2 } is already in the set.

typedef std::map<Vertex, int> t_vertex_to_counter;
t_vertex_to_counter count;
count[ x1 ]++;
assert( count[x1] == 1 );
assert( count[y1] == 1 );
count[ x2 ]++;
count[ y1 ]++;
assert( count[x1] == 2 );
assert( count[y1] == 2 );

如果您更喜欢可移植性，那么boost :: tuple很不错：

您需要一个包含4个项目的元组：