java - 为什么此哈希表中的元素未按预期排序

Question

我最近开始学习数据结构。我根据书本，使用二次探测方法写了一个哈希表。代码如下:

class QuadraticProbingHashTable<E> implements HashTable<E> {
    private static final int DEFAULT_TABLE_SIZE = 11;

    private HashEntry<E>[] array;

    private int currentSize;

    public QuadraticProbingHashTable() {
        this(DEFAULT_TABLE_SIZE);
    }

    public QuadraticProbingHashTable(int size) {
        allocateArray(size);
        makeEmpty();
    }

    @SuppressWarnings("unchecked")
    private void allocateArray(int size) {
        array = new HashEntry[nextPrime(size)];
    }

    @Override
    public int size() {
        return currentSize;
    }

    @Override
    public boolean isEmpty() {
        return currentSize == 0;
    }

    @Override
    public void clear() {
        makeEmpty();
    }

    private void makeEmpty() {
        currentSize = 0;
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
    }

    @Override
    public boolean contains(E e) {
        int pos = findPos(e);
        return isActive(pos);
    }

    @Override
    public void add(E e) {
        int pos = findPos(e);
        if (isActive(pos))
            return;
        array[pos] = new HashEntry<E>(e);
        currentSize++;
        if (currentSize > array.length / 2)
            rehash();
    }

    @Override
    public void remove(E e) {
        int pos = findPos(e);
        if (isActive(pos)) {
            array[pos].isActive = false;
            currentSize--;
        }

    }

    private int findPos(E e) {
        int offset = 1;
        int currentPos = hash(e);
        while (array[currentPos] != null && !array[currentPos].data.equals(e)) {
            currentPos += offset;
            offset += 2;
            if (currentPos >= array.length)
                currentPos -= array.length;
        }
        return currentPos;
    }

    private boolean isActive(int pos) {
        return array[pos] != null && array[pos].isActive;
    }

    private int hash(E e) {
        int hashVal = e.hashCode();
        hashVal %= array.length;
        if (hashVal < 0)
            hashVal += array.length;
        return hashVal;
    }

    private void rehash() {
        HashEntry<E>[] oldArray = array;
        allocateArray(nextPrime(array.length << 1));
        currentSize = 0;
        for (int i = 0; i < oldArray.length; i++) {
            if (oldArray[i] != null && oldArray[i].isActive)
                add(oldArray[i].data);
        }
    }

    @Override
    public String toString() {
        StringJoiner joiner = new StringJoiner();
        for (int i = 0; i < array.length; i++)
            if (isActive(i))
                joiner.add(array[i].data);
        return joiner.toString();
    }

    private static class HashEntry<E> {
        E data;

        boolean isActive;

        public HashEntry(E data) {
            this(data, true);
        }

        public HashEntry(E data, boolean isActive) {
            this.data = data;
            this.isActive = isActive;
        }
    }

    // get next prime
    public int nextPrime(int n) {
        if (n % 2 == 0)
            n++;
        while (!isPrime(n))
            n += 2;
        return n;
    }

    private boolean isPrime(int n) {
        if (n == 2 || n == 3)
            return true;
        if (n == 1 || n % 2 == 0)
            return false;
        for (int i = 3; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    // util
    private static class StringJoiner {
        private String delimiter;

        private String prefix;

        private String suffix;

        private String emptyValue;

        private StringBuilder builder;

        public StringJoiner() {
            this(", ", "[", "]");
        }

        public StringJoiner(String delimiter, String prefix, String suffix) {
            super();
            this.delimiter = delimiter;
            this.prefix = prefix;
            this.suffix = suffix;
            emptyValue = prefix + suffix;
        }

        public StringJoiner add(Object obj) {
            prepareBuilder().append(obj.toString());
            return this;
        }

        private StringBuilder prepareBuilder() {
            if (builder == null)
                builder = new StringBuilder().append(prefix);
            else
                builder.append(delimiter);
            return builder;
        }

        @Override
        public String toString() {
            if (builder == null)
                return emptyValue;
            return builder.append(suffix).toString();
        }
    }

}

interface HashTable<E> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(E e);
    void add(E e);
    void remove(E e);
}

检查了几次后，我添加了数据。我认为虽然哈希表是无序的，但是其中的元素应该是有特定顺序的。

首先测试以下一组数据:

public class MainTest {
    public static void main(String[] args) {
        HashTable<Integer> table = new QuadraticProbingHashTable<>();
        for (int i = 60; i <= 90; i++) {
            table.add(i);
        }
        System.out.println(table);
    }
}

这是排序后的结果:

[60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90]

然后我在第一个测试数据上添加了10并再次测试:

public class MainTest {
    public static void main(String[] args) {
        HashTable<Integer> table = new QuadraticProbingHashTable<>();
        // for (int i = 60; i <= 90; i++) {
        for (int i = 70; i <= 100; i++) {
            table.add(i);
        }
        System.out.println(table);
    }
}

但是结果如下:

[97, 98, 99, 100, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96]

它已经变得无序。

不知道是我写的代码有问题，还是有其他原因。有人可以帮我检查一下吗？我刚刚接触了数据结构。

Answer 1

哈希表并不意味着用作排序的数据结构。它们专为快速查找而设计，并将按照允许最快查找的顺序放置元素。

如果您的表格在某个时刻被排序，那么这只是偶然。