Реализация HashTable

Я пытаюсь реализовать функцию Hash Table в Java, и вот что я придумал. Я просто хотел бы получить мнение об этой работе. Будет ли лучший способ или какое-либо улучшение в этом коде?

HashTable.java: в основном содержит все hastable функции для создания таблицы, добавления узла и получения узла

import java.math.BigInteger;

public class HashMap {
      // Srtting table size to a max of 32, value used to modulus for hash value.
      private final static int TABLE_SIZE = 32;

      HashEntry[] table;

      HashMap() {
            table = new HashEntry[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = null;
      }

      /* function to retrieve value from the table according to key */
      public int get(String key) {
            int hash = new BigInteger(toAscii(key)).mod(new BigInteger(((Integer)TABLE_SIZE).toString())).intValue();
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] == null)
                  return -1;
            else
                  return table[hash].getValue();
      }

      /* function to add value to the table */
      public void put(String key, int value) {
            //creating hash code using key value given as a string
            int hash = new BigInteger(toAscii(key)).mod(new BigInteger(((Integer)TABLE_SIZE).toString())).intValue();
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            table[hash] = new HashEntry(key, value);
      }

      /* value to create the Hash code from he name entered, basically converting name to ASCII */
      public static String toAscii(String s){
          StringBuilder sb = new StringBuilder();
          long asciiInt;
          // loop through all values in the string, including blanks
          for (int i = 0; i < s.length(); i++){
              //getting Ascii value of character and adding it to the string.
              char c = s.charAt(i);
              asciiInt = (int)c; 
              sb.append(asciiInt);
          }
          return String.valueOf(sb);
  }
}

HashEntry.java: объект, принимающий запись, содержит setter и getters

public class HashEntry {
      private String key;
      private int value;

      HashEntry(String key, int value) {
            this.key = key;
            this.value = value;
      }     

      public String getKey() {
            return key;
      }

      public int getValue() {
            return value;
      }
}

HasheTable.java: просто тестирование моей реализации

import java.io.IOException;


public class HashTable {
    public static void main(String[] args) throws IOException
    {
        HashMap entry = new HashMap();
        entry.put("Wasif", 36100);
        entry.put("Stephen Hughes", 22100);
        System.out.println(entry.get("Stephen Hughes"));
    }
}
12 голосов | спросил Fellow Rémi 13 SatEurope/Moscow2014-12-13T16:18:13+03:00Europe/Moscow12bEurope/MoscowSat, 13 Dec 2014 16:18:13 +0300 2014, 16:18:13

2 ответа


16

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

Эта реализация хэш-таблицы немного ограничена: она поддерживает только клавиши String и значения int. Было бы хорошо обобщить его.

При получении значения ключа, не входящего в таблицу, общее ожидаемое поведение null. Поскольку вы используете int как тип значений, это невозможно, но -1 просто не кажется достаточно определенным, чтобы быть обычно понимается как «недостающее значение».

Метод toAscii очень плохой:

  • Он используется только внутри, поэтому он не должен быть общедоступным.
  • Имя не очень хорошо описывает, что он делает: преобразование строки в ascii звучит скорее как преобразование кодировки, чем вычисление хеш-кода. Было бы лучше назвать его calculateHashCode и вернуть его BigInteger
  • Еще лучше было бы использовать собственный hashCode String, а не переопределять собственные

Нейминг

    HashMap entry = new HashMap();

«запись» является несоответствующим именем для карты. «карта» будет казаться очевидным выбором.

Общие проблемы с кодированием

Класс HashEntry - это деталь реализации вашей хеш-таблицы. Таким образом, было бы лучше скрыть этот класс, сделав его private static class внутри хэш-таблицы.


Вместо этого:

new BigInteger(((Integer)TABLE_SIZE).toString());

Гораздо лучше и проще:

BigInteger.valueOf(TABLE_SIZE);

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

      long asciiInt;
      // loop through all values in the string, including blanks
      for (int i = 0; i < s.length(); i++){
          //getting Ascii value of character and adding it to the string.
          char c = s.charAt(i);
          asciiInt = (int)c; 
          sb.append(asciiInt);
      }

asciiInt должен быть объявлен внутри цикла.

Этот код выглядит очень смущенным: вы получите код char, переведите его в int для сохранения в переменной long. Это могло быть просто:

    for (int i = 0; i < s.length(); i++){
        sb.append((int) s.charAt(i));
    }

И даже проще с циклом for-each:

    for (char c : s.toCharArray()) {
        sb.append((int) c);
    }

        table = new HashEntry[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
              table[i] = null;

При повторении всех элементов массива, Я рекомендую использовать длину массива в качестве предела. Это безопаснее. Вот так:

        table = new HashEntry[TABLE_SIZE];
        for (int i = 0; i < table.length; i++) { ... }

Но поскольку вы используете этот цикл только для назначения значений null, весь цикл бессмыслен, вы можете спокойно удалить его.


Это очень подозрительно, когда вы сравниваете объекты, используя !=, как вы это делаете для ключей в этом коде:

    while (table[hash] != null && table[hash].getKey() != key)
        hash = (hash + 1) % TABLE_SIZE;

Например, как вы думаете, этот код будет напечатан:

    String key1 = new String("Jack");
    String key2 = new String("Jack");
    entry.put(key1, 11);
    entry.put(key2, 21);
    System.out.println(entry.get(key1));
    System.out.println(entry.get(key2));

Он будет печатать 11 и 21. Я предлагаю заменить != на объекты повсюду с помощью .equals(...). Затем эти два ключа будут считаться равными, как обычно ожидаются от хэш-карты, а операторы печати возвратят 21 и 21.

Другие проблемы стиля кодирования

  • Я предлагаю использовать фигурные скобки { ... } даже для блоков с одной записью
  • Вместо комментариев, таких как /* function to retrieve value from the table according to key */, используйте надлежащий JavaDoc, например:

    /**
     * Retrieve value from the table according to key
     * 
     * @param key the key to look for
     * @return the value of the key, or null if doesn't exist
     */
    
  • Поскольку поля HashEntry никогда не изменяются, вы можете сделать их final

  • Этот блок кода отображается дважды:

    while (table[hash] != null && !table[hash].getKey().equals(key)) 
        hash = (hash + 1) % TABLE_SIZE;
    

    Избегайте дублирования кода. Извлеките для частного вспомогательного метода, или реорганизовать вашу реализацию таким образом, что вам не нужно дублировать код.

    То же самое для этогокод:

    int hash = new BigInteger(toAscii(key)).mod(new BigInteger(((Integer)TABLE_SIZE).toString())).intValue();
    

Улучшенная реализация

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

private int calculateHashCode(String key) {
    int mod = key.hashCode() % TABLE_SIZE;
    return mod < 0 ? mod + TABLE_SIZE : mod;
}

private int findIndex(String key) {
    int index = calculateHashCode(key);
    while (table[index] != null && !table[index].getKey().equals(key)) {
        index = (index + 1) % TABLE_SIZE;
    }
    return index;
}

public int get(String key) {
    int index = findIndex(key);
    return table[index] == null ? -1 : table[index].getValue();
}

public void put(String key, int value) {
    table[findIndex(key)] = new HashEntry(key, value);
}
ответил janos 13 SatEurope/Moscow2014-12-13T16:56:17+03:00Europe/Moscow12bEurope/MoscowSat, 13 Dec 2014 16:56:17 +0300 2014, 16:56:17
11

В дополнение к комментариям и предложениям @ janos, у меня есть некоторые другие проблемы, чтобы указать.

Бесконечные петли

Ваш код войдет в бесконечный цикл, когда таблица будет заполнена. Ввод 33-го значения войдет в этот цикл:

        while (table[hash] != null && table[hash].getKey() != key)
              hash = (hash + 1) % TABLE_SIZE;

Даже в предложенном коде @ janos

int index = calculateHashCode(key);
while (table[index] != null && !table[index].getKey().equals(key)) {
    index = (index + 1) % TABLE_SIZE;
}

Цикл не будет завершен. Вам нужен способ идентифицировать и обрабатывать ситуацию с хашем. Самый распространенный способ сделать это «в реальной жизни» - преобразовать каждую позицию в таблицу в связанный список значений, все из которых имеют одинаковый хеш. Таким образом, вы можете идентифицировать индекс в таблице, а затем просто сканировать список неограниченного размера для необходимого вам значения. Это делает HashTable неограниченной пропускной способностью, но производительность влияет, когда списки становятся длинными, и для устранения проблемы требуется перебалансировка.

Хеш с использованием модуля Modulo

Вы вычисляете индекс из хэша, используя по модулю размер таблицы. Поскольку ваш размер таблицы равен 32, по модулю остается остаток при делении на 32. Так как 32 - это сила 2 (\ $ 2 ^ 5 \ $), вы можете сделать простую битовую маскировку для вычисления остатка. Например, значение 12345 в двоичном формате 0011000000111001. «Низкие» 5 бит: 11001, который равен 25. Остальная часть 12345/32 равна 25 (проверьте это самостоятельно ... if вы хотите).

Если мы выполняем некоторую двоичную арифметику, находим следующее:

    decimal ->  binary
      12345 ->  0011000000111001
         32 ->  0000000000100000
     32 - 1 ->  0000000000011111

 12345 & 31 ->  0000000000011001
         25 ->  0000000000011001

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

Sicne - это обычная операция в области вычислений, стоит узнать, что она есть и как это сделать. В Java также есть сведения о языках. Например, если вы хотите, чтобы таблица имела размер около 50 ... мы преобразуем ее в степень 2 следующим образом:

  1. найдите бит с наивысшим значением в значении с помощью Integer.highestOneBit(50) (который будет «32»). Обратите внимание, что это значение всегда будет состоять из двух.
  2. найти значение мощности больше, чем это значение, используя оператор сдвига влево: << 1 (сдвиг влево на 1 бит, чтобы получить 64.
  3. получить маску из этого значения, вычитая 1.

Код будет выглядеть так:

private final int tableSize = Integer.highestOneBit(approxSize) << 1;
private final int tableMask = tableSize - 1;

Теперь, где бы вы ни находились в модуле, например:

      hash = (hash + 1) % TABLE_SIZE;

вместо этого вы можете:

      hash = (hash + 1) & tableMask;

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

ответил rolfl 13 SatEurope/Moscow2014-12-13T18:33:24+03:00Europe/Moscow12bEurope/MoscowSat, 13 Dec 2014 18:33:24 +0300 2014, 18:33:24

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132