具有双重哈希冲突解决方案的哈希 table - 无限循环

Question

我已经用这个散列 table 紧张了一段时间，但我似乎无法找到导致这些无限循环的原因。插入通常在中点左右停止。密钥由一串 64 个随机符号组成，中间用下划线分隔。需要帮助尝试调试！

这里是Table构造函数，哈希函数和插入方法：

        private int maxsize;
        private int size;
        private TableEntry[] table;
        private int primeSize;

        public HashTable(int ts)
        {
            size = 0;
            maxsize = ts;
            table = new TableEntry[maxsize];
            for (int i = 0; i < maxsize; i++)
                table[i] = null;
            primeSize = getPrime();
        }

        public int getPrime()
        {
            for (int i = maxsize - 1; i >= 1; i--)
            {
                int fact = 0;
                for (int j = 2; j <= (int)Math.Sqrt(i); j++)
                    if (i % j == 0)
                        fact++;
                if (fact == 0)
                    return i;
            }

            return 3;
        }

        public void Insert(string key, double value)
        {
            if (size == maxsize)
            {
                Console.WriteLine("Table full");
                return;
            }
            int hash1 = myhash1(key);
            int hash2 = myhash2(key);
            Console.WriteLine(" Hashed keys: {0}, {1}", hash1, hash2);
            while (table[hash1] != null)
            {
                hash1 += hash2;
                hash1 %= maxsize;
            }
            table[hash1] = new TableEntry(key, value);
            size++;
        }

        private int myhash1(string key)
        {
            int hashVal = key.GetHashCode();
            hashVal %= maxsize;
            if (hashVal < 0)
                hashVal += maxsize;
            return hashVal;
        }

        private int myhash2(string key)
        {
            int hashVal = key.GetHashCode();
            hashVal %= maxsize;
            if (hashVal < 0)
                hashVal += maxsize;
            return primeSize - hashVal % primeSize;
        }

Answer 1

Insert 中的 while 循环如果在没有找到空位的情况下循环回到数组中的相同索引，则可能会进入无限循环。为防止出现此问题，您可以使用 "just find the next available free space" 策略扩充双重哈希策略 - 如果第一个策略失败，则切换到第二个策略。您需要另一个变量来跟踪 hash1 的原始值以实现它。

具有双重哈希冲突解决方案的哈希 table - 无限循环

Hash table with double hashing collision resolution - infinite loop

c#

hashtable

infinite-loop

double-hashing