對Java HashTable實現的線性探測

Question

所以我在這裏有一個HashTable實現，我只寫了數組，並且對代碼有一點幫助。不幸的是，我不太瞭解某人在運行「get」或「put」方法時添加的行。下面的while循環究竟發生了什麼？這是線性探測正確的方法嗎？爲什麼循環檢查它檢查的條件？

具體來說，

int hash = hashThis(key); 

    while(data[hash] != AVAILABLE && data[hash].key() != key) { 

     hash = (hash + 1) % capacity; 
    } 

這裏是低於整個Java類的完整參考。

public class Hashtable2 { 

private Node[] data; 
private int capacity; 
private static final Node AVAILABLE = new Node("Available", null); 

public Hashtable2(int capacity) { 

    this.capacity = capacity; 
    data = new Node[capacity]; 
    for(int i = 0; i < data.length; i++) { 

     data[i] = AVAILABLE; 
    } 
} 

public int hashThis(String key) { 

    return key.hashCode() % capacity; 
} 

public Object get(String key) { 

    int hash = hashThis(key); 

    while(data[hash] != AVAILABLE && data[hash].key() != key) { 

     hash = (hash + 1) % capacity; 
    } 
    return data[hash].element(); 
} 

public void put(String key, Object element) { 

    if(key != null) { 
     int hash = hashThis(key); 
     while(data[hash] != AVAILABLE && data[hash].key() != key) { 

      hash = (hash + 1) % capacity; 
     } 

     data[hash] = new Node(key, element); 

    } 

} 



public String toString(){ 

    String s="<"; 

    for (int i=0;i<this.capacity;i++) 
    { 
     s+=data[i]+", ";  

    } 

    s+=">"; 

    return s; 
    } 

謝謝。

Answer 1

我只是重寫了部分代碼，並添加了findHash方法 - 儘量避免代碼重複！

private int findHash(String key) { 
    int hash = hashThis(key); 

    // search for the next available element or for the next matching key 
    while(data[hash] != AVAILABLE && data[hash].key() != key) { 

     hash = (hash + 1) % capacity; 
    } 
    return hash; 
} 

public Object get(String key) { 

    return data[findHash(key)].element(); 
} 

public void put(String key, Object element) { 

    data[findHash(key)] = new Node(key, element); 
} 

你要求的是 - 這個findHash-loop究竟是什麼？數據初始化爲AVAILABLE - 含義：數據不包含任何實際數據。現在 - 當我們添加一個元素put - 首先計算一個hash值，這只是data數組放置數據的索引。現在 - 如果我們遇到該位置已經被具有相同散列值但不同密鑰的另一個元素佔用，我們嘗試找到下一個位置。而且get方法的工作原理基本相同 - 如果檢測到具有不同關鍵字的數據元素，則探測下一個元素，依此類推。 data本身就是一個所謂的環形緩衝區。也就是說，它被搜索直到數組結束，然後再次搜索開始，從索引0開始。這是通過模%運算符完成的。

好嗎？

Answer 2

使用泛型和線性探測實現碰撞解析的樣本散列表實現。在實現過程中會做出一些假設，並將它們記錄在javadoc上面的類和方法中。

此實現不具有像哈希表的keySet，等的putAll的所有方法，但涵蓋了最常用的方法，如GET，PUT刪除，大小等

還有就是在獲取代碼重複，把和刪除找到索引，並且可以改進以找到索引的新方法。上面的代碼的

class HashEntry<K, V> { 
    private K key; 
    private V value; 
    public HashEntry(K key, V value) { 
     this.key = key; 
     this.value = value; 
    } 
    public void setKey(K key) { this.key = key; } 
    public K getKey() { return this.key; } 

    public void setValue(V value) { this.value = value; } 
    public V getValue() { return this.value; } 
} 

/** 
* Hashtable implementation ... 
* - with linear probing 
* - without loadfactor & without rehash implementation. 
* - throws exception when table is full 
* - returns null when trying to remove non existent key 
* 
* @param <K> 
* @param <V> 
*/ 
public class Hashtable<K, V> { 

    private final static int DEFAULT_CAPACITY = 16; 

    private int count; 
    private int capacity; 
    private HashEntry<K, V>[] table; 

    public Hashtable() { 
     this(DEFAULT_CAPACITY); 
    } 

    public Hashtable(int capacity) { 
     super(); 
     this.capacity = capacity; 
     table = new HashEntry[capacity]; 
    } 

    public boolean isEmpty() { return (count == 0); } 

    public int size() { return count; } 

    public void clear() { table = new HashEntry[this.capacity]; count = 0; } 

    /** 
    * Returns null if either probe count is higher than capacity else couldn't find the element. 
    * 
    * @param key 
    * @return 
    */ 
    public V get(K key) { 
     V value = null; 
     int probeCount = 0; 
     int hash = this.hashCode(key); 
     while (table[hash] != null && !table[hash].getKey().equals(key) && probeCount <= this.capacity) { 
      hash = (hash + 1) % this.capacity; 
      probeCount++; 
     } 
     if (table[hash] != null && probeCount <= this.capacity) { 
      value = table[hash].getValue(); 
     } 
     return value; 
    } 

    /** 
    * Check on the no of probes done and terminate if probe count reaches to its capacity. 
    * 
    * Throw Exception if table is full. 
    * 
    * @param key 
    * @param value 
    * @return 
    * @throws Exception 
    */ 
    public V put(K key, V value) throws Exception { 
     int probeCount = 0; 
     int hash = this.hashCode(key); 
     while (table[hash] != null && !table[hash].getKey().equals(key) && probeCount <= this.capacity) { 
      hash = (hash + 1) % this.capacity; 
      probeCount++; 
     } 
     if (probeCount <= this.capacity) { 
      if (table[hash] != null) { 
       table[hash].setValue(value);     
      } else { 
       table[hash] = new HashEntry(key, value); 
       count++; 
      } 
      return table[hash].getValue(); 
     } else { 
      throw new Exception("Table Full!!"); 
     } 
    } 

    /** 
    * If key present then mark table[hash] = null & return value, else return null. 
    * 
    * @param key 
    * @return 
    */ 
    public V remove(K key) { 
     V value = null; 
     int probeCount = 0; 
     int hash = this.hashCode(key); 
     while (table[hash] != null && !table[hash].getKey().equals(key) && probeCount <= this.capacity) { 
      hash = (hash + 1) % this.capacity; 
      probeCount++; 
     } 
     if (table[hash] != null && probeCount <= this.capacity) { 
      value = table[hash].getValue(); 
      table[hash] = null; 
      count--; 
     } 
     return value; 
    } 

    public boolean contains(Object value) { 
     return this.containsValue(value); 
    } 

    public boolean containsKey(Object key) { 
     for (HashEntry<K, V> entry : table) { 
      if (entry != null && entry.getKey().equals(key)) { 
       return true; 
      } 
     } 
     return false; 
    } 

    public boolean containsValue(Object value) { 
     for (HashEntry<K, V> entry : table) { 
      if (entry != null && entry.getValue().equals(value)) { 
       return true; 
      } 
     } 
     return false; 
    } 

    @Override 
    public String toString() { 
     StringBuilder data = new StringBuilder(); 
     data.append("{"); 
     for (HashEntry<K, V> entry : table) { 
      if (entry != null) { 
       data.append(entry.getKey()).append("=").append(entry.getValue()).append(", "); 
      } 
     } 
     if (data.toString().endsWith(", ")) { 
      data.delete(data.length() - 2, data.length()); 
     } 
     data.append("}"); 
     return data.toString(); 
    } 

    private int hashCode(K key) { return (key.hashCode() % this.capacity); } 

    public static void main(String[] args) throws Exception { 
     Hashtable<Integer, String> table = new Hashtable<Integer, String>(2); 
     table.put(1, "1"); 
     table.put(2, "2"); 
     System.out.println(table); 
     table.put(1, "3"); 
     table.put(2, "4"); 
     System.out.println(table); 
     table.remove(1); 
     System.out.println(table); 
     table.put(1, "1"); 
     System.out.println(table); 
     System.out.println(table.get(1)); 
     System.out.println(table.get(3)); 
     // table is full so below line 
     // will throw an exception 
     table.put(3, "2"); 
    } 
} 

---

樣品運行。

{2=2, 1=1} 
{2=4, 1=3} 
{2=4} 
{2=4, 1=1} 
1 
null 
Exception in thread "main" java.lang.Exception: Table Full!! 
    at Hashtable.put(Hashtable.java:95) 
    at Hashtable.main(Hashtable.java:177)