Быстрый вопрос: почему лучше иметь размер хэш-таблицы в два раза больше, чем в качестве входного массива? Зачем мне нужен размер таблицы 40 (если мой массив был размером 20), не что-то ближе или даже 20?Hash Table Размер массива
Это зависит от метода столкновения. Если у вас есть идеальный метод хеширования, то размер 20 массива достаточно для 20 ключей, но в большинстве случаев будут столкновения, а это значит, что их нужно разместить на новом месте в массиве и найти, что место может быть затруднено (иногда невозможно), если осталось только одно пространство.
Вы должны принять меры предосторожности для коллизий. Предположим, что размер равен 20. И есть 20 значений. Если хеш-функция не подходит для данных, и все данные были направлены в последнюю точку, которая равна 20, и нет меры опрокидывания, данные будут помещены в следующий индекс, т.е. 21. Если все 20 данных должны были быть сопоставлены с этим последним индексом, вам понадобится еще 20 мест. Поэтому для размера данных n лучше иметь размер хеш-таблицы 2n
Термин искусства, который вы ищете, - это [коэффициент загрузки] (http://en.wikipedia.org/wiki/Hash_table#Key_statistics). Коэффициент нагрузки 50% находится на низкой стороне; загрузка более 80% - более типичная цель. –