后进先出，散列java

Question

[在学校评估中，我正在尝试使用后进先出的技术为Java程序实现数据结构。我们从老师那里得到了一个Java程序，该程序当前正在使用线性探测。当发生碰撞时，这应该发生（我必须编写的代码）：

• [将元素插入表中时，应总是将其保存在哈希函数计算的索引上。
• 如果哈希表中的索引被占用，则该索引中已存在的元素应移至下一个可用的元素，即“向右移一步”（依此类推）。因此，最新插入的元素应始终具有优先级。
• 将重复此过程，直到我们不再需要将元素“向右移动一步”（当我们获得表中的自由索引时）

我在此article中找到了一些东西，但是我无法完全理解如何在我的代码中实现它。一般来说，我对编程还是比较陌生的。

这是我们从老师那里得到的代码，我们必须使用先到先得的方法将其重写为：（对不起，英语不好，它已经从我的语言翻译成英语，希望您能理解）

package Hashing;

import java.io.IOException;
import java.util.Scanner;

    public class hashLinear {
        // Hashlength
        private int hashLength;

        // Hashtable
        private String hashTable[];

        // Number of element saved in the table
        private int n;

        // Number of probes at insertion
        private int numProbes;

        // Constructor
        // Does not check for reasonable value of hashlength
        public hashLinear(int length) {
            hashLength = length;
            hashTable = new String[length];
            n = 0;
            numProbes = 0;
        }

        // Returns load factor
        public float loadFactor() {
            return ((float) n) / hashLength;
        }

        // Returns number of data in the table
        public int numData() {
            return n;
        }

        // Returns number of probes at insertion
        public int numProbes() {
            return numProbes;
        }

        // Hashfunction
        int hash(String S) {
            int h = Math.abs(S.hashCode());
            return h % hashLength;
        }

        // Inserting string with linear probing, exits with error message if there is no available place
        void insert(String S) {
            // Calculating hash value
            int h = hash(S);

            // Linear probing
            int next = h;

            hashTable[next] = S;
            while (hashTable[next] != null) {
                // New probe
                numProbes++;

                // This index is occupied, try the next one
                next++;

                // Wrap-around
                if (next >= hashLength)
                    next = 0;

                // If we have reached original hash value, is the table full and we give up.
                // (We would normally extend the table and do a rehashing)
                if (next == h) {
                    System.err.println("\nThe hash table is full, exiting");
                }
            }

            // Stores the text string on found index
            hashTable[next] = S;

            // Increments number of elements saved
            n++;
        }

        // Searching for string with linear probing. Returns true if string is saved, else false
        boolean search(String S) {
            // Calculating hash value
            int h = hash(S);

            // Linear probing
            int next = h;

            while (hashTable[next] != null) {
                // Have we found the hash value?
                if (hashTable[next].compareTo(S) == 0)
                    return true;

                // Try the next possible
                next++;

                // Wrap-around
                if (next >= hashLength)
                    next = 0;

                // If we have come back to original hash value, the string is not present in the table
                if (next == h)
                    return false;
            }

            // Doesn't find the string, have come to probe that is null
            return false;
        }

        public static void main(String[] argv) {
            // Hash length is read from command line
            int hashLength = 0;
            Scanner input = new Scanner(System.in);
            try {
                if (argv.length != 1)
                    throw new IOException("Error: Hash length must be set");
                hashLength = Integer.parseInt(argv[0]);
                if (hashLength < 1)
                    throw new IOException("Error: Hash length needs to be bigger than 0");
            } catch (Exception e) {
                System.err.println(e);
                System.exit(1);
            }

            // Makes new hash table
            hashLinear hL = new hashLinear(hashLength);

            // Reads input and hashes all lines
            while (input.hasNext()) {
                hL.insert(input.nextLine());
            }

            // Prints out hash length, number of data read, number of collisions and load factor: 
            System.out.println("Hash length: " + hashLength);
            System.out.println("Elements: " + hL.numData());
            System.out.printf("Load factor : %5.3f\n", hL.loadFactor());
            System.out.println("Probes: " + hL.numProbes());

            // A few simple searches
            String S = "Volkswagen Karmann Ghia";
            if (hL.search(S))
                System.out.println("\"" + S + "\"" + " is present in the hash table");
            S = "Il Tempo Gigante";
            if (!hL.search(S))
                System.out.println("\"" + S + "\"" + " is not present in the hash table");
        }
    }
}

[在学校评估中，我正在尝试使用后进先出的技术为Java程序实现数据结构。我们从老师那里得到了一个Java程序，该程序正在使用...

Answer 1