我正在使用 C 语言开发硬件虚拟模拟合成器，我正在尝试提出一种有效的数据结构来管理合成器声音的动态分配以响应传入的 MIDI 消息。
我有一个结构类型，用于保存单个合成器语音（音高、低频振荡器、ADSR 设置等）的数据，我有一个"NoteOn"回调函数，该函数在解码 MIDI "Note On"消息时执行。 此函数需要从"空闲"池中获取"空闲"语音，修改结构中的某些设置，并将其分配给主合成器引擎用于生成音频样本的"播放"池。 然后，当收到"Note Off"消息时，需要从"播放"池中选择具有与"Note Off"消息中音符值对应的音符值的语音，再次修改其数据结构，并最终返回到"空闲"池（取决于信封/ADSR 设置）。
我尝试了使用两个池的链表实现，但我的实现似乎相当麻烦和缓慢。 我希望这个过程尽可能快，以保持游戏响应能力。 有什么建议吗？
如果链表太慢，通常的答案是实现哈希表。数据结构和算法有很多很多可能的变体。我只描述开放的"单一"哈希，因为这是我最熟悉的变体。
因此，对于开放哈希表，该表只是一个数组（"封闭"哈希也有一个数组，但每个元素都是一个链表）。出于性能原因，我们希望阵列最多是半满的。在最大容量下，填充的表实际上仍然有一个空插槽，因为这简化了算法。
我们还需要一个哈希函数，它接受键值的类型，并返回整数。很难预测哈希函数在集群键和整体性能方面的行为。因此，只需确保它是一个独立的功能，以后可以轻松更改。它可以像移动所有字节并将它们相加一样简单。
int hash (char *key, int key_length, int table_size)
{
int ret, i;
for (i=0, ret=0; i < key_length; i++)
{
ret += key[i] << i;
}
return abs(ret) % table_size;
}
使用哈希函数来决定从何处开始在数组中查找。如果在那里找不到键（通过对实际搜索键和存储在表中该位置的键执行memcmp()来确定），它会查看每个连续的键，从数组的末尾包装回开头，并在找到空表元素时声明失败。
#define RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
if (memcmp(table + i, &key, sizeof key) == 0 || (key_type)table[i] == 0)
return table + i;
key_value_pair *hash_lookup(key_value_pair *table, int table_size, key_type key)
{
int h, i;
h = hash(&key, sizeof key, table_size);
i = h;
RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
for ( ; i < table_size; i++)
RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
for (i=0; i < h; i++)
RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
return NULL;
}
我们需要在前面再增加一个函数来处理一些怪癖。它可以返回一个 NULL 指针，指示不仅没有找到键，而且表本身已满。一个过满的表，这实际上意味着"完全满"，但我们之前决定，一个"满"的表实际上应该有一个空元素。这意味着两个for循环都不应运行到完成;当它找到一个空表位置时，这是一个失败。对于过满的表，它必须扫描整个表，然后才能发现密钥不存在，从而完全失去使用哈希的大部分性能优势。
查找函数还可以返回指向空槽的有效指针。这也是找不到值的失败，但不是错误。如果是第一次添加键/值对，这将是存储它的槽。
或者它可以返回指向所需表元素的指针。这将比线性搜索更快，无论是数组还是链表。
从表中删除键需要我们填写序列中空出的位置。有几个选项。
如果您不担心表空间不足（它设置得非常大，并且可以控制生存期和使用情况），则可以使用已删除的特殊键（不同于空键）覆盖该条目。
或者，如果你也想回收空间，你需要查找密钥，然后扫描"链"的其余部分（密钥序列到下一个空插槽（包括环绕）），并将最后一个密钥与匹配哈希移动到要删除的密钥的位置。