创建具有快速插入、删除、成员资格测试和随机选择的数据结构

Question

这个问题因错误的形成而被否定。请重新阅读，我尝试改进它。

对于上述问题，我找到了以下答案:

"Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array."

insert(value):

• 将值附加到数组 A
• 令 i 为它在 A 中的索引。
• 设置 H[value] = i 。

remove(value): Replace the cell that contains 值 in A with the last element in A.

• 令 d 为数组 A 中的最后一个元素。
• 令 i 为 H[value] ，即要删除的值在数组中的索引。
• 设置 A[i] = d 和 H[d] = i
• 将数组 A 的大小减少 1

contains(value): return true if H contains value

• 获取value的哈希值
• 使用哈希值对包含 value 的存储桶进行索引
• 如果可以在该索引处找到 value，则返回 true

getRandomElement():

• r = random(current size of A).
• return A[r] 。

我尝试用C实现同样的功能，请引用代码帮我解答以下疑问

1. Should newData be called as a HashTable?

2. Is there a way to implement it, without keeping the size in the structure?

3. If you were to implement the same what design you would follow?

#include <stdio.h>
#define MAX 100

typedef struct data
{
    int A[MAX];
    int size = 0;
}newData;

newData *new;

bool insert(newData *n, int value)
{
    int index;
    index = hash(value)/MAX;
    // assume there is no LL to save extra value
    if ((n->A)[index] == value)
    return false;

    (n->A)[index] = value;
    return true;
}

bool remove(newData *n, int value)
{
    int index;
    index = hash(value) % MAX;
    (n->A)[index] = (n->A)[n->size];
    // is this following a correct way to delete the last element?
    n->size--;
    return true;
}

bool contains(newData *n, value)
{
    int index;
    index = hash(value) % MAX;
    if ((n->A)[index] == value)
        return true;
    return false;
}


int hash(int value)
{
    // assume it calculates a good hash and returns the value
}

int main()
{
    return 0;
}

Answer 1

• 首先，当您应该传递指向哈希表的指针时，您会按值传递哈希表

• 大多数哈希表通过使用链接列表来存储哈希到同一存储桶的元素来解决冲突。然后检索包括对列表进行线性搜索以查找元素

• 此外，当您计算元素的哈希值时，您应该将该数字除以存储桶大小并取余数，这将作为元素的新位置。 除非您的哈希函数设计为返回 1..100 范围内的值，否则您需要这样做以避免段错误错误

• 对于删除或删除元素，如果您的哈希表使用链表冲突解决方法，那么一旦您的哈希函数返回该元素应位于的索引，删除将只涉及删除该元素的链接

阅读this tutorial了解有关哈希艺术的更多信息