Недавно я прочитал о хэш-таблицах в очень известной книге « Введение в алгоритмы ». Я еще не использовал их в реальных приложениях, но хочу. Но я не знаю, с чего начать.
Может ли кто-нибудь дать мне несколько примеров его использования, например, как реализовать словарное приложение (например, ABBYY Lingvo) с использованием хеш-таблиц?
И, наконец, я хотел бы знать, в чем разница между хэш-таблицами и ассоциативными массивами в PHP, я имею в виду, какую технологию я должен использовать и в каких ситуациях?
Если я ошибаюсь (прошу прощения), пожалуйста, поправьте меня, потому что на самом деле я начинаю с хэш-таблиц, и у меня есть только базовые (теоретические) знания о них.
Большое спасибо.
В PHP ассоциативные массивы реализованы как hashtables, с немного дополнительной функциональностью.
Как бы технически говоря, ассоциативный массив не идентичен хэш-таблице – он просто реализован частично с хэш-таблицей за кулисами. Поскольку большая часть его реализации является хэш-таблицей, она может делать все, что может иметь хэш-таблица, но она может делать больше.
Например, вы можете пропустить ассоциативный массив, используя цикл for, который вы не можете сделать с хеш-таблицей.
Поэтому, когда они похожи, ассоциативный массив действительно может сделать надмножество того, что может сделать хэш-таблица, поэтому они не совсем то же самое. Подумайте об этом как hashtables плюс дополнительные функции.
Примеры кода:
Использование ассоциативного массива в качестве хэш-таблицы :
$favoriteColor = array(); $favoriteColor['bob']='blue'; $favoriteColor['Peter']='red'; $favoriteColor['Sally']='pink'; echo 'bob likes: '.$favoriteColor['bob']."\n"; echo 'Sally likes: '.$favoriteColor['Sally']."\n"; //output: bob likes blue // Sally likes pink Цитирование через ассоциативный массив :
$idTable=array(); $idTable['Tyler']=1; $idTable['Bill']=20; $idTable['Marc']=4; //up until here, we're using the array as a hashtable. //now we loop through the array - you can't do this with a hashtable: foreach($idTable as $person=>$id) echo 'id: '.$id.' | person: '.$person."\n"; //output: id: 1 | person: Tyler // id: 20 | person: Bill // id: 4 | person: Marc
Обратите внимание, особенно, как во втором примере порядок каждого элемента поддерживается (Тайлер, Билл Марк) на основе порядка, в котором они были введены в массив. Это основное различие между ассоциативными массивами и хэш-таблицами. Хэш-таблица не поддерживает связь между элементами, которые она хранит, тогда как ассоциативный массив PHP (вы даже можете сортировать ассоциативный массив PHP).
Массивы php представляют собой в основном хеш-таблицы
Разница между ассоциативным массивом и хэш-таблицей заключается в том, что ассоциативный массив является типом данных, а хеш-таблица – это реализация данных. Очевидно, что ассоциативный тип массива очень важен во многих современных языках программирования: Perl, Python, PHP и т. Д. Хэш-таблица – это основной способ реализации ассоциативного массива, но не совсем единственный способ. А ассоциативные массивы – основное использование хеш-таблиц, но не совсем единственное использование. Это не значит, что они одинаковые, но если у вас уже есть ассоциативные массивы, тогда вам обычно не следует беспокоиться об этой разнице.
По соображениям производительности может быть важно знать, что ваши ассоциативные массивы на вашем любимом языке реализованы как хеши. И может быть важно иметь некоторое представление о накладных расходах на эту реализацию. Хэш-таблицы медленнее и используют больше памяти, чем линейные массивы, как вы видите их на C.
Perl объединяет два понятия, называя ассоциативные массивы «хэшами». Как и ряд функций Perl, это не совсем неправильно, но это неряшливо.
Массив в PHP на самом деле является упорядоченной картой, а не хэш-таблицей. Основное различие между картой и хэш-таблицей заключается в невозможности запомнить порядок, в котором элементы были добавлены. С другой стороны, hashtables намного быстрее, чем карты. Сложностью выборки элемента из карты является O (nlogn), а из hashtable – O (1).
Ассоциативный массив – это массив, в котором вы не получаете доступа к элементам по индексу, а по ключу. Как это работает внутренне – это конкретная реализация (нет правила, как она должна работать). Ассоциативный массив может быть реализован хэш-таблицей (большинство реализаций это сделает), но также может быть реализовано какой-то древовидной структурой или списком пропусков, или алгоритм просто выполняет итерации по всем элементам в массиве и ищет ключ (это было бы очень медленно, но оно работает).
Хэш-таблица – способ хранения данных, где значения связаны с ключами, и где вы собираетесь находить значения для ключей в течение (обычно почти) постоянного времени. Это похоже на то, что вы ожидаете от ассоциативного массива, поэтому большинство хэш-таблиц времени используются для реализации этих массивов, но это необязательно.