哈希函数对元素顺序不敏感-解网

问：

我正在处理具有非重复元素的整数序列，出于某些原因，我试图通过构建哈希集来删除重复项。

int * a = {123, 145, 210, 77};
int * b = {145, 77, 123, 210}; // should be removed
int * c = {123, 37, 16};
int * d = {123, 145, 72, 91};

是否有对和返回相同结果的顺序不敏感的哈希函数？ab

我已经提出了一些解决方案，但它们表现不佳：

sorting - 序列是不可变的，排序将占用额外的空间和 O（NlogN）时间。

xor - 序列中的元素范围从 0 到数百，可能会浪费许多哈希值。

还有其他方法吗？

C 序列哈希集

#include <stdlib.h>
#include <stdbool.h>

struct hashset {
    int count;
    int capacity;
    struct hashset_element {
        int hash;
        int arrlen;
        int *arrval;
    } *elements;
};

void init_hashset(struct hashset *set) {
    set->count = 0;
    set->capacity = 0;
    set->elements = NULL;
}

int hash(int *arr, int len) {
    // you can replace this hash function
    // this is a pretty simple one
    int out = 0;
    for (int i = 0; i < len; i++) {
        out += arr[i];
    }
    return out;
}

void arrequals(int *arr1, int len1, int *arr2, int len2) {
    if (len1 != len2)
        return false;
    arr1srt = sort(arr1, len1);
    arr2srt = sort(arr2, len2);
    for (int i = 0; i < len1; i++) {
        if (arr1srt[i] != arr2srt[i])
            free(arr1srt);
            free(arr2srt);
            return false;
    }
    free(arr1srt);
    free(arr2srt);
    return true;
}

bool hashset_contains(struct hashset *set, int *arr, int len) {
    int rawhash = hash(arr, len);
    int hash = rawhash % set->capacity;
    for (int i = hash; i < set->capacity; i++) {
        if (set->elements[i]->arrval == NULL)
            return false;
        if (arrequals(set->elements[i]->arrval,
        set->elements[i]->arrlen, arr, len)
            return true;
    }
    for (int i = 0; i < hash; i++) {
        if (set->elements[i]->arrval == NULL)
            return false;
        if (set->elements[i]->hash == rawhash &&
        arrequals(set->elements[i]->arrval,
        set->elements[i]->arrlen, arr, len)
            return true;
    }
    return false;
}

void hashset_realloc(struct hashset *set) {
    struct hashset_element* oldarr = set->elements;
    int old_capacity = set->capacity;
    set->elements = malloc(sizeof(struct hash_element) * set->capacity + 1024);
    set->capacity += 1024;
    for (int i = 0; i < set->capacity; i++) {
        if (oldarr[i]->arrval != NULL)
            hashset_add_element(set, oldarr[i]->arrval, oldarr[i]->arrlen);
    }
}

void hashset_add_element(struct hashset *set, int *arr, int len) {
    if (!hashset_contains(set, arr, len)) {
        if (set->count >= set->capacity / 2) {
            realloc_hashset(set);
        }
        int rawhash = hash_element(arr, len);
        int hash = rawhash % set->capacity;
        for (int i = hash; i < set->capacity; i++) {
             if (set->elements[i]->arrval == NULL) {
                 set->elements[i]->hash = rawhash;
                 set->elements[i]->arrval = arr;
                 set->elements[i]->arrlen = len;
                 set->count++;
                 return;
             }
        }
        for (int i = 0; i < hash; i++) {
             if (set->elements[i]->arrval == NULL) {
                 set->elements[i]->hash = rawhash;
                 set->elements[i]->arrval = arr;
                 set->elements[i]->arrlen = len;
                 set->count++;
                 return;
             }
        }
    }
}

void destroy_hashset(struct hashset *set) {
    if (set->elements != NULL)
        free(set->elements);
}

int hashset_to_array(struct hashset *set, int **arrout, int *lenout, int maxlen) {
    int w = 0;
    for (int i = 0; i < capacity; i++) {
        if (w >= maxlen)
            break;
        arrout[w] = set->elements[i]->arrval;
        lenout[w] = set->elements[i]->arrlen;
        w++;
    }
    return set->count;
}

我没有测试此代码，但是尝试一下，如果我的代码中有错误，请随时纠正我。您必须自己实现排序功能。我不知道数组有多大，你正在使用，所以我无法为你选择一个理想的算法。顺序不敏感的比较只能在中进行。如果整数具有最大大小，则可能小到足以使用计数表。O(n*log(n))O(n)

在理想情况下，此哈希集的运行时为。最坏情况的运行时是，这不太可能发生。哈希算法的运行时为，这并不理想，但对于小型数组来说还可以。O(1)O(n)O(n)

上一个：为什么SQLite会创建空sqlite_sequence表？

下一个：对序列中的供应做出反应

哈希函数对元素顺序不敏感

Hash functions not sensitive to element order

评论