C - 如何实现 Set 数据结构? [英] C - How to implement Set data structure?

问题描述

在 C 中实现集合数据结构(唯一值的集合)有什么棘手的方法吗?集合中的所有元素都是相同的类型，并且有一个巨大的 RAM 内存.

Is there any tricky way to implement a set data structure (a collection of unique values) in C? All elements in a set will be of the same type and there is a huge RAM memory.

据我所知，对于整数，使用值索引数组可以非常快速地完成.但我想要一个非常通用的 Set 数据类型.如果一个集合可以包含它自己就好了.

As I know, for integers it can be done really fast'N'easy using value-indexed arrays. But I'd like to have a very general Set data type. And it would be nice if a set could include itself.

推荐答案

有多种实现方式设置(和映射)功能，例如:

There are multiple ways of implementing set (and map) functionality, for example:

• 基于树的方法(有序遍历)
• 基于哈希的方法(无序遍历)

既然你提到了值索引数组，让我们试试基于哈希的方法，它自然构建在值索引数组技术之上.

Since you mentioned value-indexed arrays, let's try the hash-based approach which builds naturally on top of the value-indexed array technique.

注意基于哈希与树的优缺点基于方法.

您可以设计一个哈希集(哈希表的一个特例) 指向 hashable POD 的指针，带有 链接，在内部表示为一个固定大小的哈希表桶数组>，其中:

You can design a hash-set (a special case of hash-tables) of pointers to hashable PODs, with chaining, internally represented as a fixed-size array of buckets of hashables, where:

• 一个bucket中的所有hashable具有相同的哈希值
• 存储桶可以实现为动态数组或哈希值
• 一个hashable的哈希值用于索引到桶数组(哈希值索引数组)
• 散列集中包含的一个或多个 hashable 可以是(指向)另一个散列集，甚至是散列集本身(即自包含有可能)

• all hashables in a bucket have the same hash value
• a bucket can be implemented as a dynamic array or linked list of hashables
• a hashable's hash value is used to index into the array of buckets (hash-value-indexed array)
• one or more of the hashables contained in the hash-set could be (a pointer to) another hash-set, or even to the hash-set itself (i.e. self-inclusion is possible)

拥有大量内存供您使用，您可以充分调整存储桶数组的大小，并结合良好的散列方法，显着降低 collision，实现几乎恒定时间的性能.

With large amounts of memory at your disposal, you can size your array of buckets generously and, in combination with a good hash method, drastically reduce the probability of collision, achieving virtually constant-time performance.

您必须实施:

• 用于被散列的类型的散列函数
• 用于测试两个哈希值是否相等的类型的相等函数
• 哈希集包含/insert/remove 功能.

• the hash function for the type being hashed
• an equality function for the type being used to test whether two hashables are equal or not
• the hash-set contains/insert/remove functionality.

您还可以使用开放寻址作为维护和管理存储桶的替代方法.

You can also use open addressing as an alternative to maintaining and managing buckets.

这篇关于C - 如何实现 Set 数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！