java - 为什么我的哈希表不能在更大的范围内工作？

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 方法:如果您的键已经在哈希表中，但不在键哈希码标识的位置，则执行(大约在 put 方法中的第 27 行)

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

后跟(在 put 方法的末尾)

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

它会覆盖其他一些随 secret 钥。

<小时/>

第二个问题出现在 delete 方法中。您尝试删除并重新插入所有元素。

但是，

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

如果元素碰巧被重新插入到同一位置，

将删除该元素。如果两个元素具有相同的哈希码，则很容易发生这种情况。