爲什麼這個散列表中的元素沒有按預期排序

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

散列表並不意味着被用作排序後的數據結構。它們專爲快速查找而設計，並會按照允許最快速查找的順序放置元素。

如果您的表格在一個點上排序，那麼這只是偶然。