Hashtable это так быстро

Question

с [0] * 31 ^ (n-1) + s [1] * 31 ^ (n-2) + ... + s [n-1]. Является ли хеш-функция строки Java, я предполагаю, что остальные языки похожи или близки к этой реализации.

Если у нас есть хеш-таблица и список из 50 элементов. каждый элемент состоит из 7 символов ABCDEF1, ABCDEF2, ABCDEF3 ..... ABCDEFn

Если в каждом блоке хеш-таблицы содержится 5 строк (я думаю, что эта функция сделает ее одной строкой на блок, но давайте предположим, что это 5).

Если мы вызываем col.Contains ("ABCDEFn"); // сделаю 6 сравнений и обнаружу разницу 7-го числа.

Хеш-таблица займет около 70 операций (умножение и сложение), чтобы получить хеш-код и сравнить с 5 строками в корзине. и взрыва он нашел.

Для списка потребуется около 300 сравнений, чтобы найти его.

для случая, когда есть только 10 элементов, список займет около 70 операций, а Hashtable - около 50 операций. и обратите внимание, что операции с хеш-таблицами занимают больше времени (это умножения).

Я пришел к выводу, что HybirdDictionary в .Net, вероятно, является лучшим выбором для большинства случаев, когда требуется Hashtable с неизвестным размером, потому что он позволит мне использовать список, пока список не станет больше 10 элементов. все еще нужно что-то вроде HashSet, а не словаря ключей и значений, интересно, почему нет HybirdSet !!

Так что ты думаешь?

Спасибо

Answer 1

Это действительно имеет значение? Вы обычно заботитесь о влиянии на производительность с большими коллекциями данных. 20-30 дополнительных операций, если сбор небольшой, ничего не меняет.

Answer 2

Я думаю, что вы подняли хороший вопрос. Списки могут быть быстрее, чем хеш-таблицы для небольших чисел, и это прекрасно документировано в литературе.

Однако вы можете легко создать собственную структуру данных, которая в соответствии с ее размером count() будет использовать List или Hash.