Почему моя хэш-таблица не работает на большем диапазоне?

Question

Я работаю над хеш-таблицей, в которой используется открытая адресация с линейным зондированием. Я работаю со стандартными функциями, такими как получить, вставить и удалить. Моя проблема в том, что хотя эти функции работают очень хорошо для меньших хеш-таблиц, кажется, что они работают неправильно, когда хеш-таблица становится больше. Size () не возвращает правильное значение и не получает get (). Буду очень признателен за любую информацию о том, как мне удастся решить эти проблемы.

   public class SymbolTable {
                            private static final int INIT_CAPACITY = 7;

                            /* Number of key-value pairs in the symbol table */
            private int N;
            /* Size of linear probing table */
            private int M;
            /* The keys */
            private String[] keys;
            /* The values */
            private Character[] vals;

            /**
             * Create an empty hash table - use 7 as default size
             */
            public SymbolTable() {
                this(INIT_CAPACITY);
            }

            /**
             * Create linear probing hash table of given capacity
             */
            public SymbolTable(int capacity) {
                N = 0;
                M = capacity;
                keys = new String[M];
                vals = new Character[M];
            }

            /**
             * Return the number of key-value pairs in the symbol table
             */
            public int size() {
            return N;
            }

            /**
             * Is the symbol table empty?
             */
            public boolean isEmpty() {
            return size() == 0;
            }

            /**
             * Does a key-value pair with the given key exist in the symbol table?
             */
            public boolean contains(String key) {
            return get(key) != null;
            }

            /**
             * Hash function for keys - returns value between 0 and M-1
             */
            public int hash(String key) {
            int i;
            int v = 0;

            for (i = 0; i < key.length(); i++) {
            v += key.charAt(i);
            }
            return v % M;
            }

            /**
             * Insert the key-value pair into the symbol table
             */
            public void put(String key, Character val) {

                int z = hash(key);
                if(keys[z] == null){ //Ökar endast om platsen redan är null. lösning för att omplaceringarna från delete inte ska öka värdet
                    N++;
//                                  System.out.println("stlk "+N);
                }
                if(key.equals(keys[z])){
                    vals[z]= val;
                    }
                else
                if (keys[z]!=null){
                    if(z == M -1){
                        z = 0;
                    }
                    for (int i = z; i < M; i++){
                        if (keys[z]!=null){
                            if(i == M - 1){
                                if(keys[i] == null){
                                    z=i;
                                    N++;
//                                                  System.out.println("strlk " + N);
                                    break;
                                }else{
                                i=0;
                                }
                            }}
                        if(key.equals(keys[i])){
                            vals[i]= val;
                            break;
                            }
                        if(keys[i] == null){
                            z = i;
                            N++;
//                                          System.out.println("stlk "+N);
                            break;
                        }

                    }
                }
                keys[z]=key;
                vals[z]=val;
            }


             // dummy code

            /**
             * Return the value associated with the given key, null if no such value
             */

                public Character get(String key) {
                    int index = hash(key);
                    while (keys[index] != null && !keys[index].equals(key)) {
                        index++;

                        if (index == M) {
                            index = 0;
                        }
                    }

                    return vals[index];

                } // dummy code

            /**
             * Delete the key (and associated value) from the symbol table
             */
            public void delete(String key) {

                if (keys[hash(key)] != null){  //Kollar så att strängen faktiskt finns, så att den inte deletar pga. HASHVÄRDET av strängen finns

                    if(key.equals(keys[hash(key)])){
                        keys[hash(key)] = null;
                        vals[hash(key)] = null;
                    N --;

                    for (int i = 0; i < M; i++){
                        if(keys[i] != null && hash(keys[i]) != i){ 
                        N--;
//                                      System.out.println("strlk "+N);
                        put(keys[i], vals[i]);
                        keys[i] = null;
                        vals[i] = null; 
                        }}

                    } else {
                        for (int i = 0; i < M; i++){
                                if(keys[i] != null && hash(keys[i]) != i){ 
                                N--;
//                                              System.out.println("strlk "+N);
                                put(keys[i], vals[i]);
                                keys[i] = null;
                                vals[i] = null; 
                                }
                            if(key.equals(keys[i])){
                                keys[hash(key)] = null;
                            N --;   
                        }
                        }
                    }
                }


                    }   

                    // dummy code

                    /**
                     * Print the contents of the symbol table
                     */



            // dummy code

            /**
             * Print the contents of the symbol table
             */
            public void dump() {
                String str = "";

                for (int i = 0; i < M; i++) {
                    str = str + i + ". " + vals[i];
                    if (keys[i] != null) {
                        str = str + " " + keys[i] + " (";
                        str = str + hash(keys[i]) + ")";
                    } else {
                        str = str + " -";
                    }
                    System.out.println(str);
                    str = "";
                }
            }
        }

это тестовая программа, которая используется для его запуска.

import java.io.*;
public class SymbolTableTest2 {



public static void main(final String[] args){
        final SymbolTable st = new SymbolTable(733);
        final int nums = 730;
        final int gap = 37;
        final char[] tests = new char[nums];
        int i;

    System.out.println("Checking... (no more output means success)");

    // Associate i (as a string) with a random printable character
    for (i = gap; i != 0; i = (i + gap) % nums) {
      final char ch = (char) (32 + (int) (Math.random() * ((127 - 32) + 1)));

      st.put(Integer.toString(i), ch);
      tests[i] = ch;
     }

    // Check that size() is correct
    if (st.size() != nums - 1) {
      System.out.println("size was() " + st.size()
                 + ", should have been " + (nums - 1));
     }

    // Delete some entries
    for (i = 1; i < nums; i += 2) {
      st.delete(Integer.toString(i));
     }

    // Check that size is correct
    if (st.size() != ((nums / 2) - 1)) {
      System.out.println("size was() " + st.size()
                 + ", should have been " + ((nums / 2) - 1));
     }

    // Delete same entries again
    for (i = 1; i < nums; i += 2) {
      st.delete(Integer.toString(i));
     }

    // Check that size is correct
    if (st.size() != ((nums / 2) - 1)) {
      System.out.println("size was() " + st.size()
                 + ", should have been " + ((nums / 2) - 1));
     }

    // Check that correct entries are still in table
    for (i = 2; i < nums; i += 2) {
      if (st.get(Integer.toString(i)) == null
          || st.get(Integer.toString(i)) != tests[i]) {
        System.out.println("get(" + i + ") was "
                   + st.get(Integer.toString(i))
                   + ", should have been " + tests[i]);
      }
     }

    // Check that deleted entries really were deleted
    for (i = 1; i < nums; i += 2) {
      if (st.get(Integer.toString(i)) != null) {
        System.out.println("get(" + i + ") was "
                   + st.get(Integer.toString(i))
                   + ", should have been null");
      }
     }
}}

Answer 1

Ваш метод удаления неправильный.

Следующий фрагмент кода показывает проблему:

    SymbolTable st = new SymbolTable(733);
    st.put("12", 'A');
    st.put("21", 'B');
    st.put("13", 'C');
    st.remove("13");

После запуска этого кода st будет содержать две клавиши «12» и «13» вместо «12» и «21».

---

Одной из проблем является метод put: если ваш ключ уже находится в хеш-таблице, но не в месте, указанном хеш-кодом ключей, вы выполняете (около строки 27 в методе put)

    if(key.equals(keys[i])){
        vals[i]= val;
        break;
    }

с последующим (в конце метода put)

    keys[z]=key;
    vals[z]=val;

, который перезаписывает какой-то другой случайный ключ.

---

Вторая проблема заключается в методе delete. Вы пытаетесь удалить и заново вставить все элементы.

Тем не менее,

put(keys[i], vals[i]);
keys[i] = null;
vals[i] = null;

удалит элемент, если он будет вставлен в то же место. Это может легко произойти, если два элемента имеют одинаковый хэш-код.