Блог

Я пытаюсь создать хеш-таблицу с использованием векторов, или было бы лучше использовать таблицу со структурой?

 vector<int>*hashtable = new vector<int>[m];

    for(int i = 0; i<N; i  ){
        temp = T1[i] % m;
        hashtable[temp].push_back(T1[i]);


    for (int i = 0; i <= T2[0]; i  ){
        valuefound = 0;
    std::vector<int>::iterator it;
    for (it = hashtable[i].begin(); it != hashtable[i].end();   it){
        if(T2[i 1] == *it){
            T3HS[i] = i;
            valuefound = 1;
            }
        }

}
 

Вопрос можно лучше перефразировать следующим образом: в обеих таблицах существуют два значения. Похоже, вы пытаетесь заставить T3HS хранить индексы найденных элементов.

Ваш код:

 for (int i = 0; i <= T2[0]; i  ){
}
 

Для перебора векторов я всегда использую:

 for (int i = 0; i <= T2.length(); i  ){
}
 

Существуют N или N 1 векторы хеш-таблицы, но вы смотрите только на T2[0] них.

Кстати, ваш цикл шаблона поиска будет обращаться к концу T2 массива с T2[i 1] помощью when i is T2[0] .

Потребуется некоторое время, чтобы добраться туда, так что потерпите меня.

 for (int i = 0; i < N; i  )
{
    temp = T1[i] % m;
    hashtable[temp].push_back(T1[i]);
}
 

Сортирует числа по ячейкам и сохраняет их. Отлично. Здесь проблем нет. Но это:

     std::vector<int>::iterator it;
    for (it = hashtable[i].begin(); it != hashtable[i].end();   it)
    {
        if (T2[i   1] == *it)
        {
            T3HS[i] = i;
            valuefound = 1;
        }
    }
 

Не ищет числа в этих ячейках. Он ищет повсюду. Что вы хотите сделать, это посмотреть в нужной ячейке.

     int searchval = T2[i   1]; // cache the number we're looking for. Easier debugging
    int binindex = searchval % m; // get the bin for this number
    std::vector<int>::iterator it;
    // now we look just in that one bin.
    for (it = hashtable[binindex].begin(); it != hashtable[binindex].end();   it)
    {
        if (searchval == *it)
        {
            T3HS[i] = i;
            valuefound = 1;
            break;// found it . Stop looking.
        }
    }
 

После этого появилось множество небольших улучшений:

Начните с цикла for на основе диапазона

     int searchval = T2[i   1];
    int binindex = searchval % m;
    for (int val: hashtable[binindex])
    {
        if (searchval == val)
        {
            T3HS[i] = i;
            valuefound = 1;
            break;
        }
    }
 

Затем вырежьте алгоритм поиска и поместите его в собственную функцию. Это избавляет от подобных valuefound ошибок. Функция возвращает, было ли найдено значение или нет. Функция должна делать одно и только одно. Иногда это одна вещь, объединяющая ряд других функций. Во-первых, подумайте, почему вы создаете хеш-таблицу внутри функции поиска. Имеет больше смысла иметь функцию для создания хеш-таблицы, а другую — для ее поиска. Обе функции выполняют одну и только одну вещь. В качестве дополнительного бонуса их разделение означает, что вы можете повторно использовать хэш-таблицу для нескольких поисков.

 bool search (int searchval, vector<int>*hashtable, int m)
{
    int binindex = searchval % m;
    for (int val: hashtable[binindex])
    {
        if (searchval == val)
        {
            return true;
        }
    }
    return false;
}
 

и вызовите ее

 for (int i = 0; i <= T2[0]; i  )
{
    if (search(T2[i 1], hashtable, m))
    {
        T3HS[i] = i;
    }
    else
    {
        T3HS[i] = -1;
    }
}
 

Затем вы перемещаетесь немного дальше и заполняете все утечки памяти, например

 int *T3HS = new int[T2[0]];
 

и

 vector<int>*hashtable = new vector<int> [m];
 

с vectors помощью . Никогда new , если только вам это абсолютно необходимо, потому что все new , что вам нужно delete , и выяснение, когда и где удалять вещи, может быть занозой в заднице. Пусть компилятор сделает это за вас.

Далее у вас есть группировка функций и данных, которые описывают хеш-таблицу. С таким же успехом можно было бы объединить все это в hashtable класс.

И, наконец, подумайте о том, как вы используете hashtable . Вы хотите сделать это простым и очевидным. Вам не нужен поясняющий комментарий длиной в страницу, который T2[0] содержит длину списка и всегда должен быть не больше, чем на единицу меньше длины списка. Вы просто знаете, что кто-то прочтет это неправильно. Вы втянули 1201ProgramAlarm в эту ошибку, и они не пустышка. Вам гораздо лучше использовать другую переменную, содержащую длину, или, опять же, использовать a vector , потому что он знает, сколько это.

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