0

我有一个数据结构，它是一个带有节点和边的无向图（可能是密集的）。节点 I 和 J 之间的边将具有与之关联的附加数据，我希望能够在查询时唯一标识该边，并能够快速确定 I 和 J 之间的边是否存在。

我决定使用两个表来完成此操作：

Table Nodes
-----------
node_id PK
...
(additional fields)


Table Edges
-----------
nodes_hash(node_id, node_id) PK
edge_thickness
...
(additional fields)

其中每条边的主键将由nodes_hash(node_id, node_id)采用两个节点 ID 的哈希函数计算。

我的问题：

  • 我如何想出一个好的散列函数来计算边缘 ID？
  • 我可能忽略了这种方法的任何主要缺点？
4

2 回答 2

2

没有理由需要将边编码为哈希：确保没有重复是唯一约束的简单问题。

虽然有计算散列的方法（创建路径枚举字符串，并计算其 MD5 散列或类似的东西），但存储散列并没有使用路径枚举方案来存储图形数据本身没有任何价值。路径枚举的工作方式与它在文件系统中的工作方式完全相同，存储类似/a/b/c（如果按节点 id 枚举）或1.2.1.5（如果按边序数枚举）之类的东西。

对于您的特定用例，我将使用常见的邻接表设置（除非树中的其他操作需要更专业的数据结构，例如节点集或路径/边缘枚举）。在此结构中，顶级节点具有PARENT_ID = NULL：

CREATE TABLE NODES(
  NODE_ID INT NOT NULL,
  -- OTHER NODE ATTRIBUTES
  PRIMARY KEY (NODE_ID)
);

CREATE TABLE EDGES(
  NODE_ID INT NOT NULL,
  PARENT_ID INT,
  EDGE_WEIGHT INT NOT NULL,
  -- OTHER EDGE ATTRIBUTES
  FOREIGN KEY (NODE_ID) REFERENCES NODES(NODE_ID), 
  FOREIGN KEY (PARENT_ID) REFERENCES NODES(NODE_ID),
  CHECK (PARENT_ID <> NODE_ID),                   -- This avoids simple cycles
  CONSTRAINT UNIQ_EDGE UNIQUE (NODE_ID,PARENT_ID) -- This avoids duplicate edges
);
于 2013-05-13T15:51:26.450 回答
0

为什么要使用散列函数来生成这样的密钥？

我将为节点提供一个整数主键（节点 ID）。

我将有一个用于边缘的整数主键（边缘 id）。

然后我将在每个节点的边缘表中有两列，外键关系返回到节点表。

我很容易想到使用散列函数的两个缺点。首先，您可能会发生碰撞。实际上，如果所有内容都存储为整数，那么仅根据鸽子洞原理就会发生碰撞。

其次，无论如何您都需要存储节点 ID。我能想到的几乎所有图形问题都需要知道由边连接的节点。

您将处理无向图是以下约束/触发器：

(1) 添加一个约束/触发器，即 node1 < node 2（或 <= 如果允许自连接）。

(2)在node1、node2上添加唯一索引。

(3) 添加一个插入前触发器，以确保对于任意值，node1 获得较小的值，node2 获得较大的值。

在 Oracle 中，您可以通过在最小（节点 1，节点 2）和最大（节点 1，节点）上使用基于函数的索引来组合这些。

于 2013-05-13T11:29:37.790 回答