c++ - 插入实现 'Linear Hashing'

Question

我必须为我的算法类(class)实现数据结构“线性哈希”，但我遇到了一些问题。我已经直接实现了附加功能。我必须使用以下哈希函数:

h(x) = x mod 2^d

我的测试值是:

24200, 16448, 16432, 4044, 24546, 10556, 29009, 25270, 32579, 13047

当我将此值添加到我的数据结构时，我得到以下信息:

LinearHashing [ TableSize=4 BucketSize=2 d=2 nextToSplit=0 ]
Elemente
values=
Bucket[0]
 [24200]  [16448]
Overflow Bucket:
 [16432]  [4044]
 [24546]  [10556]
 [25270]  [0]
Bucket[1]
 [29009]  [0]
Bucket[2]
 [0]  [0]
Bucket[3]
 [32579]  [13047]

但是值“25270”最终出现在错误的桶中，我已经重新检查了一千次，但我找不到我的错误。当我将 Overflowbucketsize 设置为“N/2”时，该错误已修复，但这可能只是巧合。 该示例应如下所示(如果我的算法正确):

LinearHashing [ TableSize=4 BucketSize=2 d=2 nextToSplit=0 ]
Elemente
values=
Bucket[0]
 [24200]  [16448]
Overflow Bucket:
 [16432]  [4044]
 [24546]  [10556]
 [0]  [0]
Bucket[1]
 [29009]  [0]
Bucket[2]
 [25270]  [0]
Bucket[3]
 [32579]  [13047]

我必须用这个测试程序测试我的数据结构:

http://pastebin.com/k1p4Z6e3

我的数据结构必须基于我的教授提供的这个 *.h 文件:

http://pastebin.com/79jLERuF

这是我的完整代码:

http://pastebin.com/mW09UEzx

最重要的功能如下。我的附加功能:

template <typename E, size_t N>
void LinearHashing<E,N>::add(const E e[], size_t len) {
    for(size_t i=0; i < len; ++i){
        size_t address = compIndex(e[i]);
        for(size_t j=0; j < N; ++j){
            if(table[address].bucketstatus[j] == leer){
                table[address].bucketElem[j] = e[i];
                table[address].bucketstatus[j] = besetzt;
                break;
            }else if(j == (N-1) && table[address].newoverflow == nullptr){
                table[address].newoverflow = new OverflowContainer();
                addToOverflow(e[i],table[address].newoverflow);
                split();
                reHash(nts);
                if(nts+1 == (pow(2, d))){
                    nts=0;
                    ++d;
                }else{
                    ++nts;
                }
            }else if(j == (N-1) && table[address].newoverflow != nullptr){
                addToOverflow(e[i],table[address].newoverflow);
            }
        }
    }
}

元素的索引是用下面两个函数计算的:

哈希值:

template <typename E> inline size_t hashValue(const E& e) { return size_t(e); }

补偿指数:

template <typename E, size_t N>
inline size_t LinearHashing<E, N>::compIndex(E e){
    size_t adrOP = powl(2,d);
    return hashValue(e) % adrOP;
}

溢出由以下函数添加:

template <typename E, size_t N>
void LinearHashing<E, N>::addToOverflow(E e, LinearHashing::OverflowContainer *container) {
    size_t i=0;
    while( i < N/2){
        if(container->overflowstatus[i] == leer){
            container->overflowbucket[i] = e;
            container->overflowstatus[i] = besetzt;
            break;
        }else if(i == (N/2)-1 && container->nextOverflow == nullptr){
            container->nextOverflow = new OverflowContainer();
            container = container->nextOverflow;
            split();
            reHash(nts);
            if(nts+1 == (pow(2, d))){
                nts=0;
                ++d;
            }else{
                ++nts;
            }
            i=0;
        }else if(i == (N/2)-1 && container->nextOverflow != nullptr){
            container = container->nextOverflow;
            i=0;
        }else{
            ++i;
        }
    }
}

要执行拆分，我使用此函数:

template <typename E, size_t N>
void LinearHashing<E,N>::split(){
    Bucket* tmp = new Bucket[size()+1];
    std::copy(table,table+size(),tmp);
    delete[] table;
    table = tmp;
    ++n;
}

现在我在创建新的 Overflow 时执行拆分，为了重新散列 nextToSplit 行，我使用以下重新散列函数:

template <typename E, size_t N>
void LinearHashing<E, N>::reHash(size_t index){
    bool reHashed = false;
    for(size_t i = 0; i < N; ++i){
        if(compIndex(table[index].bucketElem[i]) != compReIndex(table[index].bucketElem[i]) && table[index].bucketstatus[i] == besetzt){
            for (size_t j = 0; j < N && !reHashed ; ++j) {
                if(table[n-1].bucketstatus[j] == leer){
                    table[n-1].bucketElem[j] = table[index].bucketElem[i];
                    table[n-1].bucketstatus[j] = besetzt;
                    table[index].bucketstatus[i] = leer;
                    table[index].bucketElem[i] = 0;
                    reHashed = true;
                }
            }
            reHashed = false;
        }
    }
    if(table[index].newoverflow != nullptr){
        reHashOverflow(table[index].newoverflow);
    }
}
template <typename E, size_t N>
void LinearHashing<E, N>::reHashOverflow(OverflowContainer* container) {
    size_t i=0;
    bool reHashed = false;
    while(i < (N/2)){
        if(compIndex(container->overflowbucket[i]) != compReIndex(container->overflowbucket[i]) && container->overflowstatus[i] == besetzt){
            for(size_t j=0; j < N && !reHashed; ++j){
                if(table[n-1].bucketstatus[j] == leer){
                    table[n-1].bucketElem[j] = container->overflowbucket[i];
                    table[n-1].bucketstatus[j] = besetzt;
                    container->overflowbucket[i] = 0;
                    container->overflowstatus[i] = leer;
                    reHashed = true;
                }else if(j == N-1 && table[n-1].newoverflow == nullptr){
                    table[n-1].newoverflow = new OverflowContainer();
                    addToOverflow(container->overflowbucket[i],table[n-1].newoverflow);
                    container->overflowbucket[i] = 0;
                    container->overflowstatus[i] = leer;
                    reHashed = true;
                }else if(j == N-1 && table[n-1].newoverflow != nullptr){
                    addToOverflow(container->overflowbucket[i], table[n-1].newoverflow);
                    container->overflowbucket[i] = 0;
                    container->overflowstatus[i] = leer;
                    reHashed = true;
                }
            }
            reHashed = false;
            ++i;
        }else{
            ++i;
        }
        if(container->nextOverflow){
            container = container->nextOverflow;
            i = 0;
        }
    }
}

Answer 1

我现在已经完全重新实现它并发现了很多错误，例如split 和 rehash 函数的隐式递归。