Реализация хеш-таблицы с использованием Java


Ищу отзывы на мой Java хэш-реализация таблицы. Код использует массив списков записей как своего рода отдельной цепочки; не знаю, сколько я предпочитаю этот подход на практике, и я рассматривает возможность использования линейной / квадратичной вместо зондирования. Таблица должна изменятся выше определенной нагрузке %. Я тоже пыталась справиться с негативными хэши генерируются, и использовать премьер # размер стола для предотвращения кластеризации.

Кажется, как будто существует много различных методов и методик для использования при построении хэш-таблицу с нуля, так что любые замечания или предложения по моим подходом, стиля кодирования, соглашений, и т. д. будет принята с благодарностью! Спасибо заранее.

Реализация хеш-таблицы:

public class HashTable<K, V> {

    private ListNode<Entry<K, V>>[] table;
    private int size;
    private final int initSize = 5;
    private final double loadFactor = 0.70;
    private final int resizeFactor = 2;

    public HashTable() {
        this.table = new ListNode[this.initSize];
        for(int i = 0; i < this.table.length; i++) {
            this.table[i] = new ListNode();
        }
    }

    public V get(K key) throws Exception {
        try {
            ListNode<Entry<K, V>> bucket = getBucket(key);
            while(bucket != null) {
                if(bucket.getData().getKey().equals(key)) {
                    return bucket.getData().getValue();
                }
            }
            return null;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean put(K key, V value) throws Exception {
        try {
            if(put(new Entry(key, value))) {
                resize();
                return true;
            }
            return false;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }
    private boolean put(Entry<K, V> entry) throws Exception {
        try {
            // if bucket's data at hash index is empty, add entry
            if(this.table[hashFunction(entry.getKey())] == null) { // if bucket is null
                this.table[hashFunction(entry.getKey())] = new ListNode(entry);
                this.size++;
                return true;
            } else if(this.table[hashFunction(entry.getKey())].getData() == null) { // if bucket holds no entry data
                this.table[hashFunction(entry.getKey())].setData(entry);
                this.size++;
                return true;
            } else { // if bucket contains data:
                // iterate through bucket until a. bucket with data containing key is found, b. bucket with no entry data is found, or c. null bucket is found
                ListNode<Entry<K, V>> tempBucket = this.table[hashFunction(entry.getKey())];
                if(tempBucket.getData().getKey().equals(entry.getKey())) { // if bucket contains correct entry key data
                    tempBucket.getData().setValue(entry.getValue());
                    return true;
                }
                while(tempBucket.getNext() != null) {
                    if(tempBucket.getData().getKey().equals(entry.getKey())) { // if bucket contains correct entry key data
                        tempBucket.getData().setValue(entry.getValue());
                        return true;
                    } else { // check next bucket in list
                        tempBucket = tempBucket.getNext();
                    }
                }
                // null bucket has been found, add new entry data:
                tempBucket.setNext(new ListNode(entry));
                this.size++;
                return true;
            }
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean containsKey(K key) throws Exception {
        try {
            ListNode<Entry<K, V>> bucket = getBucket(key);
            while(bucket != null) {
                if(bucket.getData() != null) {
                    if(bucket.getData().getKey().equals(key)) {
                        return true;
                    }
                }
                bucket = bucket.getNext();
            }
            return false;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean remove(K key) throws Exception {
        try {
            ListNode<Entry<K, V>> bucket = getBucket(key);
            ListNode<Entry<K, V>> prev = null;
            while(bucket != null) {
                if(bucket.getData().getKey().equals(key)) {
                    break;
                }
                prev = bucket;
                bucket = bucket.getNext();
            }
            if(bucket == null) {
                return false;
            }
            if(prev != null) {
                prev.setNext(bucket.getNext());
            } else {
                this.table[hashFunction(key)] = bucket.getNext();
            }
            this.size--;
            return true;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    private ListNode<Entry<K, V>> getBucket(K key) {
        return this.table[hashFunction(key)];
    }

    private int hashFunction(K key) {
        int hash = key.hashCode() % this.table.length;
        return (hash < 0) ? hash * -1 : hash;
    }

    private void resize() throws Exception {
        try {
            if(this.size / (double)this.table.length > this.loadFactor) {
                int newSize = this.table.length * this.resizeFactor;
                while(newSize % 2 == 0 || newSize % 3 == 0) { // find > double current size prime number for new table size.
                    newSize++;
                }
                SinglyLinkedList<ListNode<Entry<K, V>>> oldEntries = new SinglyLinkedList(); // store current data to be rehashed later.
                for(int i = 0; i < this.table.length; i++) {
                    if(this.table[i].getData() != null) {
                        oldEntries.insertEnd(this.table[i]);
                    }
                }
                this.table = new ListNode[newSize];
                for(int i = 0; i < this.table.length; i++) {
                    this.table[i] = new ListNode();
                }
                for(int i = 0; i < oldEntries.getSize(); i++) { // rehash old values into newly-allocated array.
                    ListNode<Entry<K, V>> oldEntry = oldEntries.getElementAt(i);
                    while(oldEntry != null) {
                        put(oldEntry.getData().getKey(), oldEntry.getData().getValue());
                        this.size--; // ensure that size isn't being artificially inflated during rehash
                        oldEntry = oldEntry.getNext();
                    }
                }
            }
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public int getSize() throws Exception {
        try {
            return this.size;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean isEmpty() throws Exception {
        try {
            return this.size <= 0;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

}

Классы ввода, используется в хеш-таблице:

public class Entry<K, V> {
    private K key;
    private V value;

    public Entry() {}

    public Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

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


708
3
задан 26 января 2018 в 04:01 Источник Поделиться
Комментарии
2 ответа


  1. Пожалуйста, добавьте значение null проверить для 'ключи' я предполагаю, что вы получаете НПЭ, если ключ==значение null.

  2. Если Key == null, то хэш-код равен 0.

  3. В то время как петли В 'сделать' метод, я пытаюсь понять, куда вы продвигаетесь к следующей записи в одно ведро ?

  4. Класса запись может содержать "следующий" указатель, который ведет себя как связанный список LinkedList.

  5. ListNode<Entry<K, V>> bucket = getBucket(key); Это может быть сделано final поскольку его не изменилась в рамки метода. Аналогично final K key могут быть добавлены.

  6. В get способ вы ловить и бросать то же самое исключение. Вы, как правило, поймать исключение только если вы хотите коврик с дополнительное сообщение или привести его в более общем исключением.

  7. Вы всегда звоните resize и есть логика внутри resize что говорит вам ли продолжать resize или нет. Теперь, если можно переименуйте ее в tryResize или сделать проверку перед вызовом resize было бы более осмысленным.

3
ответ дан 28 января 2018 в 09:01 Источник Поделиться

Совет 1

Проблема за открытой адресацией (прощупывания) является то, что операции замедляются далеко за пределами \$\тета(1)\ долл., что почти гарантированное столкновение цепей (текущая реализация) в предположении, что коэффициент загрузки и хэш-функции являются обоснованными. Совет: придерживаться цепей столкновения.

Совет 2

Вы явно создать целую таблицу ListNode объекты. Я предлагаю тебе свернуть что-то вроде

// Partially a pseudocode.
private static final class CollisionChainNode<K, V> {
private final K key;
private V value;
private CollisionChainNode<K, V> prev;
private CollisionChainNode<K, V> next;
private final int keyHashCode; // This may add to performance if the key is a string/collection. For the node, the key is `final`, so that you need to compute that only once.
}

... и вы заполняете актуальный хэш table только там, где это необходимо.

Совет 3

Вы готовы, чтобы поймать некоторые исключения. Что не очень корректно при работе со структурами данных в целом: вы должны убедиться, через инварианты, что структура данных работает, как ожидалось. Единственное исключение возможно, вам придется бросить/поймать-это те, которые имеют отношение к ресурсам; обычно, памяти.

0
ответ дан 26 января 2018 в 07:01 Источник Поделиться