Хеш-таблица с двойным разрешением коллизий - бесконечный цикл - PullRequest
Новая
       16

Хеш-таблица с двойным разрешением коллизий - бесконечный цикл

0 голосов
/ 26 мая 2018

Я какое-то время подчеркивал эту хэш-таблицу, но пока не могу найти причину этих бесконечных циклов.Вставка обычно останавливается примерно на половине пути.Ключ состоит из 64 случайных символов, разделенных подчеркиванием в середине.Нужна помощь в попытке отладки этого!

Вот конструктор таблицы, хэш-функции и метод вставки: 

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

1 Ответ

0 голосов
/ 26 мая 2018

Цикл while в Insert может попасть в бесконечный цикл, если он возвращается к тому же индексу в массиве, не находя пустое место.Чтобы предотвратить эту проблему, вы можете дополнить стратегию двойного хеширования стратегией «просто найдите следующий доступный свободный объем» - переключиться на вторую стратегию, если первая стратегия не удалась.Вам потребуется другая переменная для отслеживания исходного значения hash1, чтобы реализовать это.

...