HashTable Java ... Можете ли вы проверить мой код

Question

Я пишу класс для хэш-таблицы в Java ... не могли бы вы убедиться, что я делаю это правильно до сих пор.

Мне нужно хранить объекты StudentRecord в нем .... Я вычисляю значение хеш-функции на основе идентификатора студента, который имеет тип long ...

package proj3;

import java.util.LinkedList;

public class HashTable {

    LinkedList<StudentRecord> [] buckets;
    int size;

    public HashTable(){
            size = 10;
            initialize();       
    }

    public HashTable(int initialSize){
        size = initialSize;
        initialize();
    }

    private void initialize(){
        for(int i=0; i<size; i++){
            buckets[i] = new LinkedList<StudentRecord>();
        }
    }
    /** for testing only
    private int calculateHashString(String s){
        int hash = 0;
        for(int i=0; i<s.length(); i++){
            hash += s.charAt(i);
        }
        return hash % size;
    }
    **/

    private int calculateHash(long l){
        return (int) (l % size);
    }


    public boolean contains(StudentRecord sr){
        int hash = calculateHash(sr.studentID);
        LinkedList<StudentRecord> l = buckets[hash];
        if(l.contains(sr)){
            return true;
        }
        return false;
    }

    public void put(StudentRecord sr){
        int hash = calculateHash(sr.studentID);
        LinkedList<StudentRecord> l = buckets[hash];
        if(!l.contains(sr)){
            buckets[hash].add(sr);
        }
    }

}

Answer 1

Я думаю, что вы, возможно, захотите написать модульные тесты, чтобы проверить его фактическое функционирование, независимо от того, проверят ли это ваши эксперты по здравому смыслу (SO), проверят ли они это.

Одна хорошая вещь помимо простых тестовых случаев - сравнить функционирование вашей реализации со стандартным JDK HashMap; генерировать случайные ключи и / или значения, вставлять, удалять и проверять идентичность (в той степени, в которой они должны быть) между двумя реализациями.

Answer 2

buckets никогда не инициализируется. Когда вы пытаетесь это сделать, компилятор должен выдать вам предупреждение. Придерживайтесь коллекций, предпочитая массивы (кроме примитивов).

Ваш конструктор без аргументов можно было бы проще реализовать, вызвав другой конструктор (this(10).

Выражение (int) (l % size) может возвращать отрицание даже при положительном size по нескольким причинам.

код

public boolean contains(StudentRecord sr){
    ...
    if(l.contains(sr)){
            return true;
    }
    return false;
}

может быть более четко написано как

public boolean contains(Student student) {
    ...
    return list.contains(student);
}

Answer 3

Хорошо выглядит.

Answer 4

Вы должны переопределить метод equals и hashCode.

Answer 5

Том прав, вам нужно инициализировать сегменты как новый LinkedList [размер].

Я думаю, что вы хотите сделать размер окончательным и начать с большего значения, скажем, 256. Если вы измените размер после добавления элементов в таблицу, вам нужно будет переместить их все в новые корзины (из измененных хэш-алгоритм).

С другой стороны, 10 подходит для тестирования - множество столкновений в одних и тех же сегментах!

Чтобы сэкономить память, вам не нужно инициализировать все эти новые LinkedList () при запуске, вы можете просто оставить их как нулевые. Вы можете ждать создания каждого объекта списка, пока новый элемент не достигнет нулевого сегмента. Конечно, это будет означать дополнительный код повсюду, чтобы проверить, является ли корзина, которую вы пытаетесь прочитать, нулевой, и если это так, предположите, что это пустой список.