Java HashTable 实现的线性探测

Linear Probing on Java HashTable implementation

提问by user1493543

So I have a HashTable implementation here that I wrote using only Arrays and had a little bit of help with the code. Unfortunately, I don't quite understand one of the lines someone added while running the "get" or "put" method. What exactly is happening in the while loop below? It is a method for linear probing correct? Also why is the loop checking the conditions it's checking?

所以我在这里有一个 HashTable 实现，我只使用数组编写了它，并且对代码有一些帮助。不幸的是，我不太明白有人在运行“get”或“put”方法时添加的其中一行。下面的while循环究竟发生了什么？它是一种线性探测方法正确吗？另外为什么循环检查它正在检查的条件？

Specifically,

具体来说，

int hash = hashThis(key);

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

        hash = (hash + 1) % capacity;
    }

Here's the whole Java class below for full reference.

下面是完整的 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;
    }

Thank you.

谢谢你。

回答by michael_s

I just rewrote some part of the code and added the findHash-method - try to avoid code-duplication!

我只是重写了部分代码并添加了 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); 
}

What you asked for is - what exactly does this findHash-loop? The data was initialized with AVAILABLE- meaning: the data does not (yet) contain any actual data. Now - when we add an element with put- first a hashValue is calculated, that is just an index in the dataarray where to put the data. Now - if we encounter that the position has already been taken by another element with the same hash value but a different key, we try to find the next AVAILABLEposition. And the getmethod essentially works the same - if a data element with a different key is detected, the next element is probed and so on. The dataitself is a so called ring-buffer. That is, it is searched until the end of the array and is next search again at the beginning, starting with index 0. This is done with the modulo %operator.

你问的是 - 这个 findHash 循环到底是什么？数据初始化为AVAILABLE- 意思是：数据（还）不包含任何实际数据。现在 - 当我们添加一个元素时put- 首先计算一个 hashValue，它只是data数组中放置数据的索引。现在 - 如果我们遇到该位置已经被另一个具有相同哈希值但不同键的元素占据，我们会尝试找到下一个AVAILABLE位置。并且该get方法的工作原理基本相同——如果检测到具有不同键的数据元素，则探测下一个元素，依此类推。它data本身就是一个所谓的环形缓冲区。也就是说，它被搜索到数组的末尾，然后在开始处再次搜索，从索引 0 开始。这是用模数完成的%操作员。

Alright?

好吧？

回答by JRG

Sample Hashtable implementation using Generics and Linear Probing for collision resolution. There are some assumptions made during implementation and they are documented in javadoc above class and methods.

使用泛型和线性探测解决冲突的示例哈希表实现。在实现过程中有一些假设，它们记录在类和方法上方的 javadoc 中。

This implementation doesn't have all the methods of Hashtable like keySet, putAll etc but covers most frequently used methods like get, put, remove, size etc.

这个实现没有 Hashtable 的所有方法，如 keySet、putAll 等，但涵盖了最常用的方法，如 get、put、remove、size 等。

There is repetition of code in get, put and remove to find the index and it can be improved to have a new method to find index.

在get、put、remove中找索引有重复的代码，可以改进一下找索引的新方法。

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");
    }
}

---

---

Sample run of the above code.

上面代码的示例运行。

{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)