关于数组表示树，以及并查集索引的疑惑。
来源：3-7 更多和并查集相关的话题
数据结构呆瓜
2024-01-14 23:04:19
老师好，
问题1 元素与索引对应关系的理解。
用数组表示树，以及并查集的时候，关于元素索引部分，感觉好像两者都用到了哈希表的思想。但不知我理解是否有误。
哈希表，是把目标转化成数组索引，用数组索引表示目标的数组。这一步骤通常有一个哈希公式，比如常用编程手法——字母减‘a’, 我们相减结果0 , 1代表字母a, b。这种把目标转化为索引的函数就是hash函数。
但在堆中，0默认为root根。任意节点为i，其左节点等于 2 * i + 1，右节点等于2 * i + 2。这也是某种程度上的hash函数。
而老师举例的并查集，直接把索引值天然对应元素值，是一个没有任何处理的hash函数。同时定义：本节点大小等于父节点的就是根节点。每个索引对应的元素，就是该节点的父节点。
问题2: 使用并查集，目标能否使用其它类型？如果不是int类型，是否还需要用hash函数把目标转化成索引，再进行并查集操作设计？
问题3：初始化，最初元素互不指向，如果元素过多，是否会出现内存不足问题？
判断ABC是否在一个关系网。假设社交软件上，有A,B,C,D。 A添加B，B添加C，那么我们可以把ABC归为一个关系网。D单独一个关系网。如果D添加了A,B,C任意一个，那么D也和ABC在一个关系网。
但最开始创建账号的时候，大家互没添加好友，有N元素，意味着初始N个根节点，即N个关系网。假设有千万账户，意味着最开始有千万根节点，需要开辟千万级大小数组，会不会太过占用空间？
翻译
搜索
复制
1回答
-
问题1：
可以把索引理解成是一个哈希函数。
但要注意，这是一种特殊的哈希函数，因为这个哈希函数是没有哈希冲突的。处理哈希冲突是哈希表这种数据结构的关键。但是在这里，我们不需要处理哈希冲突。
问题2：
并查集不支持其他类型，只能使用 int。如果你想要操作其他类型，如你所说，你需要一个哈希函数，把你想要操作的类型转换成索引。实际上这种操作在我们的生活中也很常见。比如我们定义了学号，就是把一个一个具体的人转换成了 int。比如我们在操作系统中，每个进程都有一个进程 id，也是把一个一个进程信息改写成了 int。
依然是注意，这里我虽然说哈希函数，但是其实是没有哈希冲突的。我局的例子也是如此，不会有两个学生同时拥有同样的学号，也不会有两个进程同时拥有同样的 id。
问题3：
不仅仅是并查集，对于所有的数据结构，当数据规模提升以后，都会导致内存不足。虽然对于某些场景，某些数据结构可能会比另一些数据结构节省更多空间，但没有任何数据结构可以让当今的大数据时代的所有数据都存在内存里。所以我们有数据库（利用外存），分布式数据库（横向 scaling）等方式来解决这一问题。顺带一提的，对这些问题的解决是近现代非常非常重要的计算机科学的方向，所谓的云计算的核心之一，也是基础之一，就是这类问题的解决。
继续加油！：）
0
相似问题