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

Question

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

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};

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

我已经想出了一些解决方案，但它们的表现很差：

排序 - 序列是不可变的，排序将涉及额外的空间和 O(NlogN) 时间。

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

还有其他方法吗？

Answer 1

散列并不是您应该做的唯一事情。由于信息丢失，完全不同的数组可能会返回相同的哈希值。为了仅删除重复项，您还需要检查等效性。哈希集也可以做到这一点，但是基于哈希放置元素，因此您可以更轻松地找到它们。

这是一个示例实现：

#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)，这并不理想，但对于小型数组来说还可以。