Частотная таблица хеш-слов

Question

Хорошо, у меня есть проект, который требует, чтобы у меня была динамическая хеш-таблица, которая учитывает частоту слов в файле. Я должен использовать java, однако нам не разрешено использовать какие-либо встроенные типы данных или встроенные классы вообще, кроме стандартных массивов. Кроме того, мне не разрешено использовать какие-либо хеш-функции из Интернета, которые, как известно, бывают быстрыми. Я должен сделать свои собственные хэш-функции. Наконец, мой инструктор также хочет, чтобы моя таблица начиналась с размера «1» и удваивалась по размеру каждый раз при добавлении нового ключа.

Моя первая идея состояла в том, чтобы суммировать значения ASCII букв, составляющих слово, и использовать их для создания хэш-функции, но разные слова с одинаковыми буквами будут одинаковыми.

Как я могу начать? Идея ASCII на правильном пути?

Answer 1

Не имеет значения, насколько хороша ваша функция хеш-функции, вы всегда столкнетесь с необходимостью разрешения конфликтов.

Если вы хотите сохранить свой подход, используя значения ASCII, вы должны не просто добавлять значения, это приведет к большим столкновениям. Вы должны работать с мощью значений, например, для слова «Помощь», которое вы просто походите: «H» * 256 + 'e' * 256 + 'l' * 256² + 'p' * 256³. Или в псевдокоде:

int hash(String word, int hashSize) 
    int res = 0 
    int count = 0; 
    for char c in word 
     res += 'c' * 256^count 
     count++ 
     count = count mod 5 
    return res mod hashSize 

Теперь вы просто должны написать свой собственный Hashtable:

class WordCounterMap 
    Entry[] entrys = new Entry[1] 

    void add(String s) 
     int hash = hash(s, entrys.length) 
     if(entrys[hash] == null{ 
      Entry[] temp = new Entry[entry.length * 2] 
      for(Entry e : entrys){ 
       if(e != null) 
        int hash = hash(e.word, temp.length) 
        temp[hash] = e; 
      entrys = temp; 
      hash = hash(s, entrys.length) 
     while(true) 
      if(entrys[hash] != null) 
       if(entrys[hash].word.equals(s)) 
        entrys[hash].count++ 
        break 
      else 
       entrys[hash] = new Entry(s) 
      hash++ 
      hash = hash mod entrys.length 

    int getCount(String s) 
     int hash = hash(s, length) 
     if(entrys[hash] == null) 
      return 0 
     while(true) 
      if(entrys[hash].word.equals(s)) 
       entrys[hash].count++ 
       break 
      hash++ 
      hash = hash mod entrys.length 


class Entry 
    int count 
    String word 

    Entry(String s) 
     this.word = s 
     count = 1 

Answer 2

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

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

Генерация функций хэширования является самостоятельным предметом, и ответа нет. Но хорошим местом для начала может быть работа с побитовыми представлениями символов в строке и выполнение на них каких-то операций свертки (поворот, сдвиг, XOR). Вы можете выполнить их каким-то образом на основе некоторого начального значения семени, а затем использовать вывод первого шага хеширования в качестве семени для следующего шага. Таким образом, вы можете в конечном итоге увеличить эффект от свертки.

Например, вы получите символ A, который равен 41 в шестнадцатеричном формате или 0100 0001 в двоичном формате. Вы можете обозначить каждый бит для обозначения некоторой операции (возможно, бит 0 является ROR, когда он равен 0, а ROL - 1, бит 1 - OR, когда он равен 0, а XOR, когда он равен 1 и т. Д.), , Вы даже можете решить, сколько сверток вы хотите сделать, основываясь на самом значении. Например, вы могли бы сказать, что нижний полубайт указывает, сколько правильного поворота вы сделаете, а верхний полубайт определяет, сколько вы будете вращать влево. Затем, как только вы получите окончательное значение, вы будете использовать это как семя для следующего символа. Это всего лишь некоторые идеи. Используйте свое воображение, чтобы узнать, что вы получаете!