#java #hash #collections
#java #хэш #Коллекции
Вопрос:
Я решил пересмотреть Java collection framework, поэтому начал с внутренней реализации. Мне в голову пришел один вопрос, который я не могу решить. Надеюсь, кто-нибудь сможет дать четкое объяснение следующему.
ArrayList использует линейный или двоичный поиск (у обоих есть плюсы / минусы), но мы можем делать с ними все, что угодно! Мой вопрос в том, почему все классы «хеширования» (например, HashMap например) используют принцип хеширования? Не могли бы они, например, использовать линейный или двоичный поиск? Почему бы просто не сохранить пару ключ / значение внутри массива? И наоборот, почему этого не происходит (например, ArrayList хранится в hashTable)?
Ответ №1:
Цель платформы collections заключается в том, чтобы программист выбирал структуру данных, соответствующую варианту использования. В зависимости от того, для чего вы это используете, подходят разные структуры данных.
Классы хеширования используют принцип хеширования, как вы выразились, потому что, если вы выбираете их, значит, это то, что вы хотите использовать. (Хеширование, как правило, является лучшим выбором для простого и понятного поиска.) Отвертка использует принцип завинчивания, потому что, если вы берете отвертку, вы хотите что-то ввернуть; если бы у вас был гвоздь, который вам нужно было забить, вы бы вместо этого взяли молоток.
Но если вы не собираетесь выполнять поиск, или если линейный поиск достаточно хорош для вас, то ArrayList это то, что вам нужно. Не стоит добавлять хэш-таблицу в коллекцию, которая никогда не будет ее использовать, и это требует затрат процессора и памяти на выполнение того, что вам не понадобится.
Комментарии:
1. Спасибо, друг, я согласен, но на самом деле это не ответило на мой вопрос. Я все еще не понимаю, насколько хеширование более эффективно, чем линейное или двоичное. Зачем добавлять еще одно переполнение? Разве они не могли бы исправить K, V pair с этими двумя уже?
2. Это более эффективно, потому что оно принимает O (1) вместо O (log n) или O (n); он должен сравнивать постоянное количество ключей, чтобы найти цель в среднем. Это быстрее, со значительным отрывом, за счет умеренных затрат памяти.
3. Например, поиск в связанном списке занимает линейное время ( O (n) ), поскольку вам пришлось бы искать значение по всему списку. Поиск в хэш-таблице занимает постоянное время ( O (1) ), поскольку вы получаете индекс значения непосредственно из самого значения («хэш-функция»).
4. Они не используют это, потому что не все хотят платить за использование памяти, когда она им не понадобится.
ArrayList.get(5)можно сразу перейти к этому индексу.5. К сожалению, оба этих комментария неверны. Получение 5-го сегмента в хэш-таблице занимает точно такое же количество времени, как и получение 5-го элемента в массиве. Но найти хэш-сегмент, связанный со строкой,
"apple"быстрее, чем проверять наличие каждого элемента массива"apple".
Ответ №2:
У меня был большой хэш значений (около 1500). Природа кода заключалась в том, что после загрузки hashmap он никогда не будет изменен. К хэш-карте обращались много раз на веб-странице, и я подумал, можно ли ускорить ее для более быстрой загрузки страницы.
Однажды у меня было немного времени, поэтому я провел серию временных тестов (используя функцию nano time). Затем я переработал использование hashmap в массив. Не ArrayList, а фактический массив[]. Я сохранил индекс с классом ключа, используемым для получения значения хэша.
Разница заключалась в том, что поиск по массиву был быстрее. Я подсчитал, что за несколько дней работы я бы сэкономил почти целую секунду!
Так что да, использование массива быстрее, чем использование хэша, YMMV 🙂
И я вернул свой код обратно к использованию hashmap, поскольку его было проще поддерживать…