Как найти строку в массиве в O (1)

Question

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

char* massageOp[6] = {"SIL","TAG","SILA","TAGS","AVS", "AVST"};

Теперь пользователь дает мне одну строку, любую строку, и я хочу знать, могу ли я найти строку в моем массиве или нет в O (1). Есть ли способ сделать это, или мне нужно пройти через весь массив, чтобы выяснить это? Спасибо.

Answer 1

Это зависит от того, как вы определяете O (1) так же, как упоминал Оли.Если вы хотите получить ОЖИДАЕМЫЕ O (1) (напомним, что в хеш-таблице могут быть коллизии, и сложно оценить сложность в худшем случае) сложность времени в количестве строк.Было бы легко использовать несколько хороших алгоритмов хеширования строк, например, мы можем использовать ELFHash:

int ELFhash(char* key, long M) {
  unsigned long h = 0;
  while(*key) {
    h = (h << 4) + *key++;
    unsigned long g = h & 0xF0000000L;
    if (g) h ^= g >> 24;
    h &= ~g;
  }
  return h % M;
}

Используя эту функцию ELFHash с вашей строкой в ​​качестве «ключа» и большим простым числом в качестве«M», вы можете получить целочисленное значение, которое является хеш-значением вашей строки.Вы также можете использовать некоторые другие функции хеширования строк и некоторые обсуждения здесь: Учебник хеширования

Answer 2

Если вы не поместите все элементы в хеш, нет, вы не можете, и средний регистр всегда будет O (n). Если вы помещаете их в хеш, вы можете просмотреть их за O (1) (замедление, если ваш алгоритм хеширования плохой).